Hard
题目描述
给定一个数字数组 digits，返回通过连接部分给定数字（以任何顺序）可以构成的最大3的倍数。如果无法构成，则返回空字符串。
由于答案可能不适合整数数据类型，请将答案作为字符串返回。注意返回的答案不能包含不必要的前导零。
示例 1：
输入：digits = [8,1,9]
输出："981"
示例 2：
输入：digits = [8,6,7,1,0]
输出："8760"
示例 3：
输入：digits = [1]
输出：""
约束条件：
1 <= digits.length <= 10^40 <= digits[i] <= 9
提示：
- 一个数是3的倍数当且仅当其各位数字之和是3的倍数
- 使用动态规划
- 为了找到最大数，尝试最大化数字的位数
- 将数字按降序排序以找到最大数
解题思路
这道题的核心思路基于数论知识：一个数是3的倍数当且仅当其各位数字之和是3的倍数。
解题思路：
贪心策略：为了构成最大的数，我们要尽可能多地使用数字，并且按降序排列。
数学分析：设所有数字之和为
sum，根据sum % 3的值分情况讨论：- 如果
sum % 3 == 0，可以使用所有数字 - 如果
sum % 3 == 1，需要移除一个余数为1的最小数字，或移除两个余数为2的最小数字 - 如果
sum % 3 == 2，需要移除一个余数为2的最小数字，或移除两个余数为1的最小数字
- 如果
实现步骤：
- 统计每个数字的出现次数
- 计算所有数字的总和
- 根据总和模3的结果，确定需要移除哪些数字
- 按照移除策略更新数字计数
- 按降序构建最终结果
特殊情况处理：
- 如果结果全为0，返回"0"而不是"000…"
- 如果无法构成任何数，返回空字符串
时间复杂度分析： O(n)，其中n是数组长度 空间复杂度分析： O(1)，只使用常数空间存储计数信息
代码实现
class Solution {
public:
string largestMultipleOfThree(vector<int>& digits) {
vector<int> count(10, 0);
int sum = 0;
// 统计数字出现次数和总和
for (int digit : digits) {
count[digit]++;
sum += digit;
}
// 根据sum % 3的值决定移除策略
if (sum % 3 == 1) {
// 优先移除一个余数为1的最小数字
if (count[1] > 0) count[1]--;
else if (count[4] > 0) count[4]--;
else if (count[7] > 0) count[7]--;
// 否则移除两个余数为2的最小数字
else {
int removed = 0;
for (int i = 2; i <= 8 && removed < 2; i += 3) {
while (count[i] > 0 && removed < 2) {
count[i]--;
removed++;
}
}
}
} else if (sum % 3 == 2) {
// 优先移除一个余数为2的最小数字
if (count[2] > 0) count[2]--;
else if (count[5] > 0) count[5]--;
else if (count[8] > 0) count[8]--;
// 否则移除两个余数为1的最小数字
else {
int removed = 0;
for (int i = 1; i <= 7 && removed < 2; i += 3) {
while (count[i] > 0 && removed < 2) {
count[i]--;
removed++;
}
}
}
}
// 构建结果字符串（从大到小）
string result = "";
for (int i = 9; i >= 0; i--) {
result += string(count[i], '0' + i);
}
// 处理前导零
if (result.empty() || result[0] == '0') {
return result.empty() ? "" : "0";
}
return result;
}
};
class Solution:
def largestMultipleOfThree(self, digits: List[int]) -> str:
count = [0] * 10
total = 0
# 统计数字出现次数和总和
for digit in digits:
count[digit] += 1
total += digit
# 根据total % 3的值决定移除策略
if total % 3 == 1:
# 优先移除一个余数为1的最小数字
if count[1] > 0:
count[1] -= 1
elif count[4] > 0:
count[4] -= 1
elif count[7] > 0:
count[7] -= 1
# 否则移除两个余数为2的最小数字
else:
removed = 0
for i in range(2, 9, 3):
while count[i] > 0 and removed < 2:
count[i] -= 1
removed += 1
elif total % 3 == 2:
# 优先移除一个余数为2的最小数字
if count[2] > 0:
count[2] -= 1
elif count[5] > 0:
count[5] -= 1
elif count[8] > 0:
count[8] -= 1
# 否则移除两个余数为1的最小数字
else:
removed = 0
for i in range(1, 8, 3):
while count[i] > 0 and removed < 2:
count[i] -= 1
removed += 1
# 构建结果字符串（从大到小）
result = []
for i in range(9, -1, -1):
result.extend([str(i)] * count[i])
result = ''.join(result)
# 处理前导零
if not result or result[0] == '0':
return "0" if result else ""
return result
public class Solution {
public string LargestMultipleOfThree(int[] digits) {
int[] count = new int[10];
int sum = 0;
// 统计数字出现次数和总和
foreach (int digit in digits) {
count[digit]++;
sum += digit;
}
// 根据sum % 3的值决定移除策略
if (sum % 3 == 1) {
// 优先移除一个余数为1的最小数字
if (count[1] > 0) count[1]--;
else if (count[4] > 0) count[4]--;
else if (count[7] > 0) count[7]--;
// 否则移除两个余数为2的最小数字
else {
int removed = 0;
for (int i = 2; i <= 8 && removed < 2; i += 3) {
while (count[i] > 0 && removed < 2) {
count[i]--;
removed++;
}
}
}
} else if (sum % 3 == 2) {
// 优先移除一个余数为2的最小数字
if (count[2] > 0) count[2]--;
else if (count[5] > 0) count[5]--;
else if (count[8] > 0) count[8]--;
// 否则移除两个余数为1的最小数字
else {
int removed = 0;
for (int i = 1; i <= 7 && removed < 2; i += 3) {
while (count[i] > 0 && removed < 2) {
count[i]--;
removed++;
}
}
}
}
// 构建结果字符串（从大到小）
StringBuilder sb = new StringBuilder();
for (int i = 9; i >= 0; i--) {
for (int j = 0; j < count[i]; j++) {
sb.Append(i);
}
}
string result = sb.ToString();
// 处理前导零
if (string.IsNullOrEmpty(result) || result[0] == '0') {
return string.IsNullOrEmpty(result) ? "" : "0";
}
return result;
}
}
var largestMultipleOfThree = function(digits) {
digits.sort((a, b) => b - a);
const sum = digits.reduce((a, b) => a + b, 0);
const remainder = sum % 3;
if (remainder === 0) {
const result = digits.join('');
return result[0] === '0' ? '0' : result;
}
const mod1 = [], mod2 = [];
for (let digit of digits) {
if (digit % 3 === 1) mod1.push(digit);
if (digit % 3 === 2) mod2.push(digit);
}
mod1.sort();
mod2.sort();
let toRemove = [];
if (remainder === 1) {
if (mod1.length > 0) {
toRemove = [mod1[0]];
} else if (mod2.length >= 2) {
toRemove = [mod2[0], mod2[1]];
} else {
return '';
}
} else {
if (mod2.length > 0) {
toRemove = [mod2[0]];
} else if (mod1.length >= 2) {
toRemove = [mod1[0], mod1[1]];
} else {
return '';
}
}
const removeSet = new Map();
for (let num of toRemove) {
removeSet.set(num, (removeSet.get(num) || 0) + 1);
}
const result = [];
for (let digit of digits) {
if (removeSet.has(digit) && removeSet.get(digit) > 0) {
removeSet.set(digit, removeSet.get(digit) - 1);
} else {
result.push(digit);
}
}
if (result.length === 0) return '';
if (result[0] === 0) return '0';
return result.join('');
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | n为数组长度，需要遍历数组统计数字并构建结果 |
| 空间复杂度 | O(1) | 只使用固定大小的计数数组和常数空间 |