306. Additive Number

技术文章 6个月前 完美者
1,802 0

标签:开头   ==   tor   第一个   注意   const   --   组成   数字   

问题:

给定一个由0~9组成的字符串,判断该字符串是否为一个可加字符串。

可加字符串:对字符串进行切分后,各切片构成的数字,除了前两个数字外,之后的数字都等于前两个之和。

??  注意:每个切片数字若不等于0,则不能以‘0‘开头。

Example 1:
Input: "112358"
Output: true
Explanation: The digits can form an additive sequence: 1, 1, 2, 3, 5, 8. 
             1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

Example 2:
Input: "199100199"
Output: true
Explanation: The additive sequence is: 1, 99, 100, 199. 
             1 + 99 = 100, 99 + 100 = 199
 
Constraints:
num consists only of digits ‘0‘-‘9‘.
1 <= num.length <= 35

  

解法:Backtracking(回溯算法)

path:到当前位置为止,切分出来的结果

optlists:num的第pos位开始,可切出来的任意长度子串。

另,由于第一个和第二个数字和其他不同,因此要对第一个和第二个数字进行遍历尝试。

??  注意:这里第一个第二个数字的尝试结束,也要记得从path中删除尝试过的结果。path.pop_back()。

  • 第一个:num[0~i]:size:i属于1~num.size/2  (余留“和”的长度)
  • 第二个:num[i~i+j]:size:j属于1~(num.size-i)/2(余留“和”的长度)

??  注意:这里num的长度最长可有35位,因此不能简单使用字符串->int,然后进行加法计算,可能出现int类型溢出。

因此,这里实现string+string=string的add方法。

 1     string add(string a, string b) {
 2         string sum;
 3         int i = a.size()-1, j = b.size()-1, flag = 0;
 4         while(i>=0 || j>=0) {
 5             int s = flag + (i>=0?a[i]-0:0) + (j>=0?b[j]-0:0);
 6             sum.insert(sum.begin(), s%10+0);
 7             flag = s/10;
 8             i--,j--;
 9         }
10         if(flag) sum.insert(sum.begin(), flag+0);
11         return sum;
12     }

代码参考:

 1 class Solution {
 2 public:
 3     bool backtrack(string num, int pos, vector<string> path) {
 4         if(pos==num.size()) return true;
 5         string cur1 = path[path.size()-2];
 6         string cur2 = path[path.size()-1];
 7         if(cur1.size() > 1 && cur1[0] == 0 || cur2.size() > 1 && cur2[0] == 0) return false;
 8         string sum = add(cur1, cur2);
 9         if(sum==num.substr(pos, sum.length())) {
10             path.push_back(sum);
11             if(backtrack(num, pos+sum.length(), path)) return true;
12             path.pop_back();
13         }
14         return false;
15         
16     }
17     bool isAdditiveNumber(string num) {
18         vector<string> path;
19         for(int i=1; i<=num.size()/2; i++) {
20             path.push_back(num.substr(0, i));
21             for(int j=1; j<=(num.size()-i)/2; j++) {
22                 path.push_back(num.substr(i, j));
23                 if(backtrack(num, i+j, path)) return true;
24                 path.pop_back();
25             }
26             path.pop_back();
27         }
28         return false;
29     }
30 
31     //string + string = string 
32     string add(string a, string b) {
33         string sum;
34         int i = a.size()-1, j = b.size()-1, flag = 0;
35         while(i>=0 || j>=0) {
36             int s = flag + (i>=0?a[i]-0:0) + (j>=0?b[j]-0:0);
37             sum.insert(sum.begin(), s%10+0);
38             flag = s/10;
39             i--,j--;
40         }
41         if(flag) sum.insert(sum.begin(), flag+0);
42         return sum;
43     }
44 };

 

306. Additive Number

标签:开头   ==   tor   第一个   注意   const   --   组成   数字   

原文地址:https://www.cnblogs.com/habibah-chang/p/14263181.html

版权声明:完美者 发表于 2021-01-13 11:01:24。
转载请注明:306. Additive Number | 完美导航

暂无评论

暂无评论...