2026-10-23：给定数位和的最大整数。用go语言，给定两个非负整数 n 和 s。请在所有位数不超过 n 的非负整数中，找出一个数，使它各个数位

2026-10-23：给定数位和的最大整数。用go语言，给定两个非负整数 n 和 s。请在所有位数不超过 n 的非负整数中，找出一个数，使它各个数位上的数字加起来恰好等于 s，并且这个数要尽可能大。如果找不到符合条件的数，就返回 -1。

1 <= n <= 5。

0 <= s <= 100。

输入： n = 2, s = 9。

输出： 90。

解释：

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

题目来自力扣4000。

分步骤过程

1.先判断是否可能构造

• 一个数最多有n位。

• 每一位最大只能是9。

• 因此最多n位的数，各位数字之和最大是n * 9。

• 如果目标和s大于n * 9，说明即使每一位都放 9，也凑不到s，因此不存在符合条件的数，直接返回-1。

2.计算需要用多少个 9

• 用s除以9，得到商和余数。

• 商表示可以先用多少个数字 9。

• 余数表示用完整数个 9 之后，还剩下多少数字和需要安排。

• 例如s = 9时，商为 1，余数为 0，表示可以用一个 9。

3.先构造由若干个 9 组成的高位部分

• 如果有q = s / 9个 9，就先构造一个由q个 9 组成的数。

• 例如q = 1时得到9；q = 2时得到99。

• 这一步的目的是把最大的数字尽量放在高位，使最终整数尽可能大。

4.处理余数

• 如果s除以 9 的余数大于 0，说明除了若干个 9 之外，还需要再放一个数字，这个数字就是余数。

• 把这个余数接在前面已经构造好的若干个 9 的后面。

• 因为多使用了一位数字，所以可用的剩余位数要减少 1。

• 例如如果已经有若干个 9，余数为 6，就会形成“……9 6”的形式。

• 如果余数为 0，则不需要追加数字，也不减少剩余位数。

5.剩余低位全部补 0

• 此时已经安排了若干个 9，可能还安排了一个余数。

• 为了让整数尽可能大，已经使用的高位不能再变小；剩余的低位对数值影响最小，因此全部补 0。

• 计算还需要补多少个 0：用当前剩余可用位数减去已经使用的 9 的个数。

• 在数值后面补相应数量的 0，相当于把原数乘以 10 的若干次幂。

• 补 0 后，总位数不会超过n，并且不会改变各位数字之和。

6.返回构造出的整数

• 最终得到的数满足：

• 位数不超过n；

• 各位数字之和等于s；

• 在所有满足条件的数中，高位尽量由 9 占据，因此数值最大。

• 如果前面判断不可能，则返回-1。

用示例说明

输入：

•n = 2

•s = 9

过程：

1. 最大数位和为2 * 9 = 18，9 <= 18，所以可能存在。

2.9 / 9 = 1，余数为0，说明可以用一个 9。

3. 构造出一个 9。

4. 余数为 0，不需要追加其他数字。

5. 当前最多 2 位，已经用了 1 位，还剩余 1 位，低位补 0。

6. 得到90。

因此输出为90。

复杂度分析

•总时间复杂度：
在题目约束1 <= n <= 5下，涉及的位数和幂运算规模都非常小，可以视为常数时间，即O(1)。
如果按一般位数n来看，构造和补 0 的过程与位数相关，可描述为O(n)，但在本题约束下仍是常数级。

•总额外空间复杂度：
整个过程中只使用了少量整数变量来保存商、余数、中间构造结果等，没有使用与输入规模相关的额外数据结构，因此额外空间复杂度为O(1)。

Go完整代码如下：

package main

 import (
    "fmt"
    "math"
)

 func largestInteger(n, s int)int {
    if s > n*9 {
        return-1
    }

     ans := int(math.Pow10(s/9)) - 1// 填 9
    if s%9 > 0 {
        ans = ans*10 + s%9// 填 s%9
        n--
    }
    return ans * int(math.Pow10(n-s/9)) // 填 0
}

 func main() {
    n := 2
    s := 9
    result := largestInteger(n, s)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 def largest_integer(n: int, s: int) -> int:
    if s > n * 9:
        return-1

     ans = 10 ** (s // 9) - 1  # 填 9
    if s % 9 > 0:
        ans = ans * 10 + s % 9  # 填 s % 9
        n -= 1

     return ans * (10 ** (n - s // 9))  # 填 0

 def main():
    n = 2
    s = 9
    result = largest_integer(n, s)
    print(result)

 if __name__ == "__main__":
    main()

C++完整代码如下：

  


 long long pow10_int(int e) {
    long long r = 1;
    for (int i = 0; i < e; ++i) r *= 10;
    return r;
}

 long long largestInteger(int n, int s) {
    if (s > n * 9) {
        return-1;
    }

     long long ans = pow10_int(s / 9) - 1; // 填 9
    if (s % 9 > 0) {
        ans = ans * 10 + s % 9;           // 填 s % 9
        n--;
    }
    return ans * pow10_int(n - s / 9);    // 填 0
}

 int main() {
    int n = 2;
    int s = 9;
    long long result = largestInteger(n, s);
    std::cout << result << std::endl;
    return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。