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.
Example 4:
Input: digits = [0,2,0,0] Output: [200] Explanation: The only valid integer that can be formed with three digits and no leading zeros is 200.
Example 5:
Input: digits = [0,0,0] Output: [] Explanation: All the integers that can be formed have leading zeros. Thus, there are no valid integers.
Constraints:
3 <= digits.length <= 100
0 <= digits[i] <= 9
Solution: Enumerate all three digits even numbers
Check 100, 102, … 998. Use a hashtable to check whether all digits are covered by the given digits.
Time complexity: O(1000*lg(1000))
Space complexity: O(10)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua class Solution { public: vector<int> findEvenNumbers(vector<int>& digits) { vector<int> counts(10); for (int d : digits) ++counts[d]; vector<int> ans; for (int x = 100; x < 1000; x += 2) { bool valid = true; vector<int> c(10); for (int t = x; t > 0; t /= 10) valid &= (++c[t % 10] <= counts[t % 10]); if (valid) ans.push_back(x); } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment