当前位置：首页 > backend >正文

LeetCode 2094.找出 3 位偶数：遍历3位偶数

backend 2025/5/15 1:31:56

【LetMeFly】2094.找出 3 位偶数：遍历3位偶数

力扣题目链接：https://leetcode.cn/problems/finding-3-digit-even-numbers/

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

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

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

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

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

示例 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 时都重复了两次。

示例 3：

输入：digits = [3,7,5]
输出：[]
解释：
使用给定的 digits 无法构造偶数。

提示：

3 <= digits.length <= 100
0 <= digits[i] <= 9

解题方法：遍历统计

首先统计给出的 $d i g i t s$ 数组中， $0 - 9$ 各有多少个（记为 $t im es [j]$ ）。

接着从 $100$ 到 $998$ 遍历所有偶数，对于其中一个偶数 $i$ ，统计 $i$ 中 $0 - 9$ 分别出现多少次（记为 $t hi s T im es [j]$ ）。

如果 $thisTimse[j]\gt times[j]$ ，则说明这个偶数无法由digits中的元素组成。

时间复杂度 $O (C D + l e n (d i g i t s))$ ，其中 $D = 10$ ， $C = 500$
空间复杂度 $O (D)$

AC代码

C++

/** @Author: LetMeFly* @Date: 2025-05-12 10:20:43* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-05-12 22:35:40*/
class Solution {
private:int cnt[10] = {0};bool isOk(int i) {if (i % 2) {return false;}int temp[10] = {0};while (i) {temp[i % 10]++;i /= 10;}for (int i = 0; i < 10; i++) {if (cnt[i] < temp[i]) {return false;}}return true;}
public:vector<int> findEvenNumbers(vector<int>& digits) {for (int d : digits) {cnt[d]++;}vector<int> ans;for (int i = 100; i < 1000; i++) {if (isOk(i)) {ans.push_back(i);}}// sort(ans.begin(), ans.end());return ans;}
};

Python

'''
Author: LetMeFly
Date: 2025-05-12 10:20:43
LastEditors: LetMeFly.xyz
LastEditTime: 2025-05-12 13:16:04
'''
from typing import Listclass Solution:def findEvenNumbers(self, digits: List[int]) -> List[int]:times = [0] * 10for d in digits:times[d] += 1ans = []for i in range(100, 1000, 2):thisTimes = [0] * 10tmp = iwhile tmp:thisTimes[tmp % 10] += 1tmp //= 10ok = Truefor j in range(10):if thisTimes[j] > times[j]:ok = Falsebreakif ok:ans.append(i)return sorted(ans)

Java

/** @Author: LetMeFly* @Date: 2025-05-12 10:20:43* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-05-12 22:38:33*/
import java.util.Arrays;
import java.util.ArrayList;class Solution {public int[] findEvenNumbers(int[] digits) {int[] times = new int[10];for (int d : digits) {times[d]++;}List<Integer> ans = new ArrayList<>();for (int i = 100; i < 1000; i += 2) {int tmp = i;int[] thisTimes = new int[10];while (tmp > 0) {thisTimes[tmp % 10]++;tmp /= 10;}boolean ok = true;for (int j = 0; j < 10; j++) {if (thisTimes[j] > times[j]) {ok = false;break;}}if (ok) {ans.add(i);}}int[] res = new int[ans.size()];for (int i = 0; i < ans.size(); i++) {res[i] = ans.get(i);}return res;}
}

Go

/** @Author: LetMeFly* @Date: 2025-05-12 21:58:15* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-05-12 22:43:11*/
package mainfunc findEvenNumbers(digits []int) []int {times := make([]int, 10)for _, d := range digits {times[d]++}ans := make([]int, 0)for i := 100; i < 1000; i += 2 {thisTimes := make([]int, 10)for tmp := i; tmp > 0; tmp /= 10 {thisTimes[tmp % 10]++}ok := truefor j := range times {if thisTimes[j] > times[j] {ok = falsebreak}}if ok {ans = append(ans, i)}}return ans
}