306. Additive Number
发布日期：2021-05-09 02:50:43
浏览次数：13
分类：博客文章
本文共 2381 字，大约阅读时间需要 7 分钟。
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, 190. 1 + 99 = 100, 99 + 100 = 199
Approach #1:
class Solution {public: bool isAdditiveNumber(string num) { if (num.length() < 3) return false; // if (num == "000") return true; // cout <<"num.length() = " << num.length() << endl; for (int i = 1; i <= num.length() / 2; ++i) { // the first number's length; if (num[0] == '0' && i > 1) return false; string s_first = num.substr(0, i); long first = stol(s_first); // cout << "first = " << s_first << endl; for (int j = 1; num.length()-i-j >= max(i, j); ++j) { string s_second = num.substr(i, j); if (j > 1 && s_second[0] == '0') break; long second = stol(s_second); // cout << "second = " << s_second << endl; if (isValid(first, second, i+j, num)) { return true; } } } return false; } private: bool isValid(long first, long second, int start, string num) { // cout << "start = " << start << endl; // cout << first << ' ' << second << endl; if (start == num.length()) return true; second = second + first; first = second - first; // cout << first << ' ' << second << endl; string sum = to_string(second); // cout << "sum = " << sum << endl; return C_startWith(sum, start, num) && isValid(first, second, start+sum.length(), num); } bool C_startWith(string sum, int start, string num) { int len = sum.length(); string temp = num.substr(start, len); return temp == sum; }};
发表评论
最新留言
白红宇的个人博客 - 记录点点滴滴的事 - 您是第 461039084 位访客