每日LeetCode-67. 二进制求和c++

106 阅读 0 评论 70 点赞

我是靠谱客的博主暴躁朋友，最近开发中收集的这篇文章主要介绍每日LeetCode-67. 二进制求和c++，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

学习耗时：1h

给定两个二进制字符串，返回他们的和（用二进制表示）。

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

示例 1:

输入: a = “11”, b = “1”
输出: “100”

解答：

（1）方法一：

不补齐直接遍历<求和+与+移位>

这个大牛的思路很巧妙
思路：直接对目标两个数组进行求和操作，然后再“&1”，即取求和后结果的最低位保存到结果数组；之后再右移取高位进入下一次遍历。
注意事项：
1、定义结果返回数组的时候使用reserve预留足够空间，避免重新分配，增加消耗；
2、循环过程中注意判断两个数组是否已经遍历完；

class Solution {
public:
    string addBinary(string a, string b) {
    
    int i = a.size()-1;
    int j = b.size()-1;
    string res;
    res.reserve(i + j);
    
    int m = 0;
    while(i >= 0 || j >= 0 || m == 1)
    {
        m += i>=0 ? a[i--]-'0' : 0;
        m += j>=0 ? b[j--]-'0' : 0;
        res.push_back((m & 1) +'0');
        m >>=1;
    }
    reverse(res.begin(), res.end());
    
    return res;
    }
 };

LeetCode代码

（2）方法二：

思路：二进制求和，满二进一

首先让两个字符串等长，若不等长，在短的字符串前补零，否则之后的操作会超出索引。
然后从后到前遍历所有的位数，同位相加，这里有一个点，用的是字符相加，利用 ASCII 码，字符在内部都用数字表示，我们不需要知道具体数值，但可知 ‘0’-‘0’ = 0， ‘0’+1=‘1’，以此类推。字符的加减，大小比较，实际上都是内部数字的加减，大小比较
判断相加后的字符，若大于等于字符‘2’，下一位需要进一

第 0位数的相加在这里是单独处理的，因为它可能涉及到字符的插入（即是否需要在最前面加一位数 ‘1’

  class Solution {
  public:
      string addBinary(string a, string b) {
          int al = a.size();
          int bl = b.size();
          while(al < bl) //让两个字符串等长，若不等长，在短的字符串前补零，否则之后的操作会超出索引
          {
              a = '0' + a;
              ++ al;
          }
          while(al > bl)
          {
              b = '0' + b;
              ++ bl;
          }
          for(int j = a.size() - 1; j > 0; -- j) //从后到前遍历所有的位数，同位相加
          {
              a[j] = a[j] - '0' + b[j];
              if(a[j] >=  '2') //若大于等于字符‘2’，需要进一
              {
                  a[j] = (a[j] - '0') % 2 + '0';
                  a[j-1] = a[j-1] + 1;
              }
          }
          a[0] = a[0] - '0' + b[0]; //将ab的第0位相加
          if(a[0] >= '2') //若大于等于2，需要进一
          {
              a[0] = (a[0] - '0') % 2 + '0';
              a = '1' + a;
          }
          return a;
      }
  };

leetcode代码

c++vector的reserve和resize

vector 的reserve增加了vector的capacity，但是它的size没有改变！而resize改变了vector的capacity同时也增加了它的size！
原因如下：
reserve是容器预留空间，但在空间内不真正创建元素对象，所以在没有添加新的对象之前，不能引用容器内的元素。加入新的元素时，要调用push_back()/insert()函数。
resize是改变容器的大小，且在创建对象，因此，调用这个函数之后，就可以引用容器内的对象了，因此当加入新的元素时，用operator[]操作符，或者用迭代器来引用元素对象。此时再调用push_back()函数，是加在这个新的空间后面的。
```
  reverse(lvalues.begin(), lvalues.end());//颠倒字符串，以方便从低位算起计算
```