2094. 找出 3 位偶数

🟢 🔖 数组 哈希表 枚举 排序 🔗 力扣open in new window LeetCodeopen in new window

题目

You are given an integer array digits, where each element is a digit. The array may contain duplicates.

You need to find all the unique integers that follow the given requirements:

The integer consists of the concatenation of three elements from digits in any arbitrary order.
The integer does not have leading zeros.
The integer is even.

For example, if the given digits were [1, 2, 3], integers 132 and 312 follow the requirements.

Return a sorted array of the unique integers.

Example 1:

Input: digits = [2,1,3,0]
Output: [102,120,130,132,210,230,302,310,312,320]
Explanation: All the possible integers that follow the requirements are in the output array.
Notice that there are no odd integers or integers with leading zeros.

Example 2:

Input: digits = [2,2,8,8,2]
Output: [222,228,282,288,822,828,882]
Explanation: The same digit can be used as many times as it appears in digits.
In this example, the digit 8 is used twice each time in 288, 828, and 882.

Example 3:

Input: digits = [3,7,5]
Output: []
Explanation: No even integers can be formed using the given digits.

Constraints:

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

题目大意

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

解题思路

排序输入数组：首先对 digits 进行排序，这样可以保证生成的数字天然按升序排列，方便去重和构造结果。
初始化：创建一个布尔数组 used 用于标记数字是否被使用，初始化结果数组 res。
递归函数：
- 通过参数 track 记录已选择的数字个数，参数 num 表示当前构造的数字。
- 遍历 digits：
  - 跳过已被使用的数字。
  - 如果是首位数字且为 0，跳过。
  - 若当前数字等于前一个数字，且前一个数字未被使用，则跳过，避免生成重复的三位数。
- 在递归过程中，更新选择状态，直接用整数运算构造数字，而非依赖字符串拼接和转换。
- 回溯时撤销状态。
终止条件：当选择了 3 个数字（track === 3），检查数字是否为偶数，是偶数则加入结果。
返回结果：将结果数组返回。

复杂度分析

时间复杂度：O(n^3)，最坏情况下生成所有长度为 3 的组合，约为 O(n^3)，剪枝后减少了无效路径的回溯，实际复杂度低于 O(n^3)。
空间复杂度：O(n)，标记数组和递归栈的深度为 O(n)。

代码

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var findEvenNumbers = function (digits) {
	digits.sort((a, b) => a - b); // 排序保证递增
	const n = digits.length;
	const res = [];
	const used = new Array(n).fill(false);

	// 回溯函数
	const backtrack = (track, num) => {
		if (track === 3) {
			// 如果构造了 3 位数
			if (num % 2 === 0) {
				// 检查是否为偶数
				res.push(num);
			}
			return;
		}

		for (let i = 0; i < n; i++) {
			if (used[i]) continue; // 跳过已使用的数字
			if (track === 0 && digits[i] === 0) continue; // 首位不能为 0
			if (i > 0 && digits[i] === digits[i - 1] && !used[i - 1]) continue; // 跳过重复的数字

			used[i] = true;
			backtrack(track + 1, num * 10 + digits[i]); // 递归构造数字
			used[i] = false; // 撤销选择
		}
	};

	backtrack(0, 0);
	return res;
};

2094. 找出 3 位偶数

# 2094. 找出 3 位偶数

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

2094. 找出 3 位偶数

题目

题目大意

解题思路

复杂度分析

代码

相关题目