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

╰+攻爆jí腚メ 2024-04-01 12:34 72阅读 0赞

### 美丽整数的最小增量 ###

#### 1.题目描述 ####

[原题入口][Link 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;
        }
    }

[Link 1]: https://leetcode.cn/problems/minimum-addition-to-make-integer-beautiful/