☆打卡算法☆LeetCode 67、二进制求和 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

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)

只需要常数级别的空间存放变量。

三、总结

从个位开始相加 先将两个字符串反转。

从头开始依次相加 直到两个字符串的末尾且无进位。

得到的字符串再反转即可。