Medium

题目描述

给定两个正整数 num 和 sum。

如果一个正整数 n 满足以下两个条件，则称其为好数：

  • n 的位数恰好为 num
  • n 各位数字的和恰好为 sum

好数 n 的得分是 n 中各位数字的平方和。

返回一个字符串，表示能够获得最大得分的好数 n。如果有多个可能的整数，返回其中最大的一个。如果不存在这样的整数，返回空字符串。

示例 1：

输入：num = 2, sum = 3
输出："30"
解释：
有 3 个好数：12、21 和 30。
- 12 的得分是 1² + 2² = 5
- 21 的得分是 2² + 1² = 5  
- 30 的得分是 3² + 0² = 9
最大得分是 9，由好数 30 获得。因此答案是 "30"。

示例 2：

输入：num = 2, sum = 17
输出："98"
解释：
有 2 个好数：89 和 98。
- 89 的得分是 8² + 9² = 145
- 98 的得分是 9² + 8² = 145
最大得分是 145。获得此得分的最大好数是 98。因此答案是 "98"。

示例 3：

输入：num = 1, sum = 10
输出：""
解释：
不存在恰好有 1 位数字且各位数字和为 10 的整数。因此答案是 ""。

约束：

  • 1 <= num <= 2 * 10⁵
  • 1 <= sum <= 2 * 10⁶

解题思路

这道题需要构造一个 num 位的数字，使得各位数字和为 sum，并且数字平方和最大。

核心思路：

  1. 平方和最大化策略：由于平方函数是凸函数，较大的数字产生更大的平方值。因此应该尽可能让某些位置的数字更大。
  2. 贪心策略：从最高位开始，尽可能放置最大的数字（9），这样既能最大化平方和，又能确保结果数字最大。
  3. 可行性检查：首先检查是否能构造出满足条件的数字。如果 sum > 9 * num（所有位都是9也无法达到要求的和）或者 sum < 1（至少需要一个非零位），则无解。

算法步骤：

  1. 边界检查：如果无法构造满足条件的数字，返回空字符串
  2. 初始化结果数组，所有位置填0
  3. 从最高位开始贪心：每一位尽可能放置最大的数字（不超过9，且不超过剩余的sum）
  4. 检查第一位是否为0，如果是则说明无法构造有效数字
  5. 将结果转换为字符串返回

这种贪心策略既保证了平方和最大，又确保了在平方和相同的情况下数字本身最大。

代码实现

class Solution {
public:
    string maxSumOfSquares(int num, int sum) {
        // 边界检查
        if (sum > 9 * num || sum < 1) {
            return "";
        }
        
        vector<int> digits(num, 0);
        int remaining = sum;
        
        // 从最高位开始贪心填充
        for (int i = 0; i < num; i++) {
            // 当前位能放的最大数字
            int maxDigit = min(9, remaining);
            digits[i] = maxDigit;
            remaining -= maxDigit;
        }
        
        // 检查第一位是否为0
        if (digits[0] == 0) {
            return "";
        }
        
        // 转换为字符串
        string result = "";
        for (int digit : digits) {
            result += to_string(digit);
        }
        
        return result;
    }
};

class Solution:
    def maxSumOfSquares(self, num: int, sum: int) -> str:
        # 边界检查
        if sum > 9 * num or sum < 1:
            return ""
        
        digits = [0] * num
        remaining = sum
        
        # 从最高位开始贪心填充
        for i in range(num):
            # 当前位能放的最大数字
            max_digit = min(9, remaining)
            digits[i] = max_digit
            remaining -= max_digit
        
        # 检查第一位是否为0
        if digits[0] == 0:
            return ""
        
        # 转换为字符串
        return ''.join(map(str, digits))

public class Solution {
    public string MaxSumOfSquares(int num, int sum) {
        // 边界检查
        if (sum > 9 * num || sum < 1) {
            return "";
        }
        
        int[] digits = new int[num];
        int remaining = sum;
        
        // 从最高位开始贪心填充
        for (int i = 0; i < num; i++) {
            // 当前位能放的最大数字
            int maxDigit = Math.Min(9, remaining);
            digits[i] = maxDigit;
            remaining -= maxDigit;
        }
        
        // 检查第一位是否为0
        if (digits[0] == 0) {
            return "";
        }
        
        // 转换为字符串
        return string.Join("", digits);
    }
}

/**
 * @param {number} num
 * @param {number} sum
 * @return {string}
 */
var maxSumOfSquares = function(num, sum) {
    // 边界检查
    if (sum > 9 * num || sum < 1) {
        return "";
    }
    
    const digits = new Array(num).fill(0);
    let remaining = sum;
    
    // 从最高位开始贪心填充
    for (let i = 0; i < num; i++) {
        // 当前位能放的最大数字
        const maxDigit = Math.min(9, remaining);
        digits[i] = maxDigit;
        remaining -= maxDigit;
    }
    
    // 检查第一位是否为0
    if (digits[0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
贪心构造O(num)O(num)
  • 时间复杂度：O(num)，需要遍历 num 位数字进行填充
  • 空间复杂度：O(num)，需要存储 num 位数字的数组