企业官网建设流程全解析

题目描述：

给你两个 正 整数 num 和 sum。
如果一个正整数 n 满足以下两个条件，则称其为 好整数：

• n 的位数 恰好 为 num。
• n 的各位数字之和 恰好 为 sum。
  一个 好整数 n 的 分数 定义为 n 的各位数字的平方和。
  返回一个 字符串，表示能获得 最大分数 的 好整数 n。如果有多个可能的整数，返回 最大 的那个。如果不存在这样的整数，返回一个空字符串。
  示例1：
  输入：num=2num = 2num=2,sum=3sum = 3sum=3
  输出：“303030”
  解释:
  有 3 个好整数：12、21 和 30。
• 12 的分数是12+22=51^2 + 2^2 = 512+22=5。
• 21 的分数是22+12=52^2 + 1^2 = 522+12=5。
• 30 的分数是32+02=93^2 + 0^2 = 932+02=9。
  最大分数是 9，由好整数 30 获得。因此，答案是 “30”。
  示例2:
  输入:num=2num = 2num=2,sum=17sum = 17sum=17
  输出: “98”
  解释:
  有两个好整数：89 和 98。
• 89 的分数是82+92=1458^2 + 9^2 = 14582+92=145。
• 98 的分数是 9^2+82=145+ 8^2 = 145+82=145。
  最大分数是 145。获得此分数的最大好整数是 98。因此，答案是 “98”。
  示例3:
  输入:num=1num = 1num=1,sum=10sum = 10sum=10
  输出: “”
  解释:
  不存在恰好有 1 位数字且各位数字之和为 10 的整数。因此，答案是 “”。
  提示:
• 1<=num<=2∗1051 <= num <= 2 * 10^51<=num<=2∗105
• 1<=sum<=2∗1061 <= sum <= 2 * 10^61<=sum<=2∗106

思路

平方函数是凸函数，对于固定的数字之和，数字越集中（即差距越大），平方和越大。因此，为了使平方和最大，应尽可能让某些位是 9，其余位是 0。但首位不能为 0，所以首位至少为 1。同时为了数值最大，应该从左到右依次填入尽可能大的数字，但要保证剩余位数能够容纳剩余的和（即剩余和不超过 9 × 剩余位数）。
贪心策略：从左到右遍历每一位，当前位取 min(9, 剩余和)。这样会优先把大的数字放在高位，同时确保后面的位有足够空间容纳剩余的和。如果 sum > 9 × num，则不可能构造，返回空字符串。

解题过程

以 num = 2, sum = 3 为例：

• 剩余和 remain = 3。
• 第 1 位：取 min(9, 3) = 3，remain 变为 0。
• 第 2 位：取 min(9, 0) = 0。
• 得到字符串 “30”，平方和 3² + 0² = 9，是最大分数，且数值最大。
  以 num = 2, sum = 17 为例：
• 第 1 位：取 min(9, 17) = 9，remain = 8。
• 第 2 位：取 min(9, 8) = 8。
• 得到 “98”，平方和 9² + 8² = 145，与 “89” 分数相同，但 “98” 更大。

复杂度

• 时间复杂度：O(num)，只需遍历 num 位。
• 空间复杂度：O(num)，需要存储结果字符串。

Code

#include<stdlib.h>/** * 构造数位平方和最大的好整数 * * @param num 数字的位数 * @param sum 各位数字之和 * @return 最大分数对应的最大整数（字符串），若不存在返回空字符串 */char*maxSumOfSquares(intnum,intsum){// 1. 检查是否存在这样的好整数// 最大可能的各位数字之和为 9 * numif(sum>9*num||sum<1){// 不存在，返回空字符串char*empty=(char*)malloc(1);empty[0]='\0';returnempty;}// 2. 分配结果字符串，长度为 num + 1（含结束符 '\0'）char*result=(char*)malloc(num+1);if(result==NULL){returnNULL;// 内存分配失败}intremain=sum;// 剩余需要分配的数字之和// 3. 从左到右贪心构造每一位for(inti=0;i<num;i++){// 当前位取尽可能大的数字，但不超过 9 和剩余和intd=(remain>9)?9:remain;result[i]='0'+d;remain-=d;}result[num]='\0';// 字符串结束符returnresult;}

注意：在 LeetCode 上提交时，函数名必须为 maxSumOfSquares，与判题模板保持一致，否则会出现 implicit declaration offunction'maxSumOfSquares'的编译错误。

总结

本题的核心是贪心策略：为了使平方和最大，应尽可能让高位取 9，直到剩余和不足以填满剩余位数。这样得到的数字集合是“若干个 9 + 一个剩余数字 + 若干个 0”，其平方和最大；同时由于从高位到低位依次取最大可能值，得到的数值也是最大的。该算法时间复杂度O(num)O(num)O(num)，空间复杂度O(num)O(num)O(num)，能够高效处理 num 高达2∗1052 * 10^52∗105的数据规模。

作者：一清风月一流年
链接：https://leetcode.cn/problems/maximize-sum-of-squares-of-digits/solutions/4043417/3723-shu-wei-ping-fang-he-de-zui-da-zhi-ttqqn/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。