千问 LeetCode 2801. 统计范围内的步进数字数目 Java实现
这道题是一道非常经典的数位 DP（Digit DP）问题。
核心思路
步进数字的定义是：相邻两个数字之差的绝对值恰好为 1。
如果直接用暴力法遍历 low 到 high 之间的每一个数去判断，在数据范围极大（比如 10^{18}）时会直接超时。
我们可以利用前缀和思想将问题转化为：
结果 = (0 到 high 的步进数字个数) - (0 到 low-1 的步进数字个数)
接下来，我们只需要实现一个函数 countSteppingNumbers(String s)，用来计算从 0 到字符串 s 代表的数字之间有多少个步进数字。这里采用记忆化搜索（Memoization）来实现数位 DP：
1. 状态定义：dfs(pos, prevDigit, isLimit, isNum)
* pos：当前处理到第几位（从左到右）。
* prevDigit：上一位填入的数字（用于判断当前位能否满足步进条件）。
* isLimit：当前位是否受到上界 s 的限制（如果前面几位都和 s 一样，当前位就不能超过 s[pos]）。
* isNum：前面是否已经填入了有效数字（用于处理前导 0 的情况，比如数字 05 其实是 5）。
2. 转移逻辑：
* 如果 isNum 为 false（前面全是前导 0），当前位可以选择跳过（继续填 0），或者填入 1-9 作为起始数字。
* 如果 isNum 为 true，当前位填入的数字 d 必须满足 Math.abs(d - prevDigit) == 1。
Java 代码实现
import java.util.Arrays;
class Solution {
private static final int MOD = 1000000007;
private char[] digits;
private Integer[][][][] memo;
public int countSteppingNumbers(String low, String high) {
// 计算 [0, high] 的步进数字个数
long countHigh = count(high);
// 计算 [0, low-1] 的步进数字个数
long countLow = count(subtractOne(low));
// 结果为两者之差，注意取模防止负数
return (int) ((countHigh - countLow + MOD) % MOD);
}
// 计算从 0 到字符串 s 代表的数字之间有多少个步进数字
private long count(String s) {
digits = s.toCharArray();
int n = digits.length;
// 记忆化数组：[位置][上一位数字(0-9)][是否受限制][前面是否已填数字]
// 上一位数字用 10 表示初始状态（前面没有数字）
memo = new Integer[n][11][2][2];
return dfs(0, 10, 1, 0);
}
private long dfs(int pos, int prevDigit, int isLimit, int isNum) {
// 递归终止条件：已经填完所有位置
if (pos == digits.length) {
// 如果前面填了有效数字，说明找到了一个合法的步进数字
return isNum == 1 ? 1 : 0;
}
// 如果该状态已经计算过，直接返回
if (memo[pos][prevDigit][isLimit][isNum] != null) {
return memo[pos][prevDigit][isLimit][isNum];
}
long res = 0;
// 确定当前位能填入的最大数字
int up = isLimit == 1 ? digits[pos] - '0' : 9;
// 1. 处理前导 0 的情况：如果前面还没填数字，当前位可以继续填 0（跳过）
if (isNum == 0) {
res = (res + dfs(pos + 1, 10, 0, 0)) % MOD;
}
// 2. 枚举当前位填入的数字 d
// 起始数字：如果前面没填数字(isNum=0)，从1开始；否则从0开始
int start = isNum == 0 ? 1 : 0;
for (int d = start; d <= up; d++) {
// 如果前面已经填了数字，需要满足步进条件：相邻数字差的绝对值为 1
if (isNum == 1 && Math.abs(d - prevDigit) != 1) {
continue;
}
// 递归进入下一位
// 新的 isLimit：只有当前位受限制且填了最大值时，下一位才受限制
int nextIsLimit = (isLimit == 1 && d == up) ? 1 : 0;
res = (res + dfs(pos + 1, d, nextIsLimit, 1)) % MOD;
}
// 记录并返回结果
memo[pos][prevDigit][isLimit][isNum] = (int) res;
return res;
}
// 字符串模拟数字减 1（处理 low - 1，避免大数溢出）
private String subtractOne(String s) {
char[] chars = s.toCharArray();
int i = chars.length - 1;
// 从最后一位开始借位
while (i >= 0 && chars[i] == '0') {
chars[i] = '9';
i--;
}
// 如果减到了最前面（比如 1000 -> 0999），且首位变成了 0
if (i >= 0) {
chars[i]--;
}
// 如果首位变成了 '0'（且原字符串长度大于1），去掉前导 0
if (chars[0] == '0' && chars.length > 1) {
return new String(chars, 1, chars.length - 1);
}
return new String(chars);
}
}
复杂度分析
* 时间复杂度：O(log N)，其中 N 是 high 的数值。数位 DP 的状态数取决于数字的位数（最多 100 位）、上一位数字（0-9，共11种状态）、是否受限（2种）和是否已填数字（2种）。总状态数非常少，每次转移最多枚举 10 个数字，因此效率极高。
* 空间复杂度：O(log N)，主要用于存储记忆化搜索的 memo 数组以及递归调用的栈空间。