2023.10.9 leetcode-2578 最小分割和

---

题目

• 给你一个正整数 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 <= 109

---

分析

• 既然题目要求我们对数字num进行分割，将num分割成两个可以带有前导0的非零整数，并且仅要求num1，num2包含num内的所有数字，最后num1+num2的值最小。
• 首先考虑单个数字的问题，根据数字组成的规律我们可知，在数字组成相同的情况下，高位向低位数值逐渐递增的数字值最小。故 num1和num2的组成数字，由高位向低位递增。
• 其次考虑两个数字的问题，当num1,num2都符合上述约束，num1、num2位数相同时，num1+num2最小，当num1、num2位数不同时，可用一个前导0不足，此时不改变num1+num2大小。
• 在num1、num2位数不同时，要保证位数大者的最高位值最小，降低高位值的权值。
• 故可得题解
  • 将num的数字进行排序
  • 将排序后的数字交替分配给num1,num2,保证高位值尽可能小

---

代码实现

class Solution {
    //将num分割为两个非负整数，num1，num2
    //num1，num2中出现的数经过重新排列可以组合为num
    //求num1+num2的最小值
    //num没有前导0，num1,num2可以有前导0
    //纯数字处理
     public int splitNum(int num) {
        int num1 = 0;
        int num2 = 0;
        int len = 0;//num长度
        int record[];
        num1 = num;
        while(num1!=0)
        {
            num1/=10;
            ++len;
        }
        record = new int[len];
        for(int i = 0;i<len;++i)
        {
            record[i] = num%10;
            num/=10;
        }
        Arrays.sort(record);
        for(int i = 0;i<len;++i)
        {
            if(i%2==0)
                num1 = num1*10+record[i];
            else{
                num2 = num2*10+record[i];
            }
        }
        return num1+num2;
    }
}

class Solution{
    public int splitNum(int num) {
        //整形数组转字符数组,快速转换
        char arr[] = Integer.toString(num).toCharArray();
        Arrays.sort(arr);
        int num1 = 0,num2 = 0;
        for(int i = 0;i<arr.length;++i)
        {
            if(i%2 == 0)
                num1 = num1*10+arr[i]-'0';
            else
                num2 = num2*10+arr[i]-'0';
        }
        return num1+num2;
    }
}

---