E

EdwardWong

V1

2022/09/07阅读:27主题:兰青

二分法及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.找出未重复的数

  1. 用O(1)时间检测整数n是否是2的幂次

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

  1. 快速幂

  2. 二进制压缩状态

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
  1. 创建二维m*n vector

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

  1. 动态创建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*>这种方式要注意newdelete的成对使用

  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>& avector<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; // 未找到目标
    }
    };

  1. 左闭右开
  • 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;
    }
    }

    }

分类:

后端

标签:

后端

作者介绍

E
EdwardWong
V1