leetcode解题：Add binary问题

2022-11-15 22:15:07

顺便把之前做过的一个简单难度的题也贴上来吧

67. Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

这种问题其实大多数人都做烂了但是在实际应用中这个问题应用很广泛有用二进制数基本就要处理加减乘除

一种最容易理解的方法但是不高效那就是转为十进制处理后再转为二进制当然这就不是我们玩leetcode的目的了

这里给出一种做这种问题的普遍解法先低位相加定义一个carry表示进位再处理多出来的部分

话不多说直接敲代码

还是基本功有问题没有找到valueof o应该大写

改正编译通过了看能不能ACCEPT

wrong answer 普天同庆

看看代码逻辑哪里出问题了看答案好像是最后的carry没有加上去日常看不出来为啥没起作用。。。。

打开eclipse 调试看看。。

运行结果果然是0 设断点

我服了我自己。。。 sum是Int 忘记处理字符和强制转换了果然要细心再细心。。。

阔以再leetcode试试

粗心被雷劈有一段忘记加carry了

成功解决- -

表现很中庸 6ms 只是解决了问题而已很显然这不是我的目的

日常看别人的优秀解决方案 2ms

public String addBinary(String a, String b) {

	char[] aArray = a.toCharArray();

	char[] bArray = b.toCharArray();

    char[] sumArray = new char[Math.max(a.length(), b.length()) + 1];

    int index = sumArray.length - 1, carry = 0;

    for(int aIndex = a.length()-1, bIndex = b.length()-1; aIndex >=0 || bIndex >= 0; aIndex--, bIndex--){

        int aNum = aIndex < 0 ? 0 : aArray[aIndex] - '0';

        int bNum = bIndex < 0 ? 0 : bArray[bIndex] - '0';

        int sum = aNum + bNum + carry;

        sumArray[index--] = (char)('0' + (sum % 2));

        carry = sum / 2;

    }

    sumArray[0] = (char)('0' + carry);

    return carry == 0 ? new String(sumArray, 1, sumArray.length - 1): new String(sumArray);

}

　　牺牲了一定的空间复杂度如果实际应用中数非常大不建议这样做

码农公寓

相关文章