LeetCode 67. 二进制求和 学习笔记(Java)

一、题目

  • 原题链接

  • 描述
    给你两个二进制字符串,返回它们的和(用二进制表示)。
    输入为 非空 字符串且只包含数字 1 和 0。

  • 示例1
    输入: a = “11”, b = “1”
    输出: “100”

  • 示例2
    输入: a = “1010”, b = “1011”
    输出: “10101”

二、题解

  • 思路:
    1.将a,b反转;
    2.反转后如果不等长,则在短的末尾补0;
    3.由于要反转后相加,因此计算规则为【各位相加,向后进位】;
    4.判断相加后的数最后一位是不是要进位,进位则在最后添加一位为1,不进位则在最后添加一位为0;
    5.判断添加一位后的数的最后一位是否为0,若为0则应去掉;
    6.反转。

  • 注意点
    1.注意String类型与int数组类型之间的转换;
    2.使用【mark】标记该位的两数相加后是否要向后进位;

三、代码(Java)

class Solution{
    public String addBinary(String a, String b){
    	//反转a、b
        String aReverse = new StringBuffer(a).reverse().toString();
        String bReverse = new StringBuffer(b).reverse().toString();
        int aLen = a.length();
        int bLen = b.length();
        //转换为String数组
        String[] aReverseArr = aReverse.split("");
        String[] bReverseArr = bReverse.split("");
        //String数组转换为int数组
        int[] aReverseIntArr = new int[aLen];
        int[] bReverseIntArr = new int[bLen];
        for(int i=0; i<aLen; i++){
            aReverseIntArr[i] = Integer.parseInt(aReverseArr[i]);
        }
        for(int i=0; i<bLen; i++){
            bReverseIntArr[i] = Integer.parseInt(bReverseArr[i]);
        }

		//反转后的int数组在末尾补零
        int[] newA = new int[Math.max(aLen,bLen)];
        int[] newB = new int[Math.max(aLen,bLen)];
        if(aLen<bLen){
            for(int i = 0; i<aLen; i++){
                newA[i] = aReverseIntArr[i];
                newB[i] = bReverseIntArr[i];
            }
            for(int i = aLen; i<bLen; i++){
                newA[i] = 0;
                newB[i] = bReverseIntArr[i];
            }
        }else if(aLen>bLen){
            for(int i = 0; i<bLen; i++){
                newA[i] = aReverseIntArr[i];
                newB[i] = bReverseIntArr[i];
            }
            for(int i = bLen; i<aLen; i++){
                newA[i] = aReverseIntArr[i];
                newB[i] = 0;
            }
        }else {
        	for(int i=0; i<aLen; i++) {
        		newA[i] = aReverseIntArr[i];
                newB[i] = bReverseIntArr[i];
        	}
        }

        int[] ansInt = new int[newA.length+1];
        //初始mark置0
        int mark = 0;
        //各位相加,向后进位
        for(int i=0; i<newA.length; i++){
            switch(mark+newA[i]+newB[i])
            {
                case 0:
                    mark = 0;
                    ansInt[i] = 0;
                    break;
                case 1:
                    mark = 0;
                    ansInt[i] = 1;
                    break;
                case 2:
                    mark = 1;
                    ansInt[i] = 0;
                    break;
                case 3:
                    mark = 1;
                    ansInt[i] = 1;
                    break;
            }
        }
        //判断最后一位是否要进位
        if(mark==1){
            ansInt[ansInt.length-1] = 1;
        }

		//反转ansInt
        int[] ansIntReverse = new int[ansInt.length];
        for(int i=0; i<ansInt.length; i++){
            ansIntReverse[i] = ansInt[ansInt.length-1-i];
        }
        //int数组类型转为String类型
		//若首位是0则去除
        StringBuffer sb = new StringBuffer();       
        if(ansIntReverse[0]==0) {
        	for(int i=1; i<ansIntReverse.length; i++) {
        		sb.append(ansIntReverse[i]);
        	}
        }else {
        	for(int num: ansIntReverse){
        		sb.append(num);
        	}
        }
        
        return sb.toString();

    }
}

四、总结

  • 几乎是第一次完全自己写出来的一题;
  • 转换过程很繁琐,有待优化;
  • 计算部分,if语句有时不太直观,这里由于二进制下的各位相加情况比较少,换成了更清晰直观的switch语句
上一篇:电商 谷歌插件 生意参谋的 访客数据 下载 版本2


下一篇:[力扣leetcode319]灯泡问题