leetcode_2698求一个整数的惩罚数

1. 题意

求n以内的惩罚数的平方和。

求一个整数的惩罚数

2. 题解

2.1 回溯

回溯列举出所有可能的字符串组合，并求和。

注意根据字符分割的值大小进行减枝。

• 代码

class Solution {
public:
    int getNumStr(string &str, int nDigit) {
        
        int ret = 0;
        for (int i = 0; i < nDigit; ++i) {
            ret = ret * 10 + ( str[i] - '0' );
        }

        return ret;
    }

    bool isSplit(string str, int v) {
        

        int sz = str.size();
        if ( 0 == sz)
            return v == 0;
        if ( v < 0 )
            return false;

        
        for (int i = 1; i <= sz; ++i) {
            int num = getNumStr(str, i);
            bool ret = isSplit(str.substr(i, sz - i), v - num);
            if (ret)
                return true;
        }

        return false;
    }

    int punishmentNumber(int n) {
        
        vector<int> dissNum;
        string str;
        for ( int i = 1; i <= 1000; ++i ) {
            int v = i * i;

            
            while ( v ) {
                str.insert(0, 1, v % 10 + '0');
                v /= 10;
            }
            
            bool isDiss = isSplit(str, i);
            if (isDiss)
                dissNum.push_back(i);

            str.clear();
        }

        int ans = 0;
        for(auto &v: dissNum) {
            if (v > n)
                break;
            ans += v * v;
        }

        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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

2.2 打表

根据上面计算出的结果，可以得到所有的惩罚数。直接遍历就可以了。

class Solution {
public:
    int punishmentNumber(int n) {
        
        vector<int> dissNum = {1,9,10,36,45,55,82,91,99,100,235,297,369,370,379,414,657,675,703,756,792,909,918,945,964,990,991,999,1000};
        int ans = 0;
        for(auto &v: dissNum) {
            if (v > n)
                break;
            ans += v * v;
        }

        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15