leedcode每日一题——1.10

累加数

• 题目介绍
  

• 思路分析

  1. 在考虑这道题时，我们需要思考决定一个有效的累加序列的元素是什么，我们知道一个有效的累加序列中的第三个数等于前两个数相加，而题目中将数以字符串的形式输入。因此连接前后的关键是第二个数，因为一旦直到第二个数以后，第一个数的末尾下标(firstEnd)等于第二个元素的起始下标(secondStart)减1，第三个数的开头下标(thirdStart)等于第二个元素的末尾下标(secondEnd)加1。
  2. 因此我们需要以第二个元素为基准进行遍历，在遍历的过程中我们需要考虑0的特殊情况，由题得一个数没有前导0。
  3. 同时我们需要整数的溢出，因为数组的最长长度是35超过了long型数据的最大范围，所以我们要用高精度加法去代替普通加法。所谓高精度加法就是说利用数组的形式实现数组的相加。因为要考虑数组的进位，所以我们需要将一个整数的位数逆序存储到数组中进行加法运算。
  4. 一个高精度加法的具体过程：
     

• 相关代码片段

class Solution {
   public boolean isAdditiveNumber(String num) {
        int len = num.length();
        //以第二个数为基准进行数组的遍历
        for (int secondStart = 1; secondStart < len - 1; secondStart  ) {
        	//保证数组当中第一个数的起始下标为0且第二个及之后的下标为不为0
            if (num.charAt(0) == '0' && secondStart != 1) {
                break;
            }
            for (int secondEnd = secondStart; secondEnd < len - 1; secondEnd  ) {
            	//保证数组当中第二个数的起始下标为0且第二个及之后的下标不为0
                if (num.charAt(secondStart) == '0' && secondEnd != secondStart) {
                    break;
                }
                if (isAdd(secondStart,secondEnd,num)){
                    return true;
                }
            }
        }
        return false;
    }
	/**
	以第二个数组为基准进行遍历
	*/
    public boolean isAdd(int secondStart, int secondEnd, String num) {
        int len = num.length();
        //第一次遍历时第一个数的起始下标为0,末尾下标为第二个数的起始下标-1
        int firstStart = 0;
        int firstEnd = secondStart - 1;
        while(secondEnd < len - 1) {
        	//根据第一个数和第二个数得到高精度加法对应的第三个数
            String third = addString(firstStart, firstEnd, secondStart, secondEnd, num);
            //第三个数的起始下标为第二个数的末尾下标 1
            //末尾下标为第三个数的起始下标加第三个数的长度
            int thirdStart = secondEnd   1;
            int thirdEnd = thirdStart   third.length() - 1;
            if(thirdEnd >= len || !num.substring(thirdStart,thirdEnd   1).equals(third)){
                break;
            }
            if(thirdEnd == len - 1){
                return true;
            }
            //转换第一个数和第二个数的起始下标和末尾下标
            firstStart = secondStart;
            firstEnd = secondEnd;
            secondStart = thirdStart;
            secondEnd = thirdEnd;
        }
        return false;
    }
	/**
	高精度加法
	*/
    public String addString(int firstStart,int firstEnd,int secondStart, int secondEnd, String num) {
        int len = num.length();
        StringBuilder third = new StringBuilder();
        int p = 0, cur = 0;
        while (secondEnd >= secondStart||firstEnd >= firstStart||cur != 0){
            if(firstEnd >= firstStart){
                cur  = num.charAt(firstEnd) - '0';
                firstEnd--;
            }
            if(secondEnd >= secondStart){
                cur  = num.charAt(secondEnd) - '0';
                secondEnd--;
            }
            p = cur % 10;
            third.append((char) (p '0'));
            cur/=10;
        }
        third.reverse();
        return third.toString();
    }
}

这篇好文章是转载于：学新通技术网