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

以下是 LeetCode 2999. 统计强大整数的数目 的 C 实现采用数位 DPDigit DP思路。核心思路强大整数的条件1. 后缀必须是 s2. 每个数位都不超过 limit利用容斥原理[start, finish] 内的强大整数个数 [0, finish] 内的个数 − [0, start-1] 内的个数。C 代码cppclass Solution {public:long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) {this-s s;this-limit limit;// 计算 [0, start-1] 内的强大整数个数t to_string(start - 1);memset(f, -1, sizeof(f));long long a dfs(0, true);// 计算 [0, finish] 内的强大整数个数t to_string(finish);memset(f, -1, sizeof(f));long long b dfs(0, true);return b - a;}private:string s; // 后缀string t; // 当前上界数字的字符串long long f[20]; // 记忆化数组-1 表示未计算int limit; // 数位上限/*** 数位 DP计算小于等于 t 的强大整数个数* param pos 当前处理到的位置* param lim 是否受上界 t 的约束tight*/long long dfs(int pos, bool lim) {// 如果上界 t 的长度比后缀 s 还短不可能有以 s 为后缀的数if (t.length() s.length()) {return 0;}// 不受 tight 约束时可以用记忆化if (!lim f[pos] ! -1) {return f[pos];}// 到达后缀区域剩余长度恰好等于 s 的长度if (t.length() - pos s.length()) {// 如果受 tight 约束需要判断后缀 s 是否 t 的剩余部分return lim ? (s.compare(t.substr(pos)) 0 ? 1 : 0) : 1;}// 当前位可选的上限int up lim ? t[pos] - 0 : 9;up min(up, limit);long long ans 0;for (int i 0; i up; i) {// 继续递归下一位更新 tight 状态ans dfs(pos 1, lim i (t[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)用于记忆化数组和递归栈。