如果你想在校招中顺利拿到更好的offer,阿秀建议你多看看前人的经验 ,比如准备 、简历 、实习 、上岸经历 、校招总结 、阿里、字节、腾讯、美团等一二线大厂真实面经 、也欢迎来一起参加秋招打卡活动 等;如果你是计算机小白,学习/转行/校招路上感到迷茫或者需要帮助,可以点此联系阿秀;免费分享阿秀个人学习计算机以来的收集到的好资源,点此白嫖;如果你需要《阿秀的学习笔记》网站中求职相关知识点的PDF版本的话,可以点此下载
# 989. 数组形式的整数加法
经典,很经典的题目,一步步渐进,直到最优解法
力扣原题链接(点我直达) (opens new window)
对于非负整数 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
1
2
3
2
3
解释 2:
输入:A = [2,7,4], K = 181
输出:[4,5,5]
解释:274 + 181 = 455
1
2
3
2
3
示例 3:
输入:A = [2,1,5], K = 806
输出:[1,0,2,1]
解释:215 + 806 = 1021
1
2
3
2
3
示例 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
2
3
2
3
提示:
1 <= A.length <= 10000
0 <= A[i] <= 9
0 <= 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, 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# 第二版,反而越改越差
执行用时 :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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 第三版,又改进了一下,快多了
执行用时 :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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44