LeetCode 2094: Finding 3-Digit Even Numbers (Digit Count Enumeration)
LeetCode 2094ArrayCountingToday we solve LeetCode 2094 - Finding 3-Digit Even Numbers.
Source: https://leetcode.com/problems/finding-3-digit-even-numbers/
English
Problem Summary
Given an array of digits, build all unique three-digit even numbers that can be formed using each occurrence at most once. The number cannot have a leading zero.
Key Idea
Count available digits (0 to 9). Then enumerate every even number from 100 to 998. For each candidate, count its three digits and verify the candidate count does not exceed available count.
Algorithm
1) Build frequency array cnt[10] from input digits.
2) For each even number x from 100 to 998:
- Extract digits a=x/100, b=(x/10)%10, c=x%10.
- Build needed frequency need[10] for a,b,c.
- If need[d] <= cnt[d] for all d, include x.
3) Return all included numbers in ascending order.
Complexity
Time complexity O(900 * 10), effectively constant.
Space complexity O(10).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int[] findEvenNumbers(int[] digits) {
int[] cnt = new int[10];
for (int d : digits) cnt[d]++;
java.util.List<Integer> ans = new java.util.ArrayList<>();
for (int x = 100; x <= 998; x += 2) {
int[] need = new int[10];
need[x / 100]++;
need[(x / 10) % 10]++;
need[x % 10]++;
boolean ok = true;
for (int d = 0; d < 10; d++) {
if (need[d] > cnt[d]) {
ok = false;
break;
}
}
if (ok) ans.add(x);
}
int[] out = new int[ans.size()];
for (int i = 0; i < ans.size(); i++) out[i] = ans.get(i);
return out;
}
}func findEvenNumbers(digits []int) []int {
cnt := make([]int, 10)
for _, d := range digits {
cnt[d]++
}
ans := make([]int, 0)
for x := 100; x <= 998; x += 2 {
need := make([]int, 10)
need[x/100]++
need[(x/10)%10]++
need[x%10]++
ok := true
for d := 0; d < 10; d++ {
if need[d] > cnt[d] {
ok = false
break
}
}
if ok {
ans = append(ans, x)
}
}
return ans
}class Solution {
public:
vector<int> findEvenNumbers(vector<int>& digits) {
vector<int> cnt(10, 0);
for (int d : digits) cnt[d]++;
vector<int> ans;
for (int x = 100; x <= 998; x += 2) {
vector<int> need(10, 0);
need[x / 100]++;
need[(x / 10) % 10]++;
need[x % 10]++;
bool ok = true;
for (int d = 0; d < 10; d++) {
if (need[d] > cnt[d]) {
ok = false;
break;
}
}
if (ok) ans.push_back(x);
}
return ans;
}
};class Solution:
def findEvenNumbers(self, digits: List[int]) -> List[int]:
cnt = [0] * 10
for d in digits:
cnt[d] += 1
ans = []
for x in range(100, 999, 2):
need = [0] * 10
need[x // 100] += 1
need[(x // 10) % 10] += 1
need[x % 10] += 1
if all(need[d] <= cnt[d] for d in range(10)):
ans.append(x)
return ansvar findEvenNumbers = function(digits) {
const cnt = Array(10).fill(0);
for (const d of digits) cnt[d]++;
const ans = [];
for (let x = 100; x <= 998; x += 2) {
const need = Array(10).fill(0);
need[Math.floor(x / 100)]++;
need[Math.floor(x / 10) % 10]++;
need[x % 10]++;
let ok = true;
for (let d = 0; d < 10; d++) {
if (need[d] > cnt[d]) {
ok = false;
break;
}
}
if (ok) ans.push(x);
}
return ans;
};中文
题目概述
给定一个数字数组，要求使用这些数字（每个下标最多使用一次）组成所有不重复的三位偶数，且百位不能为 0。
核心思路
先统计 0 到 9 每个数字的可用次数。然后枚举所有三位偶数（100 到 998，步长 2），检查候选数三个数位所需次数是否都不超过可用次数。
算法步骤
1）统计输入数组频次 cnt[10]。
2）遍历每个候选偶数 x（100 到 998，步长 2）。
3）提取百位、十位、个位并统计需求频次 need[10]。
4）若对所有数字都有 need[d] <= cnt[d]，则将该数加入答案。
5）由于按升序枚举，结果天然升序。
复杂度分析
时间复杂度约为 O(900 * 10)，可视为常数级。
空间复杂度 O(10)。
参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int[] findEvenNumbers(int[] digits) {
int[] cnt = new int[10];
for (int d : digits) cnt[d]++;
java.util.List<Integer> ans = new java.util.ArrayList<>();
for (int x = 100; x <= 998; x += 2) {
int[] need = new int[10];
need[x / 100]++;
need[(x / 10) % 10]++;
need[x % 10]++;
boolean ok = true;
for (int d = 0; d < 10; d++) {
if (need[d] > cnt[d]) {
ok = false;
break;
}
}
if (ok) ans.add(x);
}
int[] out = new int[ans.size()];
for (int i = 0; i < ans.size(); i++) out[i] = ans.get(i);
return out;
}
}func findEvenNumbers(digits []int) []int {
cnt := make([]int, 10)
for _, d := range digits {
cnt[d]++
}
ans := make([]int, 0)
for x := 100; x <= 998; x += 2 {
need := make([]int, 10)
need[x/100]++
need[(x/10)%10]++
need[x%10]++
ok := true
for d := 0; d < 10; d++ {
if need[d] > cnt[d] {
ok = false
break
}
}
if ok {
ans = append(ans, x)
}
}
return ans
}class Solution {
public:
vector<int> findEvenNumbers(vector<int>& digits) {
vector<int> cnt(10, 0);
for (int d : digits) cnt[d]++;
vector<int> ans;
for (int x = 100; x <= 998; x += 2) {
vector<int> need(10, 0);
need[x / 100]++;
need[(x / 10) % 10]++;
need[x % 10]++;
bool ok = true;
for (int d = 0; d < 10; d++) {
if (need[d] > cnt[d]) {
ok = false;
break;
}
}
if (ok) ans.push_back(x);
}
return ans;
}
};class Solution:
def findEvenNumbers(self, digits: List[int]) -> List[int]:
cnt = [0] * 10
for d in digits:
cnt[d] += 1
ans = []
for x in range(100, 999, 2):
need = [0] * 10
need[x // 100] += 1
need[(x // 10) % 10] += 1
need[x % 10] += 1
if all(need[d] <= cnt[d] for d in range(10)):
ans.append(x)
return ansvar findEvenNumbers = function(digits) {
const cnt = Array(10).fill(0);
for (const d of digits) cnt[d]++;
const ans = [];
for (let x = 100; x <= 998; x += 2) {
const need = Array(10).fill(0);
need[Math.floor(x / 100)]++;
need[Math.floor(x / 10) % 10]++;
need[x % 10]++;
let ok = true;
for (let d = 0; d < 10; d++) {
if (need[d] > cnt[d]) {
ok = false;
break;
}
}
if (ok) ans.push(x);
}
return ans;
};
Comments