共计 3040 个字符,预计需要花费 8 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 902. 最大为 N 的数字组合 ,难度为 艰难。
Tag :「动静布局」、「二分」、「数位 DP」
给定一个按 非递加程序 排列的数字数组 digits
。你能够用任意次数 $digits[i]$ 来写的数字。例如,如果 $digits = [1,3,5]$,咱们能够写数字,如 '13'
, '551'
, 和 '1351315'
。
返回 能够生成的小于或等于给定整数 $n$ 的正整数的个数。
示例 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 <= 9$
- $digits[i].length == 1$
- $digits[i]$ 是从
'1'
到'9'
的数 digits
中的所有值都 不同digits
按 非递加程序 排列- $1 <= n <= 10^9$
数位 DP + 二分
这是一道「数位 DP」的经典使用题。
因为题目给定的 digits
不蕴含 $0$,因而相当于只须要答复应用 digits
的数值可能笼罩 $[1, x]$ 范畴内的多少个数字。
起始先将字符串数组 digits
转为数字数组 nums
,假设 nums
的长度为 $m$,而后思考如何求得 $[1, x]$ 范畴内非法数字的个数。
假设咱们存在函数 int dp(int x)
函数,可能返回区间 $[1, x]$ 内非法数的个数,那么配合「容斥原理」咱们便可能答复任意区间非法数的查问:
$$
ans_{(l, r)} = dp(r) – dp(l – 1)
$$
对于本题,查问区间的左端点固定为 $1$,同时 $dp(0) = 0$,因而答案为 $dp(x)$。
而后思考如何实现 int dp(int x)
函数,咱们将组成 $[1, x]$ 的非法数分成三类:
- 位数和 $x$ 雷同,且最高位比 $x$ 最高位要小的,这部分统计为
res1
; - 位数和 $x$ 雷同,且最高位与 $x$ 最高位雷同的,这部分统计为
res2
; - 位数比 $x$ 少,这部分统计为
res3
。
其中 res1
和 res3
求解绝对简略,重点落在如何求解 res2
上。
对 $x$ 进行「从高到低」的解决(假设 $x$ 数位为 $n$),对于第 $k$ 位而言($k$ 不为最高位),假如在 $x$ 中第 $k$ 位为 $cur$,那么为了满足「大小限度」关系,咱们只能在 $[1, cur – 1]$ 范畴内取数,同时为了满足「数字只能取自 nums
」的限度,因而咱们能够利用 nums
自身有序,对其进行二分,找到满足 nums[mid] <= cur
的最大下标 $r$,依据 $nums[r]$ 与 $cur$ 的关系进行分状况探讨:
- $nums[r] = cur$: 此时地位 $k$ 共有 $r$ 种抉择,而前面的每个地位因为 $nums[i]$ 能够应用屡次,每个地位都有 $m$ 种抉择,共有 $n – p$ 个地位,因而该分支往后共有 $r * m^{n – p}$ 种非法计划。且因为 $nums[r] = cur$,往后还有分支可决策(须要统计),因而须要持续解决;
- $nums[r] < cur$:此时算上 $nums[r]$,地位 $k$ 共有 $r + 1$ 种抉择,而前面的每个地位因为 $nums[i]$ 能够应用屡次,每个地位都有 $m$ 种抉择,共有 $n – p$ 个地位,因而该分支共有 $(r + 1) * m^{n – p}$ 种非法计划,因为 $nums[r] < cur$,往后的计划数(均满足小于关系)曾经在这次被统计实现,累加后进行
break
; - $nums[r] > cur$:该分支往后不再满足「大小限度」要求,非法计划数为 $0$,间接
break
。
其余细节:实际上,咱们能够将 res1
和 res2
两种状况进行合并解决。
代码:
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
最多存在 $9$ 个元素,因而二分的复杂度能够疏忽,整体复杂度为 $O(\log{n})$ - 空间复杂度:$O(C)$
总结
数位 DP 的难度取决于「限度条件」的多少,而 LC 上仅有的几道数位 DP 题目限度条件都很少,且不须要引入额定的数据结构来记录状态,因而都属于数位 DP 的入门难度(LC 难度均为 Hard)。
简直所有的数位 DP 问题都能够归纳到上述的解法 :「将问题形象为求解一个 $[0, x]$ / $[1, x]$ 范畴计划数的办法」->「对计划数统计依据 位数 来分状况探讨:数位相等的状况 + 数位不等状况」->「统计数位相等的计划数时,须要按位解决,并依据限度条件做逻辑;统计数位不等的计划数时,通常要做一些预处理,而后配合乘法原理间接算得」。
在还没卷到数位 DP 烂大巷的当初,把握此类求解形式繁多,广泛定位为「艰难」的数位 DP 类型,还是极具性价比的。
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.902
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,局部是有锁题,咱们将先把所有不带锁的题目刷完。
在这个系列文章外面,除了解说解题思路以外,还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSou…。
在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布