侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【贪心, 模拟进位】美丽整数的最小增量【力扣第 317 场周赛】

GabrielxD
2022-10-30 / 0 评论 / 0 点赞 / 20 阅读 / 694 字 / 正在检测是否收录...

题目

6222. 美丽整数的最小增量


给你两个正整数 ntarget

如果某个整数每一位上的数字相加小于或等于 target ,则认为这个整数是一个 美丽整数

找出并返回满足 n + x美丽整数 的最小非负整数 x 。生成的输入保证总可以使 n 变成一个美丽整数。

示例 1:

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

示例 2:

输入:n = 467, target = 6
输出:33
解释:最初,n 是 467 ,且其每一位数字的和是 4 + 6 + 7 = 17 。在加 33 之后,n 变为 500 且每一位数字的和变成 5 + 0 + 0 = 5 。可以证明无法加上一个小于 33 的非负整数使 n 变成一个美丽整数。

示例 3:

输入:n = 1, target = 1
输出:0
解释:最初,n 是 1 ,且其每一位数字的和是 1 ,已经小于等于 target 。

提示:

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

解题

方法一:贪心 模拟进位

思路

一种朴素的想法是,把 n 慢慢累加,每次计算所有位的和(sum),第一次 sum <= target 时返回新数减原数就行了。但数据范围比较大,这样做必定会超时。

但是我们发现 n 作为一个数只能增大不能缩小,那么让所有位的和(以下称为 sum)变小的唯一方法就是 n 进位。
比如:n = 1234,此时 sum = 10,要让 sum 变小只能把 n + 6 这样 n 就变成了 1240sum = 7 成功变小了!

所以我们可以把 n 从低位到高位枚举放入数组中,每次模拟进位,一旦发现 sum <= target 就把数组构造回数字再减去原来的 n 就得到了 x

代码

class Solution {
    static final int N = 100;
    
    public long makeIntegerBeautiful(long _n, int target) {
        int[] digits = new int[N];
        int sum = 0, idx = 0, cnt = 0;
        long n = _n;
        while (n != 0) {
            int d = (int) (n % 10);
            sum += d;
            digits[idx++] = d;
            n /= 10;
            ++cnt;
        }
        if (sum <= target) return 0L;
        for (int i = 0; i < cnt; ++i) {
            sum = sum - digits[i] + 1;
            digits[i] = 0;
            ++digits[i + 1];
            if (i == cnt - 1) ++cnt;
            if (sum <= target) break;
        }
        long x = 0L;
        for (int i = cnt - 1; i >= 0; --i) {
            x = x * 10 + digits[i];
        }
        return x - _n;
    }
}
0

评论区