Medium

题目描述

给你一个正整数 n，返回 n 的惩罚数。

n 的惩罚数定义为满足以下条件的所有整数 i 的平方数之和：

  • 1 <= i <= n
  • i * i 的十进制表示可以分割成若干连续的子字符串，且这些子字符串表示的整数值之和等于 i。

示例 1：

输入：n = 10
输出：182
解释：恰好有 3 个整数 i 在范围 [1, 10] 内满足题目条件：
- 1，因为 1 * 1 = 1
- 9，因为 9 * 9 = 81，81 可以分割成 8 和 1，且 8 + 1 == 9
- 10，因为 10 * 10 = 100，100 可以分割成 10 和 0，且 10 + 0 == 10
因此，10 的惩罚数是 1 + 81 + 100 = 182

示例 2：

输入：n = 37
输出：1478
解释：恰好有 4 个整数 i 在范围 [1, 37] 内满足题目条件：
- 1，因为 1 * 1 = 1
- 9，因为 9 * 9 = 81，81 可以分割成 8 + 1
- 10，因为 10 * 10 = 100，100 可以分割成 10 + 0
- 36，因为 36 * 36 = 1296，1296 可以分割成 1 + 29 + 6
因此，37 的惩罚数是 1 + 81 + 100 + 1296 = 1478

约束条件：

  • 1 <= n <= 1000

提示：

  • 我们能生成一个数字的所有可能分割吗？
  • 使用递归算法将数字分成两部分，递归地生成每个部分的所有可能分割，然后以所有可能的方式组合它们。

解题思路

这道题的核心是判断一个数的平方是否可以分割成若干子字符串，使得这些子字符串的数值之和等于原数。

思路分析：

  1. 主要步骤：遍历 1 到 n 的每个数 i，检查 i * i 是否满足分割条件，如果满足则将 i * i 累加到结果中。

  2. 分割判断：对于数字 i * i 的字符串表示，我们需要尝试所有可能的分割方案。这是一个典型的回溯问题。

  3. 回溯算法：从字符串的起始位置开始，尝试取不同长度的前缀作为一个数字，然后递归处理剩余部分。如果某个分割方案的所有数字之和等于原数 i，则该数满足条件。

  4. 优化策略：

    • 及时剪枝：如果当前累积和已经超过目标值，可以提前返回
    • 避免前导零：除了单独的"0"，不考虑以"0"开头的多位数

算法流程：

  1. 对每个 i (1 ≤ i ≤ n)，计算 square = i * i
  2. 将 square 转换为字符串，使用回溯算法检查是否可以分割成和为 i 的子字符串
  3. 如果可以，将 square 加入结果

代码实现

class Solution {
public:
    int punishmentNumber(int n) {
        int result = 0;
        for (int i = 1; i <= n; i++) {
            int square = i * i;
            if (canPartition(to_string(square), 0, 0, i)) {
                result += square;
            }
        }
        return result;
    }
    
private:
    bool canPartition(const string& s, int index, int currentSum, int target) {
        if (index == s.length()) {
            return currentSum == target;
        }
        
        for (int i = index; i < s.length(); i++) {
            string substr = s.substr(index, i - index + 1);
            // 避免前导零，除非是单独的"0"
            if (substr.length() > 1 && substr[0] == '0') {
                break;
            }
            
            int num = stoi(substr);
            if (currentSum + num > target) {
                break; // 剪枝
            }
            
            if (canPartition(s, i + 1, currentSum + num, target)) {
                return true;
            }
        }
        
        return false;
    }
};

class Solution:
    def punishmentNumber(self, n: int) -> int:
        def canPartition(s, index, current_sum, target):
            if index == len(s):
                return current_sum == target
            
            for i in range(index, len(s)):
                substr = s[index:i+1]
                # 避免前导零，除非是单独的"0"
                if len(substr) > 1 and substr[0] == '0':
                    break
                
                num = int(substr)
                if current_sum + num > target:
                    break  # 剪枝
                
                if canPartition(s, i + 1, current_sum + num, target):
                    return True
            
            return False
        
        result = 0
        for i in range(1, n + 1):
            square = i * i
            if canPartition(str(square), 0, 0, i):
                result += square
        
        return result

public class Solution {
    public int PunishmentNumber(int n) {
        int result = 0;
        for (int i = 1; i <= n; i++) {
            int square = i * i;
            if (CanPartition(square.ToString(), 0, 0, i)) {
                result += square;
            }
        }
        return result;
    }
    
    private bool CanPartition(string s, int index, int currentSum, int target) {
        if (index == s.Length) {
            return currentSum == target;
        }
        
        for (int i = index; i < s.Length; i++) {
            string substr = s.Substring(index, i - index + 1);
            // 避免前导零，除非是单独的"0"
            if (substr.Length > 1 && substr[0] == '0') {
                break;
            }
            
            int num = int.Parse(substr);
            if (currentSum + num > target) {
                break; // 剪枝
            }
            
            if (CanPartition(s, i + 1, currentSum + num, target)) {
                return true;
            }
        }
        
        return false;
    }
}

var punishmentNumber = function(n) {
    function canPartition(str, target, index = 0, current = 0) {
        if (index === str.length) {
            return current === target;
        }
        
        for (let i = index + 1; i <= str.length; i++) {
            let substring = str.slice(index, i);
            let num = parseInt(substring);
            if (canPartition(str, target, i, current + num)) {
                return true;
            }
        }
        
        return false;
    }
    
    let sum = 0;
    for (let i = 1; i <= n; i++) {
        let square = i * i;
        let squareStr = square.toString();
        if (canPartition(squareStr, i)) {
            sum += square;
        }
    }
    
    return sum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × 2^d)，其中 n 是输入值，d 是平方数的位数。对于每个数字，最坏情况下需要尝试所有可能的分割方案
空间复杂度O(d)，递归调用栈的深度最多为平方数的位数

相关题目