leetcode
leetcode 1851 ~ 1900
找出 3 位偶数

找出 3 位偶数

难度:

标签:

题目描述

代码结果

运行时间: 73 ms, 内存: 16.6 MB


// 思路:
// 1. 使用三个嵌套流来生成所有可能的数字组合。
// 2. 过滤掉有前导零和不是偶数的组合。
// 3. 使用Set去重并排序。

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {
    public List<Integer> findEvenNumbers(int[] digits) {
        return IntStream.range(0, digits.length)
                .boxed()
                .flatMap(i -> IntStream.range(0, digits.length)
                        .boxed()
                        .flatMap(j -> IntStream.range(0, digits.length)
                                .boxed()
                                .map(k -> new int[]{digits[i], digits[j], digits[k]})))
                .filter(arr -> arr[0] != arr[1] && arr[1] != arr[2] && arr[0] != arr[2])
                .map(arr -> arr[0] * 100 + arr[1] * 10 + arr[2])
                .filter(num -> num >= 100 && num % 2 == 0)
                .collect(Collectors.toCollection(TreeSet::new))
                .stream()
                .collect(Collectors.toList());
    }
}

解释

方法:

该题解采用了回溯法来生成所有可能的三位数并验证其是否为偶数。首先,将数组排序以方便剪枝和去重。回溯函数 huisuo 从 1 开始计数,并根据当前位数的特定条件进行判断:若当前是百位且选中的数字为0,则跳过以避免前导零;若当前是个位且数字为奇数,则跳过以确保结果为偶数。通过递归调用 huisuo,依次在剩余的数字中选择下一个数字,直到形成一个完整的三位数后,将其添加到结果列表中。

时间复杂度:

O(n^3)

空间复杂度:

O(1)

代码细节讲解

🦆
在回溯过程中,函数 `huisuo` 的参数 `k` 是如何确保只生成三位数的?
在回溯函数`huisuo`中,参数`k`表示当前的数字位数,从1开始计数(表示百位)。回溯函数递归调用时,每进入下一层,`k`的值都会增加1,分别代表百位、十位和个位。当`k`达到4时(即表示数字已有三位),函数会停止进一步的递归调用,并将当前生成的三位数添加到结果列表中,从而确保只生成三位数。
🦆
为什么在进行剪枝时,选择跳过相同的元素而不是采取其他的去重方法?
在回溯中跳过相同的元素是为了避免生成重复的三位数。由于输入数组`digits`在开始时已被排序,相同的数字会连续排列。通过检查当前元素与前一个元素是否相同,可以有效地跳过那些在同一层次可能导致重复结果的数字。这种方法简单且直接,能够在生成结果的过程中即时剪枝,减少不必要的计算和递归调用,从而提高算法效率。
🦆
在 `huisuo` 函数中,你是如何处理数组 `digits` 来确保不使用已经选择的数字?
在`huisuo`函数中,每当选择一个数字加入到当前生成的数中后,会在递归调用`huisuo`时,传递一个更新后的`digits`数组。这个更新是通过`digits[:i] + digits[i+1:]`实现的,即从数组中移除已选择的数字。这样,新的递归层中的`digits`数组不包含当前已被选用的数字,从而确保每个数字只被使用一次。
🦆
当 `digits` 数组中所有数字都相同时(例如 [8,8,8]),这种方法是否仍然有效?
当`digits`数组中所有数字相同时,例如[8, 8, 8],这种方法仍然有效,但只能生成一个结果,即888。由于所有数字相同,第一个剪枝条件会在除第一个数字外的所有递归调用中生效,导致只有第一个数字被重复使用三次,生成一个唯一的三位数。尽管这样的输入限制了结果的多样性,算法仍能正确处理并返回有效的结果。

相关问题