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 <= 10
0 <= digits[i] <= 9

解法

方法一：哈希表 + 枚举

我们用一个哈希表 \(\textit{s}\) 记录所有不同的三位偶数，然后枚举所有可能的三位偶数，将其加入哈希表中。

最后返回哈希表的大小即可。

时间复杂度 \(O(n^3)\)，空间复杂度 \(O(n^3)\)。其中 \(n\) 为数组 \(\textit{digits}\) 的长度。

Python3JavaC++GoTypeScript

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)

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();
    }
}

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();
    }
};

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)
}

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;
}

3483. 不同三位偶数的数目

题目描述

解法

方法一：哈希表 + 枚举

评论