989. Add to Array-Form of Integer

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

解法一（暴力搜索，低效，超时错误）

//时间复杂度O(n), 空间复杂度O(1)
class Solution {
public:vector<int> addToArrayForm(vector<int>& A, int K) {int i = A.size() - 1, carry = 0;while(i >= 0) {if(K == 0 && carry == 0) break;int sum = A[i] + K % 10 + carry;A[i] = sum % 10;carry = sum / 10;K /= 10;i--;}if(K == 0) {if(carry > 0) A.insert(A.begin(), 1);}else {if(carry > 0) K++;vector<int> tempVec;while(K > 0) {tempVec.push_back(K % 10);K /= 10;}A.insert(A.begin(), tempVec.rbegin(), tempVec.rend());}return A;}
};

总结：

和之前的链表加法类似，只是链表的尾插变成了数组头插，效率有所下降。