目录题目要求阅读理解思路:数位DPJavac++总结题目要求 题目链接 阅读理解 思路:数位DP Java class Solution { public int a
题目链接
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;
}
}
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;
}
};
持续偷懒之不想写Rust,看到那一堆容器就知道肯定搞不出来来回借用克隆;
get了数位DP的方法,还是很简单的;
由本题其实可以推广到计算任意区间内的合法数字数量
因为容斥原理所以直接res in [l,r]=dp(r)−dp(l)
以上就是Java C++题解LeetCode902最大为N的数字组合数位DP的详细内容,更多关于Java C++ 最大为N的数字组合数位DP的资料请关注编程网其它相关文章!
--结束END--
本文标题: Java C++题解leetcode902最大为N的数字组合数位DP
本文链接: http://www.lsjlt.com/news/169684.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0