LeetCode 题解工作台
统计强大整数的数目
给你三个整数 start ， finish 和 limit 。同时给你一个下标从 0 开始的字符串 s ，表示一个 正 整数。 如果一个 正 整数 x 末尾部分是 s （换句话说， s 是 x 的 后缀 ），且 x 中的每个数位至多是 limit ，那么我们称 x 是 强大的 。 请你返回区间 [s…
3
题型
7
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
这道题实际上是求在给定区间 中，满足条件的数的个数。个数与数的位数以及每一位上的数字有关。我们可以用数位 DP 的思路来解决这道题。数位 DP 中，数的大小对复杂度的影响很小。 对于区间 问题，我们一般会将其转化为 然后再减去 $[1,..l - 1]$ 的问题，即：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你三个整数 start ，finish 和 limit 。同时给你一个下标从 0 开始的字符串 s ，表示一个 正 整数。
如果一个 正 整数 x 末尾部分是 s （换句话说，s 是 x 的 后缀），且 x 中的每个数位至多是 limit ，那么我们称 x 是 强大的 。
请你返回区间 [start..finish] 内强大整数的 总数目 。
如果一个字符串 x 是 y 中某个下标开始（包括 0 ），到下标为 y.length - 1 结束的子字符串，那么我们称 x 是 y 的一个后缀。比方说，25 是 5125 的一个后缀，但不是 512 的后缀。
示例 1：
输入：start = 1, finish = 6000, limit = 4, s = "124" 输出：5 解释：区间 [1..6000] 内的强大数字为 124 ，1124 ，2124 ，3124 和 4124 。这些整数的各个数位都 <= 4 且 "124" 是它们的后缀。注意 5124 不是强大整数，因为第一个数位 5 大于 4 。 这个区间内总共只有这 5 个强大整数。
示例 2：
输入：start = 15, finish = 215, limit = 6, s = "10" 输出：2 解释：区间 [15..215] 内的强大整数为 110 和 210 。这些整数的各个数位都 <= 6 且 "10" 是它们的后缀。 这个区间总共只有这 2 个强大整数。
示例 3：
输入：start = 1000, finish = 2000, limit = 4, s = "3000" 输出：0 解释：区间 [1000..2000] 内的整数都小于 3000 ，所以 "3000" 不可能是这个区间内任何整数的后缀。
提示：
1 <= start <= finish <= 10151 <= limit <= 91 <= s.length <= floor(log10(finish)) + 1s数位中每个数字都小于等于limit。s不包含任何前导 0 。
解题思路
方法一：数位 DP
这道题实际上是求在给定区间 中，满足条件的数的个数。个数与数的位数以及每一位上的数字有关。我们可以用数位 DP 的思路来解决这道题。数位 DP 中，数的大小对复杂度的影响很小。
对于区间 问题，我们一般会将其转化为 然后再减去 的问题，即：
对于本题而言，我们求出 中满足条件的数的个数，然后减去 中满足条件的数的个数，即可得到答案。
这里我们用记忆化搜索来实现数位 DP。从起点向下搜索，到最底层得到方案数，一层层向上返回答案并累加，最后从搜索起点得到最终的答案。
基本步骤如下：
- 先将 和 转化为字符串，方便后续的数位 DP。
- 设计一个函数 ，表示从第 位开始搜索，当前的限制条件为 。
- 如果最大的数字位数小于 的长度，返回 0。
- 如果当前剩余的数字位数等于 的长度，判断当前的数字是否满足条件，返回 1 或 0。
- 否则，我们计算当前位的上限 。然后遍历当前位的数字 ，从 0 到 ，递归调用 ，将结果累加到答案中。
- 如果当前的 为 false，则将当前的答案存入缓存中，避免重复计算。
- 最后返回答案。
答案为区间 中满足条件的数的个数减去区间 中满足条件的数的个数。
时间复杂度 ，空间复杂度 ，其中 为数字的上限，而 。
class Solution:
def numberOfPowerfulInt(self, start: int, finish: int, limit: int, s: str) -> int:
@cache
def dfs(pos: int, lim: int) -> int:
if len(t) < n:
return 0
if len(t) - pos == n:
return int(s <= t[pos:]) if lim else 1
up = min(int(t[pos]) if lim else 9, limit)
ans = 0
for i in range(up + 1):
ans += dfs(pos + 1, lim and i == int(t[pos]))
return ans
n = len(s)
t = str(start - 1)
a = dfs(0, True)
dfs.cache_clear()
t = str(finish)
b = dfs(0, True)
return b - a
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(\log(\textit{finish})) |
| 空间 | O(\log(\textit{finish})) |
面试官常问的追问
外企场景- question_mark
Check if the candidate can recognize the need for digit DP in problems involving number ranges and suffixes.
- question_mark
Assess whether the candidate can handle edge cases and constraints efficiently, especially when dealing with large inputs.
- question_mark
Look for understanding of how dynamic programming can be adapted to count numbers with specific suffixes.
常见陷阱
外企场景- error
Misunderstanding the constraint on digits may lead to incorrect solutions that count numbers outside the valid range.
- error
Forgetting to account for all possible numbers with the given suffix in the range could result in an incomplete solution.
- error
Failing to optimize for large inputs, leading to time or space inefficiency when handling upper bounds of the range.
进阶变体
外企场景- arrow_right_alt
Change the limit on the digits to create a different set of valid numbers.
- arrow_right_alt
Modify the suffix string to test if the solution can handle varying patterns and lengths.
- arrow_right_alt
Increase the range size to test the scalability of the solution with larger upper bounds.