LeetCode --- 字符串弛姜、數(shù)組
簡書專欄：http://www.reibang.com/nb/41796568
知乎專欄：https://zhuanlan.zhihu.com/c_174823416
一皮服、題目描述
來源：力扣（LeetCode）
給定兩個二進制字符串大磺，返回他們的和（用二進制表示）芙委。
輸入為非空字符串且只包含數(shù)字 1 和 0。
示例:
輸入: a = "11", b = "1"
輸出: "100"
輸入: a = "1010", b = "1011"
輸出: "10101"
二、實現(xiàn)思路以及代碼
- 首先明確兩個數(shù)相加，是從后往前加院尔，那么可以定義兩個指針i,j從后向前遍歷蜻展，直到其中一個小于0的時候結束循環(huán)。相加的關鍵是在于處理進位的問題邀摆。
- 單獨定義一個變量up來控制纵顾，當兩數(shù)之和加上up大于1時，表明需要向后進位栋盹，向結果字符串的首位置插入當前總和減去2（因因為總和大于1施逾，說明可能是1+1+1或1+1+0的形式，減去2之后即為進位之后留在此處的數(shù)字）例获。
- 否則表明不需要進位汉额，直接在字符串首位插入該總和。
- 結合代碼加以理解
public static String addBinary(String a, String b) {
int i = a.length() - 1;
int j = b.length() - 1;
StringBuffer br = new StringBuffer();
//定義進位變量
int up = 0;
//定義相加之和
int sum = 0;
//注意這里用的是或榨汤，不是且蠕搜，因為如果兩個字符串長度不一致，剩余的也要加上去
while (i >= 0 || j >= 0) {
//上次的進位作為本次sum的初始值
sum = up;
if (i >= 0) {
sum += a.charAt(i) - '0';
i--;
}
if (j >= 0) {
sum += b.charAt(j) - '0';
j--;
}
if (sum > 1) {
up = 1;
sum -= 2;
} else {
up = 0;
}
br.insert(0, sum);
}
//最后一位進位要加上
if (up == 1) {
br.insert(0, 1);
}
return br.toString();
}
更為簡潔的代碼：
public String addBinary(String a, String b) {
StringBuffer sb = new StringBuffer();
int i = a.length() - 1, j = b.length() - 1;
int carry = 0;
while(i >= 0 || j >=0) {
int ta = i >= 0 ? (a.charAt(i) - '0') : 0;
int tb = j >= 0 ? (b.charAt(j) - '0') : 0;
int sum = ta + tb + carry;
carry = sum / 2;
sum = sum % 2;
sb.append(sum);
i--;
j--;
}
if(carry == 1) {
sb.append("1");
}
return sb.reverse().toString();
}
三收壕、測試代碼
public static void main(String[] args) {
String a = "11";
String b = "1";
System.out.println(addBinary(a, b));
a = "1101";
b = "11";
System.out.println(addBinary(a, b));
}
輸出結果為：
100
10000
