算法学习第一弹—

早上好啊，大佬们。来看看咱们这回学点啥，在前不久刚出完C语言写的PTA中L1的题目，想必大家都不过瘾，感觉那些题都不过如此，所以，为了我们能更好的去处理更难的题目，小白兔决定奋发图强，开始学习C++算法。

前言：对于算法学习中，为了使算法更加容易成型，会很常用到STL库，这个也是C++中区别于C很大的一个板块，所以我们在正式开始学习算法之前先简单说一说C++的语法和STL库。

注：本篇所写代码提供：

链接：https://pan.quark.cn/s/d7565311ef3a
提取码：Zp6D

C++语言基础

如果把C语言比作是在做菜，那C++就是把几个预制菜加热放到一起。咱先不论菜的味道，单纯评价速度，想必C++会快很多。

对于两者之间的差别说大不大，说小也不小，最主要的就是两个的编程方式，一个是面向过程的编程，另一个是面向对象的编程方式。对于两者的区别，我们后面专门出一期来评一评，这一期我们就先爽一爽，只管这个代码怎么写就好，那些理论的东西之后再谈。

然后事先说一下，我们是相对于C语言进行说明，只说一些两者之间的差别。

头文件

首先，最早见到的不同就是头文件，在C++中提供了很多好用的头文件：

<iostream>：提供输入输出流功能，如cin、cout、cerr。
<iomanip>：提供输入输出流的格式化操作，如setw、setprecision。
<sstream>：提供字符串流功能，允许对字符串进行输入输出操作。
<vector>：提供动态数组容器。
<list>：提供双向链表容器。
<deque>：提供双端队列容器。
<set>：提供基于红黑树的有序集合。
<map>：提供基于红黑树的有序键值对集合。
<unordered_set> 和 <unordered_map>：提供基于哈希表的无序集合。
<queue>：提供队列容器适配器。
<stack>：提供栈容器适配器。
<bitset>：提供固定大小的位集合。

相较于C的那些头文件，C++中的这些头文件所包含的内容会更加全面好用。然后，C++还有一个很好用的头文件，它包含了C++中常用的大部分头文件，被称为万能头文件：

<bits/stdc++.h>

数据类型

然后是数据类型，在C++中增加 Bool 类型，这个类型讲起来比较容易，咱们简单带过一下：

首先是Bool型所包含的值只有 True（真） 和 False（假） 两种：

咱简单类比一下，在C语言中，对于一个整型数据，当它为0时，它对应的就是False，然后除了0以外，它对应的值是True。

#include <iostream>int main() {bool isFinished = false;if (isFinished) {std::cout << "The process is finished." << std::endl;} else {std::cout << "The process is still running." << std::endl;}return 0;
}

ok，这个咱就说到这里。

输入输出

在C语言里，我们的输入输出比较常用的是 scanf() 和 printf()，然后在C++里，<iostream>头文件里提供了另一种输入输出的方式 cin 和 cout。

cin 和 cout 能够检查类型不匹配，这有助于避免类型错误，而 scanf 和 printf 需要手动指定类型，更容易出错。
cin 和 cout 是 C++ 的流对象，它们支持面向对象的特性，如继承和多态，而 scanf 和 printf 是 C 风格的函数，不具备这些特性。
使用 cin 和 cout 时，如果发生输入输出错误，会抛出异常，这使得错误处理更加灵活和强大。而 scanf 和 printf 不支持异常处理。
cout 可以使用 << 操作符和 std::setw、std::setprecision 等操作来控制输出格式，这些操作比 printf 的格式化字符串更加直观和灵活。

#include <bits/stdc++.h>int main()
{//输入int a;scanf("%d", &a);std::cin >> a;//输出printf("%d", a);std::cout << a;return 0;
}

很直观得就能看出两者的差别，cin和cout在书写的时候会方便很多。

然后，可以在开始加一句，然后在后面的输入输出std::。

using namespace std;

#include <bits/stdc++.h>
using namespace std;int main()
{//输入int a;scanf("%d", &a);cin >> a;//输出printf("%d", a);cout << a;return 0;
}

但是，对于有些时候它并没有那么好用，cin 和 cout 的运行并没有 scanf 和 printf 那么快，所以对于一些时间复杂度很高的题目，输入输出很多的题目，还是用 scanf() 和 printf() 会比较好一些。

或者可以添加一句这个：

ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)；

使用了它之后有一些变化：

提高执行效率
解绑输入输出流
使用后不能使用scanf()，printf()等
而且不能使用endl，cout << endl --> cout << '\n'

对于这方面好像就这这些了，相信各位C语言大佬们很快就能记住这些了吧。

还有一个类型需要讲一下——string，这个也是一个很重要的一个类型。

string：

头文件：<string>

在C语言里面有一个字符数组，也就是 char*，它和string很像，可以说string >= char*，所以大家在用string类型的时候可以类比char*的使用方法来运用，下面我来补充一点string>的部分。

char*是一个指针
string是一个类，类内部封装了char*，管理这个字符串，是一个char*型的容器。

string的基本内容：

声明和初始化：

#include <bits/stdc++.h>
using namespace std;int main()
{string s1;//std::string s; 如果没有加 using namespace std;这一句的话，就需要这么写string s2 = "Bunny Girl"; // 直接声明和初始化一个空的字符串string s3 = s1; //Bunny Girlstring s4 = s1.substr(1, 6); //unny Greturn 0;
}

赋值：

直接赋值创建：

#include <bits/stdc++.h>
using namespace std;int main()
{string s = "Bunny Girl";return 0;
}

cin输入：

#include <bits/stdc++.h>
using namespace std;int main()
{string s;cin >> s; // 这种输入和scanf("%s")一样，不能有空格输入。cout << s << endl;return 0;
}

getline()输入：

#include <bits/stdc++.h>
using namespace std;int main()
{string s;getline(cin, s);cout << s;return 0;
}

下面就开始重头戏了，大家做好准备喔，都是重点，都要好好学

基本操作：

存取

char& operator[](int n); //通过[]方式取字符

char& at(int n); //通过at方法获取字符

#include <bits/stdc++.h>
using namespace std;int main()
{string s1 = "bunny girl";cout << s1[2] << " "; //获取第三个字符cout << s1.at(4) << "\n"; //获取第五个字符s1[2] = 'b';s1.at(4) = 't';cout << s1.at(2) << " " << s1[4] << "\n"; return 0;
}/*
n y
b t
*/

获取长度

使用size或者length方法。

需要注意的是它和 C语言中 strlen()函数的差别，strlen在遇到 ' \0 ' 时会停止后面的长度获取，但是size和length方法可以获取字符串真实长度。

我们来看看怎么个事儿：

#include <bits/stdc++.h>
using namespace std;int main()
{string s = "I am Bunny Girl";int len1 = s.size(); //15int len2 = s.length(); //15cout << len1 << "\n" << len2 << "\n";s[11] = '\0';int len3 = s.size(); //15int len4 = s.length(); //15cout << len3 << "\n" << len4 << "\n";//可见对于size和length方法是不会判断 ' \0 '来停止长度获取。 return 0;
}

拼接

在C++中提供了一种直接使用 +号来进行连接的方式。

或者，可以使用append方法来进行连接。

#include <bits/stdc++.h>
using namespace std;int main()
{
/*
字符串拼接
*/string s1 = "I am ";string s2 = "Bunny Girl";string s3 = s1 + s2;cout << s3 << "\n";string s4 = "I am ";s1.append("Bunny Girl");cout << s1 << "\n";return 0;
}//结果
//I am Bunny Girl
//I am Bunny Girl

查找

C++里的字符串字串查找使用的函数是 —— find（）

语法格式：

str.find(str, pos)

参数：

str 表示要查找的字符串

pos 表示从s的pos位置开始查找

由它引申的函数还有

find_first_of (str)，第一次出现的位置；

find_last_of (str)，最后一次出现的位置；

rfind(str，pos)：从pos开始，倒序查找符合条件的字符串；

find()函数在字符串中查找子串返回子串的首地址。和C语言中strstr()函数很像，只是在字符串中如果没有该子串时，返回的值从NULL变成了string::npos。

#include <bits/stdc++.h>
using namespace std;int main()
{
/*
字符串查找
*/string str = "Hello World, Hello C++, Hello bunny girl";size_t pos = str.find("Hello"); // 查找子串"Hello",返回第一次出现的第一个字符的下标if (pos != string::npos) {cout << "Found substring at position: " << pos << endl;} else {cout << "Substring not found" << endl;}size_t pos_no = str.find("Bunny Girl"); //查找不存在的子串if (pos != string::npos) {cout << "Found substring at position: " << pos_no << endl;} else {cout << "Substring not found" << endl;}size_t pos_1 = str.find_first_of("Hello"); //查找第一次出现的位置if (pos != string::npos) {cout << "Found substring at position: " << pos_1 << endl;} else {cout << "Substring not found" << endl;}size_t pos_2 = str.find_last_of("Hello"); //查找最后一次出现的子串的最后一位的位置if (pos != string::npos) {cout << "Found substring at position: " << pos_2 << endl;} else {cout << "Substring not found" << endl;}size_t pos_3 = str.rfind("Hello"); //从后往前查找if (pos != string::npos) {cout << "Found substring at position: " << pos_3 << endl;} else {cout << "Substring not found" << endl;}return 0;
}/*
结果
Found substring at position: 0
Found substring at position: 18446744073709551615
Found substring at position: 0
Found substring at position: 39
Found substring at position: 24
*/

替换

C++中，string::replace 有四种重载形式：

第一种：
string& replace (size_t pos, size_t len, const string& str);
从pos位置开始，长度为len的子串替换为新的str字符串。

第二种：
string& replace (size_t pos, size_t len, const string& str, size_t subpos, size_t sublen);
新增了subpos和sublen两个参数，分别表示新字符串str的子串的起始位置和长度。

第三种：
template <class InputIterator>string& replace (iterator i1, iterator i2, InputIterator first, InputIterator last);
使用迭代器来表示需要被替换的子串的范围(i1到i2)，以及新的字符串的范围(first到last)。

第四种：
string& replace (size_t pos, size_t len, const char* s);
可以接受一个C风格的字符串（也就是字符数组）作为新的字符串。

下面我演示一下这些用法：

#include <bits/stdc++.h>
using namespace std;int main()
{
/*
字符串替换
*/string str1 = "I am @ a@ bunny girl";str1.replace(0, 4,"rabit is");  //从第一个a位置开始的两个字符替换成#cout<<str1<<endl;string str2 = "I am @ a@ bunny girl";string str_temp = "rabit is";str2.replace(str2.begin(), str2.begin()+4, str_temp);  //从第一个a位置开始的两个字符替换成#cout<<str2<<endl;string str3 = "I am @ a@ bunny girl";string str_temp1 = "rabit is";str3.replace(str3.begin(), str3.begin()+4, str_temp1.begin(), str_temp1.end());  //从第一个a位置开始的两个字符替换成#cout<<str3<<endl;return 0;
}/*
结果
rabit is @ a@ bunny girl
rabit is @ a@ bunny girl
rabit is @ a@ bunny girl
*/

获取子串

语法格式：
str.substr(size_type _Off = 0,size_type _Count = npos)

返回值： string，包含s中从pos开始的len个字符的拷贝（pos的默认值是0，len的默认值是s.size() - pos，即不加参数会默认拷贝整个s）

异常：若pos的值超过了string的大小，则substr函数会抛出一个out_of_range异常；若pos+n的值超过了string的大小，则substr会调整n的值，只拷贝到string的末尾

#include <bits/stdc++.h>
using namespace std;int main()
{string s1 = "bunny girl";string s2 = "white rabit";string s01 = s1.substr(0, 5);string s02 = s2.substr(6, 10);cout << s01 << "\n" << s02 << "\n";return 0;
}/*
bunny
rabit
*/

比较

我们也拿C语言进行类比，C语言里有一个函数是strcmp()函数，在C++里面是compare()函数。

compare()函数的语法格式：

int compare(const string &s)const;  //与字符串s比较
int compare(const char *s)const;    //与字符串s比较

比较结果，和strcmp()是一样的：

s1 == s2 --> 0

s1 > s2 --> 1

s1 < s2 --> 2

#include <bits/stdc++.h>
using namespace std;int main()
{string s1 = "bunny girl";string s2 = "bunny girl";string s3 = "abcdef";string s4 = "zxyw";if (s1.compare(s2) == 0){cout << "s1 == s2" << "\n";}if (s1.compare(s3) > 0){cout << "s1 > s3" << "\n";}if (s1.compare(s4) < 0){cout << "s1 < s4" << "\n";}return 0;
}/*
s1 == s2
s1 > s3
s1 < s4
*/

插入

string& insert(int pos, const char* s); //插入字符串
string& insert(int pos, const string& str); //插入字符串
string& insert(int pos, int n, char c); //在指定位置插入n个字符c

#include <bits/stdc++.h>
using namespace std;int main()
{string s1 = "bunny girl";string s2 = "12345";s1.insert(2, s2);cout << s1;return 0;
}/*
bu12345nny girl
*/

删除

string& erase(int pos,int n=npos);//删除从Pos开始的n个字符

#include <bits/stdc++.h>
using namespace std;int main()
{string s1 = "bunny dsa girl";s1.erase(6, 4);cout << s1;return 0;
}/*
bunny girl
*/

总结

OK，那么这一期的内容就这么多，看完这些之后不要忘记刷题哦，只有在实战里面才能熟练基础。

下一期，我们开始讲STL库，小白兔会挑一些好用的容器来介绍一下，等过完这些内容就正式开始算法的学习咯，好好享受现在的美好时光吧。

小白兔把这一期里写的代码放到网盘里了，大家可以留作复习，常看常新喔。

那么Bye Bye咯，咱们下期见。