编程题常用知识点的review。
most important:想好（1）详尽步骤（2）边界特例，再开始写代码。
I.vector
#include <iostream>//0.头文件。 特性: 连续存储，动态双倍分配增长#include <vector>#include <algorithm> //relevantusing namespace std;bool comp(int a,int b){return a>b;}int main(){//1.创建与初始化vector<int> v1(10,0);vector<int> v2(v1);//也可拷贝初始化 vector<int> v2=v1;vector<vector<int>> ivec(10,v1); //二维vector//2.返回数量与判断空if(v1.empty())cout<<"it's empty";auto n=v1.size();//3.修改元素与遍历元素for(int i=0;i<n;i++)v1[i]=1;vector<int>::iterator it; //迭代器for(it=v1.begin();it!=v1.end();it++)*it=1;//4.插入与删除元素v1.push_back(9);v1.pop_back();v1.insert(v1.begin()+3, 9);//把9插入到第3个元素后面v1.erase(v1.begin()+3); //把第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.structstruct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {} //定义了节点的初始化方法};using namespace std;int main(){vector<int> ivec{1,2,3,4,5,6};//1.创建与初始化ListNode *head=new ListNode(0);//申请一个新节点,注意 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==3){q=new ListNode(0);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 sizestack<int> myStack;myStack.push(9);myStack.push(8);cout<<myStack.top()<<endl;myStack.pop();cout<<myStack.size()<<myStack.empty()<<endl;//2.queue 创建与初始化,基本操作 push pop front back empty sizequeue<int> myQueue;myQueue.push(9);myQueue.push(8);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"]=1; myMap["Lucy"]=3; myMap["Jack"]=2;//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); // 第1个位置开始，长度为3的子串//6.交换两个字符串 y.swap(x);//7.查找字串auto t=y.find(x,0);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&b1010&1100=1000或 a|b 1010|1100=1110异或a^b1010^1100=1001按位取反 ~a~1010=0101左移a<<1 1010<<1=10100带符号右移 a>>1 -1010>>1=-101无符号右移 a>>>1
