programming review (c++): (1)vector, linked list, stack, queue, map, string, bit manipulation

时间:2022-08-22 17:59:49

编程题常用知识点的review。

most important:  想好(1)详尽步骤(2)边界特例,再开始写代码。

I.vector

#include <iostream>
//0.头文件。 特性: 连续存储,动态双倍分配增长
#include <vector>
#include <algorithm> //relevant
using namespace std; bool comp(int a,int b){
return a>b;
} int main(){ //1.创建与初始化
vector<int> v1(,);
vector<int> v2(v1); //也可拷贝初始化 vector<int> v2=v1;
vector<vector<int>> ivec(,v1); //二维vector //2.返回数量与判断空
if(v1.empty())
cout<<"it's empty";
auto n=v1.size(); //3.修改元素与遍历元素
for(int i=;i<n;i++)
v1[i]=; vector<int>::iterator it; //迭代器
for(it=v1.begin();it!=v1.end();it++)
*it=; //4.插入与删除元素
v1.push_back();
v1.pop_back(); v1.insert(v1.begin()+, ); //把9插入到第3个元素后面
v1.erase(v1.begin()+); //把第3个元素后面的那个元素删掉 //5.相关函数 reverse sort
reverse(v1.begin(),v1.end());
sort(v1.begin(),v1.end(),comp); //等价于 sort(v1.rbegin(),v1.rend()); }

II.linked list

#include <iostream>
#include <vector>
//0.struct struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {} //定义了节点的初始化方法
}; using namespace std; int main(){ vector<int> ivec{,,,,,};
//1.创建与初始化
ListNode *head=new ListNode(); //申请一个新节点,注意 head= new ListNode(0)与 head= ListNode(0)的区别
ListNode *p=head,*q;
for(auto i:ivec){ //此乃尾插法,还有头插法,根据情况选择合适的,注意现在有头节点
q=new ListNode(i);
p->next=q;
p=q;
} //2.遍历元素、插入删除元素
p=head;
while(p->next!=NULL){
if(p->next->val==){
q=new ListNode();
q->next=p->next->next;
p->next=q;
}
} /* 3.经典操作: (1) 原地reverse——头插法和尾插法的运用;
(2) 判断cycle——快慢指针;
(3) 找中间节点、找间隔节点——快慢指针;
}
*/ }

III.stack && queue

#include <iostream>
#include <vector> //0.头文件 经常以vector模拟
#include <stack>
#include <queue> using namespace std; int main(){ //1.stack 创建与初始化,基本操作 push pop top empty size
stack<int> myStack;
myStack.push();
myStack.push();
cout<<myStack.top()<<endl;
myStack.pop();
cout<<myStack.size()<<myStack.empty()<<endl; //2.queue 创建与初始化,基本操作 push pop front back empty size
queue<int> myQueue;
myQueue.push();
myQueue.push();
cout<<myQueue.front()<<endl;
cout<<myQueue.back()<<endl;
myQueue.pop();
cout<<myQueue.size()<<myQueue.empty()<<endl; }

IV.map

#include <iostream>
//0.头文件 优点:快速访问/空间换时间/桶的思想,key用来去重,value用来存辅助信息。注意,有时直接用数组进行hash,而不需要借助<map>
#include <map>
using namespace std; int main(){ //1.创建
map<string,int> myMap; //2.访问、修改、增加元素
myMap["Tom"]=; myMap["Lucy"]=; myMap["Jack"]=; //3.删除元素
myMap.erase("Tom"); //也可使用 myMap.erase(myMap.find("hi")); //4.通过key查找元素
if (myMap.find("Tom")==myMap.end())
cout<<myMap.count("Tom")<<endl; //5.遍历,map内部以key的升序排列
for(auto it=myMap.begin();it!=myMap.end();it++){
cout<<it->first<<endl;
cout<<it->second<<endl;
} }

V.string

#include <iostream>
#include <vector>
//0.头文件
#include <string>
#include<sstream> //辅助 using namespace std; int main(){ //1.创建,初始化
string x="hello world",y="ld s";
getline(cin,y); //获得一行,也可再加个终止符参数 //2.常用函数与vector相同 empty, size, push_back, 下标访问 //3.+ - < > =运算符的重载 //4.关于字符变量函数 isalnum,isalpha,isdigit tolower,toupper //5.获得子串
string sub=x.substr(,); // 第1个位置开始,长度为3的子串 //6.交换两个字符串
y.swap(x); //7.查找字串
auto t=y.find(x,);
if(t!=string::npos)
cout<<t; //8.split功能
istringstream strcin(x);
string s;
vector<string> res;
while(strcin >> s)
res.push_back(s); }

VI.bit manipulation

  1. 与                          a&b          1010&1100=1000   
  2. 或                      a|b         1010|1100=1110
  3. 异或                              a^b          1010^1100=1001
  4. 按位取反                         ~a            ~1010=0101
  5. 左移                              a<<1      1010<<1=10100
  6. 带符号右移                     a>>1        -1010>>1=-101
  7. 无符号右移                     a>>>1