找出 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` 函数中,你是如何处理数组 `digits` 来确保不使用已经选择的数字?
▷🦆
当 `digits` 数组中所有数字都相同时(例如 [8,8,8]),这种方法是否仍然有效?
▷