LeetCode:67.二进制求和

LeetCode:67.二进制求和,第1张

67.二进制求和
  • 给你两个二进制字符串,返回它们的和(用二进制表示)。


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



方法一:暴力破解

设置两个指针,分别从两个字符串的尾部往前遍历,每遍历一个字符时,将该字符转换成数字进行相加 *** 作,并判断是否需要进位,并对相加结果对2进行取余,将结果作为字符拼接到最终的结果字符串中。


代码实现
string addBinary(string a, string b) {
    string sRes = "";
    int nIndexA = a.size() - 1;
    int nIndexB = b.size() - 1;
    int nCrayy = 0;
    while (nIndexA >= 0 && nIndexB >= 0) {
      int nAdd = nCrayy + a[nIndexA] + b[nIndexB] - '0' - '0';
      nCrayy = nAdd / 2;
      nAdd %= 2;
      char  cAdd = nAdd + '0';
      sRes = cAdd + sRes;

      nIndexA--;
      nIndexB--;
    }

    for (; nIndexA >= 0; nIndexA--) {
      int nAdd = nCrayy + a[nIndexA] - '0';
      nCrayy = nAdd / 2;
      nAdd %= 2;
      char  cAdd = nAdd + '0';
      sRes = cAdd + sRes;
    }
    for (; nIndexB >= 0; nIndexB--) {
      int nAdd = nCrayy + b[nIndexB] - '0';
      nCrayy = nAdd / 2;
      nAdd %= 2;
      char  cAdd = nAdd + '0';
      sRes = cAdd + sRes;
    }
    if (nCrayy) {
      char c = nCrayy + '0';
      sRes = c + sRes;
    }

    return sRes;
  }

时间复杂度: O ( max ⁡ ( m , n ) ) O(\max(m,n)) O(max(m,n))
空间复杂度: O ( 1 ) O(1) O(1)


哈哈哈哈哈,刷题只会暴力求解。



LeetCode题解

leetcode题解采用的思想也是列竖式的方法,末尾对齐,逐位相加。


leetcode题解所用的方法中首先将字符串首尾反转,在字符串 ab 中较短的一个高位补 0 0 0


每次遍历时将对应位置的答案依次存入答案字符串中,最终将答案反转。


leetcode题解中每次判断需要进行相加的数字时,采用 if 语句进行判断,这种只是基于二进制数字中只存在 0 0 0 1 1 1 两个数字的情况,如果遇到多余两个数字的情况,则需要较多的 if 语句来进行判断。


代码实现
class Solution {
public:
    string addBinary(string a, string b) {
        string ans;
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());

        int n = max(a.size(), b.size()), carry = 0;
        for (size_t i = 0; i < n; ++i) {
            carry += i < a.size() ? (a.at(i) == '1') : 0;
            carry += i < b.size() ? (b.at(i) == '1') : 0;
            ans.push_back((carry % 2) ? '1' : '0');
            carry /= 2;
        }

        if (carry) {
            ans.push_back('1');
        }
        reverse(ans.begin(), ans.end());

        return ans;
    }
};

时间复杂度: O ( max ⁡ ( m , n ) ) O(\max(m,n)) O(max(m,n))

空间复杂度: O ( 1 ) O(1) O(1)

欢迎分享,转载请注明来源:内存溢出

原文地址: https://outofmemory.cn/langs/563005.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-02
下一篇 2022-04-02

发表评论

登录后才能评论

评论列表(0条)

保存