LeetCode-306-累加数-枚举-模拟

原题链接

给一个字符串，判断一下这个字符串是不是斐波那契，但是没有给分出来数字

要挨个去枚举第一个数和第二个数

两个循环分别去枚举第一个数的结尾和第二个数的结尾

然后还要用到第一个数开头的前一个位置和第二个数开头的前一个位置
这里分别就是-1和第一个数的结尾

这样计算第一个数的长度的时候，数的结尾 - 数开头的前一个
后面需要算子串的时候找个例子画一下就知道了

整体流程大概就是，两重for循环去枚举两个数的结尾
判断一下有没有前导0，如果有说明当前不成立
大整数加法，用字符串表示，求一下和，看看后面的位置对不对的上，对不上则说明当前不成立
更新下一次要遍历的位置，如果第二个数的结尾已经走到了结尾了，说明是成立的，返回true

class Solution {
public:

    string add(string a, string b){
        vectorA, B, C;
        string ans;
        for(int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');
        for(int i = b.size() - 1; i >= 0; i --) B.push_back(b[i] - '0');
        for(int i = 0, t = 0; i < a.size() || i < b.size() || t; i ++){
            if(i < A.size())    t += A[i];
            if(i < B.size())    t += B[i];
            C.push_back(t % 10);
            t /= 10;
        }
        for(int i = C.size() - 1; i >= 0; i --)
            ans += to_string(C[i]);
        return ans;
    }

    bool isAdditiveNumber(string num) {
        for(int i = 0; i < num.size(); i ++)
            for(int j = i + 1; j + 1 < num.size(); j ++){
                int a = -1, b = i, c = j;
                while(true){
                    if(b - a > 1 && num[a + 1] == '0' || c - b > 1 && num[b + 1] == '0')  break;
                    auto x = num.substr(a + 1, b - a), y = num.substr(b + 1, c - b);
                    auto z = add(x, y);
                    if(num.substr(c + 1, z.size()) != z)    break;
                    a = b, b = c, c += z.size();
                    if(c == num.size() - 1) return true;
                }
            }
        return false;
    }
};