2698. 求一个整数的惩罚数

🟠 🔖 数学 回溯 🔗 力扣open in new window LeetCodeopen in new window

题目

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 到 n，计算 i^2
- 对于 1 ≤ i ≤ n，计算 i^2 并将其转换为字符串 str。
- 例如，若 i = 10，则 i^2 = 100，转换为字符串 "100"。
递归检查 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，否则继续尝试。
如果 i^2 满足条件，则累加到结果中
- 若 check(square.toString(), i) 结果为 true，则将 square 加入最终结果。
返回所有满足条件的 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;
};

2698. 求一个整数的惩罚数

# 2698. 求一个整数的惩罚数

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

2698. 求一个整数的惩罚数

题目

题目大意

解题思路

复杂度分析

代码

相关题目