LeetCode 2578. 最小和分割：贪心（数学）

【LetMeFly】2578.最小和分割：贪心（数学）

力扣题目链接：https://leetcode.cn/problems/split-with-minimum-sum/

给你一个正整数 num ，请你将它分割成两个非负整数 num1 和 num2 ，满足：

• num1 和 num2 直接连起来，得到 num 各数位的一个排列。

  
  	
  换句话说，num1 和 num2 中所有数字出现的次数之和等于 num 中所有数字出现的次数。
  
  

• num1 和 num2 可以包含前导 0 。
• 1
• 2
• 3
• 4
• 5

请你返回 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

方法一：贪心（数学）

先说结论：将给定数字转为字符串后将其中字符从小到大排序，然后依次分配给两个新数字即可。

不严谨的原理描述：

• 越高位数字尽量越小，因此要从小到大排序
• 最终返回的是两数之和，所以首先位数越小越好，因此尽可能两个数字长度相等
• 若两个数长度不相等，更长的那个数字的最高位要尽可能小（例如将23456分成246和35，唯一的百位是最小的2）

结论中描述的分法恰好满足。

• 时间复杂度$O(k\log k)$，其中$k=\log num$
• 空间复杂度$O(\log k)$

AC代码

C++

class Solution {
public:
    int splitNum(int num) {
        string s = to_string(num);
        sort(s.begin(), s.end());
        string n1, n2;
        for (int i = 0; i < s.size(); i++) {
            (i % 2 ? n2 : n1) += s[i];
        }
        // cout << "n1: " << n1 << ", n2: " << n2 << endl;  //**********
        return atoi(n1.c_str()) + atoi(n2.c_str());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

Python

class Solution:
    def splitNum(self, num: int) -> int:
        s = sorted(str(num))
        n = ['', '']
        for i in range(len(s)):
            n[i % 2] += s[i]
        return int(n[0]) + int(n[1])
1
2
3
4
5
6
7

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/133694187