2698.md

title	description	keywords
2698. 求一个整数的惩罚数	LeetCode 2698. 求一个整数的惩罚数题解，Find the Punishment Number of an Integer，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 2698. 求一个整数的惩罚数 求一个整数的惩罚数 Find the Punishment Number of an Integer 解题思路 数学 回溯

2698. 求一个整数的惩罚数

🟠 Medium  🔖  数学 回溯  🔗 力扣 LeetCode

题目

Given a positive integer n, return thepunishment number of n.

The punishment number of n is defined as the sum of the squares of all integers i such that:

• 1 <= i <= n
• The decimal representation of i * i can be partitioned into contiguous substrings such that the sum of the integer values of these substrings equals i.

Example 1:

Input: n = 10

Output: 182

Explanation: There are exactly 3 integers i that satisfy the conditions in the statement:

• 1 since 1 * 1 = 1
• 9 since 9 * 9 = 81 and 81 can be partitioned into 8 + 1.
• 10 since 10 * 10 = 100 and 100 can be partitioned into 10 + 0.

Hence, the punishment number of 10 is 1 + 81 + 100 = 182

Example 2:

Input: n = 37

Output: 1478

Explanation: There are exactly 4 integers i that satisfy the conditions in the statement:

• 1 since 1 * 1 = 1.
• 9 since 9 * 9 = 81 and 81 can be partitioned into 8 + 1.
• 10 since 10 * 10 = 100 and 100 can be partitioned into 10 + 0.
• 36 since 36 * 36 = 1296 and 1296 can be partitioned into 1 + 29 + 6.

Hence, the punishment number of 37 is 1 + 81 + 100 + 1296 = 1478

Constraints:

• 1 <= n <= 1000

题目大意

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

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

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

示例 1：

输入： n = 10

输出： 182

解释： 总共有 3 个整数 i 满足要求：

• 1 ，因为 1 * 1 = 1
• 9 ，因为 9 * 9 = 81 ，且 81 可以分割成 8 + 1 。
• 10 ，因为 10 * 10 = 100 ，且 100 可以分割成 10 + 0 。

因此，10 的惩罚数为 1 + 81 + 100 = 182

示例 2：

输入： n = 37

输出： 1478

解释： 总共有 4 个整数 i 满足要求：

• 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^2

   • 对于 1 ≤ i ≤ n，计算 i^2 并将其转换为字符串 str。
   • 例如，若 i = 10，则 i^2 = 100，转换为字符串 "100"。

2. 递归检查 i^2 是否能拆分成多个部分，使其和等于 i

   • 使用递归函数 check(str, target) 来判断 str 是否可以拆分成多个部分，使得这些部分的数值之和等于 target。
   • 在 check 过程中，使用 cache 记忆化存储，减少重复计算。
   • check(str, target) 的递归逻辑：
     • 终止条件：
       • 若 str 为空且 target == 0，返回 true（说明成功拆分）。
       • 若 target < 0，返回 false（说明当前路径不可能满足条件）。
     • 尝试不同的拆分方式：
       • 遍历 str 的前缀部分 str[0:i]，将其转换为数字 left。
       • 递归检查 str[i:] 是否可以构成剩余的 target - left。
       • 若找到满足条件的拆分，则返回 true，否则继续尝试。

3. 如果 i^2 满足条件，则累加到结果中

   • 若 check(square.toString(), i) 结果为 true，则将 square 加入最终结果。

4. 返回所有满足条件的 i^2 之和

复杂度分析

• 时间复杂度：O(n * 2^m)，其中 m ≈ log(n^2) = 2 log(n)。

  • 遍历 1 到 n 需要 O(n)。
  • check(str, target) 递归地尝试所有可能的拆分方式，最坏情况下接近 O(2^m)（m 为 i^2 的字符串长度）。

• 空间复杂度：O(n log(n))。

  • 记忆化哈希表 cache：O(n log(n))

    • 每次调用 check(str, target, cache)，最多存储 O(m * i) 个子问题的解。
    • 其中 m 是 i^2 的位数，i 是 target 的取值范围（最多 O(n)）。
    • 由于 m ≈ 2 log(n)，i ≤ n，所以 cache 的大小最多 O(n log(n))。

  • 递归调用栈空间：O(log(n))

    • 在 check() 递归时，每次拆分字符串 square.toString()，深度最多 O(m)（即 2 log(n)）。
    • 由于剪枝优化，实际递归深度通常比 m 更浅。
    • 最坏情况下，递归调用栈空间为 O(log(n))。

  • 总的空间复杂度： O(n log(n))，cache 是主要的空间开销，递归调用栈的影响较小。

代码

/**
 * @param {number} n
 * @return {number}
 */
var punishmentNumber = function (n) {
	// 递归检查是否可以拆分
	const check = (str, target, cache) => {
		// 如果字符串为空且目标值变为0，说明找到一种合法拆分方式
		if (str == '' && target == 0) return true;
		// 如果目标值小于0，则不可能满足条件
		if (target < 0) return false;
		// 命中缓存
		if (cache.has(str + ',' + target)) return cache.get(str + ',' + target);

		let res = false;
		// 遍历前缀，尝试不同的拆分方式
		for (let i = 0; i < str.length; i++) {
			let left = str.substring(0, i + 1); // 当前前缀
			let right = str.substring(i + 1); // 剩余部分
			// 递归检查剩余部分能否构成 target - left
			if (check(right, target - Number(left), cache)) {
				cache.set(str + ',' + target, true);
				res = true;
				break; // 一旦找到满足条件的拆分方式就退出循环
			}
		}
		cache.set(str + ',' + target, false);
		return res;
	};

	let res = 0;
	// 遍历 1 到 n，检查哪些 i^2 满足拆分条件
	for (let i = 1; i <= n; i++) {
		let cache = new Map();

		const square = i * i; // 计算 i^2
		if (check(square.toString(), i, cache)) {
			// 检查是否满足拆分条件
			res += square; // 计入最终结果
		}
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
2518	好分区的数目		数组 动态规划	🔴	🀄️ 🔗