leetCode 2578. 最小和分割 + 排序 + 贪心 + 奇偶分组（构造最优解）

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) {
        vector<int> nums;
        while(num){
            nums.push_back(num%10);
            num = num / 10;
        }
        sort(nums.begin(),nums.end());
        int num1=0,num2=0;
        for(int i=0;isize();i++) {
            if(i%2==0) num1 = num1 * 10 + nums[i];
            else num2 = num2 * 10 + nums[i];
        }
        return num1 + num2;
    }
};

这段文字来自这篇博客：位运算&1，」」1，「「1

n&1 就是判断 n 是否为奇数.

• n 为奇数时，对应的二进制数最低位一定为1，n&1的结果就是1。
• n为偶数时，相应的最低位为0，n&1的结果就是0。
• n&1 ==1 或者写 n%2 == 1 或者写 n%2

可以将i%2 == 1 写成 i&1

class Solution {
public:
    int splitNum(int num) {
        vector<int> nums;
        while(num){
            nums.push_back(num%10);
            num = num / 10;
        }
        sort(nums.begin(),nums.end());
        int num1=0,num2=0;
        for(int i=0;isize();i++) {
            if(i&1) 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 i=0;isize();i++) {
            // if(i&1) s2 += s[i];
            // else s1 += s[i];
            i&1?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 num1=0,num2=0;
        for(int i=0;isize();i++) {
            // if(i&1==1) num2 = num2 * 10 + s[i]-'0';
            // else num1 = num1 * 10 + s[i]-'0';
            i&1? 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 i=0;isize();i++) {
            // a[i % 2] = a[i % 2] * 10 + s[i] - '0'; 
            a[i&1] = a[i&1] * 10 + s[i]-'0';
        }
        return a[0] + a[1];
    }
};

• 时间复杂度：O(mlog⁡m)，其中 m 为 num 转成字符串后的长度。
• 空间复杂度：O(m)