leetcode做题笔记67

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

思路一：模拟题意

void reserve(char* s) {int len = strlen(s);for (int i = 0; i < len / 2; i++) {char t = s[i];s[i] = s[len - i - 1], s[len - i - 1] = t;}
}char* addBinary(char* a, char* b) {reserve(a);reserve(b);int len_a = strlen(a), len_b = strlen(b);int n = fmax(len_a, len_b), carry = 0, len = 0;char* ans = (char*)malloc(sizeof(char) * (n + 2));for (int i = 0; i < n; ++i) {carry += i < len_a ? (a[i] == '1') : 0;carry += i < len_b ? (b[i] == '1') : 0;ans[len++] = carry % 2 + '0';carry /= 2;}if (carry) {ans[len++] = '1';}ans[len] = '\0';reserve(ans);return ans;
}

时间复杂度O(n)，空间复杂度O(n)

分析：

本题要算二进制求和，可想到先将数组内的字符翻转后再进行相加。最后再将ans数组翻转得到答案。

总结：

本题考察对字符串的应用，掌握翻转的方法即可解决