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;
}
};