leetcode 306. Additive Number 加法数的判断 + 一个典型的DFS深度优先遍地问题

亦凉 2022-06-06 23:37 137阅读 0赞

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.

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 sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is 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?

题意很简单，是一个典型的深度优先遍历问题，直接DFS即可。

**注意加法可能造成整数的溢出，所以要注意使用long等类型，同时计算结果的比较我们使用字符串来处理，这样比较容易处理各种情况，这一点值得学习，这是一道相当经典的深度优先遍历DFS的做法，十分值得学习，必须要掌握**

代码如下：

/*
     * 我这样写挺舒服的
     * 就这样写吧，本质上就是一个DFS遍历
     * 
     * */
    class Solution 
    {
        public boolean isAdditiveNumber(String num) 
        {
            if(num==null || num.length()<=2)
                return false;
    
            //遍历构造三个数据
            for(int i=1;i<num.length();i++)
            {
                String num1=num.substring(0,i);
                if(num1.charAt(0)=='0' && num1.length()>=2)
                    continue;
                for(int j=i+1;j<num.length();j++)
                {
                    String num2=num.substring(i,j);
                    if(num2.charAt(0)=='0' && num2.length()>=2)
                        continue;
                    String num3=num.substring(j);
                    if(dfs(num1,num2,num3))
                        return true;
                }
            }
            return false;
        }
    
        private boolean dfs(String num1, String num2, String num3)
        {
            //第三个num3位空的时候直接返回true
            if(num3==null || num3.length()<=0)
                return true;
            else 
            {
                //len为-1表示false，否者继续递归尝试
                int len=add(num1,num2,num3);
                if(len>=1)
                {
                    num1=num2;
                    num2=num3.substring(0,len);
                    num3=num3.substring(len);
                    return dfs(num1, num2, num3);
                }else 
                    return false;
            }
        }
        //处理两个数据相加的问题，这里使用字符串匹配来做
        private int add(String num1, String num2, String num3) 
        {
            long res = Long.parseLong(num1) + Long.parseLong(num2);
            String one=res+"";
    
            if(one.length()>num3.length())
                return -1;
            else if(num3.startsWith(one))
                return one.length();
            else 
                return -1;
        }
    }

下面是C++的做法就是一个DFS深度优先遍历的做法，要点就是先找到两个数字，然后递归求解即可

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        bool isAdditiveNumber(string num) 
        {
            if (num.length() <= 2)
                return false;
    
            for (int i = 1; i <= num.length() - 2; i++)
            {
                for (int j = i; j <= num.length() - 2; j++)
                {
                    string a = num.substr(0, i);
                    string b = num.substr(i, j - i + 1);
                    string c = num.substr(j + 1);
                    if (dfs(a, b, c) == true)
                        return true;
                }
            }
            return false;
        }
    
        bool dfs(string a, string b, string c)
        {
            if (a.length() <= 0 || b.length() <= 0 || b.length() <= 0)
                return false;
            else if (a[0] == '0' && a.length() >= 2 || b[0] == '0' && b.length() >= 2)
                return false;
            else
            {
                string res = add(a, b);
                if (res == c)
                    return true;
                else if (res.length() > c.length())
                    return false;
                else
                {
                    string tmp = c.substr(0, res.length());
                    if (tmp == res)
                    {
                        a = b;
                        b = res;
                        c = c.substr(res.length());
                        return dfs(a, b, c);
                    }
                    else
                        return false;
                }
            }
    
        }
    
        string add(string a, string b)
        {
            long long res = stoll(a) + stoll(b);
            return to_string(res);
        }
    };