欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

小白学习之306累加数

程序员文章站 2022-07-10 19:36:12
题目的链接在这里:https://leetcode-cn.com/problems/additive-number/目录题目大意一、示意图二、解题思路java实现(网上参考的)题目大意累加数是一个字符串,组成它的数字可以形成累加序列。一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外,字符串中的其他数都等于它之前两个数相加的和。给定一个只包含数字 ‘0’-‘9’ 的字符串,编写一个算法来判断给定输入是否是累加数。说明: 累加序列里的数不会以 0 开头,所以不会出现 1, 2,...

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


题目大意

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

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

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

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


一、示意图

小白学习之306累加数

二、解题思路

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


    }
}

小白学习之306累加数

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

相关标签: LeetCode