统计范围内的步进数字数目
难度:
标签:
题目描述
Given two positive integers low and high represented as strings, find the count of stepping numbers in the inclusive range [low, high].
A stepping number is an integer such that all of its adjacent digits have an absolute difference of exactly 1.
Return an integer denoting the count of stepping numbers in the inclusive range [low, high].
Since the answer may be very large, return it modulo 109 + 7.
Note: A stepping number should not have a leading zero.
Example 1:
Input: low = "1", high = "11" Output: 10 Explanation: The stepping numbers in the range [1,11] are 1, 2, 3, 4, 5, 6, 7, 8, 9 and 10. There are a total of 10 stepping numbers in the range. Hence, the output is 10.
Example 2:
Input: low = "90", high = "101" Output: 2 Explanation: The stepping numbers in the range [90,101] are 98 and 101. There are a total of 2 stepping numbers in the range. Hence, the output is 2.
Constraints:
1 <= int(low) <= int(high) < 101001 <= low.length, high.length <= 100lowandhighconsist of only digits.lowandhighdon't have any leading zeros.
代码结果
运行时间: 57 ms, 内存: 16.3 MB
/*
* 思路：
* 1. Java Streams 通常用于处理集合和数组，而这道题涉及到BFS和大整数操作，
* 直接使用Streams并不是最优解。
* 2. 但为了演示，我们可以使用Streams来初始化步进数字并收集结果。
*/
import java.math.BigInteger;
import java.util.LinkedList;
import java.util.Queue;
import java.util.stream.IntStream;
public class StepNumberCounterStream {
public int countSteppingNumbers(String low, String high) {
BigInteger lowNum = new BigInteger(low);
BigInteger highNum = new BigInteger(high);
int[] count = {0};
int MOD = 1000000007;
Queue<BigInteger> queue = new LinkedList<>();
IntStream.rangeClosed(1, 9).forEach(i -> queue.offer(BigInteger.valueOf(i)));
while (!queue.isEmpty()) {
BigInteger num = queue.poll();
if (num.compareTo(highNum) > 0) continue;
if (num.compareTo(lowNum) >= 0) count[0] = (count[0] + 1) % MOD;
BigInteger lastDigit = num.mod(BigInteger.TEN);
BigInteger nextUp = num.multiply(BigInteger.TEN).add(lastDigit.add(BigInteger.ONE));
BigInteger nextDown = num.multiply(BigInteger.TEN).add(lastDigit.subtract(BigInteger.ONE));
if (lastDigit.compareTo(BigInteger.ZERO) > 0) queue.offer(nextDown);
if (lastDigit.compareTo(BigInteger.valueOf(9)) < 0) queue.offer(nextUp);
}
return count[0];
}
}
解释
方法:
题解采用动态规划的思想，结合记忆化搜索的方法来统计步进数字。首先，定义一个多维数组result，其中result[i][j]表示长度为j且以数字i开始的步进数字数量。通过一个预处理步骤，使用动态规划填充这个数组。动态转移方程基于前一位的数字和其相邻数字构建，确保每次构建的数字符合步进数字的要求。在主函数中，使用两个辅助函数来计算范围[low, high]内的步进数字，分别计算小于或等于high的步进数字和小于low的步进数字，然后求差值并校验low是否为步进数字，以得到最终答案。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
题解中提到了使用动态规划填充多维数组result，能否具体解释一下这个数组的含义以及如何使用该数组来统计步进数字的数量？
▷🦆
在动态转移方程中，为什么每次只考虑数字的相邻数位间差为1，而不是处理更广泛的数字差？这样的设计对算法的效率和结果精度有何影响？
▷🦆
题解中提到了对数字长度进行预处理，这种处理方式在面对非常大或非常小的输入范围时是否仍然有效？
▷