C#LeetCode刷题之#67-二进制求和（Add Binary）

问题

给定两个二进制字符串，返回他们的和（用二进制表示）。

输入为非空字符串且只包含数字 1 和 0。

输入: a = "11", b = "1"

输出: "100"

输入: a = "1010", b = "1011"

输出: "10101"

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

The input strings are both non-empty and contains only characters 1 or 0.

Input: a = "11", b = "1"

Output: "100"

Input: a = "1010", b = "1011"

Output: "10101"

示例

public class Program {

    public static void Main(string[] args) {

        var a = "1010";

        var b = "1011";

        var res = AddBinary(a, b);

        Console.WriteLine(res);

        Console.ReadKey();

    }

    private static string AddBinary(string a, string b) {

        //找出最长的加1，留1位进位

        var max = Math.Max(a.Length, b.Length) + 1;

        //按总长度补位，以便统一处理，否则要考虑边界

        var a2 = a.PadLeft(max, '0');

        var b2 = b.PadLeft(max, '0');

        //定义list存中间计算结果

        var list = new List<int>();

        //进位标志

        var carryFlag = false;

        for(int i = max - 1; i >= 0; i--) {

            var add = int.Parse(a2[i].ToString())

                      + int.Parse(b2[i].ToString());

            //计算当前位的值，如果之前进位标志为真，则额外+1

            if(carryFlag) add++;

            //大于等于2时，此时仍然需要进位，带入下一次循环

            carryFlag = add >= 2;

            //存入中间计算结果

            list.Add(add % 2);

        }

        //定义结果

        var res = string.Empty;

        //反转，list是按逆序从低位到高位的

        list.Reverse();

        //遍历输出到res

        list.ForEach(r => { res += r.ToString(); });

        //取消最高位0

        res = res.TrimStart('0');

        //如果空了，返回0

        if(res.Length == 0) res = "0";

        //返回结果

        return res;

    }

}

以上给出1种算法实现，以下是这个案例的输出结果：

分析：

设两个二进制字符串中较长的字符串的长度为 n ,那么以上算法的时间复杂度为： $O(n)$ 。

巴特西

C#LeetCode刷题之#67-二进制求和（Add Binary）

最新文章

热门文章