题目描述
思路解析
一句话答案：LeetCode 2160 拆分数位后四位数的最小和：四个数位从小到大排序，两个最小的进十位、两个最大的进个位，凑成 10×(d0+d1)+d2+d3——十位乘 10 让小数位去扛，时间 O(1)。
四位数拆成两个数，怎么让它们的和最小
给一个四位正整数 num，把它的四个数位全拆开，重新拼成两个整数 new1 和 new2，每个数位都得用上，拼出来的新数允许带前导 0。求 new1 加 new2 的最小和。题面例子 num=2932，数位是 2、9、3、2，拼成 [29,23] 时和是 52；再看 num=4009，拼成 [4,9]、另两个 0 当前导，和是 13。num 恒在 1000 到 9999 之间，四个数位一个都跑不掉。
拆法一大堆，挨个枚举划不划算
四个数位能凑出的拼法不少：两个两位数、一个三位数配一位数，还得纠结哪个数位配哪个数位，全列出来再逐种求和取最小，写起来又绕又容易漏掉某种。但位权里藏着一条规律，能把这堆枚举整个省掉。
为什么最小的数位该放十位
两个两位数，每个都有一个十位和一个个位。十位上的数字要乘 10，个位只乘 1；而四个数位之和是固定的，不管怎么拼都改不了。把和拆开看，总和 = 10×(两个十位之和) + (两个个位之和)。要让总和小，就得让乘 10 的那两个位置放尽量小的数字。所以把四个数位从小到大排好，最小的两个进十位、最大的两个进个位——让权重最大的位置承担最小的代价。
公式怎么落地，前导 0 要不要特判
排序后把四个数位记成 d0≤d1≤d2≤d3。答案直接写成 10×(d0+d1)+d2+d3：d0、d1 是两个十位，d2、d3 是两个个位。至于 d0、d1 谁分给 new1、谁分给 new2，个位那两个怎么互换，和都是同一个，不用挑。数位里若有 0，题目明说允许前导 0，把 0 放十位相当于那个新数少一位、不产生任何值，完全合法，不用任何特判——4009 就是两个 0 进十位、剩下 4 和 9 进个位，和是 13。
num=2932 拆开排序再拼，和是多少
先把数位抠出来：反复对 10 取余拿个位、再整除 10 抹掉。2932 取出 2，剩 293；取出 3，剩 29；取出 9，剩 2；取出 2，剩 0。四个数位是 2、3、9、2。排序后是 2、2、3、9。d0、d1 是 2 和 2，进十位；d2、d3 是 3 和 9，进个位。套公式：10×(2+2)+(3+9)=40+12，得 52。
公式写成 10 乘总和，答案就偏大
把公式误写成 10 乘四个数位的总和，就把个位那两个也当十位算了，结果会偏大——10 只乘最小的两位，后两位加一次就够。想去枚举『哪个小数位配哪个大数位』纯属白费力气，配法根本不影响那两份和。还有人怕数位里的 0 放十位不合法特意绕开，反倒算错，前导 0 是题目放行的，照排序加公式跑即可。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这一句:数位排好序后,最小的两个进十位、最大的两个进个位。因为十位要乘 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题