算法攻略从零到一cpp版 [复制链接]

算法攻略从零到一（cpp版）

1前言

虽然C++是向对象语，但是算法题的基本思维方式是面向过程式，也就是针对算法题我们是不需要掌握面向对象部分（继承、封装、多态）。只需要掌握刷算法的时候需要到的部分（基本输输出、STL标准模板库、string字符串等）。

使用C++刷题有几大好处：

方便的输入输出；C++的cout、cin不再像C语言里面的输入输出scanf、printf那样需要自己写明变量的类型，比如scanf("%d",n);printf("%d",n);，直接cinn;coutn；

更强大的字符串处理；C++的string字符串类提供了强大的字符串处理功能，不再像C语言里面的字符数组，处理起来比较繁琐；

STL模板库；STL的动态数组vector、集合set、映射map、栈stack、队列queue、位运算bitset，以及算法库#includealgorithm的sort排序算法函数模板等等，都极大提高了我们做题的效率；

整理自网络，非商业用途，侵权联系删除。

2算法基础之C++

2.1输入输出

leetcode平台是不需要我们自己写数据输入的，只需要在下图的红色文本框中写自己的解题代码就行。

需要自己编写输入输出。

然后在网页编辑框填写自己的代码提交评测。

2.1.1整数输入问题

最简单的输入

//最简单的输入，输入单行

SampleInput12

SampleOutput3

#includeiostreamusingnamespacestd;intmain(){inta,b;cinab;couta+bendl;//对其他题目，换成要求的复杂处理与输出return0;}

输入多行数时，直到读至输入文件末尾（EOF）为止

输入多行数时，直到读至输入文件末尾（EOF）为止说明1：当读到输入结束时，cinab返回0，循环也结束。说明2：在调试程序时，键盘输入的数据，用CTRL-Z（即按住CTRL键不放，再按下Z）组合作为输入结束，此谓键盘输入设备的“文件末尾”。重点掌握

SampleInput

SampleOutput

#includeiostreamusingnamespacestd;intmain(){inta,b;while(cinab)//当题目输入行数不确定时使用此方法{couta+bendl;}return0;}

多组由两个整数（a和b）构成的输入，a和b之间用空格隔开，每组输入单独占一行。

多组由两个整数（a和b）构成的输入，a和b之间用空格隔开，每组输入单独占一行。当输入为00时，输入结束。SampleInputSampleOutput

#includeiostreamusingnamespacestd;intmain(){inta,b;while(cinab(a

b)){couta+bendl;}return0;}

第一行是数据的组数N，从第二行是N组由两个整数（a和b）构成的输入，a和b之间用空格隔开，每组输入单独占一行

第一行是数据的组数N，从第二行是N组由两个整数（a和b）构成的输入，a和b之间用空格隔开，每组输入单独占一行重点掌握

SampleInputSampleOutput

#includeiostreamusingnamespacestd;intmain(){inta,b,n;cinn;for(inti=0;in;i++){cinab;//cin以空格或者回车作为输入输出分隔符couta+bendl;}return0;}

利用文件重定向提高调试效率

#includeiostream#includecstdiousingnamespacestd;intmain(){freopen("input.txt","r",stdin);//将输入重定向到文件input.txt（注意文件路径）inta,b;cinab;couta+bendl;return0;}//在运行程序前，将本该由键盘输入的数据，写到文件input.txt中。而在运行程序时，数据将不再需要人去输入

2.1.2读取和解析标点字符（如逗号）分隔数据

读取以逗号间隔的数字到数组中

处理输入问题：读取以逗号间隔的数字到数组中

例：

输入：1,12,

数组a：a[0]=1,a[1]=12,a[2]=

#includevector#includeiostream#includesstream#includestringusingnamespacestd;intmain(){vectorinta;strings;cins;//读取输入字符串到sstringstreaminput(s);//将字符串s转化为流stringnumstr;while(getline(input,numstr,,))//按逗号分隔为字符串（getline每次读一个）{a.push_back(stoi(numstr));}return0;}

思路：使用getline和stringstream以,为分隔符来切分数据，然后使用标准库string的数值转换函数例如字符串转整形stoi进行解析。注意：当数据以空格分隔时，可以直接用cin来读入！

2.2String类

string类，使得字符串的定义、拼接、输出、处理都更加简单。不过string只能cin和cout处理，法scanf和printf处理：

strings="helloworld";//赋值字符串strings2=s;strings3=s+s2;//字符串拼接直接+号就可以strings4;cins4;//读字符串couts;//输出字符串

cin读字符串的时候，是以空格为分隔符的，如果想要读整的字符串，就需要getline。

此外string的长度可以用strings;s.length();s.size()获取，这两个获取长度的函数功能是一样的。与C语言的char[]还要考虑尾部的\0字符，string里面是多少字符就是多少，当然也包括字符。

strings;//定义个空字符串sgetline(cin,s);//读取的字符串，包括空格couts.length();//输出字符串s的度

string中还有个很常的函数叫做substr，作是截取某个字符串中的串，法有两种形式：

strings2=s.substr(4);//表示从下标4开始直到结束strings3=s.substr(5,3);//表示从下标5开始，3个字符

2.3STL

2.3.1STL之动态数组vector（量）

之前C语intarr[]定义数组，它的缺点是数组的度不能随所欲的改变。而vector它能够在运阶段设置数组的度、在末尾增加新的数据、在中间插新的值、度任意被改变。它在头件vector，也在命名空间std，所以使的时候要引头件#includevector和usingnamespacestd;

vector、stack、queue、map、set这些在C++中都叫做容器，这些容器的都可以.size()获取到，就像strings的度s.length()获取样。只是对于string字符串我们一般是用.length()，而对于容器类我们一般用.size()。

#includeiostream#includevectorintmain(){vectorintv1;//定义个vectorv1，定义的时候没有分配coutv1.size();//输出vectorv1的，此处应该为0return0;}

vector可以开始不定义，之后resize法分配，也可以开始就定义，之后还可以对它插删除动态改变它的。且不管在main函数还是在全局中定义，它都能够直接将所有的值初始化为0（不显式地写出来，默认就是所有的元素为0）。

vectorintv(10);//直接定义度为10的int数组，默认这10个元素值都为0//或者vectorintv1;v1.resize(8);//先定义个vector变量v1，然后将度resize为8，默认这8个元素都是0//在定义的时候就可以对vector变量进初始化vectorintv3(,9);//把度的数组中所有的值都初始化为9//访问的时候像数组样直接[]下标访问即可(也可以迭代器访问，下会讲)v[1]=2;coutv[0];

除了可以访问