class Solution {
public:
int countSteppingNumbers(string low, string high) {
}
};
6957. 统计范围内的步进数字数目
给你两个正整数 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 。原站题解
golang 解法, 执行用时: 16 ms, 内存消耗: 6.3 MB, 提交时间: 2023-07-31 11:38:34
const mod = 1_000_000_007
func calc(s string) int {
memo := make([][10]int, len(s))
for i := range memo {
for j := range memo[i] {
memo[i][j] = -1 // -1 表示没有计算过
}
}
var f func(int, int, bool, bool) int
f = func(i, pre int, isLimit, isNum bool) (res int) {
if i == len(s) {
if isNum {
return 1 // 得到了一个合法数字
}
return 0
}
if !isLimit && isNum {
p := &memo[i][pre]
if *p >= 0 {
return *p
}
defer func() { *p = res }()
}
if !isNum { // 可以跳过当前数位
res += f(i+1, pre, false, false)
}
d := 0
if !isNum {
d = 1 // 如果前面没有填数字，必须从 1 开始（因为不能有前导零）
}
up := 9
if isLimit {
up = int(s[i] - '0') // 如果前面填的数字都和 s 的一样，那么这一位至多填数字 s[i]（否则就超过 s 啦）
}
for ; d <= up; d++ { // 枚举要填入的数字 d
if !isNum || abs(d-pre) == 1 { // 第一位数字随便填，其余必须相差 1
res += f(i+1, d, isLimit && d == up, true)
}
}
return res % mod // 记得取模，注意这可能会导致 calc(high) < calc(low)
}
return f(0, 0, true, false)
}
func valid(s string) bool {
for i := 1; i < len(s); i++ {
if abs(int(s[i-1])-int(s[i])) != 1 {
return false
}
}
return true
}
func countSteppingNumbers(low, high string) int {
ans := (calc(high) - calc(low) + mod) % mod // +mod 防止算出负数
if valid(low) {
ans = (ans + 1) % mod
}
return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }
cpp 解法, 执行用时: 44 ms, 内存消耗: 6.5 MB, 提交时间: 2023-07-31 11:38:16
class Solution {
const int MOD = 1e9 + 7;
int calc(string &s) {
int m = s.length(), memo[m][10];
memset(memo, -1, sizeof(memo)); // -1 表示没有计算过
function<int(int, int, bool, bool)> f = [&](int i, int pre, bool is_limit, bool is_num) -> int {
if (i == m)
return is_num; // is_num 为 true 表示得到了一个合法数字
if (!is_limit && is_num && memo[i][pre] != -1)
return memo[i][pre];
int res = 0;
if (!is_num) // 可以跳过当前数位
res = f(i + 1, pre, false, false);
int up = is_limit ? s[i] - '0' : 9; // 如果前面填的数字都和 s 的一样，那么这一位至多填数字 s[i]（否则就超过 s 啦）
for (int d = 1 - is_num; d <= up; ++d) // 枚举要填入的数字 d
if (!is_num || abs(d - pre) == 1) // 第一位数字随便填，其余必须相差 1
res = (res + f(i + 1, d, is_limit && d == up, true)) % MOD;
if (!is_limit && is_num)
memo[i][pre] = res;
return res;
};
return f(0, 0, true, false);
}
bool valid(string &s) {
for (int i = 1; i < s.length(); i++)
if (abs(int(s[i]) - int(s[i - 1])) != 1)
return false;
return true;
}
public:
int countSteppingNumbers(string low, string high) {
return (calc(high) - calc(low) + MOD + valid(low)) % MOD; // +MOD 防止算出负数
}
};
java 解法, 执行用时: 18 ms, 内存消耗: 43.2 MB, 提交时间: 2023-07-31 11:37:49
class Solution {
private static final int MOD = (int) 1e9 + 7;
public int countSteppingNumbers(String low, String high) {
return (calc(high) - calc(low) + MOD + (valid(low) ? 1 : 0)) % MOD; // +MOD 防止算出负数
}
private char s[];
private int memo[][];
private int calc(String s) {
this.s = s.toCharArray();
int m = s.length();
memo = new int[m][10];
for (int i = 0; i < m; i++)
Arrays.fill(memo[i], -1); // -1 表示没有计算过
return f(0, 0, true, false);
}
private int f(int i, int pre, boolean isLimit, boolean isNum) {
if (i == s.length)
return isNum ? 1 : 0; // isNum 为 true 表示得到了一个合法数字
if (!isLimit && isNum && memo[i][pre] != -1)
return memo[i][pre];
int res = 0;
if (!isNum) // 可以跳过当前数位
res = f(i + 1, pre, false, false);
int up = isLimit ? s[i] - '0' : 9; // 如果前面填的数字都和 s 的一样，那么这一位至多填数字 s[i]（否则就超过 s 啦）
for (int d = isNum ? 0 : 1; d <= up; d++) // 枚举要填入的数字 d
if (!isNum || Math.abs(d - pre) == 1) // 第一位数字随便填，其余必须相差 1
res = (res + f(i + 1, d, isLimit && d == up, true)) % MOD;
if (!isLimit && isNum)
memo[i][pre] = res;
return res;
}
private boolean valid(String s) {
for (int i = 1; i < s.length(); i++)
if (Math.abs((int) s.charAt(i) - (int) s.charAt(i - 1)) != 1)
return false;
return true;
}
}
python3 解法, 执行用时: 612 ms, 内存消耗: 19.9 MB, 提交时间: 2023-07-31 11:37:34
'''
数位dp
f(i, pre, is_limit, is_num): 表示构造第 i 位及其之后数位的合法方案数
pre: 表示上一个数位的值。如果 is_num = false, 则忽略pre;
is_limit: 表示当前是否受到了 n 的约束
is_num: 表示 i 前面的数位是否填了数字
'''
class Solution:
def countSteppingNumbers(self, low: str, high: str) -> int:
MOD = 10 ** 9 + 7
def calc(s: str) -> int:
@cache # 记忆化搜索
def f(i: int, pre: int, is_limit: bool, is_num: bool) -> int:
if i == len(s):
return int(is_num) # is_num 为 True 表示得到了一个合法数字
res = 0
if not is_num: # 可以跳过当前数位
res = f(i + 1, pre, False, False)
low = 0 if is_num else 1 # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）
up = int(s[i]) if is_limit else 9 # 如果前面填的数字都和 s 的一样，那么这一位至多填 s[i]（否则就超过 s 啦）
for d in range(low, up + 1): # 枚举要填入的数字 d
if not is_num or abs(d - pre) == 1: # 第一位数字随便填，其余必须相差 1
res += f(i + 1, d, is_limit and d == up, True)
return res % MOD
return f(0, 0, True, False)
return (calc(high) - calc(str(int(low) - 1))) % MOD