题目描述给你两个 正 整数 num 和 sum。如果一个正整数 n 满足以下两个条件则称其为 好整数n 的位数 恰好 为 num。n 的各位数字之和 恰好 为 sum。一个 好整数 n 的 分数 定义为 n 的各位数字的平方和。返回一个 字符串表示能获得 最大分数 的 好整数 n。如果有多个可能的整数返回 最大 的那个。如果不存在这样的整数返回一个空字符串。示例1输入num2num 2num2,sum3sum 3sum3输出“303030”解释:有 3 个好整数12、21 和 30。12 的分数是122251^2 2^2 512225。21 的分数是221252^2 1^2 522125。30 的分数是320293^2 0^2 932029。最大分数是 9由好整数 30 获得。因此答案是 “30”。示例2:输入:num2num 2num2,sum17sum 17sum17输出: “98”解释:有两个好整数89 和 98。89 的分数是82921458^2 9^2 1458292145。98 的分数是 9^282145 8^2 14582145。最大分数是 145。获得此分数的最大好整数是 98。因此答案是 “98”。示例3:输入:num1num 1num1,sum10sum 10sum10输出: “”解释:不存在恰好有 1 位数字且各位数字之和为 10 的整数。因此答案是 “”。提示:1num2∗1051 num 2 * 10^51num2∗1051sum2∗1061 sum 2 * 10^61sum2∗106思路平方函数是凸函数对于固定的数字之和数字越集中即差距越大平方和越大。因此为了使平方和最大应尽可能让某些位是 9其余位是 0。但首位不能为 0所以首位至少为 1。同时为了数值最大应该从左到右依次填入尽可能大的数字但要保证剩余位数能够容纳剩余的和即剩余和不超过 9 × 剩余位数。贪心策略从左到右遍历每一位当前位取 min(9, 剩余和)。这样会优先把大的数字放在高位同时确保后面的位有足够空间容纳剩余的和。如果 sum 9 × num则不可能构造返回空字符串。解题过程以 num 2, sum 3 为例剩余和 remain 3。第 1 位取 min(9, 3) 3remain 变为 0。第 2 位取 min(9, 0) 0。得到字符串 “30”平方和 3² 0² 9是最大分数且数值最大。以 num 2, sum 17 为例第 1 位取 min(9, 17) 9remain 8。第 2 位取 min(9, 8) 8。得到 “98”平方和 9² 8² 145与 “89” 分数相同但 “98” 更大。复杂度时间复杂度O(num)只需遍历 num 位。空间复杂度O(num)需要存储结果字符串。Code#includestdlib.h/** * 构造数位平方和最大的好整数 * * param num 数字的位数 * param sum 各位数字之和 * return 最大分数对应的最大整数字符串若不存在返回空字符串 */char*maxSumOfSquares(intnum,intsum){// 1. 检查是否存在这样的好整数// 最大可能的各位数字之和为 9 * numif(sum9*num||sum1){// 不存在返回空字符串char*empty(char*)malloc(1);empty[0]\0;returnempty;}// 2. 分配结果字符串长度为 num 1含结束符 \0char*result(char*)malloc(num1);if(resultNULL){returnNULL;// 内存分配失败}intremainsum;// 剩余需要分配的数字之和// 3. 从左到右贪心构造每一位for(inti0;inum;i){// 当前位取尽可能大的数字但不超过 9 和剩余和intd(remain9)?9:remain;result[i]0d;remain-d;}result[num]\0;// 字符串结束符returnresult;}注意在 LeetCode 上提交时函数名必须为 maxSumOfSquares与判题模板保持一致否则会出现 implicit declaration offunctionmaxSumOfSquares的编译错误。总结本题的核心是贪心策略为了使平方和最大应尽可能让高位取 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著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。