Java C语言实现LeetCode 902题最大N位数字组合数位动态规划解法是怎样的？

本文共计811个文字，预计阅读时间需要4分钟。

目录- 题目要求- 阅读理解- 思路分析- 总结与代码- 题目要求- 题目链接- 阅读理解- 思路分析- 总结与代码- 总结与代码 - 数值DP - Java - C++- 题目要求- 题目链接- 阅读理解- 思路分析- 总结与代码 - 数值DP - Java - C++

目录

• 题目要求
• 阅读理解
• 思路：数位DP
• Java
• C++
• 总结

题目要求

题目链接

阅读理解

思路：数位DP

Java

class Solution { public int atMostNGivenDigitSet(String[] digits, int n) { // 转存digits int[] nums = new int[digits.length]; for (int i = 0; i < digits.length; i++) nums[i] = Integer.parseInt(digits[i]); // 转存n List<Integer> list = new ArrayList<>(); while (n != 0) { list.add(n % 10); n /= 10; } int len = list.size(), m = nums.length, res = 0; // 目标数位数 = len for (int i = len - 1, p = 1; i >= 0; i--, p++) { int cur = list.get(i); int l = 0, r = m - 1; while (l < r) { // 二分找合适的digits[r] int mid = l + r + 1 >> 1; if (nums[mid] <= cur) l = mid; else r = mid - 1; } // 是否继续向后 if (nums[r] > cur) break; else if (nums[r] == cur) { res += r * (int)Math.pow(m, (len - p)); if (i == 0) // 构造至最后一位 res++; // 加上nums[r]做该位的可能 } else if (nums[r] < cur) { res += (r + 1) * (int)Math.pow(m, (len - p)); break; } } // 目标数位数 < len for (int i = len - 1; i > 0; i--) res += Math.pow(m, i); return res; } }

• 时间复杂度：O(log⁡n)，由于二分最大范围是1∼91可忽略，所以整体复杂度仅与n的位数有关
• 空间复杂度：O(C)，转存给出数据

C++

class Solution { public: int atMostNGivenDigitSet(vector<string>& digits, int n) { // 转存digits vector<int> nums; for (int i = 0; i < digits.size(); i++) nums.emplace_back(stoi(digits[i])); // 转存n vector<int> list; while (n != 0) { list.emplace_back(n % 10); n /= 10; } int len = list.size(), m = nums.size(), res = 0; // 目标数位数 = len for (int i = len - 1, p = 1; i >= 0; i--, p++) { int cur = list[i]; int l = 0, r = m - 1; while (l < r) { // 二分找合适的digits[r] int mid = l + r + 1 >> 1; if (nums[mid] <= cur) l = mid; else r = mid - 1; } // 是否继续向后 if (nums[r] > cur) break; else if (nums[r] == cur) { res += r * (int)pow(m, (len - p)); if (i == 0) // 构造至最后一位 res++; // 加上nums[r]做该位的可能 } else if (nums[r] < cur) { res += (r + 1) * (int)pow(m, (len - p)); break; } } // 目标数位数 < len for (int i = len - 1; i > 0; i--) res += pow(m, i); return res; } };

• 时间复杂度：O(log⁡n)，由于二分最大范围是1∼91可忽略，所以整体复杂度仅与n的位数有关
• 空间复杂度：O(C)，转存给出数据

总结

持续偷懒之不想写Rust，看到那一堆容器就知道肯定搞不出来来回借用克隆；

get了数位DP的方法，还是很简单的；

由本题其实可以推广到计算任意区间内的合法数字数量

因为容斥原理所以直接resin[l,r]=dp(r)−dp(l)

以上就是Java C++题解leetcode902最大为N的数字组合数位DP的详细内容，更多关于Java C++ 最大为N的数字组合数位DP的资料请关注自由互联其它相关文章！