【力扣】2578. 最小和分割

【力扣】2578. 最小和分割

1. 题目介绍

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

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

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

• num1 和 num2 可以包含前导 0 。
• 请你返回 num1 和 num2 可以得到的和的 最小值。

注意：

• num 保证没有前导 0 。
• num1 和 num2 中数位顺序可以与 num 中数位顺序不同。

示例：

2. 思路

• 1）对数字数位分割，得到 list 后排序，两个数字分别：

  • 你一位，我一位的拿。
  • 有0的话，固定放在第二位

• 2）当我们将给定的 num 分成 num1 和 num2 时，num1 中的数字应该是单调递增的。否则，例如 nums1=1243，我们将 4 和 3 交换可以得到更小的值。同理，nums2 中的数字也应该是单调递增的。

  • 接下来我们考虑 num1 和 num2 之间的情况。设 num1 中有一个数字 xxx 是从低到高的第 p (p≥0) 位，表示 x×10p，num2 中有一个数字 y 是从低到高的低 q 位，表示 y×10q。我们交换 x 和 y，不应该得到更小的值，因此有：
    x×10p+y×10q≤x×10q+y×10p，即：(x−y)×(10p−10q)≤0，也就是说：如果 x 的位数更高（即 10p≥10q ，那么 x 必须不能大于 y）；如果 y 的位数更高，那么 y 必须不能大于 x。
  • 结合之前得出的 num1 和 num2 分别是单调递增的，这就告诉我们：
    任何一个数字，都不能大于任何一个数中比它位数更小的数字。
  • 当 num1 和 num2 位数不相等时，我们需要补上前导零使得它们位数相等。例如，1234 和 5 是满足上述要求的，但 234 和 15 的和显然更小，这是因为我们需要把 5 看成 0005，那么 1234 中的 1 与 0[00]55 中括号部分的两个 0 是不满足要求的。这也就告诉我们，num1 和 num2 的位数差不能超过 1，否则位数少的那个数能补上至少 2 个前导零，其中不是最高位的那些前导零和位数多的那个数的最高位是不满足要求的。

因此，我们就可以得出最小和的分割方法：

• 将 num 的数字进行递增排序；
• 按照递增顺序，交替地将数字分配给 num1 和 num2

3. 解题代码

class Solution:
    def splitNum(self, num: int) -> int:
        stnum = "".join(sorted(str(num)))
        num1, num2 = int(stnum[::2]), int(stnum[1::2])
        return num1 + num2
1
2
3
4
5

4. 疑问？

貌似没有对前导0进行限制，比如现在的答案是：

• 1024 分成：02 和14就行

5. Danger

力扣（LeetCode）是领扣网络旗下专注于程序员技术成长和企业技术人才服务的品牌。源自美国硅谷，力扣为全球程序员提供了专业的IT技术职业化提升平台，有效帮助程序员实现快速进步和长期成长。此外，力扣（LeetCode）致力于解决程序员技术评估、培训、职业匹配的痛点，逐步引领互联网技术求职和招聘迈向专业化。

• 据了解到的情况，Easy题和Medium 题在面试中比较常见，通常会以手写代码之类的形式出现，您需要对问题进行分析并给出解答，并于面试官进行交流沟通，有时还会被要求分析时间复杂度8与空间复杂度°，面试官会通过您对题目的分析解答，了解您对常用算法的熟悉程度和您的程序实现功底。
• 而在一些对算法和程序实现功底要求较高的岗位，Hard 题也是很受到面试官的青睐，如果您在面试中成功Bug-Free出一道Hard题，我们相信您一定会给面试官留下很深刻的印象，并极大增加拿到Offer的概率，据相关人士统计，如果您在面试成功解出一道Hard题，拿不到Offer的概率无限接近于0。
• 所以,力扣中Easy和Medium相当于面试中的常规题，而Hard 则相当于面试中较难的题，解出—道Hard题，Offer可以说是囊中之物。

参考

【1】https://leetcode.cn/problems/split-with-minimum-sum/?envType=daily-question&envId=2023-10-09