拆分数位后四位数字的最小和 图解题解

这道题到底在问什么

输入

num = 2932

输出

52 (取 [29,23], 29+23=52)

输入

num = 4009

输出

13 (取 [4,9], 数位 0、0 当前导, 4+9=13)

输入

num = 1000

输出

1 (数位 0、0、0、1, 拼成 1)

最优解：一步一步想明白

1. 3记牢这一句:数位排好序后,最小的两个进十位、最大的两个进个位。因为十位要乘 10,让小数字去扛这个大权重,总和才压得最低。下面先把四个数位取出来。
2. 4先把舞台摆好。上面这排四个格子,准备装 num 的四个数位,现在都是空的,写着一个点。取数位的办法很直接:反复对 num 取一次除以 10 的余数,就得到当前的个位;再把 num 整除 10,把这一位抹掉。就这样一位一位往外抠,直到 num 变成 0。
3. 5第一次取:2932 对 10 取余,得到个位 2,填进第 1 格。
4. 6取完这一位,把 num 整除 10,2932 变成 293,个位那个 2 被抹掉了。第 1 格已经装好数字 2。
5. 7第二次取:293 对 10 取余,得到个位 3,填进第 2 格。
6. 8num 再整除 10,293 变成 29。第 2 格装好数字 3。到这儿取出了两位。
7. 9第三次取:29 对 10 取余,得到个位 9,填进第 3 格。
8. 10num 整除 10,29 变成 2。第 3 格装好数字 9。还剩最后一位。
9. 11第四次取:2 对 10 取余,得到个位 2,填进第 4 格。
10. 12num 整除 10,2 变成 0。第 4 格装好数字 2。num 归零,四个数位全取出来了,数组是 2、3、9、2。
11. 13四个数位都拿到了,现在是 2、3、9、2,还乱着。参考代码这一步直接调库函数排序,咱们用直观的选择排序演示:每一轮从没排好的部分里挑出最小的一个,换到最前面,结果和库排序完全一样,都是从小到大排好。
12. 14第 1 轮,在还没排好的这几格里找最小。拿第 2 格的 3 和当前最小 2 比,3 不比 2 小,最小候选不动。
13. 15第 1 轮,在还没排好的这几格里找最小。拿第 3 格的 9 和当前最小 2 比,9 不比 2 小,最小候选不动。
14. 16第 1 轮,在还没排好的这几格里找最小。拿第 4 格的 2 和当前最小 2 比,两个一样大,保留先出现的那个当最小。
15. 17本轮最小是 2,它已经在第 1 格,不用换,第 1 格就此排定。现在数组是 2、3、9、2。
16. 18第 2 轮,在还没排好的这几格里找最小。拿第 3 格的 9 和当前最小 3 比,9 不比 3 小,最小候选不动。
17. 19第 2 轮,在还没排好的这几格里找最小。拿第 4 格的 2 和当前最小 3 比,2 更小,最小候选换成第 4 格。
18. 20本轮最小是 2,把它和第 2 格的 3 交换,第 2 格就此排定。现在数组是 2、2、9、3。
19. 21第 3 轮,在还没排好的这几格里找最小。拿第 4 格的 3 和当前最小 9 比,3 更小,最小候选换成第 4 格。
20. 22本轮最小是 3,把它和第 3 格的 9 交换,第 3 格就此排定。现在数组是 2、2、3、9。
21. 23最后一格自然就是剩下的那个,排序完成。四个数位从小到大是 2、2、3、9。左边两个是最小的一对,右边两个是最大的一对,接下来就靠这个顺序来拼数。
22. 24排好的数组是 2、2、3、9。按套路分两组:左边两个 2 和 2 是要进十位的最小对,把它们标绿;右边 3 和 9 是要进个位的最大对,标蓝。下面把它们各就各位,拼出 new1 和 new2。
23. 25先摆十位。把最小的 2 放到 new1 的十位。十位要乘 10,所以这里放的是最小数字,先亏得最少。
24. 26第二小的 2 放到 new2 的十位。两个十位都用上了最小的一对数字,乘 10 之后的这份和最小,是 4 乘 10。
25. 27再摆个位。把 3 放到 new1 的个位,new1 拼成了 23。个位只乘 1,权重小,大数字放这里代价最低。
26. 28最大的 9 放到 new2 的个位,new2 拼成了 29。四个数位全部就位:new1 是 23,new2 是 29。
27. 29把两个数加起来:23 加 29 等于 52。也可以直接套公式:10 乘最小两位之和 4,再加最大两位之和 12,等于 52。这就是最小和,和开头说的 52 对上了。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def minimumSum(self, num: int) -> int:
        nums = []
        while num:
            nums.append(num % 10)
            num //= 10
        nums.sort()
        return 10 * (nums[0] + nums[1]) + nums[2] + nums[3]

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    int minimumSum(int num) {
        vector<int> nums;
        while (num) {
            nums.push_back(num % 10);
            num /= 10;
        }
        sort(nums.begin(), nums.end());
        return 10 * (nums[0] + nums[1]) + nums[2] + nums[3];
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int minimumSum(int num) {
        int[] nums = new int[4];
        for (int i = 0; num != 0; ++i) {
            nums[i] = num % 10;
            num /= 10;
        }
        Arrays.sort(nums);
        return 10 * (nums[0] + nums[1]) + nums[2] + nums[3];
    }
}

复杂度

面试官可能追问