Problem: 306. 累加数
[TOC]
暴力+高精度
判断斐波那契数列,从头开始遍历,枚举前两个数的所有情况,利用高精度计算出前两个数的和,然后比较前两个数之后子序列中是否存在这两个数的和,若存在则重复上述操作,否则继续枚举。最后都没有就不是斐波那契数列。其中还有些其它细节。。。。
class Solution {
public:
string add(string &x, string &y)
{
vector<int> a, b, c;
for(int i = x.size() - 1; i >= 0; i--) a.push_back(x[i] - '0');
for(int i = y.size() - 1; i >= 0; i--) b.push_back(y[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 z;
for(int i = c.size() - 1; i >= 0; i--) z += to_string(c[i]);
return z;
}
bool isAdditiveNumber(string num) {
int n = num.size();
if(n < 3) return 0;
vector<string> res;
function<bool(int)> dfs = [&](int i)->bool
{
int m = res.size();
if(i == n) return m >= 3;
int max = num[i] == '0' ? i + 1 : n;
for(int j = i; j < max; j++)
{
string z = num.substr(i, j - i + 1);
if(m < 2 || z == add(res[m - 2], res[m - 1]))
{
res.push_back(z);
if(dfs(j + 1)) return 1;
res.pop_back();
}
}
return 0;
};
return dfs(0);
}
};
回溯+高精度
同暴力思路,利用爆搜枚举所有数的情况,用一个数组res
记录斐波那契数列,记其大小为m
。递归边界是枚举到尾的时候,m
大小是否大于3。当m < 3
或者res
中倒数两个数的和(高精度计算)和当前的数相同时可往下递归。中间还有些细节比如前导0,可令其只为0。
class Solution {
public:
string add(string &x, string &y)
{
vector<int> a, b, c;
for(int i = x.size() - 1; i >= 0; i--) a.push_back(x[i] - '0');
for(int i = y.size() - 1; i >= 0; i--) b.push_back(y[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 z;
for(int i = c.size() - 1; i >= 0; i--) z += to_string(c[i]);
return z;
}
bool isAdditiveNumber(string num) {
int n = num.size();
if(n < 3) return 0;
for(int i = 0; i < n - 2; i++)
{
for(int j = i + 1; j < n - 1; j++)
{
int a = -1, b = i, c = j;
while(1)
{
if((b - a > 1 && num[a + 1] == '0') || (c - b > 1 && num[b + 1] == '0')) break;
string x = num.substr(a + 1, b - a), y = num.substr(b + 1, c - b), z = add(x, y);
if(z != num.substr(c + 1, z.size())) break;
a = b, b = c, c += z.size();
if(c + 1 == n) return 1;
}
}
}
return 0;
}
};