leetcode算法67.二进制求和
2023-09-11 14:22:53 时间
👏👏👏
哈喽!大家好,我是【学无止境小奇】,一位热爱分享各种技术的博主!😍😍😍
⭐【学无止境小奇】的创作宗旨:每一条命令都亲自执行过,每一行代码都实际运行过,每一种方法都真实实践过,每一篇文章都良心制作过。✊✊✊
⭐【学无止境小奇】的博客中所有涉及命令、代码的地方,除了提供图片供大家参考,另外会在图片下方提供一份纯文本格式的命令或者代码方便大家粘贴复制直接执行命令或者运行代码。🤝🤝🤝
⭐如果你对技术有着浓厚的兴趣,欢迎关注【学无止境小奇】,欢迎大家和我一起交流。😘😘😘
❤️❤️❤️感谢各位朋友接下来的阅读❤️❤️❤️
一、leetcode算法
1、 二进制求和
1.1、题目
给你两个二进制字符串,返回它们的和(用二进制表示)。
输入为 非空 字符串且只包含数字 1 和 0。
示例 1:
输入: a = “11”, b = “1”
输出: “100”
示例 2:
输入: a = “1010”, b = “1011”
输出: “10101”
1.2、思路
思路一:本题可以使用最简单的数学思想,将二进制都转化为十进制相加,然后再转化为二进制输出,但是转化为十进制后最数据的长度就有了限制,所以尽量不使用二进制向十进制转化的这种方式。
思路二:通过对二进制直接计算取得要返回的值,我们可以将两个二进制字符串逐位相加,逢二进一,最后得出要返回的字符串。这里需要注意的是低位相加后是否需要向高位进位,以及两个二进制字符串长度不一样,具体的需要怎么相加。
1.3、答案
class Solution {
public String addBinary(String a, String b) {
//new一个StringBuffer用来返回最后的字符串
StringBuffer ans = new StringBuffer();
//获取最长的字符串的长度,用来规定循环的次数,定义一个carry用来表示是哪个一个位置的进位
int n = Math.max(a.length(), b.length()), carry = 0;
for(int i = 0; i < n; i++){
//计算上一个位置的进位,这里字符‘1’减去字符‘0’等于数字1
carry += i < a.length() ? (a.charAt(a.length() -1 - i) - '0') : 0;
carry += i < b.length() ? (b.charAt(b.length() -1 - i) - '0') : 0;
ans.append((char) (carry % 2 + '0'));
//只有carry等于2的时候才能向上进一位,当carry等予0或者1的时候就不进位,所以这里除以2
carry /= 2;
}
//如果最后carry不等于0,证明有进位,则第一位加一
if(carry > 0){
ans.append('1');
}
//因为是倒叙进行的进位计算,所以最终结果需要反转一下
ans.reverse();
return ans.toString();
}
}
复杂度分析
时间复杂度:O(n)O(n),这里的时间复杂度来源于顺序遍历 aa 和 bb。
空间复杂度:O(1)O(1),除去答案所占用的空间,这里使用了常数个临时变量。
相关文章
- Java实现 LeetCode 745 前缀和后缀搜索(使用Hash代替字典树)
- Java实现 LeetCode 717 1比特与2比特字符(暴力)
- Java实现 LeetCode 680 验证回文字符串 Ⅱ(暴力)
- Java实现 LeetCode 645 错误的集合(暴力)
- Java实现 LeetCode 561 数组拆分 I(通过排序算法改写PS:难搞)
- Java实现 LeetCode 516 最长回文子序列
- Java实现 LeetCode 279 完全平方数
- Java实现 LeetCode 227 基本计算器 II(二)
- Java实现 LeetCode 95 不同的二叉搜索树 II(二)
- 【LeetCode算法-28/35】Implement strStr()/Search Insert Position
- 【LeetCode算法-20】Valid Parentheses
- LeetCode(58): 最后一个单词的长度
- 【LeetCode算法-27】Remove Element
- 【LeetCode算法-14】Longest Common Prefix
- 【LeetCode算法-9】Palindrome Number
- 【LeetCode算法-7】Reverse Integer
- LeetCode(115):不同的子序列
- 算法笔记:前缀和+哈希表(leetcode题解例)
- leetcode算法第7题
- Leetcode 1200. 最小绝对差
- Leetcode 844. 比较含退格的字符串
- Leetcode 747. 至少是其他数字两倍的最大数(可以,一次过)
- [LeetCode] 382. 链表随机节点 ☆☆☆(随机算法:蓄水池抽样)
- LeetCode刷题笔录Add Binary
- 【Leetcode刷题Python】155. 最小栈
- 【Leetcode刷题Python】96. 不同的二叉搜索树
- 【LeetCode】21. 合并两个有序链表
- 【LeetCode】八皇后