【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 是最小和。
1
2
3

示例 2：

输入：num = 687
输出：75
解释：我们可以将 687 分割成 num1 = 68 和 num2 = 7 ，和为最优值 75 。
1
2
3

提示：

• 10 <= num <= 10^9

个人题解

思路：

1. 将整数拆分成数组

2. 对数组排序，逆序逐个将数字放入sum中进行求和计算，求和时逐位进位处理

    public static int splitNum(int num) {
        int[] arrTemp = new int[10];
        int i = 0;
        while (num > 9) {
            arrTemp[i++] = num % 10;
            num /= 10;
        }
        arrTemp[i++] = num;
        int[] arr = new int[i];
        System.arraycopy(arrTemp, 0, arr, 0, i);
        Arrays.sort(arr);

        int sum = 0;
        int mul = 1;
        for (int j = arr.length - 1, index = 1; j > -1; j--, index++) {
            sum = sum + arr[j] * mul;
            if (index % 2 == 0) {
                mul *= 10;
            }
        }

        return sum;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

官方题解

class Solution {
    public int splitNum(int num) {
        char[] stnum = Integer.toString(num).toCharArray();
        Arrays.sort(stnum);
        int num1 = 0, num2 = 0;
        for (int i = 0; i < stnum.length; ++i) {
            if (i % 2 == 0) {
                num1 = num1 * 10 + (stnum[i] - '0');
            } else {
                num2 = num2 * 10 + (stnum[i] - '0');
            }
        }
        return num1 + num2;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/split-with-minimum-sum/solutions/2470641/zui-xiao-he-fen-ge-by-leetcode-solution-6fde/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20