一、题目
1、算法题目
“给定两个二进制字符串，返回他们的和，用二进制形式。”
题目链接：
来源：力扣（LeetCode）
链接：67. 二进制求和 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 非空 字符串且只包含数字 1 和 0。
示例 1： 输入: a = "11", b = "1" 输出: "100" 复制代码
示例 2： 输入: a = "1010", b = "1011" 输出: "10101" 复制代码
二、解题
1、思路分析
这个题可以使用列竖式的方法，末尾对齐，逐位相加，在二进制中逢二进一。
从最后一位开始遍历，使用一个变量表示上一位置的进位，然后将每一位的答案取模，重复上面步骤，直到所有位置的数字计算完毕。
2、代码实现
代码参考：
public class Solution { public string AddBinary(string a, string b) { char[] ac = a.ToCharArray(); Array .Reverse(ac); char[] bc = b.ToCharArray(); Array.Reverse(bc); int idx = 0; int temp = 0; bool needAdd1 = false; List<char> result = new List<char>(); while (true) { temp = 0; if (needAdd1) temp++; if (idx < ac.Length) temp += int .Parse (ac[idx].ToString ()); if (idx < bc.Length) temp += int .Parse ( bc[idx].ToString ()); result.Add (char.Parse ((temp % 2).ToString ())); needAdd1 = temp / 2 == 1; idx++; if (!needAdd1 && idx >= ac.Length && idx >= bc.Length) break; } result.Reverse(); char[] r = result.ToArray(); return new string(r); } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(n)
其中n是数组的长度，只需要遍历一遍数组即可求得答案。
空间复杂度： O(1)
只需要常数级别的空间存放变量。
三、总结
从个位开始相加 先将两个字符串反转。
从头开始依次相加 直到两个字符串的末尾且无进位。
得到的字符串再反转即可。
