LeetCode.989-數組形式的整數做加法(Add to Array-Form of Integer)

這是悅樂書的第371次更新，第399篇原創

01 看題和準備

今天介紹的是

LeetCode

算法題中

Easy

級别的第

233

題（順位題号是

989

）。對于非負整數

X

，

X

的數組形式是從左到右順序的數字數組。例如，如果

X = 1231

，則數組形式為

[1,2,3,1]

。

給定非負整數

X

的數組形式

A

，傳回整數

X + K

的數組形式。例如：

輸入：A = [1,2,0,0]，K = 34

輸出：[1,2,3,4]

說明：1200 + 34 = 1234

輸入：A = [2,7,4]，K = 181

輸出：[4,5,5]

說明：274 + 181 = 455

輸入：A = [2,1,5]，K = 806

輸出：[1,0,2,1]

說明：215 + 806 = 1021

輸入：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。

02 第一種解法

題目的意思是要我們把

K

（低位到高位）每一位數加到

A

（從後往前）中對應位上，最後輸出一個

List

思路：先處理

K

，每次拿

A

的個位數，使用對

10

取餘得到，再從

A

中取一位數出來（從後往前），兩數相加，需要判斷是否有進位産生，将和添加進

List

中，

K

再除以10，切換到新的個位數，直到

K

等于0。處理完

K

後，如果

A

中還有數沒處理完，需要再處理下，在前面處理

K

時遺留的進位依舊需要參與運算，直到處理完

A

中所有元素。最後，如果存進位的變量還有值，則需要将其添加進

List

中。因為處理資料是從後往前的順序，是以需要将

List

反轉，借助

Collections

的

reverse

方法完成。

public List<Integer> addToArrayForm(int[] A, int K) {
    List<Integer> result = new ArrayList<Integer>(); 
    int i = A.length-1, tem = 0;
    while (K > 0) {
        // i需要判斷一次，因為A的長度可能比K的位數小
        int current = K%10 + (i >=0 ? A[i--] : 0) + tem;
        // 大于10會産生進位
        if (current >= 10) {
            current -= 10;
            tem = 1;
        } else {
            tem = 0;
        }
        result.add(current);
        K /= 10;
    }
    // 如果K已經處理完了，但是A中還有數沒有處理
    while (i >= 0) {
        // 依舊需要判斷進位
        if (A[i]+tem >= 10) {
            result.add(A[i]+tem-10);
            tem = 1;
        } else {
            result.add(A[i]+tem);
            tem = 0;
        }
        i--;
    }
    // 判斷最高位是否存在進位
    if (tem != 0) {
        result.add(tem);
    }
    // 反轉result
    Collections.reverse(result);
    return result;
}
           

03 第二種解法

我們還可以對第一種解法再簡化下。

思路：将A中每次從後往前取的數，加到

K

上面（

K

最大為10000，不存在越界問題），然後每次取

K

的最後一位數（借助取餘），計算完後将

K

除以10，直到

K

等于0。

public List<Integer> addToArrayForm2(int[] A, int K) {
    List<Integer> result = new ArrayList<Integer>(); 
    int i = A.length-1, tem = K;
    while (i >= 0 || tem > 0) {
        if (i >= 0) {
            tem += A[i--];
        }
        result.add(tem%10);
        tem /= 10;
    }
    // 反轉result
    Collections.reverse(result);
    return result;
}
           

04 小結

算法專題目前已連續日更超過七個月，算法題文章239+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。

以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！