989. 数组形式的整数加法

经典，很经典的题目，一步步渐进，直到最优解法

力扣原题链接（点我直达）

对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。

给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。

示例 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. 1 <= A.length <= 10000
  2. 0 <= A[i] <= 9
  3. 0 <= K <= 10000
  4. 如果 A.length > 1，那么 A[0] != 0

第一版，自己写的,时间和空间都一般

执行用时 :180 ms, 在所有 cpp 提交中击败了54.11%的用户

内存消耗 :13.7 MB, 在所有 cpp 提交中击败了39.51%的用户

vector<int> addToArrayForm(vector<int>& A, int K) { //52134
    
    vector<int> temp,res;
    
    while (K != 0) {

        temp.push_back(K % 10);
        K = K / 10;
    }

    int i = A.size() - 1,j=0;
    for (; i>=0 && j<temp.size(); --i,++j) {
        res.push_back(temp[j] + A[i]);  
    }
    if (j == temp.size() && i>=0) {
        for (   ; i >= 0;--i) {      
            res.push_back(A[i]);
        }
    }
    else if (i == -1 && j<temp.size())
    {
        for ( ; j<temp.size(); ++j) {
            res.push_back(temp[j]);
        }
    }

    for (i = 0; i < res.size(); ++i) {
        if (res[i] > 9) {
            res[i] = res[i] - 10;
            if (i != res.size() - 1) res[i + 1] = res[i + 1] + 1;
            else
                res.push_back(1);

        }

    }

    reverse(res.begin(), res.end());

    return res;
}

第二版，反而越改越差

执行用时 :204 ms, 在所有 cpp 提交中击败了47.70%的用户

内存消耗 :13.8 MB, 在所有 cpp 提交中击败了39.51%的用户

  vector<int> addToArrayForm(vector<int>& A, int K) {
   vector<int> temp;    
    while (K != 0) {

        temp.push_back(K % 10);
        K = K / 10;
    }

    int i = A.size() - 1,j=0;
    for (; i>=0 && j<temp.size(); --i,++j) {
        temp[j]=temp[j] + A[i]; 
    }



    if (j == temp.size() && i>=0) {
        for (   ; i >= 0;--i) {      
            temp.push_back(A[i]);
        }
    }

    for (i = 0; i < temp.size(); ++i) {
        if (temp[i] > 9) {
            temp[i] = temp[i] - 10;
            if (i != temp.size() - 1) temp[i + 1] = temp[i + 1] + 1;
            else
                temp.push_back(1);

        }

    }
    reverse(temp.begin(), temp.end());

    return temp;
    }

第三版，又改进了一下，快多了

执行用时 :136 ms, 在所有 cpp 提交中击败了95.79%的用户

内存消耗 :12.3 MB, 在所有 cpp 提交中击败了92.20%的用户

    vector<int> addToArrayForm(vector<int>& A, int K) {
    vector<int> temp;   
    while (K != 0) {

        temp.push_back(K % 10);
        K = K / 10;
    }

    reverse(A.begin(), A.end());
    size_t i=0;
    for ( ; i<A.size() && i<temp.size();++i) {
        A[i]=temp[i] + A[i];
        if (A[i] > 9 && i != A.size() - 1) {
            A[i] = A[i] - 10;
            A[i+ 1] = A[i + 1] + 1;
        } 
        else if (A[i] > 9 && i == A.size() - 1) {
            A[i] = A[i] - 10;
            A.push_back(1);
        }
    }


    if (i == temp.size()) {
    for (   ; i <A.size();++i) {         
        if (A[i] > 9 && i != A.size() - 1) {
            A[i] = A[i] - 10;
            A[i + 1] = A[i + 1] + 1;
        }
        if ( A[i] > 9 && i== A.size() - 1) {
            A[i] = A[i] - 10;
            A.push_back(1);
        }
        }
    }
    else if (i == A.size())
    {
        for (; i < temp.size(); ++i) {
            A.push_back(temp[i]);
        }
    }
    reverse(A.begin(), A.end());
    return A;
    }