2026-10-23给定数位和的最大整数。用go语言给定两个非负整数 n 和 s。请在所有位数不超过 n 的非负整数中找出一个数使它各个数位上的数字加起来恰好等于 s并且这个数要尽可能大。如果找不到符合条件的数就返回 -1。1 n 5。0 s 100。输入 n 2, s 9。输出 90。解释最多由 2 位数字组成且各位数字之和为 9 的最大整数是 90。题目来自力扣4000。分步骤过程先判断是否可能构造一个数最多有n位。每一位最大只能是9。因此最多n位的数各位数字之和最大是n * 9。如果目标和s大于n * 9说明即使每一位都放 9也凑不到s因此不存在符合条件的数直接返回-1。计算需要用多少个 9用s除以9得到商和余数。商表示可以先用多少个数字 9。余数表示用完整数个 9 之后还剩下多少数字和需要安排。例如s 9时商为 1余数为 0表示可以用一个 9。先构造由若干个 9 组成的高位部分如果有q s / 9个 9就先构造一个由q个 9 组成的数。例如q 1时得到9q 2时得到99。这一步的目的是把最大的数字尽量放在高位使最终整数尽可能大。处理余数如果s除以 9 的余数大于 0说明除了若干个 9 之外还需要再放一个数字这个数字就是余数。把这个余数接在前面已经构造好的若干个 9 的后面。因为多使用了一位数字所以可用的剩余位数要减少 1。例如如果已经有若干个 9余数为 6就会形成“……9 6”的形式。如果余数为 0则不需要追加数字也不减少剩余位数。剩余低位全部补 0此时已经安排了若干个 9可能还安排了一个余数。为了让整数尽可能大已经使用的高位不能再变小剩余的低位对数值影响最小因此全部补 0。计算还需要补多少个 0用当前剩余可用位数减去已经使用的 9 的个数。在数值后面补相应数量的 0相当于把原数乘以 10 的若干次幂。补 0 后总位数不会超过n并且不会改变各位数字之和。返回构造出的整数最终得到的数满足位数不超过n各位数字之和等于s在所有满足条件的数中高位尽量由 9 占据因此数值最大。如果前面判断不可能则返回-1。用示例说明输入n 2s 9过程最大数位和为2 * 9 189 18所以可能存在。9 / 9 1余数为0说明可以用一个 9。构造出一个 9。余数为 0不需要追加其他数字。当前最多 2 位已经用了 1 位还剩余 1 位低位补 0。得到90。因此输出为90。复杂度分析总时间复杂度在题目约束1 n 5下涉及的位数和幂运算规模都非常小可以视为常数时间即O(1)。如果按一般位数n来看构造和补 0 的过程与位数相关可描述为O(n)但在本题约束下仍是常数级。总额外空间复杂度整个过程中只使用了少量整数变量来保存商、余数、中间构造结果等没有使用与输入规模相关的额外数据结构因此额外空间复杂度为O(1)。Go完整代码如下packagemainimport(fmtmath)funclargestInteger(n,sint)int{ifsn*9{return-1}ans:int(math.Pow10(s/9))-1// 填 9ifs%90{ansans*10s%9// 填 s%9n--}returnans*int(math.Pow10(n-s/9))// 填 0}funcmain(){n:2s:9result:largestInteger(n,s)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-deflargest_integer(n:int,s:int)-int:ifsn*9:return-1ans10**(s//9)-1# 填 9ifs%90:ansans*10s%9# 填 s % 9n-1returnans*(10**(n-s//9))# 填 0defmain():n2s9resultlargest_integer(n,s)print(result)if__name____main__:main()C完整代码如下#includeiostreamlonglongpow10_int(inte){longlongr1;for(inti0;ie;i)r*10;returnr;}longlonglargestInteger(intn,ints){if(sn*9){return-1;}longlonganspow10_int(s/9)-1;// 填 9if(s%90){ansans*10s%9;// 填 s % 9n--;}returnans*pow10_int(n-s/9);// 填 0}intmain(){intn2;ints9;longlongresultlargestInteger(n,s);std::coutresultstd::endl;return0;}
2026-10-23给定数位和的最大整数。用go语言给定两个非负整数 n 和 s。请在所有位数不超过 n 的非负整数中找出一个数使它各个数位上的数字加起来恰好等于 s并且这个数要尽可能大。如果找不到符合条件的数就返回 -1。1 n 5。0 s 100。输入 n 2, s 9。输出 90。解释最多由 2 位数字组成且各位数字之和为 9 的最大整数是 90。题目来自力扣4000。分步骤过程先判断是否可能构造一个数最多有n位。每一位最大只能是9。因此最多n位的数各位数字之和最大是n * 9。如果目标和s大于n * 9说明即使每一位都放 9也凑不到s因此不存在符合条件的数直接返回-1。计算需要用多少个 9用s除以9得到商和余数。商表示可以先用多少个数字 9。余数表示用完整数个 9 之后还剩下多少数字和需要安排。例如s 9时商为 1余数为 0表示可以用一个 9。先构造由若干个 9 组成的高位部分如果有q s / 9个 9就先构造一个由q个 9 组成的数。例如q 1时得到9q 2时得到99。这一步的目的是把最大的数字尽量放在高位使最终整数尽可能大。处理余数如果s除以 9 的余数大于 0说明除了若干个 9 之外还需要再放一个数字这个数字就是余数。把这个余数接在前面已经构造好的若干个 9 的后面。因为多使用了一位数字所以可用的剩余位数要减少 1。例如如果已经有若干个 9余数为 6就会形成“……9 6”的形式。如果余数为 0则不需要追加数字也不减少剩余位数。剩余低位全部补 0此时已经安排了若干个 9可能还安排了一个余数。为了让整数尽可能大已经使用的高位不能再变小剩余的低位对数值影响最小因此全部补 0。计算还需要补多少个 0用当前剩余可用位数减去已经使用的 9 的个数。在数值后面补相应数量的 0相当于把原数乘以 10 的若干次幂。补 0 后总位数不会超过n并且不会改变各位数字之和。返回构造出的整数最终得到的数满足位数不超过n各位数字之和等于s在所有满足条件的数中高位尽量由 9 占据因此数值最大。如果前面判断不可能则返回-1。用示例说明输入n 2s 9过程最大数位和为2 * 9 189 18所以可能存在。9 / 9 1余数为0说明可以用一个 9。构造出一个 9。余数为 0不需要追加其他数字。当前最多 2 位已经用了 1 位还剩余 1 位低位补 0。得到90。因此输出为90。复杂度分析总时间复杂度在题目约束1 n 5下涉及的位数和幂运算规模都非常小可以视为常数时间即O(1)。如果按一般位数n来看构造和补 0 的过程与位数相关可描述为O(n)但在本题约束下仍是常数级。总额外空间复杂度整个过程中只使用了少量整数变量来保存商、余数、中间构造结果等没有使用与输入规模相关的额外数据结构因此额外空间复杂度为O(1)。Go完整代码如下packagemainimport(fmtmath)funclargestInteger(n,sint)int{ifsn*9{return-1}ans:int(math.Pow10(s/9))-1// 填 9ifs%90{ansans*10s%9// 填 s%9n--}returnans*int(math.Pow10(n-s/9))// 填 0}funcmain(){n:2s:9result:largestInteger(n,s)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-deflargest_integer(n:int,s:int)-int:ifsn*9:return-1ans10**(s//9)-1# 填 9ifs%90:ansans*10s%9# 填 s % 9n-1returnans*(10**(n-s//9))# 填 0defmain():n2s9resultlargest_integer(n,s)print(result)if__name____main__:main()C完整代码如下#includeiostreamlonglongpow10_int(inte){longlongr1;for(inti0;ie;i)r*10;returnr;}longlonglargestInteger(intn,ints){if(sn*9){return-1;}longlonganspow10_int(s/9)-1;// 填 9if(s%90){ansans*10s%9;// 填 s % 9n--;}returnans*pow10_int(n-s/9);// 填 0}intmain(){intn2;ints9;longlongresultlargestInteger(n,s);std::coutresultstd::endl;return0;}
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
