【Warrior刷題筆記】力扣306.累加數 【列舉+高精度加法】詳細注釋 雙超100

題目

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

描述

累加數是一個字串，組成它的數字可以形成累加序列，
一個有效的累加序列必須至少包含3個數，除了最開始的兩個數以外，字串中的其他數都等于它之前兩個數相加的和，
給你一個只包含數字'0'-'9'的字串，撰寫一個演算法來判斷給定輸入是否是 累加數 ，如果是，回傳true；否則，回傳false，
說明：累加序列里的數不會以0開頭，所以不會出現1, 2, 03或者1, 02, 3的情況，

示例

1. 示例 1：

輸入："112358"
輸出：true 
解釋：累加序列為: 1, 1, 2, 3, 5, 8 ，1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

2. 示例 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(m3)，m為字串長度，加數一最多列舉m/2次，加數二最多列舉m/2次，對于每對加數長度，判斷是否滿足累加和條件的時間復雜度也是O(m)的，當然常數比較大，綜合時間復雜度O(m3)，
空間復雜度： O(m)，需要幾個額外的string變數存盤加數及累加和，每個串最長不超過m/2，

更多知識內容分享：
力扣個人主頁https://leetcode-cn.com/profile/articles/
CSDN個人主頁https://blog.csdn.net/qq_39255924
牛客個人主頁https://blog.nowcoder.net/newcoderthewarrior

標籤：其他

上一篇：【Warrior刷題筆記】劍指offer 32. 三道題，讓你學會二叉樹的深度廣度優先遍歷與遞回迭代技術

下一篇：藍橋杯ALGO-1003