[Leetcode] 第306题 累加数

 1 class Solution {
 2 public:
 3     bool isAdditiveNumber(string num) {
 4         int n = num.size();
 5         if (n < 3)return false;
 6         long long ppre = 0, pre = 0;
 7         //找出第一个数和第二个数
 8         for (int i = 1; i <= n / 2; ++i) {//第一个数的长度不能超过n/2
 9             ppre = stoi(num.substr(0, i));
10             for (int j = 1; i + j <= (n * 2) / 3; ++j) {//第一个和第二个数总的长度不能超过2/3
11                 pre = stoi(num.substr(i, j));//从位置i开始截取
12                 if (dfs(i + j, max(i, j), pre, ppre, num))return true;//第二个数不一定比第一个数大
13             }
14         }
15         return false;
16     }
17 private:
18     /**
19     * 计算当前的数是不是前两个数的和
20     * pos代表当前指针达到的位置
21     * len代表要截取的长度
22     * pre代表前面的数
23     * ppre代表前一个的前一个数
24     * s代表字符串
25     */
26     bool dfs(int pos, int len, long long pre, long long ppre, string &s) {
27         int n = s.size();
28         if (pos == n)return true;//已经计算到最后了
29         bool flag = false;
30         long long cur = 0;
31         for (int i = len; pos + i <= n; ++i) {
32             cur = stoi(s.substr(pos, i));
33             if (cur > pre + ppre)break;//当前的数大于两者之和，就跳出循环，不能再截取更长的长度了
34             if (cur < pre + ppre)continue;//如果当前的数小于两者之和，就截取更长的一位
35             flag = dfs(pos + i, i, cur, pre, s);//对当前来说两者相等，继续检验，下一次的开始长度至少和前面一个一样
36             if (flag)break;//只要找到一个，就可以跳出了
37         }
38         return flag;
39     }
40     /**
41     * 把字符串转换成整数
42     */
43     long long stoi(const string &s) {
44         if (s.size() > 1 && s[0] == '0')return -1;
45         stringstream ss(s);
46         long long res;
47         ss >> res;
48         return res;
49     }
50 
51 };