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;i<nums.size();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;i<nums.size();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;i<s.size();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;i<s.size();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;i<s.size();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)