3483. 不同三位偶数的数目
题目描述
给你一个数字数组 digits，你需要从中选择三个数字组成一个三位偶数，你的任务是求出 不同 三位偶数的数量。
注意：每个数字在三位偶数中都只能使用 一次 ，并且 不能 有前导零。
示例 1：
输入： digits = [1,2,3,4]
输出： 12
解释： 可以形成的 12 个不同的三位偶数是 124，132，134，142，214，234，312，314，324，342，412 和 432。注意，不能形成 222，因为数字 2 只有一个。
示例 2：
输入： digits = [0,2,2]
输出： 2
解释： 可以形成的三位偶数是 202 和 220。注意，数字 2 可以使用两次，因为数组中有两个 2 。
示例 3：
输入： digits = [6,6,6]
输出： 1
解释： 只能形成 666。
示例 4：
输入： digits = [1,3,5]
输出： 0
解释： 无法形成三位偶数。
提示：
3 <= digits.length <= 100 <= digits[i] <= 9
解法
方法一：哈希表 + 枚举
我们用一个哈希表 $\textit{s}$ 记录所有不同的三位偶数，然后枚举所有可能的三位偶数，将其加入哈希表中。
最后返回哈希表的大小即可。
时间复杂度 $O(n^3)$，空间复杂度 $O(n^3)$。其中 $n$ 为数组 $\textit{digits}$ 的长度。
Python3
class Solution:
def totalNumbers(self, digits: List[int]) -> int:
s = set()
for i, a in enumerate(digits):
if a & 1:
continue
for j, b in enumerate(digits):
if i == j:
continue
for k, c in enumerate(digits):
if c == 0 or k in (i, j):
continue
s.add(c * 100 + b * 10 + a)
return len(s)
Java
class Solution {
public int totalNumbers(int[] digits) {
Set<Integer> s = new HashSet<>();
int n = digits.length;
for (int i = 0; i < n; ++i) {
if (digits[i] % 2 == 1) {
continue;
}
for (int j = 0; j < n; ++j) {
if (i == j) {
continue;
}
for (int k = 0; k < n; ++k) {
if (digits[k] == 0 || k == i || k == j) {
continue;
}
s.add(digits[k] * 100 + digits[j] * 10 + digits[i]);
}
}
}
return s.size();
}
}
C++
class Solution {
public:
int totalNumbers(vector<int>& digits) {
unordered_set<int> s;
int n = digits.size();
for (int i = 0; i < n; ++i) {
if (digits[i] % 2 == 1) {
continue;
}
for (int j = 0; j < n; ++j) {
if (i == j) {
continue;
}
for (int k = 0; k < n; ++k) {
if (digits[k] == 0 || k == i || k == j) {
continue;
}
s.insert(digits[k] * 100 + digits[j] * 10 + digits[i]);
}
}
}
return s.size();
}
};
Go
func totalNumbers(digits []int) int {
s := make(map[int]struct{})
for i, a := range digits {
if a%2 == 1 {
continue
}
for j, b := range digits {
if i == j {
continue
}
for k, c := range digits {
if c == 0 || k == i || k == j {
continue
}
s[c*100+b*10+a] = struct{}{}
}
}
}
return len(s)
}
TypeScript
function totalNumbers(digits: number[]): number {
const s = new Set<number>();
const n = digits.length;
for (let i = 0; i < n; ++i) {
if (digits[i] % 2 === 1) {
continue;
}
for (let j = 0; j < n; ++j) {
if (i === j) {
continue;
}
for (let k = 0; k < n; ++k) {
if (digits[k] === 0 || k === i || k === j) {
continue;
}
s.add(digits[k] * 100 + digits[j] * 10 + digits[i]);
}
}
}
return s.size;
}