leetcode
leetcode 851 ~ 900
连续差相同的数字

连续差相同的数字

难度:

标签:

题目描述

代码结果

运行时间: 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函数中,如何确保每个生成的数字都没有前导零?
在DFS函数中确保生成的数字没有前导零是通过从1到9的每个数字开始递归搜索实现的。这意味着每个数字的第一位总是在1到9之间,从而排除了任何前导零的可能性。这种方法自然而然地避免了生成以0开头的数字,因为递归的起始点排除了0。
🦆
为什么在递归的内部检查`bit + k <= 9`和`bit - k >= 0`,这些条件是如何保证数字在0到9的合法范围内的?
检查`bit + k <= 9`和`bit - k >= 0`是为了确保添加到数字中的每个新位都是有效的十进制数字(即介于0到9之间)。这些条件确保在递归过程中构造的数字不会包含非法的数字位。例如,如果`bit + k`的结果超过9或`bit - k`的结果小于0,则相应的位将不符合数字的标准格式,因此这些情况被排除在递归逻辑之外。
🦆
题解中提到递归的基本情况是`pos == n`,请问在这种情况下直接将num添加到结果列表中是否考虑了所有边界条件?
当`pos == n`时,意味着已经构建了一个长度为n的数字,此时将`num`添加到结果列表中是符合题目要求的。这里的基本情况确实考虑了所有边界条件,因为只有当数字长度恰好为n时,此数字才被认为是完全构建的并被添加到结果中。这个检查确保了不会有长度不足或过长的数字被添加到结果集。
🦆
为什么当`k != 0`时,才考虑`bit - k`的情况,将k等于0时的行为与k不等于0时的行为进行对比,会有什么不同?
当`k != 0`时,`bit - k`和`bit + k`产生的结果是不同的,这代表着数字可以在增加和减少的方向上拓展。但如果`k = 0`,则`bit + k`和`bit - k`都将产生相同的结果,即`bit`本身。这会导致重复的递归调用,因为两种情况下添加到数字中的值是一样的。为了避免这种不必要的重复和可能的性能问题,当`k = 0`时,只需考虑`bit + k`的情况,从而避免重复添加相同的数字位。

相关问题