67. Add Binary - Easy

发布时间：2020-12-14 04:27:42 所属栏目：大数据来源：网络整理

导读：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 . Example 1: Input: a = "11",b = "1"Output: "100" Example 2: Input: a = "1010",b = "1011"Output:

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.

Example 1:

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

Example 2:

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

从后往前加，用两个参数，sum和remainder分别表示和、余数。当两个string数组下标不越界时，sum等于两个数相加，res append (sum % 2)，余数为 sum/2，表示进位，下一次进入循环时，sum就等于remainder，在此基础上继续累加。最后当两个string都加完，考虑进位：如果最后的余数为0，不进位；如果不为0，在res里append最后一次循环得到的余数。

由于append的顺序和二进制数的高低位顺序是相反的，最后还要把res反转一下

time: O(n),space: O(n)

class Solution {
    public String addBinary(String a,String b) {
        StringBuilder res = new StringBuilder();
        int i = a.length() - 1,j = b.length() - 1;
        int remainder = 0;
        while(i >= 0 || j >= 0) {
            int sum = remainder;
            if(i >= 0) {
                sum += a.charAt(i--) - ‘0‘;
            }
            if(j >= 0) {
                sum += b.charAt(j--) - ‘0‘;
            }
            res.append(sum % 2);
            remainder = sum / 2;
        }
        if(remainder != 0) {
            res.append(remainder);
        }
        return res.reverse().toString();
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!