0512 - 2094. 找出 3 位偶数

1. 题目链接

2094. 找出 3 位偶数 - 力扣（LeetCode）

2. 题目描述

给你一个整数数组 digits ，其中每个元素是一个数字（0 - 9）。数组中可能存在重复元素。

你需要找出 所有 满足下述条件且 互不相同 的整数：

• 该整数由 digits 中的三个元素按 任意 顺序 依次连接 组成。
• 该整数不含 前导零
• 该整数是一个 偶数

例如，给定的 digits 是 [1, 2, 3] ，整数 132 和 312 满足上面列出的全部条件。

将找出的所有互不相同的整数按 递增顺序 排列，并以数组形式返回。

3. 题目示例

示例 1 :

输入：digits = [2,1,3,0]
输出：[102,120,130,132,210,230,302,310,312,320]
解释：
所有满足题目条件的整数都在输出数组中列出。 
注意，答案数组中不含有 奇数 或带 前导零 的整数。

示例 2 :

输入：digits = [2,2,8,8,2]
输出：[222,228,282,288,822,828,882]
解释：
同样的数字（0 - 9）在构造整数时可以重复多次，重复次数最多与其在 digits 中出现的次数一样。 
在这个例子中，数字 8 在构造 288、828 和 882 时都重复了两次。

4. 解题思路

1. 问题理解：
   • 给定一个数字数组digits，需要从中构造所有可能的3位偶数。
   • 每个数字只能使用一次（即不能重复使用同一个数字，除非原数组中有多个相同的数字）。
   • 第一位不能是0，第三位必须是偶数（0, 2, 4, 6, 8）。
2. 关键思路：
   • 统计数字频率：首先统计每个数字（0-9）在原数组中的出现次数。
   • 回溯法（DFS）：使用深度优先搜索生成所有可能的3位数，同时满足：
     • 第一位非0。
     • 第三位是偶数。
     • 每个数字的使用次数不超过其在原数组中的出现次数。
3. 算法流程：
   • 统计数字频率。
   • 使用DFS生成所有可能的3位数，递归过程中检查数字可用性和位置约束。
   • 将结果收集到列表中，最后转换为数组返回。

5. 题解代码

class Solution {
    public int[] findEvenNumbers(int[] digits) {
        // 统计每个数字（0-9）的出现次数
        int[] cnt = new int[10];
        for(int d : digits){
            cnt[d]++;
        }

        // 使用DFS生成所有可能的3位偶数
        List<Integer> ans = new ArrayList<>();
        dfs(0, 0, cnt, ans);
        
        // 将结果转换为数组返回
        return ans.stream().mapToInt(i -> i).toArray();
    }

    private void dfs(int i, int x, int[] cnt, List<Integer> ans){
        // 当生成到第3位时，检查是否是偶数并加入结果
        if(i == 3){
            ans.add(x);
            return;
        }
        
        // 尝试所有可能的数字（0-9）
        for(int d = 0; d < 10; d++){
            // 检查数字是否可用，并满足条件：
            // 第一位不能是0，第三位必须是偶数
            if(cnt[d] > 0 && (i == 0 && d > 0 || i == 1 || i == 2 && d % 2 == 0)){
                cnt[d]--; // 使用该数字
                dfs(i + 1, x * 10 + d, cnt, ans); // 递归生成下一位
                cnt[d]++; // 回溯，恢复数字计数
            }
        }
    }
}

6. 复杂度分析

1. 时间复杂度：
   • 统计数字频率：O(n)，其中n是digits的长度。
   • DFS生成所有可能的3位数：最坏情况下需要尝试10^3 = 1000种组合（每位有10种可能）。
   • 总时间复杂度：O(n + 10^3) ≈ O(n + 1000)。
2. 空间复杂度：
   • 数字频率数组：O(10) = O(1)。
   • DFS递归栈：O(3) = O(1)（递归深度为3）。
   • 结果列表：最坏情况下可能有O(10^3) = O(1000)个结果。
   • 总空间复杂度：O(1000) = O(1)（因为1000是常数）。