LeetCode 题解工作台
拆分数位后四位数字的最小和
给你一个四位 正 整数 num 。请你使用 num 中的 数位 ，将 num 拆成两个新的整数 new1 和 new2 。 new1 和 new2 中可以有 前导 0 ，且 num 中 所有 数位都必须使用。 比方说，给你 num = 2932 ，你拥有的数位包括：两个 2 ，一个 9 和一个 3 …
3
题型
7
代码语言
3
相关题
当前训练重点
简单 · 贪心·invariant
答案摘要
class Solution: def minimumSum(self, num: int) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个四位 正 整数 num 。请你使用 num 中的 数位 ，将 num 拆成两个新的整数 new1 和 new2 。new1 和 new2 中可以有 前导 0 ，且 num 中 所有 数位都必须使用。
- 比方说，给你
num = 2932，你拥有的数位包括：两个2，一个9和一个3。一些可能的[new1, new2]数对为[22, 93]，[23, 92]，[223, 9]和[2, 329]。
请你返回可以得到的 new1 和 new2 的 最小 和。
示例 1：
输入：num = 2932 输出：52 解释：可行的 [new1, new2] 数对为 [29, 23] ，[223, 9] 等等。 最小和为数对 [29, 23] 的和：29 + 23 = 52 。
示例 2：
输入：num = 4009 输出：13 解释：可行的 [new1, new2] 数对为 [0, 49] ，[490, 0] 等等。 最小和为数对 [4, 9] 的和：4 + 9 = 13 。
提示：
1000 <= num <= 9999
解题思路
方法一
class Solution:
def minimumSum(self, num: int) -> int:
nums = []
while num:
nums.append(num % 10)
num //= 10
nums.sort()
return 10 * (nums[0] + nums[1]) + nums[2] + nums[3]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for a clear understanding of greedy strategies in number optimization.
- question_mark
Candidates should demonstrate the ability to use sorting effectively in algorithm design.
- question_mark
The approach should validate that splitting digits and minimizing sums is optimal.
常见陷阱
外企场景- error
Failing to account for leading zeros when forming the two numbers.
- error
Not correctly sorting the digits before pairing them.
- error
Incorrectly assuming that any random splitting of digits will give the smallest sum.
进阶变体
外企场景- arrow_right_alt
Handling different ranges of numbers, such as working with more or fewer digits.
- arrow_right_alt
Exploring the same problem with a constraint on no leading zeros.
- arrow_right_alt
Adjusting the problem to consider non-greedy approaches or more complex number splits.