首页 > 其他分享 >[ LeetCode ] 67. Add Binary

[ LeetCode ] 67. Add Binary

时间:2023-12-10 11:56:12浏览次数:28  
标签:Binary String int res sum countA Add carry LeetCode

题目

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

思考

题外话:根据LeetCode premium的说法,这题是no.4最常被Facebook面试问到的题目

这题是二进制相加的问题

什么是二进制

二进制是一种计数系统,基于数字 0 和 1。与十进制每10进1不同,二进制每2进1
二进制:0 -> 1 -> 10 就对应着十进制:0 -> 1 -> 2

难点

在解决这道问题时,个人觉得难点在于如何进位,其中包括了前进一位时,当前位归零记录进位到下一位的运算,在代码实现时都让我有点卡顿

解决

首先,对于两个二进制相加,肯定要从最末尾的一位开始,而两个数字长度未必相同
所以我们先初始化两个指针分别指向两个数字String a和 String b的末尾
int countA = a.length() - 1;
int countB = b.length() - 1;

然后我们用sumcarry分别记录当前位下一位的情况
有这么些情况:

  1. sum = 0,那么向结果String res加入0,carry也为0;
  2. sum = 1, 那么 res.append(1), carry = 0;
  3. sum = 2, res.append(0), carry = 1;
  4. sum = 3, res.append(1), carry = 1;
    以上就是进位逻辑

最后不要忘记将进位也加入结果,如果carry不是0,那就加入结果
然后逆向输出

代码

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder res = new StringBuilder();
        int countA = a.length() - 1;
        int countB = b.length() - 1;
        int carry = 0;
        while(countA >= 0 || countB >= 0) {
            int sum = carry;
            if (countA >= 0) sum += a.charAt(countA--) - '0';
            if (countB >= 0) sum += b.charAt(countB--) - '0';
            carry = sum > 1 ? 1 : 0;
            res.append(sum%2);
        }
        if (carry != 0) {res.append(carry);}
        return res.reverse().toString();
    }
}

总结

主要还是要熟悉String的操作,以及想到记录当前位和进位的逻辑。

标签:Binary,String,int,res,sum,countA,Add,carry,LeetCode
From: https://www.cnblogs.com/zoexcode/p/17892275.html

相关文章

  • [LeetCode Hot 100] LeetCode155. 最小栈
    题目描述思路一:使用辅助栈定义一个[数据栈]来支持push、pop、top操作定义一个[辅助栈],其栈顶为当前的最小值,以支持常数时间复杂度的getMin操作思路二:使用ArrayDeque栈元素中除了保存当前值之外,额外保存当前最小值使用静态内部类方法一:对应思路一classMinStack{......
  • Leetcode刷题day9-栈.队列-栈转队列.队列转栈
    232.用栈实现队列232.用栈实现队列-力扣(LeetCode)请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):实现 MyQueue 类:voidpush(intx) 将元素x推到队列的末尾intpop() 从队列的开头移除并返回元素intpeek() 返回队......
  • One added/edited TODO item was found. Would you like to review it?
    ......
  • [LeetCode Hot 100] LeetCode20. 有效的括号
    题目描述思路:栈的经典应用。注意下遇到右括号的代码,即边界情况://遇到右括号,则进行括号匹配if(!stack.isEmpty()&&stack.peek()==match(c)){ //如果匹配则直接弹出栈顶元素 stack.pop();}else{ //如果不匹配则直接返回false returnfalse;}方法一:class......
  • HydroOJ 从入门到入土(6)Caddy设置自动SSL证书, 开启高压缩比算法(brotli)节约网络带宽
    Caddy既出,何需Nginx?目录1.Caddy是啥2.Caddy配置简介3.使用gzip/br节省带宽3.1先把静态文件全部压缩3.2caddyfile中开启precompressed选项3.3查看是否成功1.Caddy是啥Caddy是用来替代Nginx的新一代反代工具,配置简单很多.有了Caddy,就不要再装N......
  • nerdctl run -d 报"failed to call cni.Setup: plugin type=\"bridge\" failed (ad
    背景:执行 nerdctl run-d --namenginx-p8080:80nginx时,报如下错误FATA[0000]failedtocreateshimtask:OCIruntimecreatefailed:runccreatefailed:unabletostartcontainerprocess:errorduringcontainerinit:errorrunninghook#0:errorrunningh......
  • 【LeetCode-中等-链表】两数相加
    这是个关于链表的题目,以前在C#中写代码时,对链表接触比较少,所以刚好接这个题目来更好的熟悉一下链表题目大概是这样的,给你两个非空的链表,表示两个非负的整数.它们每位数字都是按照逆序的方式存储的,并且每个节点只能存储一位数字 =》首先我们来理解这句话是什么意思我们来看......
  • [LeetCode Hot 100] LeetCode23. 合并K个升序链表
    题目描述思路:优先队列使用优先队列这个数据结构,对于这个数据结构,我们不用去管内部是如何实现的,我们只要知道有这么一种数据结构能帮助我们将一堆数据塞到优先队列这一个黑盒中,然后我们可以获取这堆数中最小的值或者最大的值。代码一:/***Definitionforsingly-linkedlis......
  • LeetCode876. 链表的中间结点
    题目描述思路:快慢指针快指针一次走两步慢指针一次走一步当快指针到达末尾的时候,慢指针所指的就是链表的中点方法一:/***Definitionforsingly-linkedlist.*publicclassListNode{*intval;*ListNodenext;*ListNode(){}*ListNode(......
  • [LeetCode Hot 100] LeetCode2. 两数相加
    题目描述思路:模拟每次3个数相加:l1链表的值+l2链表的值+进位如果l1链表不为空或者l2链表不为空或者进位不为0我们就执行循环那么和存储的是t%10进位就是t/10因为题目需要创造一条链表,所以我们创建一个dummy结点的话会方便一点。方法一:/***Definitionfo......