LEETCODE 67. Add Binary 解题思路分析

题目大意:

二进制求和

给定两个二进制字符串,返回他们的和(用二进制表示)。

输入为非空字符串且只包含数字 1 和 0

示例 1:

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

示例 2:

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=67

解题思路分析:

这是一道简单的二进制加法运算题。与十进制加法相同,我们从低位开始,相同位上的数字相加,同时还要加上前一位的进位数,他们的和与2的余数即是当前位上的数字,与2的商是进位数(进到下一位)。所有位上的数字加完之后,不要忘记查看进位数是否大于0,如果是,则需要将进位数设置到最高位上。

实现代码:

public String addBinary(String a, String b) {
    // 数字a的最低位
    int indexA = a.length()-1;
    // 数字b的最低位
    int indexB = b.length()-1;
    // 返回结果
    StringBuilder sb = new StringBuilder();
    // 进位数
    int carry=0;
    // 从最低位开始循环累加2个数字上的所有位数
    while(indexA>=0||indexB>=0){
        // 数字a当前位上的数,如果已经超过最高位,当前数为0
        int n1=indexA>=0?a.charAt(indexA)-'0':0;
        // 数字b当前位上的数,如果已经超过最高位,当前数为0
        int n2=indexB>=0?b.charAt(indexB)-'0':0;
        // 当前位上的和
        int sum=n1+n2+carry;
        // 和与2的余数为当前位
        int num=sum%2;
        // 和与2的商为进位数
        carry=sum/2;
        // 将当前位加到返回结果的最高位
        sb.insert(0,num);
        // 两个数字均向高位进一位
        indexA--;
        indexB--;
    }
    // 如果进位大于0,将进位加到返回结果最高位
    if(carry>0) sb.insert(0,1);
    // 将返回结果转为字符串返回
    return sb.toString();
}

本题解法执行时间为2ms。

Runtime: 2 ms, faster than 77.75% of Java online submissions for Add Binary.

Memory Usage: 38.6 MB, less than 5.62% of Java online submissions for Add Binary.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
本文链接: https://leetcode.jp/leetcode-67-add-binary-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。