编程题常用知识点的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
- 与 a&b 1010&1100=1000
或 a|b 1010|1100=1110
异或 a^b 1010^1100=1001
按位取反 ~a ~1010=0101
左移 a<<1 1010<<1=10100
带符号右移 a>>1 -1010>>1=-101
无符号右移 a>>>1
