<cite id="am4wa"></cite>

306. Additive Number

eccozhou 發布于2019-08-16 10:36 / 3196人閱讀

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.

public class Solution {
    public boolean isAdditiveNumber(String num) {
        if(num == null || num.length() == 0) return false;
        int n = num.length();
        for(int i = 1; i <= n/2; i++){                            // len of x1
            for(int j = 1; Math.max(i, j) + i + j <= n; j++) {    // len of x2
                if(isValid(i, j, num)) return true;
            }
        }
        return false;
    }
    
    public boolean isValid(int i, int j, String num){
        if(i > 1 && num.charAt(0) == "0") return false;
        if(j > 1 && num.charAt(i) == "0") return false;
        String sum;
        Long x1 = Long.parseLong(num.substring(0, i));
        Long x2 = Long.parseLong(num.substring(i, i+j));
        for(int start = i + j; start < num.length(); start += sum.length()){
            x2 = x1 + x2;            // sum of x1 and x2, and became new x2
            x1 = x2 - x1;            // last x2 is new x1
            sum = x2.toString();
            if(!num.startsWith(sum, start)) return false;
        }
        return true;
    }
}

GPU云服務器云服務器 Additive 306云服務器 number number用法

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

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

leetcode306. Additive Number

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

2shou 2019-08-15 15:09 評論0 收藏0
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
[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