LC 2698. 求一个整数的惩罚数
题目描述
这是 LeetCode 上的 2698. 求一个整数的惩罚数 ,难度为 中等。
给你一个正整数 $n$,请你返回 $n$ 的 惩罚数 。
$n$ 的 惩罚数 定义为所有满足以下条件 $i$ 的数的平方和:
$1 <= i <= n$
$i \times i$ 的十进制表示的字符串可以分割成若干连续子字符串,且这些子字符串对应的整数值之和等于 $i$ 。
示例 1:1
2
3
4
5
6
7
8
9输入: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:1
2
3
4
5
6
7
8
9
10输入: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, i]$,若当前数值 $i$ 满足要求,则将 $i \times i$ 累加到答案中。
问题关键转为:如何判定 $i \times i$ 是否能够分割成多个整数,使其累加值为 $i$。
简单做法是通过递归来做:每次从当前值的低位开始截取,通过「取余」和「地板除」操作,得到截取部分和剩余部分,再继续递归处理。
Java 代码:
1 |
|
Python 代码:1
2
3
4
5
6
7
8
9
10
11
12class Solution:
def punishmentNumber(self, n: int) -> int:
def check(t, x):
if t == x:
return True
d = 10
while t >= d and t % d <= x:
if check(t // d, x - (t % d)):
return True
d *= 10
return False
return sum([i * i if check(i * i, i) else 0 for i in range(1, n + 1)])
C++ 代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
bool check(int t, int x) {
if (t == x) return true;
int d = 10;
while (t >= d && t % d <= x) {
if (check(t / d, x - (t % d))) return true;
d *= 10;
}
return false;
}
int punishmentNumber(int n) {
int ans = 0;
for (int i = 1; i <= n; i++) {
if (check(i * i, i)) ans += i * i;
}
return ans;
}
};
TypeScript 代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16function punishmentNumber(n: number): number {
function check(t: number, x: number): boolean {
if (t === x) return true;
let d = 10;
while (t >= d && t % d <= x) {
if (check(Math.floor(t / d), x - (t % d))) return true;
d *= 10;
}
return false;
}
let ans = 0;
for (let i = 1; i <= n; i++) {
if (check(i * i, i)) ans += i * i;
}
return ans;
};
- 时间复杂度:$O(n \log{n^2})$
- 空间复杂度:$O(\log{n^2})$
打表
更进一步,对于 $[1, x]$ 范围内的惩罚数必然包含了 $[1, y]$(其中 $y < x$)中的惩罚数。
即多个样例之间必然存在重复计算,我们可通过「打表」进行预处理:定义 $f[i]$ 为 $n = i$ 时的答案(惩罚数),对于 $f[i]$ 而言,起始为 $f[i - 1]$,若数值 $i$ 本身满足要求,则将 $i \times i$ 累加到 $f[i]$ 当中。
Java 代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
static int[] f = new int[1010];
static {
for (int i = 1; i <= 1000; i++) {
f[i] = f[i - 1];
if (check(i * i, i)) f[i] += i * i;
}
}
static boolean check(int t, int x) {
if (t == x) return true;
int d = 10;
while (t >= d && t % d <= x) {
if (check(t / d, x - (t % d))) return true;
d *= 10;
}
return false;
}
public int punishmentNumber(int n) {
return f[n];
}
}
Python 代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15def check(t, x):
if t == x:
return True
d = 10
while t >= d and t % d <= x:
if check(t // d, x - (t % d)):
return True
d *= 10
return False
f = [0] * 1010
for i in range(1, 1010):
f[i] = f[i - 1] + (i * i if check(i * i, i) else 0)
class Solution:
def punishmentNumber(self, n: int) -> int:
return f[n]
C++ 代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23inline bool check(int t, int x) {
if (t == x) return true;
int d = 10;
while (t >= d && t % d <= x) {
if (check(t / d, x - (t % d))) return true;
d *= 10;
}
return false;
}
int f[1010];
int _ = []() {
for (int i = 1; i < 1010; i++) {
f[i] = f[i - 1];
if (check(i * i, i)) f[i] += i * i;
}
return 0;
}();
class Solution {
public:
int punishmentNumber(int n) {
return f[n];
}
};
TypeScript 代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17function check(t: number, x: number): boolean {
if (t === x) return true;
let d = 10;
while (t >= d && t % d <= x) {
if (check(Math.floor(t / d), x - (t % d))) return true;
d *= 10;
}
return false;
}
const f = new Array(1010).fill(0);
for (let i = 1; i < 1010; i++) {
f[i] = f[i - 1];
if (check(i * i, i)) f[i] += i * i;
}
function punishmentNumber(n: number): number {
return f[n];
};
- 时间复杂度:$O(1)$
- 空间复杂度:$O(C)$,其中 $C = 1000$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.2698
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!