【每日一题】求一个整数的惩罚数

Tag

【递归】【回溯】【2023-10-25】

---

题目来源

2698. 求一个整数的惩罚数

---

题目解读

求一个数 n 的惩罚数，返回它的所有惩罚数的平方和。n 的惩罚数满足以下两个条件：

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

---

解题思路

思路明确，我们需要从 1 到 n 枚举 i，使用一个返回值为 bool 类型的函数 check() 来判断 i 是否是惩罚数，如是，则加入到答案中。

方法一：递归

我们具体来看一下函数 check() 如何定义，行参列表中的参数为 t 和 x：

• t 表示需要分割的整数;
• x 表示分割后的整数的和的目标值。

我们使用 check(t, s) 来判断是否可以将整数 t 分割成和为 x 的整数，我们可以从当前值的低位开始截取，通过取整与取余运算操作，得到截取的部分和剩下的部分，比如说一开始要判断 整数 t 是否可以分割成和为 x 的整数，先分割成最低为和剩下位，我们需要判断剩下的位表示的数 t / 10 是否可以分割成和为 x - (t % d) 的整数，这是一个子问题，可以使用递归来完成。

实现代码

class 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 res = 0;
        for (int i = 1; i <= n; ++i) {
            if (check(i * i, i)) {
                res += i * i;
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

复杂度分析

时间复杂度：$O(nlog{n}^2)$。

空间复杂度：$O(logn)$。

还有一种使用回溯的写法，核心也是判断枚举的 i 是否是惩罚数。以下解释与代码均来自 求一个整数的惩罚数 官方题解。

对于每个数字 i，首先需要将 $i^2$ 转换为字符串 s，然后依次将字符串 s 进行枚举分割子串，分别枚举第一个子串 $s[0\cdots i]$、第二个子串 $s[i+1\cdots j]$，依次枚举剩余的子串，同时累加这些子串对应的十进制整数值之和为 tot，如果存在分割方案使得数值之和 tot=i，则说明 i 符合要求，如果当前的 tot 大于 i 时则中止当前的搜索。依次检测在区间 $[1,n]$ 中有多少满足要求的数字 i，并返回这些数字 i 的平方和。

class Solution {
public:
    bool dfs(string& s, int pos, int tot, int target) {
        if (pos == s.size()) {
            return tot == target;
        }

        int sum = 0;
        for (int i = pos; i < s.size(); ++i) {
            sum = sum * 10 + s[i] - '0';
            if (sum + tot > target) break;
            if (dfs(s, i+1, sum + tot, target)) return true;
        }
        return false;
    }

    int punishmentNumber(int n) {
        int res = 0;
        for (int i = 1; i <= n; ++i) {
            string s = to_string(i*i);
            if (dfs(s, 0, 0, i)) {
                res += i * i;
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

其他语言

python3

递归

class Solution:
    def punishmentNumber(self, n: int) -> int:
        def check(t: int, x: int) -> bool:
            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)])
1
2
3
4
5
6
7
8
9
10
11
12

回溯

class Solution:
    def punishmentNumber(self, n: int) -> int:
        def dfs(s: str, pos: int, tot: int, target: int) -> bool:
            if pos == len(s):
                return tot == target
            sum = 0
            for i in range(pos, len(s)):
                sum = sum * 10 + int(s[i])
                
                if sum + tot > target: break
                if dfs(s, i+1, sum + tot, target):
                    return True
            return False

        res = 0
        for i in range(1, n+1):
            if dfs(str(i*i), 0, 0, i):
                res += i * i
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出