526互联

[LeetCode] 2578. Split With Minimum Sum

发布时间 2023-10-09 14:23:57作者: CNoodle

Given a positive integer num, split it into two non-negative integers num1 and num2 such that:

  • The concatenation of num1 and num2 is a permutation of num.
    • In other words, the sum of the number of occurrences of each digit in num1 and num2 is equal to the number of occurrences of that digit in num.
  • num1 and num2 can contain leading zeros.

Return the minimum possible sum of num1 and num2.

Notes:

  • It is guaranteed that num does not contain any leading zeros.
  • The order of occurrence of the digits in num1 and num2 may differ from the order of occurrence of num.

Example 1:

Input: num = 4325
Output: 59
Explanation: We can split 4325 so that num1 is 24 and num2 is 35, giving a sum of 59. We can prove that 59 is indeed the minimal possible sum.

Example 2:

Input: num = 687
Output: 75
Explanation: We can split 687 so that num1 is 68 and num2 is 7, which would give an optimal sum of 75.

Constraints:

  • 10 <= num <= 109

最小和分割。

给你一个正整数 num ，请你将它分割成两个非负整数 num1 和 num2 ，满足：

  • num1 和 num2 直接连起来，得到 num 各数位的一个排列。
    • 换句话说，num1 和 num2 中所有数字出现的次数之和等于 num 中所有数字出现的次数。
  • num1 和 num2 可以包含前导 0 。

请你返回 num1 和 num2 可以得到的和的 最小 值。

注意：

num 保证没有前导 0 。

num1 和 num2 中数位顺序可以与 num 中数位顺序不同。

思路是贪心。具体做法是把 num 先转换成一个 charArray，对其排序，然后遍历这个 charArray，将遍历到的每个 digit 分配到 num1 和 num2 中，以这种方式最后拼接出来的 num1 和 num2 才是最小的。

时间O(nlogn)

空间O(n)

Java实现

 1 class Solution {
 2     public int splitNum(int num) {
 3         char[] nums = String.valueOf(num).toCharArray();
 4         Arrays.sort(nums);
 5         int n = nums.length;
 6         int num1 = 0;
 7         int num2 = 0;
 8         boolean flag = true;
 9         for (int i = 0; i < n; i++) {
10             char cur = nums[i];
11             if (flag) {
12                 num1 = num1 * 10 + cur - '0';
13             } else {
14                 num2 = num2 * 10 + cur - '0';
15             }
16             flag = !flag;
17         }
18         return num1 + num2;
19     }
20 }

 

LeetCode 题目总结