4000. 给定数位和的最大整数

题目描述

给你两个非负整数 n 和 s。

返回满足下述条件的最大整数：

最多有 n 位数字。
其各位数字之和等于 s 。

如果不存在这样的整数，则返回 -1。

示例 1：

输入： n = 2, s = 9

输出： 90

解释：

最多由 2 位数字组成且各位数字之和为 9 的最大整数是 90。

示例 2：

输入： n = 2, s = 19

输出： -1

解释：

不存在最多由 2 位数字组成且各位数字之和为 19 的整数，因此答案为 -1。

示例 3：

输入： n = 5, s = 0

输出： 0

解释：

唯一一个各位数字之和为 0 的非负整数是 0。

提示：

1 <= n <= 5
0 <= s <= 100

解法

方法一：贪心

思考

要得到 \(n\) 位且数位和为 \(s\) 的整数，若枚举所有满足和约束的数再取最大，在 \(n\le 5\) 时也能算完，只是完全没有必要。

数位和固定时，整数的大小由高位决定：高位每增大 \(1\)，对数值的贡献都大于任何低位调整。因此从高位到低位依次放入当前还能使用的最大数字 \(\min(s,9)\)，把余量留给更低的数位。

若 \(n\times 9<s\)，则即使每一位都取 \(9\) 仍凑不足 \(s\)，直接返回 \(-1\)。

若 \(n \times 9 < s\)，即使每一位都取 \(9\) 也无法凑出数位和 \(s\)，返回 \(-1\)。

否则，为使整数尽可能大，应优先让高位取尽可能大的数字。从高位到低位共构造 \(n\) 位：每一位取 \(\min(s, 9)\)，并令 \(s\) 减去该值。最终得到的整数即为答案（若 \(s = 0\)，结果为 \(0\)）。

时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScript

class Solution:
    def largestInteger(self, n: int, s: int) -> int:
        if n * 9 < s:
            return -1
        ans = 0
        for _ in range(n):
            x = min(s, 9)
            ans = ans * 10 + x
            s -= x
        return ans

class Solution {
    public int largestInteger(int n, int s) {
        if (n * 9 < s) {
            return -1;
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int x = Math.min(s, 9);
            ans = ans * 10 + x;
            s -= x;
        }
        return ans;
    }
}

class Solution {
public:
    int largestInteger(int n, int s) {
        if (n * 9 < s) {
            return -1;
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int x = min(s, 9);
            ans = ans * 10 + x;
            s -= x;
        }
        return ans;
    }
};

func largestInteger(n int, s int) (ans int) {
    if n*9 < s {
        return -1
    }
    for i := 0; i < n; i++ {
        x := min(s, 9)
        ans = ans*10 + x
        s -= x
    }
    return
}

function largestInteger(n: number, s: number): number {
    if (n * 9 < s) {
        return -1;
    }
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        const x = Math.min(s, 9);
        ans = ans * 10 + x;
        s -= x;
    }
    return ans;
}

4000. 给定数位和的最大整数

题目描述

解法

方法一：贪心

评论