当前位置 : 主页 > 编程语言 > java >

Java C++题解leetcode902最大为N的数字组合数位DP

来源:互联网 收集:自由互联 发布时间:2023-01-30
目录 题目要求 阅读理解 思路:数位DP Java C++ 总结 题目要求 题目链接 阅读理解 思路:数位DP Java class Solution { public int atMostNGivenDigitSet(String[] digits, int n) { // 转存digits int[] nums = new int
目录
  • 题目要求
  • 阅读理解
  • 思路:数位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的方法,还是很简单的;

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

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

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

上一篇:Java C++题解leetcode904水果成篮
下一篇:没有了
网友评论