LeetCode-67. 二进制求和(java)

bug菌

发布于 2023-05-27 15:23:53

1830

发布于 2023-05-27 15:23:53

文章被收录于专栏：《项目实战教学》《项目实战教学》

一、前言：

👨‍🎓作者：bug菌 ✏️博客：CSDN、掘金等 💌公众号：猿圈奇妙屋 🚫特别声明：原创不易，转载请附上原文出处链接和本文声明，谢谢配合。 🙏版权声明：文章里可能部分文字或者图片来源于互联网或者百度百科，如有侵权请联系bug菌处理。

二、题目描述：

题目： 给你两个二进制字符串，返回它们的和（用二进制表示）。输入为非空字符串且只包含数字 1 和 0。

具体请看如下示例：

示例 1:

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

示例 2:

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

提示：

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

题目来源：LeetCode官网题目难度：⭐⭐

三、思路分析：

上一题刚刷加一。这又出来一题二进制求和，思路相对还是比较清晰的，逢2进1嘛。整体思路就是将两个字符串较短的用 0 补齐，使得两个字符串长度一致，然后从末尾进行遍历两两计算，得到最终结果。

不确定最后的结果是否会多出一位进位，所以根据进位标记进行判断：

定义一个进位标记flag，然后再进行值相加 sum = a.charAt(i) + b.charAt(i) + flag；此时sum就存在三种情况。
当sum = 2，说明需要进位，flag = 1，此时ans = ‘0’+ans；
当sum = 3，说明不仅需要进位，flag = 1，此时ans= ‘1’ + ans；
当sum为其他，则不需要进位，flag = 0；ans = sum+ans;

四、算法实现：

补齐法_AC代码：

具体算法代码实现如下：

class Solution {
     public String addBinary(String a, String b) {
         String ans = "";
         //补0
         if (a.length() < b.length()) {
             String temp = a;
             a = b;
             b = temp;
         }
         //长度做差
         int len =  a.length() - b.length();
         //补零操作
         if (a.length() != b.length()) {
             for (int i = 0; i < len; i++) {
                 b = '0' + b;
             }
         }
         //标记是否需要进位
         int flag = 0;
         //进行叠加
         for (int i = a.length() - 1; i >= 0; i--) {
             int aNum = a.charAt(i) - '0';
             int bNum = b.charAt(i) - '0';
             int sum = aNum + bNum + flag;
             //需要进位且本身=0
             if (sum == 2) {
                 ans = "0" + ans;
                 flag = 1;
                 //需要进位，且本身=1
             } else if (sum == 3) {
                 ans = "1" + ans;
                 flag = 1;
             } else {
                 //不需要动
                 ans = sum + ans;
                 flag = 0;
             }
         }
         //确保最后一位需要进位
         if (flag == 1) {
             ans = "1" + ans;
         }
         return ans;
     }
 }