• 关键字:字符串处理、高精度、进制
  • 难度:简单
  • 前置知识:字符串、进制
  • 题目大意:对于给定的两个二进制字符串,计算它们的加法

题目描述

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

For example,

a = "11"

b = "1"

Return "100".

解法

为了叙述的方便,在后文中用ab表示输入的二进制字符串

这道题目相对来说非常简单,同LC43一样是高精度计算的题目,但是这道题目相对来说就要简单很多。主要是因为二进制的进位是非常简单的,要么是0,要么是1,所以我们就没有必要先将字符串转化为数组存储的数字,统一进位之后再转回字符串,而是可以直接就是用一个临时变量来进行存储进位信息,也不会将题目的逻辑变得复杂。

具体的实现主要分为这样几步:

  • 因为字符串的顺序是从高到低进行存储的,不方便对齐进行加法,所以我们将ab中较短的字符串前面添加一些0来使得他们的长度变为一致。
  • 然后从ab的最低位开始逐位做二进制加法,取余数和商记得要用2做除数而不是10。
  • 另外,不要忘记答案的长度可能长于输入的字符串。

这道题目相对简单,是练习高精度这种技巧的一道好题目!

参考代码

class Solution {
public:
    string addBinary(string a, string b) {
        // 先将两个字符串的位数补齐至相同
        int n = max(a.length(), b.length());
        while (a.length() < n) a = "0" + a;
        while (b.length() < n) b = "0" + b;
        // 然后从最低位开始进行加法,使用临时变量存储进位信息
        string ans = "";
        int j = 0;
        for (int i = n - 1; i >= 0; i--) {
            // 计算加法,并考虑之前的进位
            j = j + (a[i] - '0') + (b[i] - '0');
            // 处理进位并计算答案
            ans = (char) ('0' + j % 2) + ans;
            j = j / 2;
        }
        // 判断是否有未处理的进位
        if (j > 0) {
            ans = "1" + ans;
        }
        // 返回答案
        return ans;
    }
};

登录发表评论 注册

反馈意见