给你一个整数数组 digits ，其中每个元素是一个数字（0 - 9）。数组中可能存在重复元素。
你需要找出 所有 满足下述条件且 互不相同 的整数：
该整数由 digits 中的三个元素按 任意 顺序 依次连接 组成。
该整数不含 前导零
该整数是一个 偶数
例如，给定的 digits 是 [1, 2, 3] ，整数 132 和 312 满足上面列出的全部条件。
将找出的所有互不相同的整数按 递增顺序 排列，并以数组形式返回。
其中:
3 <= digits.length <= 100
0 <= digits[i] <= 9
例子
输入： digits = [2,1,3,0]
输出： [102,120,130,132,210,230,302,310,312,320]
解释：
所有满足题目条件的整数都在输出数组中列出。
注意，答案数组中不含有 奇数 或带 前导零 的整数。
输入：digits = [2,2,8,8,2]
输出：[222,228,282,288,822,828,882]
解释：
同样的数字（0 - 9）在构造整数时可以重复多次，重复次数最多与其在 digits 中出现的次数一样。
在这个例子中，数字 8 在构造 288、828 和 882 时都重复了两次。
输入：digits = [3,7,5]
输出：[]
解释：
使用给定的 digits 无法构造偶数。
输入：digits = [0,2,0,0]
输出：[200]
解释：
**唯一一个不含 前导零 且满足全部条件的整数是 200 。
输入：digits = [0,0,0]
输出：[]
解释：
构造的所有整数都会有 前导零 。因此，不存在满足题目条件的整数。
解题思路
题意稍微解释下, 给你个数组, 找出所有不重复, 3位(不含前导0), 偶数
其实这道题有个很巧妙的解法, 我们只需要遍历100 ~ 998中所有偶数, 找到不重复且每一位都在数组中元素即可
- 遍历数组
digits, 找到每个元素出现个数 - 遍历
100 ~ 998中所有偶数, 每一位元素个数都小于出现次数的3位数
例如: [2,1,3,0]
- 每一位出现次数用数组表示[1, 1, 1, 1, 0, 0, 0, 0, 0, 0], 也可用字典表示 {0:1, 1:1 ... 8:0, 9:0}
- 遍历
100 ~ 998中所有偶数, 例如 100, 2个0不满足, 102满足....
代码
未翻译版
class Solution {
func findEvenNumbers(_ digits: [Int]) -> [Int] {
var arr = Array(repeating: 0, count: 10), res = [Int](), i = 100
for i in digits { arr[i] += 1 }
while i < 999 {
var temp = arr, now = i
for j in 0..<3 {
let y = now % 10
now /= 10
if temp[y] == 0 { break }
if j == 2 { res.append(i) }
temp[y] -= 1
}
i += 2
}
return res;
}
}
翻译版
class Solution {
func findEvenNumbers(_ digits: [Int]) -> [Int] {
// 定义 arr 为计数数组, 当然这里也可用字典计数
// res为结果, 遍历参数i
var arr = Array(repeating: 0, count: 10), res = [Int](), i = 100
// 遍历 digits 得到每一位出现次数,
for i in digits { arr[i] += 1 }
// 循环 100 ~ 998 中的数
while i < 999 {
// 定义temp = arr now为当前元素
var temp = arr, now = i
// 做3次取余数, 其实目的就是找到每一位元素
for j in 0..<3 {
// 取余, 当前元素除10
let y = now % 10
now /= 10
// 如果出现次数不满足break弹出
if temp[y] == 0 { break }
// 3位都满足, 则添加
if j == 2 { res.append(i) }
// 对应出现次数 - 1
temp[y] -= 1
}
// 确保是偶数 i = i + 2
i += 2
}
// 返回结果
return res;
}
}
题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址
网友评论