Easy

题目描述

给你一个由数字组成的数组 digits。你的任务是确定使用这些数字能够形成的不同三位偶数的数量。

注意：每个数字的每份拷贝在一个数字中只能使用一次，并且不能有前导零。

示例 1：

输入：digits = [1,2,3,4]
输出：12
解释：可以形成的12个不同的三位偶数是：124, 132, 134, 142, 214, 234, 312, 314, 324, 342, 412, 432。注意222不能形成，因为只有1个数字2。

示例 2：

输入：digits = [0,2,2]
输出：2
解释：唯一可以形成的三位偶数是：202和220。注意数字2可以使用两次，因为它在数组中出现了两次。

示例 3：

输入：digits = [6,6,6]
输出：1
解释：只能形成666。

示例 4：

输入：digits = [1,3,5]
输出：0
解释：无法形成偶数三位数。

约束条件：

  • 3 <= digits.length <= 10
  • 0 <= digits[i] <= 9

解题思路

这道题要求我们找出能用给定数字组成的所有不同三位偶数的数量。

解题思路：

  1. 偶数条件：三位数要是偶数，个位数必须是偶数（0, 2, 4, 6, 8）
  2. 无前导零：百位数不能是0
  3. 数字使用限制：每个数字只能使用其在数组中出现的次数

方法一：枚举法（推荐）

  • 枚举所有可能的百位、十位、个位组合
  • 对于每种组合，检查是否满足条件：
    • 个位是偶数
    • 百位不为0
    • 三个位置的数字在原数组中有足够的数量
  • 使用Set去重，因为可能有重复的数字组合

方法二：回溯法 也可以使用回溯法逐位构造，但对于这个问题，枚举法更直观简洁。

实现时需要统计每个数字的出现次数，然后枚举所有可能的三位数组合，检查是否能用现有数字构成。

代码实现

class Solution {
public:
    int totalNumbers(vector<int>& digits) {
        vector<int> count(10, 0);
        for (int d : digits) {
            count[d]++;
        }
        
        set<int> uniqueNumbers;
        
        for (int h = 1; h <= 9; h++) {
            for (int t = 0; t <= 9; t++) {
                for (int u = 0; u <= 9; u += 2) {
                    if (count[h] > 0 && count[t] > 0 && count[u] > 0) {
                        vector<int> used(10, 0);
                        used[h]++;
                        used[t]++;
                        used[u]++;
                        
                        bool valid = true;
                        for (int i = 0; i < 10; i++) {
                            if (used[i] > count[i]) {
                                valid = false;
                                break;
                            }
                        }
                        
                        if (valid) {
                            uniqueNumbers.insert(h * 100 + t * 10 + u);
                        }
                    }
                }
            }
        }
        
        return uniqueNumbers.size();
    }
};

class Solution:
    def totalNumbers(self, digits: List[int]) -> int:
        from collections import Counter
        
        count = Counter(digits)
        unique_numbers = set()
        
        for h in range(1, 10):
            for t in range(0, 10):
                for u in range(0, 10, 2):
                    used = Counter([h, t, u])
                    
                    valid = True
                    for digit, freq in used.items():
                        if count[digit] < freq:
                            valid = False
                            break
                    
                    if valid:
                        unique_numbers.add(h * 100 + t * 10 + u)
        
        return len(unique_numbers)

public class Solution {
    public int TotalNumbers(int[] digits) {
        int[] count = new int[10];
        foreach (int d in digits) {
            count[d]++;
        }
        
        HashSet<int> uniqueNumbers = new HashSet<int>();
        
        for (int h = 1; h <= 9; h++) {
            for (int t = 0; t <= 9; t++) {
                for (int u = 0; u <= 9; u += 2) {
                    int[] used = new int[10];
                    used[h]++;
                    used[t]++;
                    used[u]++;
                    
                    bool valid = true;
                    for (int i = 0; i < 10; i++) {
                        if (used[i] > count[i]) {
                            valid = false;
                            break;
                        }
                    }
                    
                    if (valid) {
                        uniqueNumbers.Add(h * 100 + t * 10 + u);
                    }
                }
            }
        }
        
        return uniqueNumbers.Count;
    }
}

var totalNumbers = function(digits) {
    const count = new Array(10).fill(0);
    for (const d of digits) {
        count[d]++;
    }
    
    const uniqueNumbers = new Set();
    
    for (let h = 1; h <= 9; h++) {
        for (let t = 0; t <= 9; t++) {
            for (let u = 0; u <= 9; u += 2) {
                const used = new Array(10).fill(0);
                used[h]++;
                used[t]++;
                used[u]++;
                
                let valid = true;
                for (let i = 0; i < 10; i++) {
                    if (used[i] > count[i]) {
                        valid = false;
                        break;
                    }
                }
                
                if (valid) {
                    uniqueNumbers.add(h * 100 + t * 10 + u);
                }
            }
        }
    }
    
    return uniqueNumbers.size;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(1) - 最多枚举9×10×5=450种组合，常数时间
空间复杂度O(1) - 使用固定大小的计数数组和集合，最多存储450个数字

相关题目