题目描述:
给你一个正整数 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; } };