小白学习之306累加数

题目的链接在这里：https://leetcode-cn.com/problems/additive-number/

---

题目大意

累加数是一个字符串，组成它的数字可以形成累加序列。

一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。

给定一个只包含数字 ‘0’-‘9’ 的字符串，编写一个算法来判断给定输入是否是累加数。

说明: 累加序列里的数不会以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。

---

一、示意图

二、解题思路

java实现（网上参考的）

代码如下：

class Solution {
    public boolean isAdditiveNumber(String num) {
    //java双百解法 暴力穷举加法元素可能出现的位置，再求和
    int len=num.length();
    //先将字符串转化为int数组
    int []nums=new int [len];
    for(int i=0;i<len;i++){
         nums[i]=num.charAt(i)-'0';
    }
    //加法第一个元素的起点是0
    int l=0;
    //第一层遍历：第二个元素的起点
    for(int r=1;r<=(len-1)/2;r++){
        //第二个元素的首位为0，这种特殊情况只看出现在遍历的第一层中
        //一旦开始第二层遍历，必然不会出现这种情况
        //在这种情况下，直接将0当做第二个元素，无论成功与否都没必要再扩展第二个
        if(nums[r]==0){
            if(judgeSum(nums,l,r,r+1)){
                return true;
            }
            //再就是不能成功，需要开始第二层遍历
            continue;
        }
        //开始了第二层的遍历，也就是和的起点，这里加了两个约束条件，（1）s不能超出末尾
        //(2)s到末尾的长度至少应该容纳和，而和的最小长度可以表示为两个相加元素的最长长度
        for(int s=r+1;s<len&&len-s>=Math.max(r-1,s-r);s++){
            //首先排除第一位是0的情况
            if(nums[s]==0){
                continue;
            }
            if(judgeSum(nums,l,r,s)){
                return true;
            }
        }
    }
    return false;
    }
    //再写对应的函数 参数首先是nums，然后是两个元素的起点和和的起点
    private boolean judgeSum(int[]nums,int i,int j ,int k){
        //求两个元素的和
        int p=0,a=j-1,b=k-1;
        int []sum=new int[Math.max(j-i+1,k-j+1)];
        int index=sum.length-1;
        while(a>=i||b>=j){
            int s=(a>=i?nums[a--]:0)+(b>=j?nums[b--]:0)+p;
            sum[index--]=s%10;
            p=s/10;
        }
        if(p!=0){
            sum[0]=p;
        }
        //验证和是否能与字符串中的数字对上
        a=sum[0]==0?1:0;
        int c=k;
        while(a<sum.length&&c<nums.length){
            if(sum[a]==nums[c]){
                a++;
                c++;
            }
            else{
                //验证不通过
                return false;
            }
        }
        //和已经达到末尾，但是还没有验证结束，计算有误
        if(a!=sum.length){
            return false;
        }
        //如果和已经达到末尾，表示计算结束
        if(c==nums.length){
            return true;
        }
        //接着这次的位置继续递归
        return judgeSum(nums,j,k,c);


    }
}

本文地址：https://blog.csdn.net/qq_41115379/article/details/109639207