LeetCode 2698. 求一个整数的惩罚数：模拟（二进制枚举）

【LetMeFly】2698.求一个整数的惩罚数：模拟（二进制枚举）

力扣题目链接：https://leetcode.cn/problems/find-the-punishment-number-of-an-integer/

给你一个正整数 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

方法一：模拟（二进制枚举）

其实很简单，用$i$从$1$到$n$枚举，对于某个$i$：

将$i^2$转为字符串处理，接着用二进制从$0$到$2^{len(i^2)}-1$枚举“切割平方字符串的位置”，将每一部分的字符串相加看是否等于$i^2$即可。

• 时间复杂度$O(n\times \log n)$（$\log n^2=2\times \log n$）
• 空间复杂度$O(\log n)$

AC代码

C++

class Solution {
private:
    int check(int n) {
        string to = to_string(n * n);
        int l = to.size();
        for (int mask = 0; mask < (1 << l); mask++) {
            int cnt = 0;
            int nowNum = 0;
            for (int i = 0; i < l; i++) {
                nowNum = nowNum * 10 + (to[i] - '0');
                if ((mask >> i) & 1) {  // 这一位后面隔开
                    cnt += nowNum;
                    nowNum = 0;
                }
            }
            if (cnt + nowNum == n) {  // 想着“会有结尾的i是不行的”
                return n * n;
            }
        }
        return 0;
    }
public:
    int punishmentNumber(int n) {
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += check(i);
        }
        return ans;
    }
};
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
28
29
30

Python

class Solution:
    def check(self, n: int) -> int:
        to = str(n * n)
        l = len(to)
        for mask in range(1 << l):
            cnt = 0
            thisNum = 0
            for i in range(l):
                thisNum = thisNum * 10 + ord(to[i]) - ord('0')
                if (mask >> i) & 1:
                    cnt += thisNum
                    thisNum = 0
            if cnt + thisNum == n:
                return n * n
        return 0


    def punishmentNumber(self, n: int) -> int:
        return sum(self.check(i) for i in range(1, n + 1))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/134043248