【Warrior刷题笔记】力扣306.累加数【枚举+高精度加法】详细注释双超100

题目

来源：力扣
地址：https://leetcode-cn.com/problems/additive-number/

描述

累加数是一个字符串，组成它的数字可以形成累加序列。
一个有效的累加序列必须至少包含3个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。给你一个只包含数字'0'-'9'的字符串，编写一个算法来判断给定输入是否是累加数。如果是，返回true；否则，返回false。说明：累加序列里的数不会以0开头，所以不会出现1, 2, 03或者1, 02, 3的情况。

示例

示例 1：

输入："112358"
输出：true 
解释：累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

示例 2：

输入："199100199"
输出：true 
解释：累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199

解题思路

本题可以采用按题给条件模拟遍历的方法解决。
一个有效的累加序列必须至少包含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。

【Warrior刷题笔记】力扣306.累加数 【枚举+高精度加法】详细注释 双超100

题目

描述

示例

解题思路

代码

复杂度分析

全站热榜

【Warrior刷题笔记】力扣306.累加数【枚举+高精度加法】详细注释双超100