306. Additive Number

eccozhou 发布于2019-08-16 10:36 / 3190人阅读

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用法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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