【Warrior刷题笔记】力扣306.累加数
题目
来源：力扣
地址：https://leetcode-cn.com/problems/additive-number/
描述
累加数是一个字符串，组成它的数字可以形成累加序列。
一个有效的累加序列必须至少包含3个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。 给你一个只包含数字'0'-'9'的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回true；否则，返回false。 说明：累加序列里的数不会以0开头，所以不会出现1, 2, 03或者1, 02, 3的情况。
示例
- 示例 1：
- 示例 2：
解题思路
本题可以采用按题给条件模拟遍历的方法解决。
一个有效的累加序列必须至少包含3个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。
因此：
1.首先计算字符串长度，如果小于三，直接返回假；
2.否则从1开始，依次枚举第一个加数（以下简称加数一）的长度i，直至i==m/2，因为如果第一个加 数的长度超过m/2， 则无论如何，即便第二个加数（以下简称加数二）长度为1，也无法使得和的长度满足条件；
3.对于每一个加数一，从1开始，依次枚举第二个加数的长度j，直至j+i+(i<j?j:i) == m，理由如2；
4.对于每一对i，j，截取加数一s1为num.substr(0,i)，截取加数二s2为num.substr(i,j)，如果加数二含有前缀零，跳出本次循环，否则计算加数一二累加和s3为add(s1, s2)（string add(string& s1, string& s2)为防止大整数相加溢出而采用的辅助字符串加法函数。但实际提交过程中发现测试样例数字都很小。。。），根据s1，s2累加长度startS4及s3长度len截取字符串中备选累加和s4为num.substr(startS4, len)；
5.同样的，判断s4是否含有前导零，若含有则跳出本次循环；若不含前导零，比较s3，s4是否相等，若相等则更新s1为s2，s2为s3，s3为add(s1, s2)，并截取s4；
6.重复过程5直至startS4+len>m。若遍历过程中不含有不等累加和，则返回真，否则跳出本次循环；
7.若枚举所有加数一加数二都未符合累加数条件，返回假。
代码
class Solution {
public:
bool isAdditiveNumber(string num) {
int m = num.size();//串长
if(m<3) return false;//串长低于3则返回假
for(int i = 1; i <= m/2; ++i){//枚举不同的加数1长度
for(int j = 1; j+i+(i<j?j:i) <= m; ++j){//枚举不同的加数2长度
string s1 = num.substr(0,i);//截取加数一
string s2 = num.substr(i,j);//截取加数二
if(s2.size()>1 && s2[0]=='0') continue;//若加数二含有前导零，跳出本次循环
string s3 = add(s1, s2);//计算累加和
int len = s3.size();//计算累加和长度
int startS4 = i + j;//计算备选累加和截取开始位置
string s4 = num.substr(startS4, len);//截取备选累加和
if(s4.size()>1 && s4[0]=='0') continue;//若备选累加和含有前导零，跳出本次循环
bool canReturn = true;//标记是否为累加序列，初始化为真
while(startS4+len<=m){//依次遍历
if(s3==s4){//若备选累加和与实际计算值相等
s1 = s2;//更新s1
s2 = s3;//更新s2
s3 = add(s1, s2);//计算s3
startS4 += len;//计算s4开始位置
len = s3.size();//计算s4长度
s4 = num.substr(startS4,len);//截取s4
if(s2.size()>1 && s2[0]=='0'){//若s4含有前导零，则标记本次枚举不是累加序列，跳出本次循环
canReturn = false;
break;
}
}
else{//若一直相等，标记为累加序列
canReturn = false;
break;
}
}
if(canReturn) return true;//返回真
}
}//遍历完都不满足累加序列条件，返回假
return false;
}
inline string add(string& s1, string& s2){//辅助字符串加法
int m = s1.size();//串1长
int n = s2.size();//串2长
int len = m<n ? n : m;//两串长度最大值
string head;//补零字符串
for(int i = 0; i < ((n-m>=0) ? n-m : m-n); ++i) head += '0';//填充补零字符串
if(m<n) s1 = head + s1;//填充零
else s2 = head + s2;
int carry = 0;//进位初始化为0
for(int i = len - 1; i >= 0; --i){//按位加
int sum = (s1[i]-'0') + (s2[i]-'0') + carry;//求和
if(sum>9){ //如果和大于9
s1[i] = to_string(sum-10)[0];//当前位修改为to_string(sum-10)[0]
carry = 1;//进位置为1
}
else{
s1[i] = to_string(sum)[0];//否则当前位修改为to_string(sum)[0]
carry = 0;//进位置于0
}
}
if(carry==0) return s1;//若进位为零返回s1
else return "1" + s1;//否则返回"1"+s1;
}
}; | |
时间复杂度： O(m³)。m为字符串长度。加数一最多枚举m/2次，加数二最多枚举m/2次，对于每对加数长度，判断是否满足累加和条件的时间复杂度也是O(m)的，当然常数比较大。综合时间复杂度O(m³)。
空间复杂度： O(m)。需要几个额外的string变量存储加数及累加和，每个串最长不超过m/2。
查看45道真题和解析
