902. 最大为 N 的数字组合 : 经典「数位 DP + 二分」运用题

简介: 902. 最大为 N 的数字组合 : 经典「数位 DP + 二分」运用题

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的 902. 最大为 N 的数字组合 ,难度为 困难


Tag : 「动态规划」、「二分」、「数位 DP」


给定一个按 非递减顺序 排列的数字数组 digits。你可以用任意次数 digits[i]digits[i] 来写的数字。例如,如果 digits = [1,3,5]digits=[1,3,5],我们可以写数字,如 '13', '551', 和 '1351315'


返回 可以生成的小于或等于给定整数nn 的正整数的个数 。


示例 1:


输入:digits = ["1","3","5","7"], n = 100
输出:20
解释:
可写出的 20 个数字是:
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.
复制代码


示例 2:


输入:digits = ["1","4","9"], n = 1000000000
输出:29523
解释:
我们可以写 3 个一位数字,9 个两位数字,27 个三位数字,
81 个四位数字,243 个五位数字,729 个六位数字,
2187 个七位数字,6561 个八位数字和 19683 个九位数字。
总共,可以使用D中的数字写出 29523 个整数。
复制代码


示例 3:


输入:digits = ["7"], n = 8
输出:1
复制代码


提示:


  • 1 <= digits.length <= 91<=digits.length<=9
  • digits[i].length == 1digits[i].length==1
  • digits[i]digits[i] 是从 '1''9' 的数
  • digits 中的所有值都 不同
  • digits 按 非递减顺序 排列
  • 1 <= n <= 10^91<=n<=109


数位 DP + 二分



这是一道「数位 DP」的经典运用题。


由于题目给定的 digits 不包含 00,因此相当于只需要回答使用 digits 的数值能够覆盖 [1, x][1,x] 范围内的多少个数字。


起始先将字符串数组 digits 转为数字数组 nums,假定 nums 的长度为 mm,然后考虑如何求得 [1, x][1,x] 范围内合法数字的个数。


假定我们存在函数 int dp(int x) 函数,能够返回区间 [1, x][1,x] 内合法数的个数,那么配合「容斥原理」我们便能够回答任意区间合法数的查询:


ans_{(l, r)} = dp(r) - dp(l - 1)ans(l,r)=dp(r)dp(l1)


对于本题,查询区间的左端点固定为 11,同时 dp(0) = 0dp(0)=0,因此答案为 dp(x)dp(x)


然后考虑如何实现 int dp(int x) 函数,我们将组成 [1, x][1,x] 的合法数分成三类:


  • 位数和 xx 相同,且最高位比 xx 最高位要小的,这部分统计为 res1
  • 位数和 xx 相同,且最高位与 xx 最高位相同的,这部分统计为 res2
  • 位数比 xx 少,这部分统计为 res3


其中 res1res3 求解相对简单,重点落在如何求解 res2 上。


xx 进行「从高到低」的处理(假定 xx 数位为 nn),对于第 kk 位而言(kk 不为最高位),假设在 xx 中第 kk 位为 curcur,那么为了满足「大小限制」关系,我们只能在 [1, cur - 1][1,cur1] 范围内取数,同时为了满足「数字只能取自 nums」的限制,因此我们可以利用 nums 本身有序,对其进行二分,找到满足 nums[mid] <= cur 的最大下标 rr,根据 nums[r]nums[r]curcur 的关系进行分情况讨论:


  • nums[r] = curnums[r]=cur: 此时位置 kk 共有 rr 种选择,而后面的每个位置由于 nums[i]nums[i] 可以使用多次,每个位置都有 mm 种选择,共有 n - pnp 个位置,因此该分支往后共有 r * m^{n - p}rmnp 种合法方案。且由于 nums[r] = curnums[r]=cur,往后还有分支可决策(需要统计),因此需要继续处理;
  • nums[r] < curnums[r]<cur:此时算上 nums[r]nums[r],位置 kk 共有 r + 1r+1 种选择,而后面的每个位置由于 nums[i]nums[i] 可以使用多次,每个位置都有 mm 种选择,共有 n - pnp 个位置,因此该分支共有 (r + 1) * m^{n - p}(r+1)mnp 种合法方案,由于 nums[r] < curnums[r]<cur,往后的方案数(均满足小于关系)已经在这次被统计完成,累加后进行 break
  • nums[r] > curnums[r]>cur:该分支往后不再满足「大小限制」要求,合法方案数为 00,直接 break


其他细节:实际上,我们可以将 res1res2 两种情况进行合并处理。


代码:


class Solution {
    int[] nums;
    int dp(int x) {
        List<Integer> list = new ArrayList<>();
        while (x != 0) {
            list.add(x % 10);
            x /= 10;
        }
        int n = list.size(), m = nums.length, ans = 0;
        // 位数和 x 相同
        for (int i = n - 1, p = 1; i >= 0; i--, p++) {
            int cur = list.get(i);
            int l = 0, r = m - 1;
            while (l < 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) {
                ans += r * (int) Math.pow(m, (n - p));
                if (i == 0) ans++;
            } else if (nums[r] < cur) {
                ans += (r + 1) * (int) Math.pow(m, (n - p));
                break;
            }
        }
        // 位数比 x 少的
        for (int i = 1, last = 1; i < n; i++) {
            int cur = last * m;
            ans += cur; last = cur;
        }
        return ans;
    }
    public int atMostNGivenDigitSet(String[] digits, int max) {
        int n = digits.length;
        nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = Integer.parseInt(digits[i]);
        return dp(max);
    }
}
复制代码


  • 时间复杂度:由于 digits 最多存在 99 个元素,因此二分的复杂度可以忽略,整体复杂度为 O(\log{n})O(logn)
  • 空间复杂度:O(C)O(C)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.902 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

目录
打赏
0
0
0
0
6
分享
相关文章
科普:如果电容器阻断直流电,为什么还要在直流电路中使用电容器?
如果电容器阻止直流,那么为什么它用于直流电路?问题不应该是为什么,而是如何!电容器在直流电路中有许多应用,如旁路、滤波、耦合和去耦。因此,利用这种阻隔直流和通过交流的特性,电容器可用于不同的应用。这取决于它连接到电路的方式、电容值、信号频率、电压和其他几个因素。
1864 0
科普:如果电容器阻断直流电,为什么还要在直流电路中使用电容器?
Dev-C++详细安装教程及中文设置(附带安装包链接)
Dev-C++详细安装教程及中文设置(附带安装包链接)
4394 0
开源FaaS平台(二):Apache OpenWhisk
Apache OpenWhisk是一个开源FaaS平台,是一个由IBM和Adobe驱动的开源项目,可以部署在云或数据中心内。相比其他Serverless项目,OpenWhisk是一个健壮的、可扩展的平台,支持数千并发触发器和调用。OpenWhisk项目的基本信息如下表
1168 0
机器学习中空间和时间自相关的分析:从理论基础到实践应用
空间和时间自相关是数据分析中的重要概念,揭示了现象在空间和时间维度上的相互依赖关系。本文探讨了这些概念的理论基础,并通过野火风险预测的实际案例,展示了如何利用随机森林模型捕捉时空依赖性,提高预测准确性。
459 0
机器学习中空间和时间自相关的分析:从理论基础到实践应用
1)Redis 属于单线程还是多线程?不同版本之间有什么区别?
1)Redis 属于单线程还是多线程?不同版本之间有什么区别?
229 1
Kali Linux预装的自动化渗透测试工具
Kali Linux预装的自动化渗透测试工具
458 2
Spring Cloud Dubbo: 微服务通信的高效解决方案
【4月更文挑战第28天】在微服务架构的发展中,服务间的高效通信至关重要。Spring Cloud Dubbo 提供了一种基于 RPC 的通信方式,使得服务间的调用就像本地方法调用一样简单。本篇博客将探讨 Spring Cloud Dubbo 的核心概念,并通过具体实例展示其在项目中的实战应用。
342 2
史上最详细Docker安装Mycat中间件 | 实现主从的读写分离
史上最详细Docker安装Mycat中间件 | 实现主从的读写分离
808 2

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问