电影网站建设,广州seo服务,wordpress 多站点建站教程,公司怎么建设官网2578. 最小和分割 - 力扣#xff08;LeetCode#xff09; 给你一个正整数 num #xff0c;请你将它分割成两个非负整数 num1 和 num2 #xff0c;满足#xff1a;
num1 和 num2 直接连起来#xff0c;得到 num 各数位的一个排列。 换句话说#xff0c;num1 和 num2 中所…2578. 最小和分割 - 力扣LeetCode 给你一个正整数 num 请你将它分割成两个非负整数 num1 和 num2 满足
num1 和 num2 直接连起来得到 num 各数位的一个排列。 换句话说num1 和 num2 中所有数字出现的次数之和等于 num 中所有数字出现的次数。num1 和 num2 可以包含前导 0 。
请你返回 num1 和 num2 可以得到的和的 最小 值。
注意
num 保证没有前导 0 。num1 和 num2 中数位顺序可以与 num 中数位顺序不同。 思路分析总结来自https://leetcode.cn/problems/split-with-minimum-sum/
1.满足nums1 和 nums2的位数小于 bit_len(num) / 2 尽可能最短2.依次给nums1 和 nums2 分配较小的数给高位
1用一个 nums数组 来存放num的各个位的数字然后 sort排序再根据思路分析将其转化为num1 和 num2
class Solution {
public:int splitNum(int num) {vectorint nums;while(num){nums.push_back(num%10);num num / 10;}sort(nums.begin(),nums.end());int num10,num20;for(int i0;inums.size();i) {if(i%20) num1 num1 * 10 nums[i];else num2 num2 * 10 nums[i];}return num1 num2;}
};
这段文字来自这篇博客位运算1」」1「「1
n1 就是判断 n 是否为奇数.
n 为奇数时对应的二进制数最低位一定为1n1的结果就是1。n为偶数时相应的最低位为0n1的结果就是0。n1 1 或者写 n%2 1 或者写 n%2
可以将i%2 1 写成 i1
class Solution {
public:int splitNum(int num) {vectorint nums;while(num){nums.push_back(num%10);num num / 10;}sort(nums.begin(),nums.end());int num10,num20;for(int i0;inums.size();i) {if(i1) num2 num2 * 10 nums[i];else num1 num1 * 10 nums[i];}return num1 num2;}
};
(2) 将num先转成字符串接着根据思路分析拼接两个字符串s1和s2最后转成int相加后返回
class Solution {
public:int splitNum(int num) {string s to_string(num);sort(s.begin(),s.end());string s1,s2;for(int i0;is.size();i) {// if(i1) s2 s[i];// else s1 s[i];i1?s2 s[i] : s1 s[i];}return stoi(s1) stoi(s2);}
};
3将num先转成字符串接着根据思路分析获得num1和num2相加后返回
class Solution {
public:int splitNum(int num) {string s to_string(num);sort(s.begin(),s.end());int num10,num20;for(int i0;is.size();i) {// if(i11) num2 num2 * 10 s[i]-0;// else num1 num1 * 10 s[i]-0;i1? num2 num2 * 10 s[i]-0 : num1 num1 * 10 s[i]-0;}return num1 num2;}
};
4将3进行进一步优化省去三目运算
class Solution {
public:int splitNum(int num) {string s to_string(num);sort(s.begin(),s.end());int a[2]{};for(int i0;is.size();i) {// a[i % 2] a[i % 2] * 10 s[i] - 0; a[i1] a[i1] * 10 s[i]-0;}return a[0] a[1];}
};
时间复杂度O(mlogm)其中 m 为 num 转成字符串后的长度。空间复杂度O(m)
