Leetcode No.67 Add Binary二进制求和(c++实现)

1. 题目

1.1 英文题目

Given two binary strings a and b, return their sum as a binary string.

1.2 中文题目

给定两个二进制字符串,返回他们的和(用二进制表示)。输入为非空字符串且只包含数字 1 和 0。

1.3输入输出

输入 输出
a = "11", b = "1" "100"
a = "1010", b = "1011" "10101"

1.4 约束条件

  • 1 <= a.length, b.length <= 104
  • a and b consist only of '0' or '1' characters.
  • Each string does not contain leading zeros except for the zero itself.

2. 分析

2.1 一般算法

class Solution {
public:
    int lengthOfLastWord(string s) {
        int sLen = s.size();
        int start = 0;//最后一个单词的最后一个字母位置
        int end = 0;//最后一个单词前的空格位置(注意:不是最后一个单词的第一个字母位置)
        for (int i = sLen - 1; i >= 0; i--)//逆序遍历
        {
            if (start == 0 && s[i] != ' ')//第一个非空格处,记为start
                start = i;
            else if (start != 0 && s[i] == ' ')//已经有start(也就是找到最后一个单词)的前提下,找到第二个空格,记为end,且退出循环
            {
                end = i;
                break;
            }
            if (i == 0 && s[i] != ' ')//若一直遍历到0处才找到非空格元素,则将end-1
                end--;
        }
        return start - end;
    }
};

2.2 大神算法

参考:https://leetcode.com/problems/add-binary/discuss/24475/Short-code-by-c%2B%2B

class Solution
{
public:
    string addBinary(string a, string b)
    {
        string resultStr = "";

        int carry = 0, aIndex = a.size() - 1, bIndex = b.size() - 1;//初始化余数和a,b索引值
        while (aIndex >= 0 || bIndex >= 0 || carry == 1)//余数==1是针对最高位可能进位的情况
        {
            carry += aIndex >= 0 ? a[aIndex--] - '0' : 0;
            carry += bIndex >= 0 ? b[bIndex--] - '0' : 0;
            resultStr = char(carry % 2 + '0') + resultStr;
            carry /= 2;
        }

        return resultStr;
    }
};
上一篇:Mysql 主从同步之Got fatal error 1236 from master when reading data from binary log: 'Could not find


下一篇:1064 Complete Binary Search Tree