leetcode306. Additive Number

2shou 发布于2019-08-15 15:09 / 1140人阅读

摘要：为了减少无效遍历，我们可以在寻找第一个数字和第二个数字的时候及时终止。我们可以知道第一个数字的长度不应该超过字符串长度的一般，第二个数字的长度无法超过字符串长度减去第一个数字的长度。因此一旦遇到，在判断完作为加数时是否合法后，直接跳出循环。

题目要求

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);
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

专线服务超融合服务器 Additive 306云服务器 Leetcod LeetCode

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

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