“给定两个二进制字符串,返回他们的和,用二进制形式。”
题目链接:
来源:力扣(LeetCode)
链接:67. 二进制求和 - 力扣(LeetCode) (leetcode-cn.com)
给你两个二进制字符串,返回它们的和(用二进制表示)。
输入为 非空 字符串且只包含数字 1
和 0
。
示例 1:
输入: a = "11", b = "1"
输出: "100"
示例 2:
输入: a = "1010", b = "1011"
输出: "10101"
这个题可以使用列竖式的方法,末尾对齐,逐位相加,在二进制中逢二进一。
从最后一位开始遍历,使用一个变量表示上一位置的进位,然后将每一位的答案取模,重复上面步骤,直到所有位置的数字计算完毕。
代码参考:
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);
}
}
时间复杂度 : O(n)
其中n是数组的长度,只需要遍历一遍数组即可求得答案。
空间复杂度: O(1)
只需要常数级别的空间存放变量。
从个位开始相加 先将两个字符串反转。
从头开始依次相加 直到两个字符串的末尾且无进位。
得到的字符串再反转即可。