继续创造,加快生长!这是我参与「日新计划 10 月更文应战」的第18天,点击查看活动详情

标题描绘

这是 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<=1091 <= n <= 10^9

数位 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(l – 1)

关于本题,查询区间的左端点固定为 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, cur – 1] 规模内取数,一起为了满意「数字只能取自 nums」的约束,因而咱们可以利用 nums 自身有序,对其进行二分,找到满意 nums[mid] <= cur 的最大下标 rr,依据 nums[r]nums[r]curcur 的关系进行分情况评论:

  • nums[r]=curnums[r] = cur: 此刻方位 kk 共有 rr 种挑选,然后面的每个方位因为 nums[i]nums[i] 可以运用屡次,每个方位都有 mm 种挑选,共有 n−pn – p 个方位,因而该分支往后共有 r∗mn−pr * m^{n – p} 种合法计划。且因为 nums[r]=curnums[r] = cur,往后还有分支可决策(需求计算),因而需求继续处理;
  • nums[r]<curnums[r] < cur:此刻算上 nums[r]nums[r],方位 kk 共有 r+1r + 1 种挑选,然后面的每个方位因为 nums[i]nums[i] 可以运用屡次,每个方位都有 mm 种挑选,共有 n−pn – p 个方位,因而该分支共有 (r+1)∗mn−p(r + 1) * m^{n – p} 种合法计划,因为 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(\log{n})
  • 空间复杂度:O(C)O(C)

总结

数位 DP 的难度取决于「约束条件」的多少,而 LC 上仅有的几道数位 DP 标题约束条件都很少,且不需求引入额外的数据结构来记载状况,因而都归于数位 DP 的入门难度(LC 难度均为 Hard)。

简直一切的数位 DP 问题都可以归纳到上述的解法 :「将问题笼统为求解一个 [0,x][0, x] / [1,x][1, x] 规模计划数的方法」->「对计划数计算依据 位数 来分情况评论:数位持平的情况 + 数位不等情况」->「计算数位持平的计划数时,需求按位处理,并依据约束条件做逻辑;计算数位不等的计划数时,通常要做一些预处理,然后合作乘法原理直接算得」。

在还没卷到数位 DP 烂大街的现在,掌握此类求解方法单一,普遍定位为「困难」的数位 DP 类型,还是极具性价比的。

最后

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

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

为了便利各位同学可以电脑上进行调试和提交代码,我建立了相关的库房:github.com/SharingSour… 。

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

更多更全更热门的「笔试/面试」相关资料可拜访排版精巧的 合集新基地