Given an integer array of digits, return the largest multiple of three that can be formed by concatenating some of the given digits in any order.
Since the answer may not fit in an integer data type, return the answer as a string.
If there is no answer return an empty string.
Example 1:
Input: digits = [8,1,9] Output: "981"
Example 2:
Input: digits = [8,6,7,1,0] Output: "8760"
Example 3:
Input: digits = [1] Output: ""
Example 4:
Input: digits = [0,0,0,0,0,0] Output: "0"
Constraints:
1 <= digits.length <= 10^40 <= digits[i] <= 9- The returning answer must not contain unnecessary leading zeros.
Solution: Greedy + Math + Counting sort
Count the numbers of each digit.
if sum % 3 == 0, we can use all digits.
if sum % 1 == 0, we can remove one digits among {1, 4, 7} => sum % 3 == 0
if sum % 2 == 0, we can remove one digits among {2, 5, 8} => sum % 3 == 0
if sum % 2 == 0, we have to remove two digits among {1, 4, 7} => sum % 3 == 0
if sum % 1 == 0, we have to remove two digits among {2, 5, 8} => sum % 3 == 0
Time complexity: O(n)
Space complexity: O(n) w/ output, O(1) w/o output
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
// Author: Huahua class Solution { public: string largestMultipleOfThree(vector<int>& digits) { vector<int> c(10); for (int d : digits) ++c[d]; auto getNum = [&](const vector<int>& ds) { for (int d : ds) --c[d]; string ans; for (int d = 9; d >= 1; --d) ans.append(c[d], '0' + d); ans.append(ans.empty() ? min(1, c[0]) : c[0], '0'); return ans; }; const int r = accumulate(begin(digits), end(digits), 0) % 3; vector<vector<int>> rs{{0, 3, 6, 9}, {1, 4, 7}, {2, 5, 8}}; // Use all digitis. if (r == 0) return getNum({}); // Remove one among {1, 4, 7}, {2, 5, 8} for (int d : rs[r]) if (c[d]) return getNum({d}); // Remove two among {1, 4, 7}^2 (r = 2), {2, 5, 8}^2 (r = 1) for (int d1 : rs[3 - r]) for (int d2 : rs[3 - r]) if (d1 == d2 && c[d1] > 1 || d1 != d2 && c[d1] && c[d2]) return getNum({d1, d2}); return ""; } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
# Author: Huahua class Solution: def largestMultipleOfThree(self, digits: List[int]) -> str: c = collections.Counter(digits) def getNum(ds): ans = [] for d in ds: c[d] -= 1 for d in range(9, 0, -1): ans += [d] * c[d] ans += [0] * min(1 if not ans else c[0], c[0]) return ''.join(map(str, ans)) rs = [[0, 3, 6, 9], [1, 4, 7], [2, 5, 8]] r = sum(digits) % 3 if r == 0: return getNum([]) for d in rs[r]: if c[d] > 0: return getNum([d]) for d1, d2 in zip(rs[3 - r], rs[3 - r]): if d1 == d2 and c[d1] >= 2 or d1 != d2 and c[d1] and c[d2]: return getNum([d1, d2]) return "" |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment