LeetCode力扣每日一题(Java):67、二进制求和

2023-12-14 13:19:30

一、题目

二、解题思路

1、我的思路(残缺版)

好家伙,又是一道我盯着屏幕看了半天还没思路的题目

我只有一部分残缺的思路,在这里先写下来吧

我们可以先创建一个空字符串(后文称新字符串),用于后续存储相加后的二进制数

二进制数相加是从低位开始的,在相加的过程中,我们会先得到低位的数值,后得到高位的数值,也就是说在逐位存储相加结果的过程中,要把新得到的数值插入到新字符串的最前面。可是我们熟知的关于字符串的API都是在最末尾追加元素,要怎么实现在头部插入元素呢?

于是我往回翻了之前写过的博客,在看到StringBuilder的成员方法后,我有了思路

具体API见这篇博客:小白备战蓝桥杯:Java常用API-CSDN博客

我们可以将每位相加得到的结果依次追加到StringBuilder字符串末尾,最后反转字符串,再将StringBuilder转换成String返回即可

于是我写了如下残缺的代码

StringBuilder add = new StringBuilder("");


        add.reverse();
        return add.toString();

可写完这一步后,我又在相加操作上犯了难,怎么将字符串中的1和0转换成数值1和0呢?进位操作要怎么处理呢?如果两个字符串a和b的位数不同,又要怎么操作呢?

原谅我这题需要直接放官方题解了,因为我确实没写出来

2、官方题解

StringBuffer ans = new StringBuffer();

        int n = Math.max(a.length(), b.length()), carry = 0;
        for (int i = 0; i < n; ++i) {
            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.append((char) (carry % 2 + '0'));
            carry /= 2;
        }

        if (carry > 0) {
            ans.append('1');
        }
        ans.reverse();

        return ans.toString();

纯看代码是不是有点看不懂?没关系,我们给它加上注释

public String addBinary(String a, String b) {
    // 用于存储结果的字符串
    StringBuffer ans = new StringBuffer();

    // 计算最长的字符串长度
    int n = Math.max(a.length(), b.length());
    // 进位值
    int carry = 0;
    
    // 从低位开始逐位相加
    for (int i = 0; i < n; ++i) {
        // 获取对应位置的字符并转换为数字,如果超出字符串长度则使用 0
        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.append((char) (carry % 2 + '0'));
        // 更新进位值
        carry /= 2;
    }

    // 如果最高位还有进位,需要额外添加一个 1 到结果字符串中
    if (carry > 0) {
        ans.append('1');
    }
    // 反转结果字符串得到最终结果
    ans.reverse();

    return ans.toString();
}

看完官方题解后,我发现我当初的第一个疑问(怎么将字符串中的1和0转换成数值1和0呢?)解决起来还是非常简单的,看来还是我积累的不够

其实只用利用ASCII码即可,整数和字符相加或相减时,会根据ASCII码进行运算 -> 字符串对应位置字符 - ‘0’ =?字符串对应位置数值,也就是上述代码中的? a.charAt(a.length() - 1 - i) - '0'

相应地,(char)(字符串对应位置数值 + '0')?=?字符串对应位置字符,也就是上述代码中的 (char) (carry % 2 + '0')

文章来源:https://blog.csdn.net/lbcbjtlhmjq/article/details/134987944
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。