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

目录
  • 题目要求
  • 阅读理解
  • 思路:数位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的资料请关注我们其它相关文章!

(0)

相关推荐

  • Java C++题解leetcode915分割数组示例

    目录 题目要求 思路一:两次遍历 Java C++ Rust 思路二:一次遍历 Java C++ Rust 题目要求 题目链接 思路一:两次遍历 题目的意思也就是左半边数组的最大值小于等于右半边数组的最小值,那么就找这个分界点就好: 首先从后向前遍历,找[i,n−1]里最小的值: 然后从前向后遍历,找[0,i]里最大的值: 然后找满足max[i]<=min[i+1]的分割点i: 可以将2.3两步结合为一步完成,由于iii从前向后不断增大,所以用后面(较大)的值覆盖更新之前的值. 找到分界点的索引

  • Java C++题解leetcode 1684统计一致字符串的数目示例

    目录 题目 思路:模拟 Java C++ Rust 题目 题目要求 思路:模拟 用一个哈希表记录可出现的字母,然后逐一遍历每个单词每个字母,符合条件则结果加一. Java class Solution { public int countConsistentStrings(String allowed, String[] words) { boolean[] hash = new boolean[26]; for (var a : allowed.toCharArray()) hash[a -

  • Java C++刷题leetcode1106解析布尔表达式

    目录 题目 思路:栈[计算器] Java C++ Rust 总结 题目 题目要求 思路:栈[计算器] 和计算器原理类似,分别用两个栈存操作数和操作符,然后到)就开始运算前面的内容,括号里运算都相同所以还是比较简单的. 要注意字母t.f和布尔值true.false的转换. Java class Solution { public boolean parseBoolExpr(String expression) { Deque<Character> tfs = new ArrayDeque<

  • Java C++ leetcode面试零矩阵

    目录 题目要求 思路:模拟 Java C++ Rust 总结 题目要求 思路:模拟 定义两个数组分别记录每行or每列中为0的元素: 0所在的行列清零也就意味着元素所在行or列有0则置零[废话连篇]: 所以一次遍历找出有0的行列,一次遍历根据其将相应元素置零. Java class Solution { public void setZeroes(int[][] matrix) { int n = matrix.length, m = matrix[0].length; boolean[] row

  • Java C++题解leetcode816模糊坐标示例

    目录 题目 思路:枚举 Java C++ Rust 总结 题目 题目要求 思路:枚举 既然要输出每种可能了,那必然不能“偷懒”,就暴力枚举咯: 在每个间隔处添加逗号: 定义函数decPnt(sta, end)分别列举逗号左右两边的数能构成的可能性: 同样在每个间隔添加小数点: 注意两种不合法的结构——前导0和后缀0: 不要忘记无小数点的整数版本, 分别组合两边的不同可能性,根据要求各式加入答案. Java class Solution { String str; public List<Stri

  • Java C++题解leetcode1620网络信号最好的坐标

    目录 题目 思路:暴力模拟 Java C++ Rust 题目 题目要求 思路:暴力模拟 因为数据范围小,所以是万万没想到的逐个遍历…… 遍历每个塔,然后找每个塔辐射的范围,用一个大矩阵记录每个点对应的信号大小,同时维护当前最大的信号及其对应坐标. Java class Solution { public int[] bestCoordinate(int[][] towers, int radius) { int[][] grid = new int[110][110]; int cx = 0,

  • Java C++题解leetcode消失的两个数字实例

    目录 题目要求 思路:数学推导 Java C++ Rust 总结 题目要求 思路:数学推导 不重复的数组序列可以根据高斯公式计算所有元素的总和: 用当前数组长度加上两个缺失的数字可以得到所有数字长度,即可应用公式. 减去当前数组和即可得到缺失数字和sumsumsum: 两个缺失的数字分别位于m=sum2m=\frac{sum}{2}m=2sum两边: 遍历当前数组中所有小于(或大于)mmm的值,找到缺失的一个: 同样利用两个“和”的差值得到: 利用sumsumsum即可得到另一个. Java c

  • Java C++题解leetcode1598文件夹操作日志搜集器

    目录 题目要求 思路:模拟 Java C++ Rust 总结 题目要求 思路:模拟 根据日志判断目前在哪一级子文件夹即可,级数就等于返回时的步数,主文件夹级数初始为000: xl:级数+1+1+1: ./:级数不变: ../:级数−1-1−1. Java class Solution { public int minOperations(String[] logs) { int res = 0; for (String l : logs) { if (l.equals("../"))

  • Java C++题解leetcode字符串轮转KMP算法详解

    目录 题目要求 思路一:双指针(模拟) Java C++ 思路二:子串 手写KMP Java dp C++ dp 调API Java C++ 总结 题目要求 思路一:双指针(模拟) Java class Solution { public boolean isFlipedString(String s1, String s2) { if (s1.length() != s2.length()) return false; int n = s1.length(); if (n == 0) retu

  • Java C++题解 leetcode第k个数实例

    目录 题目要求 思路一:小根堆 Java C++ 思路二:多路归并[多指针] Java C++ Rust 总结 题目要求 思路一:小根堆 中文题目描述不太清晰,但其实由题目可以发现,当x满足条件时,3x.5x.7x分别也都满足条件. 将满足条件的数依次放入优先队列存放用于后续计算,由于每次要取待计算队列中最小的数x,所以定义小根堆: 弹出x,计算3x.5x.7x并入队: 用一个哈希表记录防止重复入队. 每次取数(pop)时进行计数,到第k次结束,当前队首即为答案. Java <学到了> 1L也

  • Java C++题解leetcode判定是否为字符重排

    目录 题目要求 思路一:排序 Java C++ Rust 思路二:词频统计 Java C++ Rust 总结 题目要求 思路一:排序 Java class Solution { public boolean CheckPermutation(String s1, String s2) { if(s1.length() != s2.length()) return false; char[] sort1 = s1.toCharArray(); Arrays.sort(sort1); char[]

  • Java C++题解leetcode672灯泡开关示例

    目录 题目要求 思路:找规律 Java C++ Rust 总结 题目要求 思路:找规律 找到尽可能最精简的通项表达,今日参考:京城打工人 首先,归纳每个开关会影响的灯,其中(k=0,1,2,…): 开关 反转灯编号 一 k 二 2k 三 2k+1 四 3k+1 可见灯以6盏为周期具有相同变化,所以以下只需要推导第一个周期里的6盏灯即可. 观察前6盏灯: 灯 开关 1 一.三.四 2 一.二 3 一.三 4 一.二.四 5 一.三 6 一.二 发现灯2.6和3.5分别受同样的开关影响,所以状态相同

  • Java C++ 题解leetcode1619删除某些元素后数组均值

    目录 题目要求 思路:模拟 Java C++ Rust 题目要求 思路:模拟 根据题意模拟即可: 排序然后只取中间符合条件的数加和然后计算均值: 根据给出的数组长度n为20的倍数,5%可直接取n/20: 两边各去除5%,则剩余长度为0.9n. Java class Solution { public double trimMean(int[] arr) { Arrays.sort(arr); int n = arr.length, tot = 0; for (int i = n / 20; i

  • Java C++题解leetcode817链表组件示例

    目录 题目要求 思路:模拟 Java C++ Rust 总结 题目要求 思路:模拟 Java class Solution { public int numComponents(ListNode head, int[] nums) { int res = 0; Set<Integer> set = new HashSet<>(); for (int x : nums) set.add(x); // 转存nums while (head != null) { if (set.cont

  • Java C++题解leetcode1441用栈操作构建数组示例

    目录 题目要求 思路:模拟[双指针] Java C++ Rust 题目要求 思路:模拟[双指针] 按题意模拟即可: 一个指针cur依次指向target中的每个元素,另一个指针i依次指向1∼n的数字: 对i所指向的每个数字进行Push操作,然后判断当前数字与target[cur]是否相等: 相等则判断下一个数字,同时将cur指向下一个元素: 否则需进行Pop操作. 过程中需注意cur的越界,当其越界则target构造完毕. Java class Solution { public List<Str

随机推荐