LeetCode 67. 二进制求和
2023-09-14 09:13:12 时间
题目描述
给你两个二进制字符串 a
和 b
,以二进制字符串的形式返回它们的和。
数据范围
- 1 < = a . l e n g t h , b . l e n g t h < = 1 0 4 1 <= a.length, b.length <= 10^4 1<=a.length,b.length<=104
a
和b
仅由字符'0'
或'1'
组成- 字符串如果不是
"0"
,就不含前导零
样例1:
输入:a = “11”, b = “1”
输出:“100”
样例2:
输入:a = “1010”, b = “1011”
输出:“10101”
算法
(模拟)
模拟人工进行二进制加法的过程。
假设输入的两个字符串是 a
和 b
。
为了简化代码,我们进行如下操作:
- 如果a的长度小于b的长度,我们交换a和b;
- 翻转a和b,使得每个二进制数的最低位存储在字符串第0个位置;
然后从低位到高位依次计算每一位,过程中需要记录前一位的进位。
如果最高位的进位是1,则需要在最高位的位置补上1。
时间复杂度
- 两个字符串遍历的次数是常数,故总时间复杂度为 O ( n ) O(n) O(n)。
空间复杂度
- 需要额外的空间。
C++ 代码
class Solution {
public:
string addBinary(string a, string b) {
if (a.size() < b.size()) swap(a, b);
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
int t = 0;
int k = 0;
string res;
while (k < b.size())
{
t += a[k] - '0' + b[k] - '0';
res += to_string(t & 1);
t /= 2;
k ++ ;
}
while (k < a.size())
{
t += a[k] - '0';
res += to_string(t & 1);
t /= 2;
k ++ ;
}
if (t) res += '1';
reverse(res.begin(), res.end());
return res;
}
};
相关文章
- Java实现 LeetCode 767 重构字符串(ASCII的转换)
- Java实现 LeetCode 762 二进制表示中质数个计算置位(位运算+JDK的方法)
- Java实现 LeetCode 761 特殊的二进制序列(括号问题)
- Java实现 LeetCode 752 打开转盘锁(暴力)
- Java实现 LeetCode 693 交替位二进制数(位运算)
- Java实现 LeetCode 551 学生出勤记录 I(暴力大法好)
- Java实现 LeetCode 401 二进制手表
- Java实现 LeetCode 401 二进制手表
- Java实现 LeetCode 67 二进制求和
- Java实现LeetCode #986 - Interval List Intersections
- Java实现LeetCode 139 单词拆分
- LeetCode(67):二进制求和
- LeetCode(4):两个排序数组的中位数
- LeetCode(107): 二叉树的层次遍历 II
- LeetCode-面试题 05.02. 二进制数转字符串【数学,字符串,位运算】
- LeetCode-1758. 生成交替二进制字符串的最少操作数【字符串,三行代码!】
- LeetCode-762. 二进制表示中质数个计算置位【二进制,质数,判断质数优化】
- Leetcode 2022. 将一维数组转变成二维数组
- Leetcode 696. 计数二进制子串(有待解决)
- Leetcode 1290. 二进制链表转整数
- leetcode第一刷_Search in Rotated Sorted Array
- 【Leetcode刷题Python】LeetCode 478. 在圆内随机生成点
- 【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色