算法 1.2.1 二进制求和 【leetcode 67】

题目描述

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

示例 1:
输入: a = "11", b = "1"
输出: "100"

示例 2:
输入: a = "1010", b = "1011"
输出: "10101"

提示：
每个字符串仅由字符 '0' 或 '1' 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 "0" ，就都不含前导零。

数据结构

• 字符串

算法思维

• 遍历
• 数学思维（竖式相加）

解题要点

• 数学思维的运用（模拟进位）
• 下标的控制（避免遍历字符串时越界）
• 使用 StringBuffer 操作不定长字符串

解题思路

一. Comprehend 理解题意

可以理解为 “竖式相加” 问题

二. Choose 选择数据结构与算法

数据结构：字符串
算法思维：遍历、数学思维（竖式相加）
时间复杂度：O(m+n) -- 两个字符串的遍历
空间复杂度：O(max(m,n)) -- 一个 StringBuffer 的内存空间

三. Code 编码实现基本解法

class Solution{
  public String addBinary(String a, String b) {

        int carry = 0;
        int sum = 0;
        int num = 0;
        StringBuffer str = new StringBuffer();

        //1.从尾到头遍历字符串
        for(int i=0; i<a.length() || i<b.length(); i++){
            //2.拿到每位数值
            int x = i<a.length() ? a.charAt(a.length()-1-i) - '0' : 0;
            int y = i<b.length() ? b.charAt(b.length()-1-i) - '0' : 0;

            //3.按位相加，计算进位，每位数值存入 StringBuffer 中
            sum = x + y + carry;
            carry = sum / 2;
            num = sum % 2;
            str.append(num); //(char)(num + '0')
        }

        //4.如果最终有进位，就单独插入一次进位
        if (carry > 0) str.append(carry); //(char)(carry + '0')

        //5.将字符串反转，返回
        return str.reverse().toString();
    }
}

执行耗时：3 ms，击败了55.04% 的Java用户
内存消耗：36.9 MB，击败了93.46% 的Java用户

四. Consider 思考更优解

减少判断、循环，删除不必要的变量和数据结构

五. Code 编码实现最优解

class Solution{
    public String addBinary(String a, String b) {

        int carry = 0;
        int n = Math.max(a.length(),b.length());
        StringBuffer str = new StringBuffer();

        //1.从尾到头遍历字符串
        for(int i=0; i<n; i++){

            //2.拿到每位数值,按位相加，计算进位，
            carry += i<a.length() ? a.charAt(a.length()-1-i) - '0' : 0;
            carry += i<b.length() ? b.charAt(b.length()-1-i) - '0' : 0;

            //3.每位数值存入 StringBuffer 中
            str.append((char)(carry % 2 + '0'));
            carry /= 2;
        }

        //5.将字符串反转并返回，如果最终有进位就加1
        return carry>0 ? "1" + str.reverse().toString() : str.reverse().toString();
    }
}

执行耗时：3 ms，击败了55.04% 的Java用户
内存消耗：36.9 MB，击败了94.64% 的Java用户

六. Change 变形与延伸

=== 待续 ===