【算法刷题】——美丽整数的最小增量

美丽整数的最小增量

1.题目描述

原题入口

给你两个正整数 n 和 target 。
如果某个整数每一位上的数字相加小于或等于 target ，则认为这个整数是一个 美丽整数 。
找出并返回满足 n + x 是 美丽整数 的最小非负整数 x 。生成的输入保证总可以使 n 变成一个美丽整数。

示例 1：
输入：n = 16, target = 6 输出：4 解释：最初，n 是 16 ，且其每一位数字的和是 1 + 6 = 7 。在加 4
之后，n 变为 20 且每一位数字的和变成 2 + 0 = 2 。可以证明无法加上一个小于 4 的非负整数使 n 变成一个美丽整数。

提示：

• 1 <= n <= 10^12
• 1 <= target <= 150
• 生成的输入保证总可以使 n 变成一个美丽整数。

2.解题思路

题目描述很容易读懂，给定一个数n，要求n加上一个最小的数 相加之后的数各个数位之和小于 target。最容易想到的思路就是暴力穷举，一直加1直到符合条件。但是看题目数据量 n是12次方的，穷举肯定就超时了。
换一种思路，如何把一个数位的数变小，只能加。很容易想到只要进位变成0，那么这个数位的数就减少了。比如 734504727 10 这个测试示例，我们从低位到高位 每个数位都变成0 一直到符合条件为止。因此我们需要一个集合存储n的各个数位，这样方便进行数位和、相加的数大小的计算。

734504727 39
734504730 33
734504800 31
734505000 24
734510000 20
734600000 20
735000000 15
740000000 11
800000000 8

3.代码实现

class Solution {
    // 记录每一位的数
    List<Integer> list = new ArrayList<>();
    public long makeIntegerBeautiful(long n, int target) {

        // 记录当前各位数之和
        int ans = add(n);

        //如果本身就符合条件直接返回0
        if(ans  <= target) return 0L;

        //记录加的数
        long res = 0L;

        //当前到哪一位
        int idx = 0;

        while (idx < list.size() && ans > target){

            //当前位变0  注意 list存储的是进位前的数位 进位后都要加1 
            ans = ans - list.get(idx) + (idx == 0 ? 1 : 0) ;

            //加的数字  除了最后一位其余的都进位了，但是list集合中没有更新，因此需要再-1
            res += ((10-list.get(idx) - (idx == 0 ? 0 : 1)) * Math.pow(10,idx));
            idx++;
        }

        return res;

    }

    int add(long n){
        int num = 0;
        while( n!= 0){
            num += n % 10;
            list.add((int) (n % 10));
            n /= 10;
        }

        return  num;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43