LeetCode 题解工作台
统计范围内的步进数字数目
给你两个正整数 low 和 high ，都用字符串表示，请你统计闭区间 [low, high] 内的 步进数字 数目。 如果一个整数相邻数位之间差的绝对值都 恰好 是 1 ，那么这个数字被称为 步进数字 。 请你返回一个整数，表示闭区间 [low, high] 之间步进数字的数目。 由于答案可能很大…
2
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们注意到，题目求的是区间 $[low, high]$ 内的步进数的个数，对于这种区间 的问题，我们通常可以考虑转化为求 $[1, r]$ 和 $[1, l-1]$ 的答案，然后相减即可。另外，题目中只涉及到不同数位之间的关系，而不涉及具体的数值，因此我们可以考虑使用数位 DP 来解决。 我们设计一个函数 $dfs(pos, pre, lead, limit)$，表示当前处理到第 位，前一位数…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你两个正整数 low 和 high ，都用字符串表示，请你统计闭区间 [low, high] 内的 步进数字 数目。
如果一个整数相邻数位之间差的绝对值都 恰好 是 1 ，那么这个数字被称为 步进数字 。
请你返回一个整数，表示闭区间 [low, high] 之间步进数字的数目。
由于答案可能很大，请你将它对 109 + 7 取余 后返回。
注意：步进数字不能有前导 0 。
示例 1：
输入：low = "1", high = "11" 输出：10 解释：区间 [1,11] 内的步进数字为 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 和 10 。总共有 10 个步进数字。所以输出为 10 。
示例 2：
输入：low = "90", high = "101" 输出：2 解释：区间 [90,101] 内的步进数字为 98 和 101 。总共有 2 个步进数字。所以输出为 2 。
提示：
1 <= int(low) <= int(high) < 101001 <= low.length, high.length <= 100low和high只包含数字。low和high都不含前导 0 。
解题思路
方法一：数位 DP
我们注意到，题目求的是区间 内的步进数的个数，对于这种区间 的问题，我们通常可以考虑转化为求 和 的答案，然后相减即可。另外，题目中只涉及到不同数位之间的关系，而不涉及具体的数值，因此我们可以考虑使用数位 DP 来解决。
我们设计一个函数 ，表示当前处理到第 位，前一位数字是 ，当前数字是否只包含前导零 ，当前数字是否达到上界 的方案数。其中，而 的范围是 。
函数 的执行逻辑如下：
如果 超出了 的长度，说明我们已经处理完了所有数位，如果此时 为真，说明当前数字只包含前导零，不是一个合法的数字，我们可以返回 表示方案数为 ；否则我们返回 表示方案数为 。
否则，我们计算得到当前数位的上界 ，然后在 范围内枚举当前数位的数字 ：
- 如果 且 为真，说明当前数字只包含前导零，我们递归计算 的值并累加到答案中；
- 否则，如果 为 ，或者 和 之间的差的绝对值为 ，说明当前数字是一个合法的步进数，我们递归计算 的值并累加到答案中。
最终我们返回答案。
在主函数中，我们分别计算 和 的答案 和 ，最终答案为 。注意答案的取模运算。
时间复杂度 ，空间复杂度 ，其中 表示 数字的大小，而 表示数字集合。
相似题目：
class Solution:
def countSteppingNumbers(self, low: str, high: str) -> int:
@cache
def dfs(pos: int, pre: int, lead: bool, limit: bool) -> int:
if pos >= len(num):
return int(not lead)
up = int(num[pos]) if limit else 9
ans = 0
for i in range(up + 1):
if i == 0 and lead:
ans += dfs(pos + 1, pre, True, limit and i == up)
elif pre == -1 or abs(i - pre) == 1:
ans += dfs(pos + 1, i, False, limit and i == up)
return ans % mod
mod = 10**9 + 7
num = high
a = dfs(0, -1, True, True)
dfs.cache_clear()
num = str(int(low) - 1)
b = dfs(0, -1, True, True)
return (a - b) % mod
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for an understanding of dynamic programming with state transitions.
- question_mark
Evaluate the candidate’s approach to handling large ranges with minimal space complexity.
- question_mark
Ask about optimizations to handle edge cases such as long number strings.
常见陷阱
外企场景- error
Misunderstanding the problem's definition of stepping numbers, leading to incorrect digit transitions.
- error
Failing to account for the exact difference of 1 between adjacent digits in the dynamic programming solution.
- error
Overlooking the time complexity of processing very large numbers as strings without efficient state management.
进阶变体
外企场景- arrow_right_alt
Allow negative stepping numbers.
- arrow_right_alt
Explore solutions using iterative methods rather than recursion with memoization.
- arrow_right_alt
Test performance with larger ranges and verify optimization strategies.