of02二进制加法

leecode

题目描述

给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。

输入为 非空 字符串且只包含数字 1 和 0。

示例 1:

输入: a = "11", b = "10" 输出: "101" 示例 2:

输入: a = "1010", b = "1011" 输出: "10101"

提示：

每个字符串仅由字符 '0' 或 '1' 组成。 1 <= a.length, b.length <= 10^4 字符串如果不是 "0" ，就都不含前导零。

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/JFETK5 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

法1(模拟相加)

总体思路:模拟二进制进行运算,满二进一

1. 分为两种情况进行考虑
   (1)len相同
   循环相加,定义一个临时变量t用于储存进位,循环遍历他们相同的位,从右往左开始,
   1)一个1,本位变1,进位为0
   1)2个,本位变0,进位为1
   1)3个1,本位变1,进位为1
   //全部为0就不用动\

核心代码

if t == 1 && a[i] == '1' || t == 1 && b[i] == '1' || a[i] == '1' && b[i] == '1' { //当有两个以上(含),则进一
   if a[i] == '1' && b[i] == '1' && t == 1 { //当abt三个同时为一时进一,同时原位为1;3=(11)2
    a[i] = '1'
   } else { //进一原位为0;;2=(10)2
    a[i] = '0'
    t = 1
   }
  } else if a[i] == '1' || b[i] == '1' || t == 1 {
   //三个有一个为1
   a[i] = '1' //原位为1
   t = 0      //进位为0
  }
  //全部为0就不用动
 }

循环执行,直到i==0 (2)len不同
相同的位数拿去相加,在最后返回 的时候将字符串拼接上去

//t接收记录进位
 s, t := addsamelen(a[len(a)-len(b):], b)    //先加相同长度

t==0时直接拼接返回
t==1时在与后面的 进行相加,直到不在进位为止\

核心代码

for i := len(a) - len(b) - 1; t == 1; i-- { //加剩下的不同长度的当t==1时,
   if a[i] == '0' { //当有0出现就可以返回值了
    a[i] = '1'
    return string(a[:len(a)-len(b)]) + s
   } else if a[i] == '1' { //如果是一就要进位
    if i == 0 { //如果结尾是一就要拼接一个"1"上去
     a[i] = '0'
     return "1" + string(a[:len(a)-len(b)]) + s
    } else { //继续进位
     a[i] = '0'
    }
   }
  }
  return string(a[:len(a)-len(b)]) + s //如果t==0时就直接返回拼接字符串

执行结果

法1

func addBinary(a string, b string) string {
    if a=="0"||b=="0" {//判断是否有0,有的话返回另一个数
  if a=="0" {
   return b
  }else {
   return a
  }
 }
 if len(a) == len(b) { //长度相同时因为没有前置0,所以必进一
  a, _ = addsamelen([]byte(a), []byte(b))
  return "1" + a
 }
 if len(a) > len(b) { //长度不同的情况
  return adddiflen([]byte(a), []byte(b))
 } else {
  return adddiflen([]byte(b), []byte(a))
 }
}



// 不同的二进制长度求和,返回相加的字符串;;a长b短
func adddiflen(a, b []byte) string {
 //接收记录进位
 s, t := addsamelen(a[len(a)-len(b):], b)    //先加相同长度
 for i := len(a) - len(b) - 1; t == 1; i-- { //加剩下的不同长度的当t==1时,
  if a[i] == '0' { //当有0出现就可以返回值了
   a[i] = '1'
   return string(a[:len(a)-len(b)]) + s
  } else if a[i] == '1' { //如果是一就要进位
   if i == 0 { //如果结尾是一就要拼接一个"1"上去
    a[i] = '0'
    return "1" + string(a[:len(a)-len(b)]) + s
   } else { //继续进位
    a[i] = '0'
   }
  }
 }
 return string(a[:len(a)-len(b)]) + s //如果t==0时就直接返回拼接字符串
}



// 相同的二进制长度求和,返回相加的s字符串与进位t
func addsamelen(a, b []byte) (string, int) {
 t := 0 //储存是否进一位
 for i := len(a) - 1; i >= 0; i-- {
  if t == 1 && a[i] == '1' || t == 1 && b[i] == '1' || a[i] == '1' && b[i] == '1' { //当有两个以上(含),则进一
   if a[i] == '1' && b[i] == '1' && t == 1 { //当abt三个同时为一时进一,同时原位为1;3=(11)2
    a[i] = '1'
   } else { //进一原位为0;;2=(10)2
    a[i] = '0'
    t = 1
   }
  } else if a[i] == '1' || b[i] == '1' || t == 1 {
   //三个有一个为1
   a[i] = '1' //原位为1
   t = 0      //进位为0
  }
  //全部为0就不用动
 }
 return string(a), t //返回相加的字符串与进位
}

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 2 MB , 在所有 Go 提交中击败了 92.25% 的用户 通过测试用例： 294 / 294