二进制求和问题

港控/mmm° 2022-12-28 04:17 104阅读 0赞

### 题目描述： ###

给定一个二进制字符串，返回它们的和（用二进制表示），已知字符串非空且只包含1和0。

### 思路和算法： ###

可以模拟十进制中的加法，只不过在十进制中式锋十进一，二进制中需要逢二进一。

具体的，我们可以取n = max\{|a|,|b|\}，循环n次，从最低为开始遍历。我们使用一个变量carry表示上一个位置的进位，初始值位0。记当前位置对齐的两个位位ai 和 bi，则每一位的答案为（carry + ai + bi)mod 2，下一位的进位为（carry+ai+bi\_/2。重复上述步骤，直到数字a和b的每一位计算完毕。最后如果carry的最高位不为0，则将最高位添加到计算结果的末尾。

### 算法java实现： ###

public String addBinary(String a, String b) {
        StringBuffer ans = new StringBuffer();
        int n = Math.max(a.length(),b.length()), carry = 0;
        for (int i=0;i<n;++i){
            carry += i<a.length() ? (a.charAt(a.length()-1 - i)-'0'):0;
            carry += i<b.length() ? (b.charAt(b.length()-1 - i)-'0'):0;
            //判断是否有进位
            carry /= 2;
        }
        //最后一位有进位
        if (carry > 0) {
            ans.append('1');
        }
        //顺序反转
        ans.reverse();
        //转换为字符串输出
        return ans.toString();
    }

### 代码讲解： ###

carry += i<a.length() ? (a.charAt(a.length()-1 - i)-'0'):0;

*  三目运算符

result = <expression> ? <statement1> : <statement3>;

其中expression是一个布尔表达式，当expression为真时，执行statement1，否则执行statement3。

*  int与char的转换

(a.charAt(a.length()-1 - i)-'0')

### 复杂度分析： ###

假设n = max\{|a|,|b|\}

*  时间复杂度为：O(n)，这里的时间复杂度来源于顺序遍历a和b。
 *  空间复杂度为：O(1)，出去答案所占用的空间，这里使用了常数个临时变量。

发表评论取消回复

表情：

评论列表（有 0 条评论，104人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode：二进制求和

二进制求和给定两个二进制字符串，返回他们的和（用二进制表示）。输入为**非空**字符串且只包含数字 `1` 和 `0`。 **示例 1:** 输入:...

素颜马尾好姑娘i/ 2024年04月19日 11:25/ 0 赞/ 3 阅读

相关 67. 二进制求和

题目链接： [https://leetcode.cn/problems/add-binary/][https_leetcode.cn_problems_add-binary]

一时失言乱红尘/ 2024年04月03日 09:48/ 0 赞/ 7 阅读

相关二进制求和问题

题目描述：给定一个二进制字符串，返回它们的和（用二进制表示），已知字符串非空且只包含1和0。思路和算法：可以模拟十进制中的加法，只不过在十进制中式锋十进一，

港控/mmm°/ 2022年12月28日 04:17/ 0 赞/ 105 阅读

相关 67. 二进制求和

> 给你两个二进制字符串，返回它们的和（用二进制表示）。 > > 输入为非空字符串且只包含数字 1 和 0。 > > > > 示例 1: > > 输入: a =

ゞ浴缸里的玫瑰/ 2022年10月16日 09:54/ 0 赞/ 121 阅读

相关 67. 二进制求和【简单】

67. 二进制求和【简单】题目描述：给你两个二进制字符串，返回它们的和（用二进制表示）。输入为非空字符串且只包含数字 `1` 和 `0`。

忘是亡心i/ 2022年10月11日 06:13/ 0 赞/ 123 阅读

相关 67.二进制求和

题目描述：给你两个二进制字符串，返回它们的和（用二进制表示）。输入为非空字符串且只包含数字 `1` 和 `0`。示例：输入: a = "1010", b =

女爷i/ 2022年09月12日 14:51/ 0 赞/ 127 阅读

相关 67. 二进制求和

[力扣![icon-default.png?t=L892][icon-default.png_t_L892]/images/20220828/295a4690af8c468eb

旧城等待，/ 2022年09月11日 13:18/ 0 赞/ 131 阅读

相关二进制求和[LeetCode]

[题目描述][Link 1] 思路从后向前遍历每一个字符串的每一个字符，直到走完所有位，比如两个字符串分别是a="101" 和 b="11" 则第一次取a的最

柔光的暖阳◎/ 2022年01月20日 12:23/ 0 赞/ 146 阅读

相关二进制求和

题目描述给定两个二进制字符串，返回他们的和（用二进制表示）。输入为非空字符串且只包含数字 1 和 0。示例 1: 输入: a = "11", b =

た入场券/ 2021年12月11日 14:55/ 0 赞/ 221 阅读

相关 leetcode67. 二进制求和

题目：　　给定两个二进制字符串，返回他们的和（用二进制表示）。　　输入为非空字符串且只包含数字 1 和 0。示例 1: 　　输入: a = "11", b = "

妖狐艹你老母/ 2021年11月02日 08:06/ 0 赞/ 212 阅读