力扣2578. 最小和分割

简介: 力扣2578. 最小和分割

题目描述:

给你一个正整数 num ,请你将它分割成两个非负整数 num1num2 ,满足:

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

请你返回 num1num2 可以得到的和的 最小 值。

注意:

  • num 保证没有前导 0 。
  • num1num2 中数位顺序可以与 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;
    }
};


相关文章
|
6月前
|
算法 测试技术 C#
区间合并|LeetCode2963:统计好分割方案的数目
区间合并|LeetCode2963:统计好分割方案的数目
|
6月前
|
Go
golang力扣leetcode 416.分割等和子集
golang力扣leetcode 416.分割等和子集
44 0
|
6月前
|
Go
golang力扣leetcode 132.分割回文串II
golang力扣leetcode 132.分割回文串II
52 0
|
3月前
|
Python
【Leetcode刷题Python】416. 分割等和子集
LeetCode 416题 "分割等和子集" 的Python解决方案,使用动态规划算法判断是否可以将数组分割成两个元素和相等的子集。
29 1
|
3月前
|
Python
【Leetcode刷题Python】131. 分割回文串
LeetCode题目131的Python编程解决方案,题目要求将给定字符串分割成所有可能的子串,且每个子串都是回文串,并返回所有可能的分割方案。
21 2
|
5月前
|
存储 算法 数据可视化
LeetCode 132题详解:使用动态规划与中心扩展法解决分割回文串 II 的最少分割次数问题
LeetCode 132题详解:使用动态规划与中心扩展法解决分割回文串 II 的最少分割次数问题
|
5月前
|
存储 算法 数据可视化
LeetCode 131题详解:高效分割回文串的递归与动态规划方法
LeetCode 131题详解:高效分割回文串的递归与动态规划方法
|
5月前
dp表,哈希表,力扣5.最长回文子串力扣1745.分割回文串IV力扣132.分割回文串II优先级队列(堆)是什么下面是手动实现小根堆力扣1046.最后一块石头的重量
dp表,哈希表,力扣5.最长回文子串力扣1745.分割回文串IV力扣132.分割回文串II优先级队列(堆)是什么下面是手动实现小根堆力扣1046.最后一块石头的重量
|
6月前
|
Java
leetcode-131:分割回文串
leetcode-131:分割回文串
42 1
|
算法
代码随想录算法训练营第四十一天 | LeetCode 416. 分割等和子集
代码随想录算法训练营第四十一天 | LeetCode 416. 分割等和子集
46 1
代码随想录算法训练营第四十一天 | LeetCode 416. 分割等和子集