参考文献
判断一个字符串是否是斐波那契数列,注意前导0过滤
ref{:target=”_blank”}
通过枚举两个数的结尾id和高精度加法来做
C++ 代码
class Solution {
public:
// (l,r]左开右必区间 描述一个数字的长度,这里只用枚举 第一个数的结尾和第二个数的结尾即可
// 第三个数可以直接用 Add 推导出来
bool isAdditiveNumber(string num) {
int n = num.size();
// i 表示第一个数结尾,包含i,j表示第二个数结尾
for(int i=0; i<n; ++i){
// j+1 表示 至少留给第三个数1位
for(int j=i+1; j+1<n; ++j) {
// (a,b] (b,c] (c, ?] 表示三个数
int a = -1, b = i, c = j;
// 前导0过滤
if(b-a > 1 && num[a+1]=='0')continue;
if(c-b > 1 && num[b+1]=='0')continue;
while(1){
string num1 = num.substr(a+1, b-a);
string num2 = num.substr(b+1, c-b);
string num3 = Add(num1, num2);
// cout << num1 << "," << num2 << "," << num3 << endl;
// 判断是否合法,不合法重新搜索i,j
if(num.substr(c+1, num3.size()) != num3)break;
if(c + num3.size() == n-1)return true;
// 合法则继续搜索
a = b, b = c, c = c + num3.size();
// cout << a << ",," << b << ",," << c << endl;
}
}
}
return false;
}
// 高精度加法
string Add(string num1, string num2){
vector<int> A,B,C;
for(int i=num1.size()-1; i>=0; i--)A.push_back(num1[i]-'0');
for(int i=num2.size()-1; i>=0; i--)B.push_back(num2[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;
}
string res;
while(C.size()>1 && C.back()=='0')C.pop_back();
for(int i=C.size()-1; i>=0; i--) res += to_string(C[i]);
return res;
}
};