题目描述
思路解析动画文字版
记牢这一句:数位排好序后,最小的两个进十位、最大的两个进个位。因为十位要乘 10,让小数字去扛这个大权重,总和才压得最低。下面先把四个数位取出来。
先把舞台摆好。上面这排四个格子,准备装 num 的四个数位,现在都是空的,写着一个点。取数位的办法很直接:反复对 num 取一次除以 10 的余数,就得到当前的个位;再把 num 整除 10,把这一位抹掉。就这样一位一位往外抠,直到 num 变成 0。
第一次取:2932 对 10 取余,得到个位 2,填进第 1 格。
取完这一位,把 num 整除 10,2932 变成 293,个位那个 2 被抹掉了。第 1 格已经装好数字 2。
第二次取:293 对 10 取余,得到个位 3,填进第 2 格。
num 再整除 10,293 变成 29。第 2 格装好数字 3。到这儿取出了两位。
第三次取:29 对 10 取余,得到个位 9,填进第 3 格。
num 整除 10,29 变成 2。第 3 格装好数字 9。还剩最后一位。
第四次取:2 对 10 取余,得到个位 2,填进第 4 格。
num 整除 10,2 变成 0。第 4 格装好数字 2。num 归零,四个数位全取出来了,数组是 2、3、9、2。
四个数位都拿到了,现在是 2、3、9、2,还乱着。参考代码这一步直接调库函数排序,咱们用直观的选择排序演示:每一轮从没排好的部分里挑出最小的一个,换到最前面,结果和库排序完全一样,都是从小到大排好。
第 1 轮,在还没排好的这几格里找最小。拿第 2 格的 3 和当前最小 2 比,3 不比 2 小,最小候选不动。
第 1 轮,在还没排好的这几格里找最小。拿第 3 格的 9 和当前最小 2 比,9 不比 2 小,最小候选不动。
第 1 轮,在还没排好的这几格里找最小。拿第 4 格的 2 和当前最小 2 比,两个一样大,保留先出现的那个当最小。
本轮最小是 2,它已经在第 1 格,不用换,第 1 格就此排定。现在数组是 2、3、9、2。
第 2 轮,在还没排好的这几格里找最小。拿第 3 格的 9 和当前最小 3 比,9 不比 3 小,最小候选不动。
第 2 轮,在还没排好的这几格里找最小。拿第 4 格的 2 和当前最小 3 比,2 更小,最小候选换成第 4 格。
本轮最小是 2,把它和第 2 格的 3 交换,第 2 格就此排定。现在数组是 2、2、9、3。
第 3 轮,在还没排好的这几格里找最小。拿第 4 格的 3 和当前最小 9 比,3 更小,最小候选换成第 4 格。
本轮最小是 3,把它和第 3 格的 9 交换,第 3 格就此排定。现在数组是 2、2、3、9。
最后一格自然就是剩下的那个,排序完成。四个数位从小到大是 2、2、3、9。左边两个是最小的一对,右边两个是最大的一对,接下来就靠这个顺序来拼数。
排好的数组是 2、2、3、9。按套路分两组:左边两个 2 和 2 是要进十位的最小对,把它们标绿;右边 3 和 9 是要进个位的最大对,标蓝。下面把它们各就各位,拼出 new1 和 new2。
先摆十位。把最小的 2 放到 new1 的十位。十位要乘 10,所以这里放的是最小数字,先亏得最少。
第二小的 2 放到 new2 的十位。两个十位都用上了最小的一对数字,乘 10 之后的这份和最小,是 4 乘 10。
再摆个位。把 3 放到 new1 的个位,new1 拼成了 23。个位只乘 1,权重小,大数字放这里代价最低。
最大的 9 放到 new2 的个位,new2 拼成了 29。四个数位全部就位:new1 是 23,new2 是 29。
把两个数加起来:23 加 29 等于 52。也可以直接套公式:10 乘最小两位之和 4,再加最大两位之和 12,等于 52。这就是最小和,和开头说的 52 对上了。
边界:1000 的三个 0 当前导得 1;9999 全是 9 得 198;4009 两个 0 进十位不计,得 13。
面试重点:贪心让小数位进十位、公式 10 乘(最小对) 加(最大对)、非零百位一定更差,故按两个两位槽来算即可。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass 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]复杂度
- 时间：O(1)，num 恒为四位数,取数位固定循环 4 次,排序也只对 4 个元素排,拼数是常数次加乘。整段和输入规模无关,是固定的常数工作量,记 O(1)。若推广到 k 位,则排序主导为 O(k log k)
- 空间：O(1)，只用一个长度固定为 4 的数位容器,外加几个临时变量。不随任何规模增长,是常数空间 O(1)
易错点
面试追问把动画讲成自己的话
追问这题核心思路一句话怎么说?
追问怎么证明这样拼一定最优?
追问为什么可以只按两个两位数来算, 不用管三位数加一位数?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
跳跃游戏 II
LeetCode 45 · 中等 · 沿着 贪心套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题