最小和分割

难度:

标签:

题目描述

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 <= 10⁹

代码结果

运行时间: 22 ms, 内存: 16.0 MB

/*
 * 思路：
 * 1. 将数字转换成字符数组。
 * 2. 对字符数组进行排序。
 * 3. 将排序后的字符数组中的字符分为两部分，构成num1和num2。
 * 4. 尽量让num1和num2的位数差不多，使其和最小。
 */

import java.util.Arrays;
import java.util.stream.Collectors;

public class Solution {
    public int splitNum(int num) {
        // 将数字转换为字符数组并排序
        String sortedDigits = Arrays.stream(String.valueOf(num).split("")).sorted().collect(Collectors.joining());
        // 用来构建num1和num2的StringBuilder
        StringBuilder num1 = new StringBuilder();
        StringBuilder num2 = new StringBuilder();
        // 交替分配字符给num1和num2
        for (int i = 0; i < sortedDigits.length(); i++) {
            if (i % 2 == 0) {
                num1.append(sortedDigits.charAt(i));
            } else {
                num2.append(sortedDigits.charAt(i));
            }
        }
        // 将StringBuilder转换为整数并求和
        return Integer.parseInt(num1.toString()) + Integer.parseInt(num2.toString());
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.splitNum(4325)); // 输出 59
        System.out.println(sol.splitNum(687));  // 输出 75
    }
}

解释

方法:

这个题解的基本思路是，首先统计数字num中各个数字的出现次数。然后，从1到9遍历这些数字，并根据它们的出现次数，将数字依次分配给两个数num1和num2，始终将数字添加到当前和较小的那个数。通过这种方法，我们试图均衡num1和num2的数值，从而使它们的总和尽可能小。这种贪心策略通过比较两者的当前值来决定将下一个数字添加到哪个数，从而尽量保持两者的平衡。

时间复杂度:

O(1)

空间复杂度:

O(1)

代码细节讲解

🦆

在题解中提到，将数字分配给当前和较小的数字以保持平衡，这种方法是否总是能保证最终和的最小值？如果不是，能否给出一个反例？

▷

这种贪心策略并不总是能保证最终和的最小值。贪心策略是基于当前情况做出最优决策的方法，但它并不总是能得到全局最优解。例如，对于数字1122，按照题解的方法，第一个数字1会分配给num1，第二个1会分配给num2，然后两个2也会按照当前的大小平衡分配。这将导致num1和num2为112和12，和为124。但是最优的分割应该是121和12，和为133。这个例子显示了贪心策略可能无法达到最小和的情况。

🦆

题解中使用了从1到9的遍历顺序，不从0开始是基于什么考虑？如果在某些情况下0的处理不当，是否会影响最终结果？

▷

题解中从1到9的遍历顺序是为了避免在数字的最前面不合适地放置0，因为0放在数字的开头会使数字的数值降低或变为0，影响最终的和。例如，如果0放在num1或num2的开始，可能会导致一个数字本质上没有增加任何值。而将0放置在非首位可以确保0的加入不会影响数字的有效值。如果处理不当，如将0作为首位添加，确实会影响最终的结果，因为这会导致一个数值本身大大降低。

🦆

在处理数字的出现次数时，题解使用了`Counter`类来统计，为什么选择使用`Counter`而不是其他数据结构如数组或字典？

▷

在Python中，`Counter`类是一个专门用于计数的容器，继承自字典。使用`Counter`可以直接统计各元素的出现次数，非常适合用于统计频率的场景。相比于数组，`Counter`提供了更多的灵活性和内置功能，如自动处理不存在的键的情况。相比于普通字典，`Counter`还提供了如`most_common`等有用的方法，可以简化代码并提高效率。因此，`Counter`在处理此类计数问题时通常是更优选的选择。

🦆

题解中没有明确说明如何处理数字分配后前导0的问题。对于分割后的num1或num2，如果其中一个数字是0如何处理？

▷

在题解的策略中，数字的分配是从1到9，因此在构建数字的过程中不会出现前导0的情况。每个数字的分配都是基于非零数字，所以不会产生前导0的问题。如果0出现在输入数字num中，它将被添加到已经至少由一个非零数字的num1或num2中，因此，0只会增加数的量级，而不会成为前导0。

最小和分割

题目描述

代码结果

解释

代码细节讲解

相关问题