P0989_AddToArrayFormOfInteger.java

package yyl.leetcode.p09;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

import yyl.leetcode.util.Assert;

/**
 * <h3>数组形式的整数加法</h3><br>
 * 对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。<br>
 * 给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。<br>
 * 
 * <pre>
 * 示例 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
 * </pre>
 * 
 * 提示： <br>
 * ├ 1 <= A.length <= 10000 <br>
 * ├ 0 <= A[i] <= 9 <br>
 * ├ 0 <= K <= 10000 <br>
 * └ 如果 A.length > 1，那么 A[0] != 0 <br>
 */
public class P0989_AddToArrayFormOfInteger {

    public static void main(String[] args) {
        Solution solution = new Solution();
        Assert.assertEquals(Arrays.asList(1, 2, 3, 4), //
                solution.addToArrayForm(new int[] { 1, 2, 0, 0 }, 34)//
        );
        Assert.assertEquals(Arrays.asList(4, 5, 5), //
                solution.addToArrayForm(new int[] { 2, 7, 4 }, 181)//
        );
        Assert.assertEquals(Arrays.asList(1, 0, 2, 1), //
                solution.addToArrayForm(new int[] { 2, 1, 5 }, 806)//
        );
        Assert.assertEquals(Arrays.asList(1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0), //
                solution.addToArrayForm(new int[] { 9, 9, 9, 9, 9, 9, 9, 9, 9, 9 }, 1)//
        );
        Assert.assertEquals(Arrays.asList(2, 3), //
                solution.addToArrayForm(new int[] { 0 }, 23)//
        );
    }

    // 逐位相加
    // 逐位将数字加在一起，从低位到高位依次计算。
    // 因为 K 是一个 int ，可以 K 加入数组表示的数的最低位
    // 时间复杂度：O(max⁡(n,log⁡K))，其中 n 为数组的长度。
    // 空间复杂度：O(1)，不计算返回值所占空间。
    static class Solution {
        public List<Integer> addToArrayForm(int[] A, int K) {
            LinkedList<Integer> answer = new LinkedList<>();
            for (int i = A.length - 1; i >= 0; i--) {
                K = A[i] + K;
                answer.addFirst(K % 10);
                K /= 10;
            }
            for (; K > 0; K /= 10) {
                answer.addFirst(K % 10);
            }
            return answer;
        }
    }
}