?

一、題目描述

累加數(shù)是一個字符串，組成它的數(shù)字可以形成累加序列。

一個有效的累加序列必須至少包含 3 個數(shù)。除了最開始的兩個數(shù)以外，字符串中的其他數(shù)都等于它之前兩個數(shù)相加的和。

給定一個只包含數(shù)字?'0'-'9'?的字符串，編寫一個算法來判斷給定輸入是否是累加數(shù)。

說明:?累加序列里的數(shù)不會以 0 開頭，所以不會出現(xiàn)?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

二、題目分析

1）情況非常多，采用回溯的方法
2）特殊情況：以0為開頭的非零整數(shù)；特大數(shù)long? long

3）具體解析請看代碼注釋

?

三、實現(xiàn)代碼

1 class Solution { 2 public: 3 bool isAdditiveNumber(string num) { 4 int n = num.size(); 5 if (n < 3)return false; 6 long long ppre = 0, pre = 0; 7 //找出第一個數(shù)和第二個數(shù) 8 for (int i = 1; i <= n / 2; ++i) {//第一個數(shù)的長度不能超過n/2 9 ppre = stoi(num.substr(0, i)); 10 for (int j = 1; i + j <= (n * 2) / 3; ++j) {//第一個和第二個數(shù)總的長度不能超過2/3 11 pre = stoi(num.substr(i, j));//從位置i開始截取 12 if (dfs(i + j, max(i, j), pre, ppre, num))return true;//第二個數(shù)不一定比第一個數(shù)大 13 } 14 } 15 return false; 16 } 17 private: 18 /** 19 * 計算當前的數(shù)是不是前兩個數(shù)的和 20 * pos代表當前指針達到的位置 21 * len代表要截取的長度 22 * pre代表前面的數(shù) 23 * ppre代表前一個的前一個數(shù) 24 * s代表字符串 25 */ 26 bool dfs(int pos, int len, long long pre, long long ppre, string &s) { 27 int n = s.size(); 28 if (pos == n)return true;//已經(jīng)計算到最后了 29 bool flag = false; 30 long long cur = 0; 31 for (int i = len; pos + i <= n; ++i) { 32 cur = stoi(s.substr(pos, i)); 33 if (cur > pre + ppre)break;//當前的數(shù)大于兩者之和，就跳出循環(huán)，不能再截取更長的長度了 34 if (cur < pre + ppre)continue;//如果當前的數(shù)小于兩者之和，就截取更長的一位 35 flag = dfs(pos + i, i, cur, pre, s);//對當前來說兩者相等，繼續(xù)檢驗，下一次的開始長度至少和前面一個一樣 36 if (flag)break;//只要找到一個，就可以跳出了 37 } 38 return flag; 39 } 40 /** 41 * 把字符串轉(zhuǎn)換成整數(shù) 42 */ 43 long long stoi(const string &s) { 44 if (s.size() > 1 && s[0] == '0')return -1; 45 stringstream ss(s); 46 long long res; 47 ss >> res; 48 return res; 49 } 50 51 };

需要注意的地方有：第8行和第10行的等號；第43行的const

轉(zhuǎn)載于:https://www.cnblogs.com/zhizhiyu/p/10190438.html

總結(jié)

以上是生活随笔為你收集整理的[Leetcode] 第306题 累加数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。