leetcode306. Additive Number

2shou 發布于2019-08-15 15:09 / 1234人閱讀

摘要：為了減少無效遍歷，我們可以在尋找第一個數字和第二個數字的時候及時終止。我們可以知道第一個數字的長度不應該超過字符串長度的一般，第二個數字的長度無法超過字符串長度減去第一個數字的長度。因此一旦遇到，在判斷完作為加數時是否合法后，直接跳出循環。

題目要求

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.

思路和代碼

這里涉及一個廣度優先遍歷，首先嘗試所有合適的第一個數字和第二個數字，然后在此基礎上繼續判斷后序的字符串是否是一個Additive Number。

為了減少無效遍歷，我們可以在尋找第一個數字和第二個數字的時候及時終止。我們可以知道第一個數字的長度不應該超過字符串長度的一般，第二個數字的長度無法超過字符串長度減去第一個數字的長度。

還有一個特殊情況是以0為開頭。這里我們只有當取0時是合法的。因此一旦遇到0，在判斷完0作為加數時是否合法后，直接跳出循環。

    public boolean isAdditiveNumber(String num) {
        if(num==null || num.length() < 3) return false;
        for(int i = 1 ; i<=num.length()/2; i++){
            //如果以0開頭，則只能取0作為加數
            if(num.charAt(0)=="0" && i>1) break;
            String s1 = num.substring(0, i);
            long num1 = Long.parseLong(s1);
            for(int j = i+1 ; j<=num.length()-i ; j++){
                //如果以0開頭，則只能取0作為加數
                if(num.charAt(i)=="0" && j>i+1) break;
                String s2 = num.substring(i, j);
                long num2 = Long.parseLong(s2);
                //遞歸判斷
                if(isAdditiveNumber(num.substring(j), num1, num2)){
                    return true;
                }
            }
        }
        return false;
    }
    
    
    private boolean isAdditiveNumber(String num, long num1, long num2){
        //如果剩余長度為0，說明之前都是AdditiveNumber，返回true
        if(num.length()==0) return true;
        long add = num1 + num2;
        String adds = add + "";
        //遞歸判斷
        return num.startsWith(adds) && isAdditiveNumber(num.substring(adds.length()), num2, add);
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

云服務器 GPU云服務器 Additive 306云服務器 Leetcod LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/68893.html

LeetCode 306. Additive Number

摘要：描述累加數是一個字符串，組成它的數字可以形成累加序列。一個有效的累加序列必須至少包含個數。說明累加序列里的數不會以開頭，所以不會出現或者的情況。示例輸入輸出解釋累加序列為。 LeetCode 306. Additive Number Description Additive number is a string whose digits can form additive sequen...

GeekQiaQia 2019-07-31 10:03 評論0 收藏0
306. Additive Number

摘要：題目解答不越界長度的當可以走到后面沒有和了的時候，說明這個滿足條件直接可以知道這個是不是存在于中越界長度的越界長的度題目：Additive number is a string whose digits can form additive sequence. A valid additive sequence should contain at least three numbers...

dkzwm 2019-08-14 14:23 評論0 收藏0
306. Additive Number

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 addi...

eccozhou 2019-08-16 10:36 評論0 收藏0
[LeetCode] Additive Number

Additive Number 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 ...

yibinnn 2019-08-14 16:38 評論0 收藏0
容器最大盛水量

摘要：容器最大盛水量給定個非負整數，，，，其中每個表示坐標，處的點。找到兩條線，它們與軸一起形成一個容器，使得容器含有最多的水。容器最大盛水量 Container With Most Water 給定n個非負整數a1，a2，...，an，其中每個表示坐標（i，ai）處的點。繪制n條垂直線，使得線i的兩個端點在（i，ai）和（i，0）處。找到兩條線，它們與x軸一起形成一個容器，使得容器...

luckyw 2019-07-25 12:04 評論0 收藏0