Additive number is a string whose digits can form additive sequence.
A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.
Given a string containing only digits '0'-'9'
, write a function to determine if it's an additive number.
Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03
or 1, 02, 3
is invalid.
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
Follow up:
How would you handle overflow for very large input integers?
A:
TNND, 凌晨,4,5点钟,真是伤脑子。 再不熬夜了。
一个SB的错误, 应该时continue, 我因为以前写成了return false. 搞了半个小时
class Solution { public: bool isAdditiveNumber(string num) { int n = num.length(); if( n==0 ) return true; for(int end1 = 0;end1<n-2;end1++){ // end of first number, inclusive if(end1 > 0 && num[0] == '0') return false; for(int end2 = end1+1; end2+1<n;end2++){ int len1 = end1+1; int len2 = end2 - end1; if(len2 > 1 && num[end1+1] == '0') continue; if(helper(num.substr(0, len1), num.substr(end1+1,len2), num.substr(end2+1))){ return true; } } } return false; } private: bool helper(string a, string b, string num){ int carry = 0; while(num.length()>0){ string c = getSum(a,b); if(num.find(c) != 0) return false; num = num.substr(c.length()); a = b; b = c; } return true; } string getSum(string a, string b){ string res = ""; int carry = 0; int na = a.length(), nb = b.length(); for(int i = 0; i<max(na, nb); i++){ int c1 = (i<na)? a[na-1-i]-'0':0; int c2 = (i<nb)? b[nb-1-i]-'0':0; res = to_string( (c1+c2+carry)%10 ) + res; carry = (c1 + c2 + carry) / 10; } if(carry) res = "1"+res; return res; } };
No comments:
Post a Comment