LeetCode306 累加数

• 题目描述

累加数 是一个字符串，组成它的数字可以形成累加序列。

一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外，序列中的每个后续数字必须是它之前两个数字之和。

给你一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。

说明：累加序列里的数，除数字 0 之外，不会 以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。

链接：https://leetcode.cn/problems/additive-number

• 示例

输入:  199100199

输出：true

解释：累加序列为: 1,99,100,199。1 + 99 = 100, 99 + 100 = 199

• 算法思想

采用回溯法，依次尝试所有可能的字符串相加结果，例如"199100199"，先取字符串“1”，然后向下递归，取字符串“9”，...，当回溯到第一层时，取字符串“19”，然后再向下递归，取字符串“9”，...，当再次回溯到第一层时，取字符串“199”，然后再向下递归，取字符串“1”，...，每层递归与第一层的情况相同。

每次选取一个字符串时要判断其合法性，若其第一个字符为0，则需要将其放至上一层的字符串中。

每成功截取一段字符串时，加入容器中，当容器元素个数大于等于3时，要判断是否满足累加条件，每次只需判断最后三个元素即可，因为只要容器元素个数大于等于3时，我们就判断，所以只需判断最新的三个元素。

• 代码

 1 #include<iostream>
 2 #include<vector>
 3 #include<string>
 4 using namespace std;
 5 vector<string> nums;
 6 //判断截取的字符串的合法性
 7 bool check(string s) {
 8     if (s[0] == '0' && s.size() > 1) return false;//该数字以0开头，不合法
 9     return true;
10 }
11 //计算两数相加结果，返回字符串结果
12 string addStr(string s1, string s2) {
13     string result="";
14     int b = 0, c = 0;//b为本位和，c为进位和
15     int i = s1.length()-1, j = s2.length() - 1;
16     while (i >= 0 || j >= 0||c>0) {//当j,i大于0或进位和大于0就进行循环
17         int m = i < 0 ? 0 : s1[i] - '0';
18         int n = j < 0 ? 0 : s2[j] - '0';
19         b = m+ n+c;
20         c = b / 10;
21         b -= c * 10;  
22         result= to_string(b)+result;
23         i--;
24         j--;
25     }
26     return result;
27 }
28 bool backtracking(string num, int curStart) {
29     //先判断num容器里的数字是否符合累加
30     if (nums.size() >= 3) {
31         if (nums[nums.size() - 1] != addStr(nums[nums.size() - 2], nums[nums.size() - 3])) //不符合返回false
32             return false;
33         else if (curStart == num.size())//如果已经走到头了，返回true
34             return true;
35     }
36     for (int curEnd = curStart + 1; curEnd<=num.length(); curEnd++) {//选定一个结尾，依次尝试所有数的可能
37         string curStr = num.substr(curStart, curEnd - curStart);//截取下该数
38         if (!check(curStr)) {//检查该数是否合法,不合法，该字符串的第一个字符应放至上一个字符串
39             return false;
40         }
41         nums.push_back(curStr);//字符串合法就放入容器
42         //递归
43         if (backtracking(num, curEnd)) return true;
44         //回溯
45         nums.pop_back();
46     }
47     return false;
48 }
49 int main() {
50     string num;
51     cin >> num;
52     nums.clear();
53     //回溯法解决
54     if(backtracking(num, 0) == 0 )
55        cout << "false" << endl; 
56     else
57        cout << "true" << endl;
58     return 0;
59 }

参考资料:leetcode每日一题：306累加数_哔哩哔哩_bilibili