当前位置：首页 > article >正文

线性表力扣67. 二进制求和

article 2024/9/25 13:21:22

题目 67. 二进制求和

翻译

主要思路

核心思路是像竖式计算一样，不过需要将字符串a和b反转后逐位进行二进制计算得到字符串c，最后再将c反转就是答案

逐位计算的时候利用count，在将a和b当前位置数字相加后通过模2来决定字符串c对应位置的数字

count /= 2，是清除了当前的进位，同时保留了下一位的进位

最后如果count不为0，说明字符串c还要进一位

第一次写错误

代码

class Solution {
public:
    string addBinary(string a, string b) {
        string ansString;   
        int scanlLength = max(a.size(), b.size());    //需要扫描的长度取两个字符串中最大值
        reverse(a.begin(), a.end());    //翻转两个字符串
        reverse(b.begin(), b.end());
        int count = 0;  //count表示是否进位
        for(int i = 0; i < scanlLength; i++) {
            count += i < a.length() ? (a.at(i) == '1') : 0;  //count 上递增，如果i还小于字符串a的长度，看字符串a当前位置是不是1，如果是1，a.at(i) == '1'返回1，则count递增1，否则递增0，下面一条语句同理 
            count += i < b.length() ? (b.at(i) == '1') : 0;
            ansString.push_back((count % 2) ? '1' : '0');   //count表示当前位计算结果，如果count % 2 == 0，说明要么计算结果是0，不用进位，当前位就是0，要么计算结果是2，如果是1，要么计算结果是3，要进位；进位后是1，要么计算结果是1，不用进位
            count /= 2;     //保留了下一位的进位
        }
        if(count) { //如果count不为0，表示还要往下进一位
            ansString.push_back('1');
        }
        reverse(ansString.begin(), ansString.end());
        return ansString;
    }
};