推 MurasakiSion: c++大師 02/14 08:18
推 a9486l: 大師 02/14 08:20
→ Rushia: 大師 02/14 11:53
67. Add Binary
給定兩個二進位字串 a, b，
求 a+b 的後的二進位字串。
Example 1:
Input: a = "11", b = "1"
Output: "100"
Explanation: a = 3, b = 1, 相加後為 4 (100)
Example 2:
Input: a = "1010", b = "1011"
Output: "10101"
Explanation: a = 10, b = 11, 相加後為 21 (10101)
解題思路:
很基本的大數運算，
直接拿兩個二進位字串做直式加法就行了，
先把字串反轉後對齊末端，
從後面開始做加法再看要不要進位，
最後再把答案反轉過來。
C++ code:
class Solution {
public:
string addBinary(string a, string b) {
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
int size = max(a.size(), b.size());
string c(size + 1, '0');
for(int i = 0; i < size; i++){
if(i < a.size()) c[i] += a[i] - '0';
if(i < b.size()) c[i] += b[i] - '0';
if(c[i] > '1'){
c[i] -= 2;
c[i+1] += 1;
}
}
if(c.back() == '0') c.pop_back();
reverse(c.begin(), c.end());
return c;
}
};
---
這題直接用別的語言寫應該會簡單很多
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.229.216 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1676333759.A.3B0.html