首页 > 代码库 > [LeetCode] Add Binary

[LeetCode] Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100"

思路:时间复杂度O(n), 空间复杂度O(1)

 1 class Solution { 2 public: 3     string addBinary(string a, string b) { 4         string result; 5         if (a.size() == 0 || b.size() == 0) { 6             return a.size() == 0 ? b : a; 7         } 8          9         int carry  = 0;10         int i = a.size() - 1;11         int j = b.size() - 1;12         while (i >= 0 || j >= 0) {13             const int a_val = i >= 0 ? a[i--] - 0: 0;14             const int b_val = j >= 0 ? b[j--] - 0: 0;15             int temp_sum = a_val + b_val + carry;16             result.push_back((temp_sum % 2) + 0);17             carry = temp_sum / 2;18         }19         20         if (carry == 1) result.push_back(1);21         reverse(result.begin(), result.end());22         return result;23     }24 };

 

[LeetCode] Add Binary