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 <= A.length <= 100000 <= A[i] <= 90 <= K <= 10000- 如果
A.length > 1，那么A[0] != 0
第一版，自己写的,时间和空间都一般
执行用时 :180 ms, 在所有 cpp 提交中击败了54.11%的用户
内存消耗 :13.7 MB, 在所有 cpp 提交中击败了39.51%的用户
vector<int>addToArrayForm(vector<int>&A, intK) { //52134
vector<int>temp,res;
while (K!=0) {
temp.push_back(K%10);
K=K/10;
}
inti=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]);
}
}
elseif (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());
returnres;
}
第二版，反而越改越差
执行用时 :204 ms, 在所有 cpp 提交中击败了47.70%的用户
内存消耗 :13.8 MB, 在所有 cpp 提交中击败了39.51%的用户
vector<int>addToArrayForm(vector<int>&A, intK) {
vector<int>temp;
while (K!=0) {
temp.push_back(K%10);
K=K/10;
}
inti=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());
returntemp;
}
第三版，又改进了一下，快多了
执行用时 :136 ms, 在所有 cpp 提交中击败了95.79%的用户
内存消耗 :12.3 MB, 在所有 cpp 提交中击败了92.20%的用户
vector<int>addToArrayForm(vector<int>&A, intK) {
vector<int>temp;
while (K!=0) {
temp.push_back(K%10);
K=K/10;
}
reverse(A.begin(), A.end());
size_ti=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;
}
elseif (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);
}
}
}
elseif (i==A.size())
{
for (; i<temp.size(); ++i) {
A.push_back(temp[i]);
}
}
reverse(A.begin(), A.end());
returnA;
}
