原题链接:
https://leetcode.cn/problems/find-the-punishment-number-of-an-integer/description/

解法1: 递归

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

class Solution {
    /*
    *  打表预处理
    *  递归求解
    * */

    // 将[1,1000] 所有符合条件的惩罚数 都储存再 PRE_SUM数组中继续记录
    private static final int [] PRE_SUM = new int[1001];


    // 静态方法 只会运行一次
    static {
        for(int i = 1 ; i <= 1000 ; i++){
            // 转换为字符串
            char [] s = Integer.toString(i * i).toCharArray();
            // 这里使用了前缀和处理 后续主函数内直接调用就行 不需要再判断了 算是一种优化
            PRE_SUM[i] = PRE_SUM[i - 1] +  (dfs(s,i,0,0) ? i * i : 0);
        }
    }

    /***
     *
     * @param s 当前处理的字符串
     * @param i 当前遍历到的数 i
     * @param p dfs枚举分割的起点
     * @param sum i*i 字符串数的和
     * @return
     */
    private static boolean dfs(char [] s, int i, int p,int sum){
        // 当前已经分割到了 s的最后的一位 直接返回
        if(p == s.length){
            return  sum == i;
        }

        int x = 0;
        // 分割字符串 进行遍历
        for(int j = p ; j < s.length ; j++){
            // 因为是从前往后开始拆分 那么每拆一位 算出当前值 将到sum进行组合求出结果
            x = x * 10 + s[j] - '0';
            // 如果符合条件 直接返回
            if(dfs(s,i,j+1,sum + x)){
                return true;
            }
        }
        return false;
    }

    public int punishmentNumber(int n) {
        return PRE_SUM[n];
    }
}