连续差相同的数字
难度:
标签:
题目描述
代码结果
运行时间: 27 ms, 内存: 16.2 MB
// Java Stream solution
/*
* Solution Approach using Java Streams:
* 1. Similar recursive approach as the regular Java solution but with Streams.
* 2. Use IntStream to iterate through possible starting digits.
* 3. Use recursive stream generation to build numbers.
* 4. Collect the results into a list.
*/
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;
public class SolutionStream {
public List<Integer> numsSameConsecDiff(int n, int k) {
return IntStream.range(1, 10)
.boxed()
.flatMap(i -> findNumbersStream(i, n - 1, k))
.collect(Collectors.toList());
}
private Stream<Integer> findNumbersStream(int currentNumber, int remainingDigits, int k) {
if (remainingDigits == 0) return Stream.of(currentNumber);
int lastDigit = currentNumber % 10;
return Stream.concat(
(lastDigit + k <= 9 ? findNumbersStream(currentNumber * 10 + (lastDigit + k), remainingDigits - 1, k) : Stream.empty()),
(k != 0 && lastDigit - k >= 0 ? findNumbersStream(currentNumber * 10 + (lastDigit - k), remainingDigits - 1, k) : Stream.empty())
);
}
}
解释
方法:
这个题解采用了深度优先搜索(DFS)的方法来解决问题。首先,题解定义了一个递归函数 dfs,该函数用于构建满足条件的数字。函数的参数包括当前位的数字(bit)、到目前为止构建的数字(num)以及当前的位置(pos)。如果当前的位置等于n,意味着已经构建了一个长度为n的数字,将其添加到结果列表res中。否则,递归地尝试在当前数字后添加bit+k和bit-k(如果它们在0到9的范围内且合法)。整个搜索从1到9的每个数字开始,避免了前导零的问题。通过这种方式,可以生成所有符合条件的数字。
时间复杂度:
O(2^n)
空间复杂度:
O(n)
代码细节讲解
🦆
在DFS函数中,如何确保每个生成的数字都没有前导零?
▷🦆
为什么在递归的内部检查`bit + k <= 9`和`bit - k >= 0`,这些条件是如何保证数字在0到9的合法范围内的?
▷🦆
题解中提到递归的基本情况是`pos == n`,请问在这种情况下直接将num添加到结果列表中是否考虑了所有边界条件?
▷🦆
为什么当`k != 0`时,才考虑`bit - k`的情况,将k等于0时的行为与k不等于0时的行为进行对比,会有什么不同?
▷