67. 二进制求和——【Leetcode每日一题】
2023-09-14 09:01:27 时间
67. 二进制求和
给你两个二进制字符串 a
和 b
,以二进制字符串的形式返回它们的和。
示例 1:
输入:a = “11”, b = “1”
输出:“100”
示例 2:
输入:a = “1010”, b = “1011”
输出:“10101”
提示:
- 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” ,就不含前导零
思路:
模拟位运算:
- 从两个字符串的末尾,一步一步运算,满2进位;
优化:
- 任意一位相加,要加三个数,分别为:
a
的第i
位,b
的第i
位 ,- 以及前一位的进位
carry
代码:(Java、C++)
Java
public class AddBinary {
public static void main(String[] args) {
// TODO Auto-generated method stub
String a = "11";
String b = "1";
System.out.println(addBinary(a,b));
}
public static String addBinary(String a, String b) {
StringBuilder str = new StringBuilder();
boolean carry = false;
if(a.length() > b.length()) {
String temp = a;
a = b;
b = temp;
}
for(int i = a.length() - 1; i >= 0; i--) {
if(a.charAt(i) == '1' && b.charAt(i + b.length() - a.length()) == '1') {
str.append(carry == true ? '1' : '0');
carry = true;
}else if(a.charAt(i) == '1' || b.charAt(i + b.length() - a.length()) == '1') {
str.append(carry == true ? '0' : '1');
}else if(carry){
str.append('1');
carry = false;
}else {
str.append('0');
}
}
for(int i = b.length() - a.length() - 1; i >= 0; i--) {
if(carry && b.charAt(i) == '1') {
str.append('0');
}else if(carry || b.charAt(i) == 1) {
str.append('1');
carry = false;
}else {
str.append(b.charAt(i));
}
}
if(carry) {
str.append('1');
}
return str.reverse().toString();
}
}
优化:
Java
public String addBinary(String a, String b) {
int i = a.length() - 1, j = b.length() - 1, carry = 0;
StringBuilder str = new StringBuilder();
while (carry == 1 || i >= 0 || j >= 0) {
if (i >= 0 && a.charAt(i--) == '1') {
carry++;
}
if (j >= 0 && b.charAt(j--) == '1') {
carry++;
}
str.append(carry % 2);
carry /= 2;
}
return str.reverse().toString();
}
C++
string addBinary(string a, string b) {
int i = a.size() - 1, j = b.size() - 1, carry = 0;
string str;
while (i >= 0 || j >= 0 || carry == 1)
{
if (i >= 0 && a[i--] == '1') {
carry++;
}
if (j >= 0 && b[j--] == '1') {
carry++;
}
str += carry % 2 + '0';
carry /= 2;
}
reverse(str.begin(), str.end());
return str;
}
运行结果:
复杂度分析:
- 时间复杂度:
O
(
n
)
O(n)
O(n),n位字符串
a
和b
中长度最长的那个。 - 空间复杂度: O ( 1 ) O(1) O(1),除去答案所占用的空间,这里使用了常数个临时变量。
题目来源:力扣。
注:仅供学习参考, 如有不足,欢迎指正!
相关文章
- leetcode 1019. 链表中的下一个更大节点 js实现
- leetcode 78. 子集 js 实现
- LeetCode周赛302,这也太卷了,20分钟ak也只有300名……
- LeetCode周赛283,第一名送iWatch,少年你参赛了吗?
- leetcode-5最长回文子串(manacher算法)
- LeetCode 1389. 按既定顺序创建目标数组
- leetcode二叉树的层次遍历_完全二叉树的中序序列
- Leetcode分类——贪心算法
- LeetCode笔记:Biweekly Contest 89
- leetcode 234. 回文链表 js 实现
- JavaScript刷LeetCode拿offer-并查集
- map小试牛刀,LeetCode界的abandon有多难?
- leetcode:合并两个有序数组
- Leetcode 跳跃游戏
- JavaScript刷LeetCode拿offer-双指针技巧(上)_2023-03-15
- 【算法】动态规划 ③ ( LeetCode 62.不同路径 | 问题分析 | 自顶向下的动态规划 | 自底向上的动态规划 )