LeetCode 题解工作台
最小和分割
给你一个正整数 num ，请你将它分割成两个非负整数 num1 和 num2 ，满足： num1 和 num2 直接连起来，得到 num 各数位的一个排列。 换句话说， num1 和 num2 中所有数字出现的次数之和等于 num 中所有数字出现的次数。 num1 和 num2 可以包含前导 0 。…
3
题型
6
代码语言
3
相关题
当前训练重点
简单 · 贪心·invariant
答案摘要
我们先用哈希表或数组 统计 中各个数字出现的次数，用变量 记录 的位数。 接下来，枚举 所有位数 ，将 中的数字按照从小到大的顺序交替地分配给 和 ，记录在一个长度为 的数组 中。最后，返回 中的两个数之和即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个正整数 num ，请你将它分割成两个非负整数 num1 和 num2 ，满足：
num1和num2直接连起来，得到num各数位的一个排列。- 换句话说，
num1和num2中所有数字出现的次数之和等于num中所有数字出现的次数。
- 换句话说，
num1和num2可以包含前导 0 。
请你返回 num1 和 num2 可以得到的和的 最小 值。
注意：
num保证没有前导 0 。num1和num2中数位顺序可以与num中数位顺序不同。
示例 1：
输入：num = 4325 输出：59 解释：我们可以将 4325 分割成num1= 24 和num2= 35 ，和为 59 ，59 是最小和。
示例 2：
输入：num = 687 输出：75 解释：我们可以将 687 分割成num1= 68 和num2= 7 ，和为最优值 75 。
提示：
10 <= num <= 109
解题思路
方法一：计数 + 贪心
我们先用哈希表或数组 统计 中各个数字出现的次数，用变量 记录 的位数。
接下来，枚举 所有位数 ，将 中的数字按照从小到大的顺序交替地分配给 和 ，记录在一个长度为 的数组 中。最后，返回 中的两个数之和即可。
时间复杂度 ，空间复杂度 。其中 为 的位数；而 为 中不同数字的个数，本题中 。
class Solution:
def splitNum(self, num: int) -> int:
cnt = Counter()
n = 0
while num:
cnt[num % 10] += 1
num //= 10
n += 1
ans = [0] * 2
j = 0
for i in range(n):
while cnt[j] == 0:
j += 1
cnt[j] -= 1
ans[i & 1] = ans[i & 1] * 10 + j
return sum(ans)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate demonstrates understanding of greedy algorithms and sorting techniques.
- question_mark
The candidate shows the ability to break down a problem into manageable subproblems.
- question_mark
The candidate approaches the problem with the correct choice of sorting and distribution strategy.
常见陷阱
外企场景- error
Not sorting the digits of the number, leading to suboptimal splits.
- error
Failing to alternate the digits between `num1` and `num2` effectively.
- error
Overcomplicating the solution by trying to use dynamic programming or other complex methods when sorting and a greedy approach are sufficient.
进阶变体
外企场景- arrow_right_alt
What if the number has repeating digits?
- arrow_right_alt
What if the number is large, near the upper constraint?
- arrow_right_alt
How would you modify the approach to handle smaller numbers with fewer digits?