欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[leetcode] 306. Additive Number 解题报告

程序员文章站 2022-05-10 15:13:31
题目链接:https://leetcode.com/problems/additive-number/ Additive number is a string whose di...

题目链接:https://leetcode.com/problems/additive-number/

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should containat leastthree numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

For example:
"112358"is an additive number because 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
"199100199"is also an additive number, the additive sequence is:1, 99, 100, 199.
1 + 99 = 100, 99 + 100 = 199

Note:Numbers in the additive sequencecannothave leading zeros, so sequence1, 2, 03or1, 02, 3is invalid.

Given a string containing only digits'0'-'9', write a function to determine if it's an additive number.

Follow up:
How would you handle overflow for very large input integers?



思路: 一个基本的思想就是确定了第一个和第二个数之后, 以后的数就是验证了, 所以只要枚举第一和第二个数, 然后不断验证下面的字符串子串是否是前两个数的和即可. 因为数字可能超出整数的范围, 因此在验证一个数是否是另外两个和的时候, 可以用字符串相加来模拟整数相加. 另外需要注意的是'0'字符, 如果他在子串的首位, 那么他只能以"0"的形式存在, 并且"0"只可能作为第一个数或者第二个数.

代码如下:

class Solution {
public:
    string add(string s1, string s2)
    {
        string result;
        int flag = 0, i = s1.size()-1, j = s2.size()-1;
        while(i >=0 || j >=0)
        {
            int num1=0, num2=0;
            if(i >=0) num1 = s1[i]-'0';
            if(j >= 0) num2 = s2[j]-'0';
            result.insert(result.begin(), '0'+(num1+num2+flag)%10);
            flag = (num1+num2+flag)/10;
            i--, j--;
        }
        if(flag == 1) result.insert(result.begin(), '1');
        return result;
    }
    
    bool DFS(string num, string num1, string num2)
    {
        if(num.size()==0 || num[0] == '0') return false;
        for(int i =0; i