Kimi k2.6 LeetCode 2999. 统计强大整数的数目 Java实现

以下是 LeetCode 2999. 统计强大整数的数目 的 Java 实现采用数位 DPDigit DP思路。核心思路强大整数的条件1. 后缀必须是 s2. 每个数位都不超过 limit利用容斥原理[start, finish] 内的强大整数个数 [0, finish] 内的个数 − [0, start-1] 内的个数。对于每个上界 x用数位 DP 从高位到低位逐位构造同时满足- 若当前位处于后缀区域则必须填 s 对应位置的数字- 若当前位不在后缀区域则每位可选 0 到 min(limit, 上界对应位数字)受 tight 约束Java 代码javaclass Solution {private String s; // 后缀private String t; // 当前上界数字的字符串private Long[] f; // 记忆化数组private int limit; // 数位上限public long numberOfPowerfulInt(long start, long finish, int limit, String s) {this.s s;this.limit limit;// 计算 [0, start-1] 内的强大整数个数t String.valueOf(start - 1);f new Long[20];long a dfs(0, true);// 计算 [0, finish] 内的强大整数个数t String.valueOf(finish);f new Long[20];long b dfs(0, true);return b - a;}/*** 数位 DP计算小于等于 t 的强大整数个数* param pos 当前处理到的位置* param lim 是否受上界 t 的约束tight*/private long dfs(int pos, boolean lim) {// 如果上界 t 的长度比后缀 s 还短不可能有以 s 为后缀的数if (t.length() s.length()) {return 0;}// 不受 tight 约束时可以用记忆化if (!lim f[pos] ! null) {return f[pos];}// 到达后缀区域剩余长度恰好等于 s 的长度// 此时必须匹配后缀 sif (t.length() - pos s.length()) {// 如果受 tight 约束需要判断后缀 s 是否 t 的剩余部分// 如果 s t.substring(pos)说明这个后缀可以放得下返回 1// 否则返回 0return lim ? (s.compareTo(t.substring(pos)) 0 ? 1 : 0) : 1;}// 当前位可选的上限int up lim ? t.charAt(pos) - 0 : 9;up Math.min(up, limit);long ans 0;for (int i 0; i up; i) {// 继续递归下一位更新 tight 状态ans dfs(pos 1, lim i (t.charAt(pos) - 0));}// 记忆化只有不受 tight 约束时才存储if (!lim) {f[pos] ans;}return ans;}}关键点说明要点 说明容斥原理 count(finish) - count(start-1) 得到区间答案后缀处理 当剩余长度等于 s.length() 时进入强制匹配后缀的逻辑tight 约束 limtrue 表示当前构造的前缀与上界 t 完全相同下一位不能超过 t 的对应位记忆化 只有 limfalse不受 tight 约束时才缓存结果因为 limtrue 时结果与具体上界相关数位上限 每位可选 0 到 min(limit, 上界对应位)同时满足 limit 和 tight 两个约束复杂度分析- 时间复杂度O(\log M \times D)其中 M 是数值上界最大 10^{15}D 10 为可选数字个数。实际由于记忆化状态数约为 O(\log M)。- 空间复杂度O(\log M)用于记忆化数组和递归栈。示例验证以 start1, finish6000, limit4, s124 为例- count(6000)构造以 124 结尾且每位 ≤ 4 的数前缀可选 0,1,2,3,4得到 124, 1124, 2124, 3124, 4124, 5124但 5124 首位 5 4 被排除共 5 个- count(0) 0- 答案 5 - 0 5