计算机创新协会冬令营——暴力枚举题目04

说句实话，单纯的暴力枚举题目太难找了┭┮﹏┭┮，接招吧~~

题目

2094. 找出 3 位偶数 - 力扣（LeetCode）

给你一个整数数组 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

Java解法：暴力遍历

这需要挨个找到全部的数，然后注意去重即可。

class Solution {
    public int[] findEvenNumbers(int[] digits) {
        int len = digits.length;
        // 这里使用集合的原因主要是java中数组的长度是事先固定的，但是我们又不知道长度，所以采用集合
        Set<Integer> set = new HashSet<>();
        // 三层for循环解决问题
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                for (int k = 0; k < len; k++) {
                    // 重复位置跳过
                    if (i == j || j == k || i == k) {
                        continue;
                    }
                    // 判断是否满足条件
                    int num = digits[i] * 100 + digits[j] * 10 + digits[k];
                    if (num >= 100 && num % 2 == 0) {
                        // 满足条件加入集合
                        set.add(num);
                    }
                }
            }
        }
        // 集合转化为 int数组
        int[] res = set.stream().mapToInt(Integer::intValue).toArray();
        // 从小到大排序
        Arrays.sort(res);
        return res;
    }
}

C解法

这段C的解法由于我对C不太了解哈，找其他学长写的，大家看不懂的话可以理解思路即可。

或者在力扣找使用C的同学看一看他们通过的代码♪


// 定义比较函数用于排序
int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

// 判断是否为偶数
int isEven(int num) {
    return num % 2 == 0;
}

int* findEvenNumbers(int* digits, int digitsSize, int* returnSize) {
    // 生成所有可能的三位数
    int count = 0;
    int maxResultSize = digitsSize * digitsSize * digitsSize;
    int* result = (int*)malloc(sizeof(int) * maxResultSize);
    int* isVisited = (int*)calloc(1000, sizeof(int));

    for (int i = 0; i < digitsSize; i++) {
        for (int j = 0; j < digitsSize; j++) {
            for (int k = 0; k < digitsSize; k++) {
                // 判断索引是否相同
                if (i != j && i != k && j != k) {
                    // 将三个数字按顺序连接成三位数
                    int number = digits[i] * 100 + digits[j] * 10 + digits[k];

                    // 检查是否满足条件且未访问过
                    if (isEven(number) && number >= 100 && number <= 999 && !isVisited[number]) {
                        result[count++] = number;
                        isVisited[number] = 1;
                    }
                }
            }
        }
    }

    // 如果没有找到符合条件的数字，则返回空数组
    if (count == 0) {
        free(result);
        free(isVisited);
        *returnSize = 0;
        return NULL;
    }

    // 排序结果数组
    qsort(result, count, sizeof(int), compare);

    // 动态分配内存以保存结果
    int* finalResult = (int*)malloc(sizeof(int) * count);
    for (int i = 0; i < count; i++) {
        finalResult[i] = result[i];
    }

    // 释放内存
    free(result);
    free(isVisited);

    // 更新返回结果的大小
    *returnSize = count;

    return finalResult;
}

C++解法

class Solution {
public:
    vector<int> findEvenNumbers(vector<int>& digits) {
        int len = digits.size();
        std::set<int> s;

        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                for (int k = 0; k < len; k++) {
                    // 重复位置跳过
                    if (i == j || j == k || i == k) {
                        continue;
                    }

                    // 判断是否满足条件
                    int num = digits[i] * 100 + digits[j] * 10 + digits[k];
                    if (num >= 100 && num % 2 == 0) {
                        // 满足条件加入集合
                        s.insert(num);
                    }
                }
            }
        }

        // 集合转化为 vector
        std::vector<int> res(s.begin(), s.end());

        // 从小到大排序
        std::sort(res.begin(), res.end());

        return res;
    }
};

Python3

class Solution:
    def findEvenNumbers(self, digits: List[int]) -> List[int]:
        length = len(digits)
        result_set = set()

        # 三层for循环解决问题
        for i in range(length):
            for j in range(length):
                for k in range(length):
                    # 重复位置跳过
                    if i == j or j == k or i == k:
                        continue

                    # 判断是否满足条件
                    num = digits[i] * 100 + digits[j] * 10 + digits[k]
                    if 100 <= num <= 999 and num % 2 == 0:
                        # 满足条件加入集合
                        result_set.add(num)

        # 集合转化为列表，并排序
        result_list = sorted(list(result_set))
        return result_list