simulation/add-binary
优质
小牛编辑
127浏览
2023-12-01
Add Binary
描述
Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return 100
.
分析
手工模拟大整数加法。
代码
// Add Binary
// Time Complexity: O(max(m,n)), Space Complexity: O(max(m,n))
class Solution {
public String addBinary(String a, String b) {
StringBuilder result = new StringBuilder();
int i = a.length() - 1, j = b.length() - 1, carry = 0;
while(i >= 0 || j >= 0 || carry > 0) {
int x = i < 0 ? 0 : a.charAt(i--) - '0';
int y = j < 0 ? 0 : b.charAt(j--) - '0';
int sum = x + y + carry;
result.append(sum % 2);
carry = sum / 2;
}
return result.reverse().toString();
}
}
// Add Strings
// Time Complexity: O(max(m,n)), Space Complexity: O(max(m,n))
class Solution {
public:
string addBinary(string a, string b) {
string result;
int i = a.length() - 1, j = b.length() - 1, carry = 0;
while(i >= 0 || j >= 0 || carry > 0) {
int x = i < 0 ? 0 : a[i--] - '0';
int y = j < 0 ? 0 : b[j--] - '0';
int sum = x + y + carry;
result.insert(result.begin(), (sum % 2) + '0');
carry = sum / 2;
}
return result;
}
};