989-數(shù)組形式的整數(shù)加法

XBaron 發(fā)布于2019-08-19 11:33 / 1414人閱讀

摘要：前言的數(shù)組形式的整數(shù)加法對(duì)于非負(fù)整數(shù)而言，的數(shù)組形式是每位數(shù)字按從左到右的順序形成的數(shù)組。給定非負(fù)整數(shù)的數(shù)組形式，返回整數(shù)的數(shù)組形式。

前言

Weekly Contest 123的數(shù)組形式的整數(shù)加法：

對(duì)于非負(fù)整數(shù) X 而言，X 的數(shù)組形式是每位數(shù)字按從左到右的順序形成的數(shù)組。例如，如果 X = 1231，那么其數(shù)組形式為 [1,2,3,1]。
給定非負(fù)整數(shù) X 的數(shù)組形式 A，返回整數(shù) X+K 的數(shù)組形式。
示例1：
輸入：A = [1,2,0,0], K = 34
輸出：[1,2,3,4]
解釋：1200 + 34 = 1234
示例2：
輸入：A = [2,7,4], K = 181
輸出：[4,5,5]
解釋：274 + 181 = 455
示例3：
輸入：A = [2,1,5], K = 806
輸出：[1,0,2,1]
解釋：215 + 806 = 1021
示例4：
輸入：A = [9,9,9,9,9,9,9,9,9,9], K = 1
輸出：[1,0,0,0,0,0,0,0,0,0,0]
解釋：9999999999 + 1 = 10000000000
提示：

1 <= A.length <= 10000
0 <= A[i] <= 9
0 <= K <= 10000
如果 A.length > 1，那么 A[0] != 0

解題思路

此題解題思路類似兩數(shù)相加，而且leetcode官方也有此題的解答。需要注意的是需要先將兩個(gè)入?yún)⑥D(zhuǎn)換成鏈表后，按照兩數(shù)相加的解題步驟處理即可。

實(shí)現(xiàn)代碼

   /**
     * 989. 數(shù)組形式的整數(shù)加法
     * @param A
     * @param K
     * @return
     */
    public List addToArrayForm(int[] A, int K) {
        List result=new ArrayList<>();
        char[] chars=String.valueOf(K).toCharArray();
        int times=chars.length>A.length?chars.length:A.length;
        //將K轉(zhuǎn)成鏈表
        List kList=new LinkedList<>();
        for(int i=0;i) kList).addFirst(0);
        }
        //將A轉(zhuǎn)換成鏈表
        List aList=new LinkedList<>();
        for(int i=0;i) aList).addFirst(0);
        }
        int carry=0;//進(jìn)位
        for(int i=times-1;i>=0;i--){//逆序遍歷鏈表
            int k=kList.get(i);
            int a= aList.get(i);
            int num=k+a+carry;
            if(num>=10){//相加大于0則進(jìn)位
                carry=num/10;
                num=num%10;
            }else{
                carry=0;
            }
            //頭插法，將每一位的運(yùn)算放在數(shù)組首位
            result.add(0,num);
        }
        if(carry>0){//最后一位是否存在進(jìn)位
            result.add(0,carry);
        }
        return result;
    }