力扣2578. 最小和分割

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

题目描述：

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

• num1 和 num2 直接连起来，得到 num 各数位的一个排列。
  • 换句话说，num1 和 num2 中所有数字出现的次数之和等于 num 中所有数字出现的次数。
• num1 和 num2 可以包含前导 0 。

请你返回 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 <= 10^9

思路：

这个题很简单，就是把num里面的所有位数全部取出来，然后分给两个数，看怎么组合两个数的和最小。首先，这两个数num1和num2的位数一定相差不能超过1，比如说，如果num是一个四位数，那么num1和num2一定是两个两位数相加，否则就是一个三位数加一个一位数，不利于得到最小和。

而且，要想num1+num2最小，这两个数的各个位数的排序一定是小的在前面。

比如说num=1324,那么1和2是最小的两个数，把他们分别反在num1,num2高位，在安排3、4。

注意这里由于两数相加是相应位数相加，所以对于同一位而言，1+2和2+1没有区别，也就是说13+24与14+23没有区别。

这样一来，直接将num的各个位数从小到大依次安排在num1和num2的高位就OK。

代码：

class Solution {
public:int splitNum(int num) {vector<int> arr;int a=0;int b=0;while(num){int k=num%10;arr.push_back(k);num/=10;}sort(arr.begin(),arr.end());for(int i=0;i<arr.size();i++){if(i%2==0){a=a*10+arr[i];}else{b=b*10+arr[i];}}return a+b;}
};

这篇关于力扣2578. 最小和分割的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---