赞
赏
leetcode 官方第 67 题。给你两个二进制字符串,返回它们的和(用二进制表示)。输入为非空字符串且只包含数字 1
和 0
。
示例1:
输入: a = "11", b = "1"
输出: "100"
示例2:
输入: a = "1010", b = "1011"
输出: "10101"
提示:
我们一般的情况下对十进制求和比较熟悉,其实二进制求和与十进制求和是类似的,十进制求和是遇 10 进 1。二进制求和是遇 2 进 1。我们可以从右往左遍历二进制数值,然后将每个遍历到的数据进行相加。
例如 11 + 1 :
就算是十进制数据,我们是从右往左逐位相加。因为逢 2 需要进 1 位。所以 1 + 1 = 2,要转换为 0。并且将前一位进 1。前一位数据进行相加操作的时候,需要再额外加 1。
计算顺序如下:
例如 1010 + 1011:
和上面的步骤类型,要从右往左计算对应位置上面的和。因为逢 2 进 1。所以我们需要定义一个中间临时值,用来标记当前操作的时候是否需要再额外加 1。
计算顺序如下:
/**
*逢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();
}
}
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)
}