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

本文主要是介绍LeetCode 2578. 最小和分割：贪心（数学），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

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

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

  <ul><li>换句话说，<code>num1</code> 和&nbsp;<code>num2</code>&nbsp;中所有数字出现的次数之和等于&nbsp;<code>num</code>&nbsp;中所有数字出现的次数。</li>
  </ul>
  </li>
  <li><code>num1</code> 和&nbsp;<code>num2</code>&nbsp;可以包含前导 0 。</li>
  

请你返回 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());}
};

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])

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

这篇关于LeetCode 2578. 最小和分割：贪心（数学）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---