.8.21-.9.6 the first version

​

1 闰年

(year % 4 == 0 && year % 100 != 0) || (year % 400 = 0)

预处理每个月的天数，用空间换时间

intdaytab[2][13]={{0,31,28,31,30,31,30,31,31,30,31,30,31}{0,31,29,31,30,31,30,31,31,30,31,30,31}}

2 保留几位输出

cout<<fixed<<setprecision(2);

/qq_36667170/article/details/79265224

3.C语言读取text文件

/cprogramming/c-file-io.html

#include<iostream>#include<stdio.h>usingnamespacestd;intmain(){//逐行写FILE*fp=NULL;charbuffw[26];fp=fopen("1.txt","w+");for(inti=0;i<26;i++){buffw[i]='a'+i;}//fprintf(fp,"Thisistestingforfprintf...\n");fputs(buffw,fp);fclose(fp);//逐行读//FILE*fp=NULL;charbuffr[255];fp=fopen("D:\\devcpp\\baoyan\\1.txt","r");while(!feof(fp)){fgets(buffr,255,fp);//printf("%s\n",buff);cout<<buffr;}fclose(fp);}

只读模式创建文件

fp.open("2.txt",fstream::out);

c++读取文件首选

/developer/article/1403612

#include<iostream>#include<fstream>#include<stdio.h>usingnamespacestd;intmain(){//写入fstreamwfile;wfile.open("1.txt");charsdata[26];for(inti=0;i<26;i++){sdata[i]='z'-i;wfile<<sdata[i]<<endl;}//cout<<sdata<<endl;wfile.close();//读取stringdata="";fstreamrfile;rfile.open("1.txt");//rfile.getline(data,27);//读取num-1个字符while(getline(rfile,data))cout<<data<<endl;rfile.close();return0;}

4.vector容器

/w3cnote/cpp-vector-container-analysis.html

//vector容器#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;intmain(){vector<int>obj;vector<int>::iteratorit;for(inti=5;i>=0;i--){obj.push_back(i);}//sort(obj.begin(),obj.end());for(it=obj.begin();it!=obj.end();it++){cout<<*it<<"";}return0;}

5 sort函数

sort（first，last，comp）

起始地址first，last

comp 排序方式默认升序

重写sort函数可以变为降序

#include<iostream>#include<algorithm>#include<cstdio>usingnamespacestd;boolcompare(inta,intb){returna>b;//升序排列，如果改为returna>b，则为降序}intmain(){intn=5;intarr[n];for(inti=0;i<n;i++){scanf("%d",&arr[i]);}sort(arr,arr+n,compare);for(inti=0;i<n;i++){printf("%d",arr[i]);}return0;}

compare函数：

比较函数，在遇到新的排序规则时，黄金法则：当比较函数返回值为true时，表示比较函数是第一个参会将排在第二个参数前面。

/practice/0383714a1bb749499050d2e0610418b1?tpId=40&tqId=21333&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking

#include<iostream>#include<algorithm>#include<string>usingnamespacestd;structstudent{stringname;intgrade;intorder;};boolcompare1(studenta,studentb){if(a.grade==b.grade){returna.order<b.order;}else{returna.grade>b.grade;}}boolcompare2(studenta,studentb){if(a.grade==b.grade){returna.order<b.order;}else{returna.grade<b.grade;}}intmain(){intn;intfunc;cin>>n>>func;studentstu[n];for(inti=0;i<n;i++){cin>>stu[i].name>>stu[i].grade;stu[i].order=i;}if(func==0){sort(stu,stu+n,compare1);}else{sort(stu,stu+n,compare2);}for(inti=0;i<n;i++){cout<<stu[i].name<<""<<stu[i].grade<<endl;}return0;}

6.二分查找

在查找次数很多的情况下，二分查找优于线性查找

二分查找需要先排序，再查找；

while(left<=right){

注意二分法退出循环的条件。

/practice/d93db01c2ee44e8a9237d63842aca8aa?tpId=40&tqId=21531&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking

#include<iostream>#include<algorithm>usingnamespacestd;intBinarySearch(inta,intnum[],intn){intleft=0;intright=n-1;intmid=(left+right)/2;while(left<=right){if(num[mid]==a){return1;}elseif(num[mid]<a){left=mid+1;}else{right=mid-1;}mid=(left+right)/2;}return0;}intmain(){intn,m;while(cin>>n){intarr[n];for(inti=0;i<n;i++){cin>>arr[i];}sort(arr,arr+n);cin>>m;intnum,target;for(inti=0;i<m;i++){cin>>num;target=BinarySearch(num,arr,n);if(target==1){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}}return0;}

7.字符串string

string

/cplusplus/cpp-strings.html

插入删除

长度

#include<iostream>#include<string>usingnamespacestd;intmain(){stringstr="HelloWorld!";intn=str.length();//长度str.insert(0,"zq");//把"zq"插入到位置"0"//cout<<str;str.erase(0,2);//删除从位置0开始的2个字符str.clear();cout<<str;return0;}

常用函数

find（）

没找到返回-1

substr（）

下标从0开始

#include<iostream>#include<string>usingnamespacestd;intmain(){stringstr="HelloWorld!";intfound=str.find("Hello");cout<<found<<endl;stringstr1=str.substr(0,5);cout<<str1;return0;}

常见应用

巧用ASCII码计算

/practice/a5edebf0622045468436c74c3a34240f?tpId=60&tqId=29490&tPage=1&ru=/kaoyan/retest/1001&qru=/ta/tsing-kaoyan/question-ranking

#include<iostream>#include<string>usingnamespacestd;intmain(){stringstr1,str2;cin>>str1>>str2;intlen1,len2;len1=str1.length();len2=str2.length();intsum=0;for(inti=0;i<len1;i++){for(intj=0;j<len2;j++){sum=sum+(str1[i]-'0')*(str2[j]-'0');}}cout<<sum;return0;}

getline()可以获取一行带空格的字符串，cin>>str遇到空格就会停止输入

/practice/136de4a719954361a8e9e41c8c4ad855?tpId=61&tqId=29505&tPage=1&ru=/kaoyan/retest/1002&qru=/ta/pku-kaoyan/question-ranking

#include<iostream>#include<string>#include<algorithm>usingnamespacestd;intmain(){stringstr;intsym;while(getline(cin,str)){for(inti=0;i<str.length();i++){if(str[i]<='z'&&str[i]>='a'){sym=str[i]-'a';sym=(sym+1)%26;str[i]='a'+sym;}if(str[i]<='Z'&&str[i]>='A'){sym=str[i]-'A';sym=(sym+1)%26;str[i]='A'+sym;}}for(inti=0;i<str.length();i++){cout<<str[i];}cout<<endl;}return0;}

循环平移

取余的方法P49

/practice/ff99c43dd07f4e95a8f2f5448da3772a?tpId=61&tqId=29562&tPage=4&ru=/kaoyan/retest/1002&qru=/ta/pku-kaoyan/question-ranking

字母出现次数统计

用一个number数组统计各个出现的概率

学会构造辅助数组

/practice/4ec4325634634193a7cd6798037697a8?tpId=63&tqId=29574&tPage=1&ru=/kaoyan/retest/9001&qru=/ta/zju-kaoyan/question-ranking

#include<iostream>#include<cstring>#include<algorithm>#include<cstdio>usingnamespacestd;intnum[128];//128个ASCII码intmain(){stringstr1,str2;while(getline(cin,str1)){if(str1=="#"){break;}getline(cin,str2);memset(num,0,sizeof(num));for(inti=0;i<str2.size();i++){num[str2[i]]++;}for(inti=0;i<str1.size();i++){printf("%c%d\n",str1[i],num[str1[i]]);}}return0;}

int的范围

int有32位，2^32-1，注意int的范围使用

/practice/5928127cc6604129923346e955e75984?tpId=61&tqId=29517&tPage=1&ru=/kaoyan/retest/1002&qru=/ta/pku-kaoyan/question-ranking

注意pow函数，需要头文件<math.h>,pow(2,n);

#include<iostream>#include<string>#include<algorithm>#include<math.h>usingnamespacestd;intmain(){strings;while(cin>>s){intsum=0;for(inti=0;i<s.length();i++){if(s[i]=='0')continue;sum=sum+(s[i]-'0')*(pow(2,s.length()-i)-1);}cout<<sum<<endl;}}

首字母大写问题

/practice/91f9c70e7b6f4c0ab23744055632467a?tpId=61&tqId=29529&tPage=2&ru=/kaoyan/retest/1002&qru=/ta/pku-kaoyan/question-ranking

复习：注意getline函数的使用（C语言可以用gets）

大写与小写字母的ASCII差值的使用

#include<iostream>#include<string>#include<algorithm>usingnamespacestd;intmain(){strings;intp;while(getline(cin,s)){if(s[0]>='a'&&s[0]<='z'){p=s[0]+'A'-'a';s[0]=p;}for(inti=1;i<s.size();i++){if(s[i]==''||s[i]=='\t'||s[i]=='\n'||s[i]=='\r'){i=i+1;if(s[i]>='a'&&s[i]<='z'){p=s[i]+'A'-'a';s[i]=p;}else{i=i-1;}}}cout<<s;}}

字符串匹配

kmp算法

重点理解next数组的求法

#include<iostream>#include<string>#include<algorithm>//KMP算法usingnamespacestd;constintMAXM=10000;constintMAXN=1000000;intnextTable[MAXM];intpattern[MAXM];inttext[MAXN];//创建next表voidGetNextTable(intm){intj=0;nextTable[j]=-1;inti=-1;while(j<m){if(i==-1||pattern[i]==pattern[j]){i++;j++;nextTable[j]=i;}else{i=nextTable[i];}}}intmain(){return0;}

8 数据结构一

向量

vector

主要应用于不知道需要多大数组的方法

#include<vector>

push_back()

pop_back()

empty()

size()

insert()

erase()

clear()

begin()

end()

#include<iostream>#include<string>#include<vector>usingnamespacestd;vector<int>obj;intmain(){for(inti=0;i<5;i++){obj.push_back(i);}obj.insert(obj.begin(),3,15);obj.pop_back();for(inti=0;i<obj.size();i++){cout<<obj[i]<<endl;}obj.erase(obj.begin()+5,obj.end());vector<int>::iteratorit;for(it=obj.begin();it!=obj.end();it++){cout<<*it<<"";}obj.clear();return0;}

/practice/ccc3d1e78014486fb7eed3c50e05c99d?tpId=60&tqId=29492&tPage=1&ru=/kaoyan/retest/1001&qru=/ta/tsing-kaoyan/question-ranking

求因数

#include<iostream>#include<vector>usingnamespacestd;ints(intx){intsum=0;for(inti=1;i<=x/2;i++){if(x%i==0){sum=sum+i;}}//cout<<sum<<endl;returnsum;}intmain(){vector<int>obj1;vector<int>obj2;for(inti=2;i<=60;i++){if(i==s(i)){obj1.push_back(i);}elseif(i<s(i)){obj2.push_back(i);}}cout<<"E"<<":";for(inti=0;i<obj1.size();i++){cout<<""<<obj1[i];}cout<<endl;cout<<"G"<<":";for(inti=0;i<obj2.size();i++){cout<<""<<obj2[i];}return0;}

队列

STL-queue

#include<queue>

queue<type>name

empty()

size()

push()

pop()

front()

back()

队头删除元素

队尾添加元素

队列应用约瑟夫问题

循环队列

案例

#include<iostream>#include<queue>#include<algorithm>usingnamespacestd;//模拟循环队列intmain(){intn,p,m;while(cin>>n>>p>>m){if(n==0&&p==0&&m==0){break;}queue<int>children;for(inti=1;i<=n;i++){children.push(i);//加入编号}for(inti=1;i<p;i++){children.push(children.front());children.pop();//把编号为p的放在第一位}while(!children.empty()){for(inti=1;i<m;i++){//m-1个小孩重新入队children.push(children.front());children.pop();}if(children.size()==1){cout<<children.front()<<endl;}else{cout<<children.front()<<',';}children.pop();}}return0;}

栈

stack

stack<typename>name

empty()

size()

push()

pop()

top()和队列不同的地方，只能访问栈顶

栈的应用

无法实现确定存放容器的大小

逆序输出

/practice/c54775799f634c72b447ef31eb36e975?tpId=40&tqId=21440&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking

注意：int最大值：2^31-1=214748364（9位）

long long 最大值 2^64-1=9223372036854775807（19位）

#include<iostream>#include<string>#include<algorithm>#include<stack>usingnamespacestd;stack<longlong>st;//用long longintmain(){intn;while(cin>>n){for(inti=0;i<n;i++){longlongnum;cin>>num;st.push(num);}while(!st.empty()){cout<<st.top()<<"";st.pop();}cout<<endl;}return0;}

括号匹配

括号左右匹配

表达式求值

简单计算器

用栈解决

数据栈

符号栈

/practice/5759c29a28cb4361bc3605979d5a6130?tpId=63&tqId=29576&tPage=1&ru=/kaoyan/retest/9001&qru=/ta/zju-kaoyan/question-ranking

#include<iostream>#include<algorithm>#include<stack>#include<string>#include<iomanip>usingnamespacestd;intpr(charc){//优先级顺序if(c=='#'){return0;}elseif(c=='$'){return1;}elseif(c=='+'||c=='-'){return2;}else{return3;}}//取参与运算的数据doublegetNumber(strings,int&index){doublenumber=0;while(s[index]>='0'&&s[index]<='9'){number=number*10+s[index]-'0';index++;}returnnumber;cout<<1;cout<<number<<endl;}//计算doubleCalculate(doublex,doubley,charop){doubleresult=0;if(op=='+'){result=x+y;}elseif(op=='-'){result=x-y;}elseif(op=='*'){result=x*y;}elseif(op=='/'){result=x/y;}returnresult;}intmain(){stringstr;while(getline(cin,str)){if(str=="0"){break;}intindex=0;//字符串处理定位stack<double>data;//数据栈stack<char>op;//运算符栈str=str+'$';op.push('#');//cout<<str;while(index<str.size()){if(str[index]==''){index++;}elseif(str[index]>='0'&&str[index]<='9'){data.push(getNumber(str,index));//cout<<str;//cout<<data.top();//cout<<"zq";}else{if(pr(op.top())<pr(str[index])){op.push(str[index]);index++;//cout<<str;}else{doubley=data.top();//x和y顺序不能反data.pop();doublex=data.top();data.pop();//cout<<str;data.push(Calculate(x,y,op.top()));op.pop();//cout<<str;}}}//cout<<op.top();cout<<fixed<<setprecision(2)<<data.top()<<endl;}return0;}

#include<iostream>#include<stack>#include<string>#include<iomanip>usingnamespacestd;stack<double>num;stack<char>op;//优先级intpr(chars){if(s=='#'){return0;}elseif(s=='$'){return1;}elseif(s=='+'||s=='-'){return2;}else{return3;}}doubleresult(doublen1,doublen2,chart){if(t=='+'){returnn1+n2;}elseif(t=='-'){returnn1-n2;}elseif(t=='*'){returnn1*n2;}elseif(t=='/'){returnn1/n2;}}intmain(){stringstr;while(getline(cin,str)){if(str=="0"){break;}else{inti=0;op.push('#');str=str+'$';intlen=str.length();while(i<len){if(str[i]==''){i++;//cout<<i<<endl;}elseif(str[i]>='0'&&str[i]<='9'){intsum=0;while(str[i]>='0'&&str[i]<='9'){sum=sum*10+str[i]-'0';i++;}num.push(sum);//cout<<num.top()<<endl;}else{//cout<<str[i]<<endl;if(pr(op.top())<pr(str[i])){//cout<<str[i]<<endl;op.push(str[i]);//cout<<op.top()<<endl;i++;}else{doublet1=num.top();num.pop();doublet2=num.top();num.pop();chart=op.top();op.pop();doubled=result(t2,t1,t);num.push(d);}}}}cout<<fixed<<setprecision(2)<<num.top()<<endl;num.pop();}}

9 数学问题

进制转换

字符串的加减乘除

/practice/fd972d5d5cf04dd4bb4e5f027d4fc11e?tpId=60&tqId=29498&tPage=2&ru=/kaoyan/retest/1001&qru=/ta/tsing-kaoyan/question-ranking

//author：Q_Zhang#include<iostream>#include<string>#include<vector>usingnamespacestd;stringDivide(stringstr,intx){//字符串除法intremainder=0;//余数for(inti=0;i<str.size();i++){intnum=remainder*10+str[i]-'0';//每一步余数与下一位的组合str[i]=num/x+'0';//除法运算remainder=num%x;//在这一位的余数}intpos=0;cout<<remainder<<endl;while(str[pos]=='0'){//去除产生多余的0pos++;}returnstr.substr(pos);}intmain(){stringx;cin>>x;x=Divide(x,5);cout<<x;return0;}

最大公约数，最小公倍数

辗转相除法求最大公约数

两数乘积除以最大公约数即为最小公倍数

非递归

/practice/6f2c84bc438eb5ef05e382536fd3?tpId=40&tqId=21492&tPage=8&rp=8&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking

#include<iostream>usingnamespacestd;intmax(inta,intb){intr;if(a<b){r=a;a=b;b=r;}r=a%b;while(r!=0){a=b;b=r;r=a%b;}returnb;}intmain(){intm,n,result;while(cin>>m>>n){result=max(m,n);cout<<result<<endl;}return0;}

递归很简单自行查阅

质数

素数筛法

找到一个素数，就将它所有倍数均标记为非素数，则判定其为素数，并标记它的所有倍数为非素数，然后继续遍历

/practice/7f4be54b37a04fdaa4ee545819151114?tpId=66&tqId=29630&tPage=1&ru=/kaoyan/retest/1004&qru=/ta/buaa-kaoyan/question-ranking

#include<iostream>#include<vector>usingnamespacestd;constintMAXN=10001;vector<int>prime;boolisPrime[MAXN];voidInit(){for(inti=0;i<MAXN;i++){isPrime[i]=true;}isPrime[0]=false;isPrime[1]=false;for(inti=2;i<MAXN;i++){if(!isPrime[i]){continue;}prime.push_back(i);for(intj=i*i;j<MAXN;j=j+i){isPrime[j]=false;}}}intmain(){Init();intn;booloutput=false;while(cin>>n){for(inti=0;i<prime.size();i++){if(prime[i]>=n){break;}elseif(prime[i]%10==1){output=true;cout<<prime[i]<<"";}}if(!output){cout<<-1;}cout<<endl;}return0;}

质数判断

/practice/5fd9c28b1ce746dd99287a04d8fa9002?tpId=40&tqId=21494&tPage=8&rp=8&ru=%2Fta%2Fkaoyan&qru=%2Fta%2Fkaoyan%2Fquestion-ranking

#include<iostream>#include<cmath>usingnamespacestd;boolJudge(intx){if(x<2){returnfalse;}intbound=sqrt(x);for(inti=2;i<=bound;i++){if(x%i==0){returnfalse;}}returntrue;}intmain(){intn;bools;while(cin>>n){s=Judge(n);if(s){cout<<"yes"<<endl;}else{cout<<"no"<<endl;}}return0;}

分解质因数

/practice/20426b85f7fc4ba8b0844cc04807fbd9?tpId=60&tqId=29479&tPage=1&ru=/kaoyan/retest/1001&qru=/ta/tsing-kaoyan/question-ranking

、

#include<iostream>#include<algorithm>#include<cmath>usingnamespacestd;intmain(){intn;while(cin>>n){intnum=0;intbound=sqrt(n);for(inti=2;i<=bound;i++){while(n%i==0){num++;n=n/i;}}if(n!=1)num++;//特别注意：如果n为质数的情况下cout<<num<<endl;}return0;}

快速幂

核心思想：将指数化为2进制数，1对应的位是快速求幂的分解的指数

#include<iostream>#include<cmath>#include<algorithm>usingnamespacestd;intFast(inta,intb,intmod){intanswer=1;while(b!=0){//核心思想：转化为2进制if(b%2==1){answer=answer*a;answer=answer%mod;}b=b/2;a=a*a;a=a%mod;}returnanswer;}intmain(){inta,b;while(cin>>a>>b){if(a==0&&b==0){break;}cout<<Fast(a,b,1000)<<endl;}return0;}

矩阵快速幂

原理同快速幂，初始状态为单位矩阵

大整数的加减乘除 重要

/practice/4c39c984ea3848b48e111b8e71ec1dd4?tpId=69&tqId=29656&tPage=1&ru=/kaoyan/retest/11002&qru=/ta/hust-kaoyan/question-ranking

#include<iostream>#include<string>#include<vector>#include<algorithm>usingnamespacestd;voidSwitch(string&a,string&b){stringc=a;a=b;b=c;}intmain(){stringa,b;intlen1,len2,p;while(cin>>a>>b){vector<int>obj;len1=a.size();len2=b.size();if(len2<len1){Switch(a,b);}intremain=0;inti=a.size()-1;//特别注意：交换过后需要重新求解长度intj=b.size()-1;for(;i>=0;i--,j--){p=a[i]-'0'+b[j]-'0'+remain;if(p>=10){remain=1;p=p-10;obj.push_back(p);}else{obj.push_back(p);remain=0;}}for(;j>=0;j--){p=b[j]-'0'+remain;if(p>=10){remain=1;p=p-10;obj.push_back(p);}else{obj.push_back(p);remain=0;}}if(remain==1){obj.push_back(1);}for(intk=obj.size()-1;k>=0;k--){cout<<obj[k];}obj.clear();cout<<endl;}return0;}

第二种思路：进位统一处理

#include<iostream>#include<string>#include<vector>#include<algorithm>usingnamespacestd;voidSwitch(string&a,string&b){stringc=a;a=b;b=c;}intmain(){stringa,b;intlen1,len2,p;while(cin>>a>>b){vector<int>obj;len1=a.size();len2=b.size();if(len2<len1){Switch(a,b);}intremain=0;inti=a.size()-1;intj=b.size()-1;for(;i>=0;i--,j--){p=a[i]-'0'+b[j]-'0'+remain;if(p>=10){remain=1;p=p-10;obj.push_back(p);}else{obj.push_back(p);remain=0;}}for(;j>=0;j--){p=b[j]-'0'+remain;if(p>=10){remain=1;p=p-10;obj.push_back(p);}else{obj.push_back(p);remain=0;}}if(remain==1){obj.push_back(1);}for(intk=obj.size()-1;k>=0;k--){cout<<obj[k];}obj.clear();cout<<endl;}return0;}

乘法稍微改一下就成

#include<iostream>#include<string>usingnamespacestd;intmain(){stringa,b;intlen1,len2,len3,i,j,k=0;cin>>a;cin>>b;len1=a.length();len2=b.length();len3=len1+len2;intaa[len1+1]={0},bb[len2+1]={0},cc[len3+1]={0};for(i=1;i<=len1;i++){aa[i]=a[len1-i]-'0';}for(i=1;i<=len2;i++){bb[i]=b[len2-i]-'0';}for(i=1;i<=len1;i++){for(j=1;j<=len2;j++){cc[i+j-1]=cc[i+j-1]+aa[i]*bb[j]; //小技巧要注意}}for(i=1;i<=len3;i++){cc[i+1]=cc[i+1]+cc[i]/10;cc[i]=cc[i]%10;}while(len3>0&&cc[len3]==0){len3--;}if(len3==0){cout<<0<<endl;}else{for(i=len3;i>0;i--){cout<<cc[i];}cout<<endl;}return0;}

10 贪心策略

最优时间分配：

选择结束时间最早的

/practice/fda725b4d9a14010bb145272cababef1?tpId=61&tPage=3&ru=%2Fkaoyan%2Fretest%2F1002&qru=%2Fta%2Fpku-kaoyan%2Fquestion-ranking

11 递归与分治

1.子问题要与原始问题相同

2.不能无限制调用本身，必须有个递归出口

阶乘可以用递归

汉诺塔

后期总结补充

分治法

斐波那契数列

#include<iostream>#include<algorithm>usingnamespacestd;intFibonacci(intn){if(n==1||n==0){returnn;}else{returnFibonacci(n-1)+Fibonacci(n-2);}}intmain(){intn;while(cin>>n){cout<<Fibonacci(n)<<endl;}}

子树有多少个节点问题

/questionTerminal/f74c7506538b44399f2849eba2f050b5

12 搜索（难度较大，掌握后level上升一个台阶）

广度优先搜索BFS

需要有访问标记

玛雅密码

/practice/761fc1e2f03742c2aa929c19ba96dbb0?tpId=60&tqId=29484&tPage=1&ru=/kaoyan/retest/1001&qru=/ta/tsing-kaoyan/question-ranking

深度优先搜索DFS

八皇后问题

/practice/fbf428ecb0574236a2a0295e1fa854cb?tpId=61&tqId=29558&tPage=3&ru=/kaoyan/retest/1002&qru=/ta/pku-kaoyan/question-ranking

题解https://leetcode-/problems/n-queens/solution/nhuang-hou-by-leetcode-solution/

13 数据结构二

二叉树的遍历

#include<iostream>#include<algorithm>#include<queue>usingnamespacestd;structTreeNode{intdata;TreeNode*leftChild;TreeNode*rightChild;};//前序遍历voidPreOrder(TreeNode*root){if(root==NULL){return;}cout<<root->data;PreOrder(root->leftChild);PreOrder(root->rightChild);return;}//中序遍历voidInOrder(TreeNode*root){if(root==NULL){return;}InOrder(root->leftChild);cout<<root->data;InOrder(root->rightChild);return;}//后序遍历voidPostOrder(TreeNode*root){if(root==NULL){return;}PostOrder(root->leftChild);PostOrder(root->rightChild);cout<<root->data;return;}//层序遍历voidLevelOrder(TreeNode*root){queue<TreeNode*>myQueue;if(root!=NULL){myQueue.push(root);}while(!myQueue.empty()){TreeNode*current=myQueue.front();myQueue.pop();cout<<current->data;if(current->leftChild!=NULL){myQueue.push(current->leftChild);}if(current->rightChild!=NULL){myQueue.push(current->rightChild);}}return;}intmain(){return0;}

通过先序遍历和中序遍历构建树

/questionTerminal/6e732a9632bc4d12b442469aed7fe9ce

（未理解）

#include<iostream>#include<algorithm>usingnamespacestd;structTreeNode{chardata;TreeNode*leftChild;TreeNode*rightChild;TreeNode(charc):data(c),leftChild(NULL),rightChild(NULL){}};TreeNode*Build(stringstr1,stringstr2){if(str1.size()==0){returnNULL;}charc=str1[0];TreeNode*root=newTreeNode(c);intposion=str2.find(c);root->leftChild=Build(str1.substr(1,posion),str2.substr(0,posion));root->rightChild=Build(str1.substr(posion+1),str2.substr(posion+1));returnroot;}voidPostOrder(TreeNode*root){if(root==NULL){return;}PostOrder(root->leftChild);PostOrder(root->rightChild);cout<<root->data;return;}intmain(){stringstr1,str2;while(cin>>str1>>str2){TreeNode*root=Build(str1,str2);PostOrder(root);cout<<endl;}return0;}

二叉排序树

/practice/30a0153649304645935c949df7599602?tpId=69&tqId=29654&tPage=1&ru=/kaoyan/retest/11002&qru=/ta/hust-kaoyan/question-ranking%E2%80%8B

(未理解）

#include<iostream>#include<algorithm>usingnamespacestd;structTreeNode{intdata;TreeNode*leftNode;TreeNode*rightNode;TreeNode(intx):data(x),leftNode(NULL),rightNode(NULL){}};TreeNode*Insert(TreeNode*root,intx,intfather){if(root==NULL){root=newTreeNode(x);cout<<father<<endl;}elseif(x<root->data){root->leftNode=Insert(root->leftNode,x,root->data);}else{root->rightNode=Insert(root->rightNode,x,root->data);}returnroot;}intmain(){intn;while(cin>>n){TreeNode*root=NULL;for(inti=0;i<n;i++){intx;cin>>x;root=Insert(root,x,-1);}}return0;return0;}

优先队列

#include<queue>

优先队列的典型应用：

priority_queue<int>myQueue;

默认是大顶堆

哈夫曼树

哈夫曼树需要改为小顶堆，用greater

priority_queue<int,vector<int>,greater<int>>myQueue;

/practice/162753046d5f47c7aac01a5b2fcda155?tpId=67&tqId=29635&tPage=1&ru=/kaoyan/retest/1005&qru=/ta/bupt-kaoyan/question-ranking

#include<iostream>#include<queue>usingnamespacestd;intmain(){intn;while(cin>>n){priority_queue<int,vector<int>,greater<int>>myQueue;while(n--){intx;cin>>x;myQueue.push(x);}intresult=0;while(myQueue.size()>1){intp=myQueue.top();myQueue.pop();intq=myQueue.top();myQueue.pop();result=result+p+q;myQueue.push(p+q);}cout<<result<<endl;}return0;}

散列表

#include<map>map<int,int>name;map.empty()map.size()map.insert();map.erase();[]at()find()clear()begin()end()

散列表操作

#include<iostream>#include<map>#include<string>usingnamespacestd;map<string,int>myMap;intmain(){myMap["em"]=67;myMap.insert(pair<string,int>("bob",72));cout<<myMap.size()<<endl;cout<<myMap["bob"]<<endl;cout<<myMap.at("em")<<endl;myMap.erase("em");map<string,int>::iteratorit;for(it=myMap.begin();it!=myMap.end();it++){cout<<it->first<<''<<it->second<<endl;}myMap.clear();it=myMap.find("bob");if(it==myMap.end()){cout<<"没找到";}return0;}

字串计算

/practice/bcad754c91a54994be31a239996e7c11?tpId=61&tqId=29540&tPage=2&ru=%2Fkaoyan%2Fretest%2F1002&qru=%2Fta%2Fpku-kaoyan%2Fquestion-ranking

注意substr()的使用

#include<iostream>#include<map>#include<string>usingnamespacestd;intmain(){stringstr;while(cin>>str){map<string,int>count;for(inti=0;i<=str.size();i++){for(intj=0;j<i;j++){stringkey=str.substr(j,i-j);count[key]++;}}map<string,int>::iteratorit;for(it=count.begin();it!=count.end();it++){if(it->second>1){cout<<it->first<<""<<it->second<<endl;}}}return0;}

14 图论（really difficult）学会再提升一个level

最小生成树

最短路径 迪杰斯特拉算法

拓扑排序

关键路径

后续更新

（水平有限）

15 动态规划

斐波那契额数列的变体

上楼梯问题

/questionTerminal/c978e3375b404d598f1808e4f89ac551

#include<iostream>#include<algorithm>usingnamespacestd;constintMAXN=92;longlongdp[MAXN];intmain(){dp[0]=0;dp[1]=1;for(inti=2;i<MAXN;i++){dp[i]=dp[i-1]+dp[i-2];}intn;while(cin>>n){cout<<dp[n+1]<<endl;}return0;}

最大连续子序列和

/questionTerminal/df219d60a7af4171a981ef56bd597f7b

#include<iostream>#include<algorithm>usingnamespacestd;constintMAXN=1000000;longlongarr[MAXN];longlongdp[MAXN];longlongMax(intn){longlongmaxs=0;for(inti=0;i<n;i++){if(i==0){dp[i]=arr[i];}else{dp[i]=max(arr[i],dp[i-1]+arr[i]);}maxs=max(maxs,dp[i]);}returnmaxs;}intmain(){intn;while(cin>>n){for(inti=0;i<n;i++){cin>>arr[i];}longlonganswer=Max(n);cout<<answer<<endl;}return0;}

二维：

/practice/1c5fd2e69e534cdcaba17083a5c56335?tpId=61&tqId=29506&tPage=1&ru=/kaoyan/retest/1002&qru=/ta/pku-kaoyan/question-ranking

最长递增子序列

设置一个dp[ ]表示以A[ i ]作为末尾的最长递归子序列长度，则最长递增子序列长度是dp[ ]数组中的最大值

两种情况：

A[i]之前的元素都比她大，则dp[ i ]=1;

之前的元素比它小

/questionTerminal/dcb97b18715141599b64dbdb8cdea3bd

#include<iostream>usingnamespacestd;constintMAXN=1000;intarr[MAXN];intdp[MAXN];intmain(){intn;while(cin>>n){for(inti=0;i<n;i++){cin>>arr[i];}intanswer=0;for(inti=0;i<n;i++){dp[i]=arr[i];for(intj=0;j<i;j++){if(arr[j]<arr[i]){dp[i]=max(dp[i],dp[j]+arr[i]);}}answer=max(answer,dp[i]);}cout<<answer<<endl;}return0;}

最长公共子序列

dp[ i ] [ j ]表示以S1[i]和S2[j]作为末尾的最长公共子序列长度

s1[i]==s2[j] dp[i][j]=dp[i-1][j-1]+1;s1[i]!=s2[j]dp[i][j]=max(dp[i][j-1],dp[i-1][j]);

/practice/f38fc44b43cf44eaa1de407430b85e69?tpId=62&tqId=29471&tPage=2&ru=/kaoyan/retest/2002&qru=/ta/sju-kaoyan/question-ranking

#include<iostream>#include<cstring>usingnamespacestd;constintMAXN=1001;chars1[MAXN];chars2[MAXN];intdp[MAXN][MAXN];intmain(){while(scanf("%s%s",s1+1,s2+1)!=EOF){intn=strlen(s1+1);intm=strlen(s2+1);for(inti=0;i<=n;i++){for(intj=0;j<=m;j++){if(i==0||j==0){dp[i][j]=0;continue;}if(s1[i]==s2[j]){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=max(dp[i][j-1],dp[i-1][j]);}}}cout<<dp[n][m];}return0;}

背包问题

0-1背包

（未理解）欢迎交流

/questionTerminal/b44f5be34a9143aa84c478d79401e22a

（记住）

#include<iostream>usingnamespacestd;constintMAXN=1001;intv[MAXN];//价值intw[MAXN];//重量intdp[MAXN];intmain(){intn,m;while(cin>>m>>n){for(inti=0;i<n;i++){cin>>w[i]>>v[i];}for(inti=0;i<=m;i++){//初始化dp[i]=0;}for(inti=0;i<n;i++){for(intj=m;j>=w[i];j--){ //特别注意要逆序遍历dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}}cout<<dp[m]<<endl;}return0;}

完全背包

与0-1背包不同，每种物品可以取不止一件

（未理解）

只需将0-1背包的逆向改为正向即可

其他问题

整数拆分

/questionTerminal/376537f4609a49d296901db5139639ec

#include<iostream>usingnamespacestd;constintMAXN=1000001;intdp[MAXN];intmain(){dp[0]=1;dp[1]=1;for(inti=2;i<=MAXN;i++){if(i%2==0){dp[i]=(dp[i-1]+dp[i/2])%1000000000;}else{dp[i]=dp[i-1];}}intn;while(cin>>n){cout<<dp[n]<<endl;}return0;}

-9-6于南京NUIST