嗨客网搜索
二进制求和

描述

leetcode 官方第 67 题。给你两个二进制字符串,返回它们的和(用二进制表示)。输入为非空字符串且只包含数字 10

示例1:

输入: a = "11", b = "1" 输出: "100"

示例2:

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

提示:

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

思路

我们一般的情况下对十进制求和比较熟悉,其实二进制求和与十进制求和是类似的,十进制求和是遇 10 进 1。二进制求和是遇 2 进 1。我们可以从右往左遍历二进制数值,然后将每个遍历到的数据进行相加。

例如 11 + 1 :

13_二进制求和.png

就算是十进制数据,我们是从右往左逐位相加。因为逢 2 需要进 1 位。所以 1 + 1 = 2,要转换为 0。并且将前一位进 1。前一位数据进行相加操作的时候,需要再额外加 1。

计算顺序如下:

  • 第一步:1 + 1 =2。需要将当前的值设置为 0,并且将前一位是否需要加 1 的临时字段设置为 1。
  • 第二部:1 + 0 + 1 = 2。当前第一个二进制数是 1。第二个二进制数没有值,就相当于 0。由于前一位相加之和是 2。需要前进一位,所以当前值需要加 1。计算结果为 2,需要将 2 转换成 0。将额外相加的临时值设置为 1。
  • 判断额外相加的值是否为 1,如果是 1 就将 1 加上,如果不为 1 就结束。
  • 将现有结果反转,得到最终数据。

例如 1010 + 1011:

14_二进制求和.png

和上面的步骤类型,要从右往左计算对应位置上面的和。因为逢 2 进 1。所以我们需要定义一个中间临时值,用来标记当前操作的时候是否需要再额外加 1。

计算顺序如下:

  • 第一步:0 + 1 = 1。
  • 第二步:1 + 1 = 2 ,转换成 0,在前一位相加是否需要额外加 1 的值赋值为 1。
  • 第三步:0 + 0 + 1 = 1。
  • 第四步:1 + 1 =2,转换为 0,在前一位相加是否需要额外加 1的值赋值为 1。
  • 第五步:判断额外相加的值是否为 1,如果是 1 就将 1 加上,如果不为 1 就结束。
  • 第六步:将现有结果反转,得到最终数据。

代码具体实现

Java语言版本

/** *逢2进1 */ class Solution { public String addBinary(String a, String b) { char[] aarray = a.toCharArray(); char[] barray = b.toCharArray(); int alength = aarray.length; int blength = barray.length; int maxLength = (alength > blength ? alength : blength); int currentAvalue = 0; int currentBvalue = 0; //记录是否上一次相加操作大于 2 ,当前操作是否要加 1 int tmpValue = 0; //记录遍历 a 数组的位置 int aCurrentIndex = alength - 1; //记录遍历 b 数组的位置 int bCurrentIndex = blength - 1; //用来接受返回值 StringBuffer retStrBuffer = new StringBuffer(); for (int i = 0; i < maxLength; i++) { if (aCurrentIndex >= 0) { //因为 char 类型的数据会被转换成 ASCII 码,所以减去 ‘0’ currentAvalue = aarray[aCurrentIndex] - '0'; aCurrentIndex--; } else { currentAvalue = 0; } if (bCurrentIndex >= 0) { currentBvalue = barray[bCurrentIndex] - '0'; bCurrentIndex--; } else { currentBvalue = 0; } int tmpTotalValue = (currentBvalue + currentAvalue + tmpValue); if (tmpTotalValue >= 2) { //逢 2 进 1 tmpTotalValue = tmpTotalValue - 2; tmpValue = 1; } else { tmpValue = 0; } retStrBuffer.append(tmpTotalValue); } if (tmpValue == 1) { //因为追加的时候是从最右侧开始追加,所以需要将字符串反转 return "1" + retStrBuffer.reverse().toString(); } //因为追加的时候是从最右侧开始追加,所以需要将字符串反转 return retStrBuffer.reverse().toString(); } }

Go语言版本

func addBinary(a string, b string) string { a = reverse(a) b = reverse(b) var( aByte = []byte(a) bByte = []byte(b) aLength = len(aByte) bLength = len(bByte) maxLength = If(aLength > bLength , aLength , bLength).(int) currentAvalue = 0 currentBvalue = 0 //记录是否上一次相加操作大于 2 ,当前操作是否要加 1 tmpValue = 0 ) //记录遍历 a 数组的位置 aMaxIndex := aLength - 1 //记录遍历 b 数组的位置 bMaxIndex := bLength - 1 //var retStrBuffer bytes.Buffer var retStr string for i := 0; i < maxLength; i++ { if i <= aMaxIndex { //因为 char 类型的数据会被转换成 ASCII 码,所以减去 ‘0’ currentAvalue = int(aByte[i]) - int('0') }else { currentAvalue = 0 } if i <= bMaxIndex { currentBvalue = int(bByte[i]) - int('0') } else { currentBvalue = 0 } var tmpTotalValue = currentBvalue + currentAvalue + tmpValue if tmpTotalValue >= 2 { //逢 2 进 1 tmpTotalValue = tmpTotalValue - 2 tmpValue = 1 } else { tmpValue = 0 } retStr += strconv.Itoa(tmpTotalValue) } if tmpValue == 1 { retStr += strconv.Itoa(1) } return reverse(retStr) } //三木运算符效果 func If(condition bool, trueVal, falseVal interface{}) interface{} { if condition { return trueVal } return falseVal } //数据反转函数 func reverse( str string ) string { r := []rune(str) for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 { r[i], r[j] = r[j], r[i] } return string(r) }

赞助商链接:


嗨客网顶部