题目描述
给你一个正整数 n
,请你返回 n
的 惩罚数。
n
的 惩罚数 定义为所有满足以下条件 i
的数的平方和:
1 <= i <= n
i * i
的十进制表示的字符串可以分割成若干连续子字符串,且这些子字符串对应的整数值之和等于i
。
样例
输入: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
输入: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
算法
(递归回溯) $O(n \cdot 4^{\lg n})$
- 从 $1$ 到 $n$ 枚举并判定惩罚数。
- 通过递归回溯的方式判定,每一位有两种选择,和前序数位组成一个分割数字,或者新开一个分割数字。
时间复杂度
- 每个数字需要 $O(2^{\lg (n^2)})$ 的时间判定,共有 $n$ 个数字,故总时间复杂度为 $O(n \cdot 4^{\lg n})$。
空间复杂度
- 需要 $O(\lg n)$ 的额外空间存储递归的系统栈。
C++ 代码
class Solution {
private:
bool check(int i, int sum, int remain, const string &s) {
if (sum > remain)
return false;
if (i == s.size()) {
if (remain == sum)
return true;
return false;
}
if (check(i + 1, sum * 10 + s[i] - '0', remain, s))
return true;
return check(i + 1, s[i] - '0', remain - sum, s);
}
public:
int punishmentNumber(int n) {
int ans = 0;
for (int i = 1; i <= n; i++) {
string t = to_string(i * i);
if (check(1, t[0] - '0', i, t))
ans += i * i;
}
return ans;
}
};