LeetCode_字元串_簡單_67.二進制求和

目錄

• 1.題目
• 2.思路
• 3.代碼實作（Java）

1.題目

給你兩個二進制字元串，傳回它們的和（用二進制表示）。

輸入為 非空 字元串且隻包含數字 1 和 0。

示例 1：

輸入: a = “11”, b = “1”

輸出: “100”

示例 2：

輸入: a = “1010”, b = “1011”

輸出: “10101”

提示：

每個字元串僅由字元 ‘0’ 或 ‘1’ 組成。

1 <= a.length, b.length <= 104

字元串如果不是 “0” ，就都不含前導零。

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/add-binary

2.思路

（1）将字元串 a 和 b 轉化成十進制數并求和，然後再轉化為二進制數即可。不過當題目中字元串的長度非常大時，就有可能超過Java所能表示的範圍，是以該思路具有一定的局限性。

（2）采用整數加法中列豎式的方法來求解本題，即将這兩個二進制字元串從低位到高位逐位相加，并且記錄相加過程中産生的進位，将其考慮到下一輪運算中即可。

3.代碼實作（Java）

//（1）思路1
public String addBinary(String a, String b) {
    /*
        toBinaryString(int i):傳回int變量的二進制表示的字元串
        Integer.parseInt(s,2):将字元串s轉換為二進制的整數
    */
    return Integer.toBinaryString(Integer.parseInt(a,2)+Integer.parseInt(b,2));
}
           

//（2）思路2
public String addBinary(String a, String b) {
	//代碼來自本題官方題解
	/*
		在使用 StringBuffer類時，每次都會對 StringBuffer對象本身進行操作，而不是生成新的對象，
		是以如果需要對字元串進行修改推薦使用StringBuffer，而此題可好需要需要對字元串進行修改。
	*/
    StringBuffer ans = new StringBuffer();
	//carry表示進位
    int n = Math.max(a.length(), b.length()), carry = 0;
    for (int i = 0; i < n; ++i) {
		//将a和b的最低位依次進行相加
        carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
        carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
		//将中間結果追加到ans之後
        ans.append((char) (carry % 2 + '0'));
		/* 
			進行上述的一次計算後，carry的可能取值為0、1或2
			1.carry=0，說明a、b目前位上的值均為'0'，沒有進位
			2.carry=1，說明a、b目前位上的值有一個位'0'，有一個為'1'，沒有進位
			3.carry=2，說明a、b目前位上的值均為'1'，産生進位
			當進行下一輪計算時，隻有當carry=2時才産生了進位，此時需要使carry變成1，
			而其它情況下沒有産生進位，則使carry變成0即可，而carry/=2正好滿足要求
		*/
        carry/=2;
    }
	//如果進位大于0，則需要向高位添加一個"1"
    if (carry > 0) {
        ans.append('1');
    }
	/*
		reverse():将字元序列進行反轉
		例如s="123"，那麼s.reverse()之後，s="321"
	*/
    ans.reverse();
	//以字元串的形式進行傳回
    return ans.toString();
}