二分法及C++之Vector容器，位运算

基础C++知识

位运算

1. 按位与 & 如果两个相应二进制位都为1，则该位的结果值为1，否则为0.

2. 按位或 | 如果相应的二进制位中只要有一个为1，则该位的结果值为1.

3. 按位异或 ^ 若参加运算的两个二进制位值相同则为0，否则为1

4. 取反 ~

5. 移位运算

左移运算

<< 用来将一个数的各二进制位全部左移n位，低位以0补充，高位越界后舍弃，这样可能会导致数值的符号发生正负变化。

1左移n位： 1<<n=2^n （假设未越界） n左移一位： n<<1=2*n （假设未越界）

下面是越界的情况:

int a =9115 0010001110011011 (9115的二进制表示)
a<<1=18230 0100011100110110 (高位越界后舍弃)
a<<2=-29076 1000111001101100(高位越界后舍弃，此时高位为1，代表负值)

note: 左移是乘2的运算，但是要注意正负值发生改变的情况，如果最高位由0变成1或者由1变成0，那么就不是单纯的数值乘2那么简单了。

右移运算

>> 将一个数的二进制右移一位，右位越界舍弃，最高位补0.右移运算不会出现数值符号改变的情况。

note: 右移>>可以理解为除以2向下取整，与int/2可以理解为除以2向上取整。
即（-3）>>2=-2和（-3）/2=-1的区别。

位运算的常用技巧

这些之后有时间在补充。

1. 判断奇偶性

2.求a的b次方

3.找出未重复的数

4. 用O（1）时间检测整数n是否是2的幂次

5.计算在一个32位的整数的二进制表示中有多少个1

6. 快速幂

7. 二进制压缩状态

C++ 中vector<vector >的基本使用方法

vector 是一种封装可以动态改变数组大小的顺序容器（sequence container），跟其他容器一样，可以存放各种类型的对象。其即具有数组可以使用索引和指针 操作数组的优势，又可以避免数组容易出现越界且动态性不好的缺点。

vector常见的定义方式

vector<vector <int> >,最后一个>之前应该有一个空格，要不然有些编译器会报错。

1. vector<vector<int> >array2(3)
% array2可以保存3个变量，向量的长度是可以改变的，`array[i]`返回的是第`i`个向量，`array[i][j]`返回的是第`i`个向量中的第`j`个元素。

2. vector<int> a(5)； //定义了5个整型元素的向量，其初值是0。

3. vector<int> a(5,1); //定义了5个整型元素的向量，且给出每个元素的初值为1.
  
4. vector<int>a(b);// 用b向量创建a向量，整体复制性赋值

5. vector<int>a(b.begin(),b.begin()+3); // 定义a值为b中第0个到第2个（共三个）元素。
  
6. int b[7]={1,2,3,4,5,6,7}; vector<int>a(b,b+7); // 从数组b中获取初值。
  
7. 创建一维vector
vector<int>numbers;  // 不指明长度
  
vector<int>numbers(n); // 指明长度为n

8. 创建二维m*n vector

创建m*n的二维vector. vector <vector >nums(m,vector (n)); //m*n的二维vector，初始化为包含m个vector对象，每个对象都是一个新创建的vector的拷贝，而这个新创建的vector初值为0.

9. 动态创建m*n的二维vector

• method 1

vector<vector<int> > nums;
nums.resize(m);
for (int i=0;i<m;i++) nums[i].resize(n);

• method 2

  vector<vector<int> >nums;
   nums.resize(m,vector<int>(n));

获得二维数组的行数：nums.size();

获得二维数组的列数： nums[0].size();

数组的遍历：

  
  int m=nums.size(),n=size[0].size();
  for(int i=0;i<m;i++){
    for(int j=0;j<n;j++){
      cout<<nums[i][j]<<endl;
    }
  }
     

基本操作

a. 头文件 #include<vector>

b. 创建vector对象：vector dp;

c. 尾部插入数字： dp.push_back(a);

d. 使用下标访问元素，cout<< dp[0]<<endl;

e. 使用迭代器访问元素：

  vector::iterator it;
  for (it=dp.begin();it!=dp.end();it++) cout<<*it<<endl;

f. 删除元素 dp.erase(dp.begin()+2); 删除第3个元素. dp.erase(dp.begin()+i,dp.begin()+j);删除区间[i,j-1].

删除最后一个元素：dp.pop_back();

g. 获取向量大小： dp.size();

h. 清空vector：dp.clear();

i: 排序：sort(dp.begin(),dp.end());

j: 翻转: reverse(dp.begin(),dp.end());

k: 合并两个vector：

vector<int>nums1(m),nums2(n);
vector<int>nums;
nums.resize(m+n);
merge(nums1.begin(),nums.end(),nums2.begin(),nums.end(),nums);

l; 判断vector是否为空; vector.empty();

vector<int> 与vector<int *>的区别

1. vector<int> 不需要动态的操作内存，不用担心内存泄漏的问题，但是对于vector<int*>这种方式要注意new和delete的成对使用

2. 当int换成其他类型或结构或类时，用vector<int*>会节省内存。

3.当需要对变量不断读写操作时，最好使用指针形式，仅仅通过传递指针可以加快访问速度。

  vector<int> vecTemp;
  for(int i=0;i<10;i++){
  vecTemp.push_back(i);   //这种方式不需要动态new内存，也不需要删除。        
  }
                        

  vector<int*> vecTemp;
  for (int i=0;i<10;i++){
       int* nTemp= new int;  
       *nTemp=i;
       vecTemp.push_back(nTemp);
}
                    

vector *a;

当使用这种vector指针时，指针a指向的是存放整型的vector，是不能使用a[i]访问值的，只能通过a->at[i]访问值。

vector<int>& a与vector<int> a的区别

带&代表传入函数的是vector的引用，函数内部对vector改动，vector就会改变；而vector<int> a传入的是vector的复制品，在地址空间重新开辟了一块地址，函数内部对其改动不会影响原vector的值。

二分法

二分查找使用的前提条件是有序数组且无重复元素，如果有重复元素的话，会出现使用二分查找返回的元素下标可能不是唯一的。

二分法边界的确定

1. 左闭右闭

• while (left<=right) 要使用<=，因为left==right有意义.
• if(nums[middle]>target),right要赋值middle-1，因为当前这个nums[middle]一定不是target,接下来要查找的便是middle-1

• C++的实现

  class Solution(){
  public:
   int search(vector<int>& nums, int target){
      int left=0;
      int right=nums.size()-1;  // 定义target在左闭右闭的区间里。
   while (left<=right){
      int middle=left+((right-left)/2); //防止溢出，等同于（left+right）/2
      if (nums[middle]>target){
          right=middle-1;
         }else if (nums[middle]<target){
          left=middle+1                                }else{
          return midlle;                                 }                       
     }
    return -1;   // 未找到目标
   }
  };
  
  

2. 左闭右开

• while(left<right)
• if(nums[middle]>target), right更新为middle，因为当前nums[middle]不等于target。

• C++的实现

  class Solution(){
  public:
    int search(vector<int>&nums, target){
    int left=0;
    int right =nums.size();   //注意与左闭右闭的区别
   while (left<right){
      int middle = left+((right-left)>>1);
      if (nums[middle]>target){
        right=middle;
      }else if(nums[middle]<target){
       left=middle+1;                               }else{
      return middle;                      }
       return -1;                              
      }
    }
  
  }