拆分数位后四位数字的最小和

问题描述(来源于LeetCode)

给定一个四位正整数 num，使用所有数位拆成两个新的整数 new1 和 new2（可以有前导0），返回可以得到的最小和。

解题思路分析

问题本质

这是一个组合优化问题，需要找到将四个数字分成两组的最佳方式，使得两个两位数的和最小。

核心洞察

要使两个两位数的和最小：

将最小的两个数字放在十位
将较大的两个数字放在个位
这样能确保两个数都尽可能小

数学证明

对于四个排序后的数字 a ≤ b ≤ c ≤ d：

最优分配：10a + d 和 10b + c
总和：10(a + b) + (c + d)

代码实现

class Solution:
    def minimumSum(self, num: int) -> int:
        分解四位数字
        a = num % 10           # 个位
        b = (num // 10) % 10   # 十位  
        c = (num // 100) % 10  # 百位
        d = num // 1000        # 千位
            # 排序四个数字
    	digits = [a, b, c, d]
   	    digits.sort()
    
        # 构造最优组合
        num1 = digits[0] * 10 + digits[3]  # 最小和最大组合
        num2 = digits[1] * 10 + digits[2]  # 中间两个组合
    
        return num1 + num2

算法详解

步骤分解

数字分解：提取四位数的每一位
数字排序：将四个数字按升序排列
最优组合：
- 第一个数：最小的数字在十位，最大的数字在个位
- 第二个数：第二小的数字在十位，第三小的数字在个位
计算和：返回两个数的和

为什么这样最优？

假设排序后数字为 a ≤ b ≤ c ≤ d：

十位应该放最小的数字 a 和 b
个位应该放较大的数字 c 和 d
组合方式：10a + d 和 10b + c 的和最小

复杂度分析

时间复杂度：O(1)
- 固定处理4个数字，排序也是常数时间
空间复杂度：O(1)
- 使用固定大小的数组存储数字

示例分析

示例1：num = 2932

分解数字：2, 9, 3, 2
排序后：2, 2, 3, 9
构造数字：

- num1 = 2×10 + 9 = 29
- num2 = 2×10 + 3 = 23
  和：29 + 23 = 52

示例2：num = 4009

分解数字：4, 0, 0, 9  
排序后：0, 0, 4, 9
构造数字：

- num1 = 0×10 + 9 = 9
- num2 = 0×10 + 4 = 4
  和：9 + 4 = 13

测试用例

测试用例	输入num	分解数字	排序后	构造数字	输出和
1	2932	[2,9,3,2]	[2,2,3,9]	29+23	52
2	4009	[4,0,0,9]	[0,0,4,9]	9+4	13
3	1234	[1,2,3,4]	[1,2,3,4]	14+23	37
4	1000	[1,0,0,0]	[0,0,0,1]	1+0	1

边界情况考虑

包含零的情况：正确处理前导零
重复数字：多个相同数字的处理
极值情况：1000, 9999等边界值

算法正确性证明

贪心选择性质

每次选择当前最小的可用数字放在十位，这种局部最优选择能导致全局最优解。

最优子结构

问题的解包含子问题的最优解，四个数字的最优分配包含三个数字的最优分配思想。

扩展思考

实际应用

资源分配优化
负载均衡问题
数据分片策略

总结

这道题目展示了贪心算法在组合优化问题中的应用：

问题分析：理解问题的组合特性
规律发现：找到数字分配的最优模式
算法设计：设计简单有效的贪心策略
正确性验证：确保贪心选择的合理性

解题的关键在于发现"小数字放在高位"这一核心洞察，体现了通过观察发现规律的重要解题技巧。