67. Add Binary
Analysis
二进制加法，应该不难哈。
Code
因为题目给定的 a 和 b 的长度规模在 $[1, 10^4]$，所以不能转换成十进制求和后再转换为二进制。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
45
46
47
48
49
50
51
52
53
54
55class Solution {
public:
string addBinary(string a, string b) {
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
string ans;
int len1 = a.length(), len2 = b.length();
int p1 = 0, p2 = 0, carry = 0;
while(p1 < len1 && p2 < len2) {
int tmp = a[p1++] + b[p2++] + carry - 2 * '0';
if(tmp == 0) {
ans.push_back('0');
carry = 0;
} else if(tmp == 1) {
ans.push_back('1');
carry = 0;
} else if(tmp == 2) {
ans.push_back('0');
carry = 1;
} else {
ans.push_back('1');
carry = 1;
}
}
while(p1 < len1) {
int tmp = carry + a[p1++] - '0';
if(tmp == 0) {
ans.push_back('0');
carry = 0;
} else if(tmp == 1) {
ans.push_back('1');
carry = 0;
} else {
ans.push_back('0');
carry = 1;
}
}
while(p2 < len2) {
int tmp = carry + b[p2++] - '0';
if(tmp == 0) {
ans.push_back('0');
carry = 0;
} else if(tmp == 1) {
ans.push_back('1');
carry = 0;
} else {
ans.push_back('0');
carry = 1;
}
}
if(carry) ans.push_back('1');
reverse(ans.begin(), ans.end());
return ans;
}
};
先逆置字符串会方便计算，因为不知道那个数更大，所以干脆都写一个循环算了。
嗯，现在把重复的部分封装一下：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
45
46class Solution {
void addremains(string &s, int &pos, string &ans, int &carry) {
while(pos < s.length()) {
int tmp = carry + s[pos++] - '0';
if(tmp == 0) {
ans.push_back('0');
carry = 0;
} else if(tmp == 1) {
ans.push_back('1');
carry = 0;
} else {
ans.push_back('0');
carry = 1;
}
}
}
public:
string addBinary(string a, string b) {
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
string ans;
int len1 = a.length(), len2 = b.length();
int p1 = 0, p2 = 0, carry = 0;
while(p1 < len1 && p2 < len2) {
int tmp = a[p1++] + b[p2++] + carry - 2 * '0';
if(tmp == 0) {
ans.push_back('0');
carry = 0;
} else if(tmp == 1) {
ans.push_back('1');
carry = 0;
} else if(tmp == 2) {
ans.push_back('0');
carry = 1;
} else {
ans.push_back('1');
carry = 1;
}
}
if(p1 != len1) addremains(a, p1, ans, carry);
if(p2 != len2) addremains(b, p2, ans, carry);
if(carry) ans.push_back('1');
reverse(ans.begin(), ans.end());
return ans;
}
};
感觉这样写不太美观哈。
实际上，也不是一定非要写到外面去，carry 对应的不同情况也可以通过取余运算和除运算汇总到一起。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
string addBinary(string a, string b) {
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
string ans;
int len1 = a.length(), len2 = b.length();
int maxlen = max(len1, len2), carry = 0;
for(int i = 0; i < maxlen; i++) {
carry += i < len1 ? (a[i] == '1') : 0;
carry += i < len2 ? (b[i] == '1') : 0;
ans.push_back((carry % 2) ? '1' : '0');
carry /= 2;
}
if(carry) ans.push_back('1');
reverse(ans.begin(), ans.end());
return ans;
}
};
如果题目限制了四则运算，那这个题还可以用位运算来解决，之后补一下吧。
989. Add to Array-Form of Integer
Analysis
一个以数组形式储存的整数和一个 int 型整数，计算二者之和。
Code
因为 k 的取值范围是 $[1, 10^4]$，所以 k 最多也就是 5 位，那么实际上只用计算数组的最后几位与 k 的和，然后在加回数组上去就可以了。但是又可能存在 num 比 k 小的情况，这样综合考虑下来，不如直接两个数组做大数加法得了😓。
按照上一个题的思路来完成就可以了：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public:
vector<int> addToArrayForm(vector<int>& num, int k) {
vector<int> knum, ans;
while(k) {
knum.push_back(k % 10);
k /= 10;
}
reverse(num.begin(), num.end());
int carry = 0, size1 = num.size(), size2 = knum.size();
int maxsize = max(size1, size2);
for(int i = 0; i < maxsize; i++) {
carry += i < size1 ? num[i] : 0;
carry += i < size2 ? knum[i] : 0;
ans.push_back(carry % 10);
carry /= 10;
}
if(carry) ans.push_back(carry);
reverse(ans.begin(), ans.end());
return ans;
}
};
但是针对这个问题而言，真的需要用一个数组来保存 k 吗？应该是不需要的吧。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public:
vector<int> addToArrayForm(vector<int>& num, int k) {
vector<int> ans;
int size = num.size();
for(int i = size - 1; i >= 0; i--) {
int sum = num[i] + k % 10;
k /= 10;
if(sum >= 10) {
k++;
sum -= 10;
}
ans.push_back(sum);
}
while(k) {
ans.push_back(k % 10);
k /= 10;
}
reverse(ans.begin(), ans.end());
return ans;
}
};
看了下官方的题解，这个题好像还有一种思路，那就是直接把 k 加到最后一位，让个位数字为这一位的结果，剩下的数字在加上前一位：1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public:
vector<int> addToArrayForm(vector<int>& num, int k) {
int size = num.size();
vector<int> ans;
for(int i = size - 1; i >= 0 || k > 0; i--, k /= 10) {
if(i >= 0) k += num[i];
ans.push_back(k % 10);
}
reverse(ans.begin(), ans.end());
return ans;
}
};
这段代码好像看起来更精简一点。
Summary
这两天做的题怎么都是这种大数四则运算的题目？感觉没什么趣味性...
