算法|每日一题|求一个整数的惩罚数|回溯

2698. 求一个整数的惩罚数

原题地址： 力扣每日一题：求一个整数的惩罚数

给你一个正整数 n ，请你返回 n 的 惩罚数 。

n 的 惩罚数 定义为所有满足以下条件 i 的数的平方和：

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

class Solution {
    public int punishmentNumber(int n) {
        int res = 0;
        // 惩罚数是从1到n中符合条件的数字的和，所以遍历i到n
        for (int i = 1; i <= n; i++) {
            String s = Integer.toString(i * i);
            // 返回true就加到惩罚数里
            if (dfs(s, 0, 0, i)) {
                res += i * i;
            }
        }
        return res;
    }
	// pos是当前搜索的子字符串的起始位置，tot是当前已经搜索到的数字序列的总和
    public boolean dfs(String s, int pos, int tot, int target) {
        if (pos == s.length()) {
            return tot == target;
        }
        int sum = 0;
        for (int i = pos; i < s.length(); i++) {
            sum = sum * 10 + s.charAt(i) - '0';
            if (sum + tot > target) {
                break;
            }
            if (dfs(s, i + 1, sum + tot, target)) {
                return true;
            }
        }
    return false;
    }
}
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
31

如果对您有帮助，请点赞关注支持我，谢谢！❤
如有错误或者不足之处，敬请指正！❤