手把手写算法（学个语言）

本文风格已经改进的适合你的口味了吗？欢迎大家在本文末尾投票

为什么要使用C++刷算法？

1. 在已经学习过C语⾔的前提下，学习C++并使⽤它刷算法的学习成本⾮常低，同时C++向下兼容C，C语⾔⾥⾯的语法完全可以在C++⽂件中运⾏。
2. C++拥有丰富的STL标准模版库。很多东西直接调用即可,很多情况下C语⾔解决问题会⽐C++的STL解决该问题麻烦很多。
3. C++的 string 类型，cin，cout输入输出相对来说比char和scanf，printf要方便很多。
4. 我们不需要掌握C++面向对象的部分，只需要掌握刷算法的时候需要⽤到的部分（基本输⼊输出、STL标准模板库、 string 字符串等）就可以了，C语⾔和C++有很多相似之处，且C++向下兼容C语⾔，很多地方都可以直接使用C的语法。

//使用C++的cin,cout的a + b
#include 
using namespace std;

int main()
{
    int a,b;
    cin >> a >> b;
    cout << a + b << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11

名称空间using namespace std的解释

​ 这句话是使⽤“std”这个名称空间（ namespace ）的意思～因为有的时候不同⼚商定义的函数名称彼此之间可能会重复，为了避免冲突，就给所有的函数都封装在各⾃的名称空间⾥⾯，使⽤这个函数的时候就在main函数前⾯写明⽤了什么名称空间，⼏乎在C++中使⽤到的⼀些⽅法如 cin 、 cout 都是在 std 名称空间⾥⾯的，其实也可以不写这句话，但是使⽤ std ⾥⾯的⽅法的时候就会麻烦点，要在⽅法名前加上 std:: ，⽐如写成这样：

std::cin >> n;
1

cin和cout输入输出

就如同 scanf 和 printf 在 stdio.h 头⽂件中⼀样， cin 和 cout 在头⽂件 iostream ⾥，看名字就知道， io 是输⼊输出 input 和 output 的⾸字⺟,stream 是流，所以这个 iostream 头⽂件⾥包含的⽅法就是管理⼀些输⼊输出流的。

cin 和 cout ⽐较⽅便，不⽤像C语⾔⾥的 scanf，printf 那样写得那样繁琐,cin >> n; 和scanf(“%d”, &n);是⼀样的意思（⽽且⽤ cin 再也不⽤担⼼像 scanf ⼀样忘记写取地址符 & 了耶），注意 cin 是向右的箭头，表示将内容输⼊到 n 中。

同样， cout << n; 和 printf(“%d”, n); ⼀样的意思，此时 cout 是向左的两个箭头，注意和 cin 区分开来 。

⽽且不管 n 是 double 还是 int 或者是 char 类型，只⽤写 cin >> n; 和 cout << n; 这样简单的语句就好，不⽤像C语⾔中需要根据 n 的类型对应地写 %lf 、 %d 、 %c 这样麻烦。

endl 和 “\n” 是⼀个意思， endl 的全称是end of line，表示⼀⾏输出结束，然后输出下⼀⾏。

C++的头文件

//C中继承的头文件
#include  // 相当于C语⾔⾥⾯的#include 
#include  // 相当于C语⾔⾥⾯的#include 
#include  // 相当于C语⾔⾥⾯的#include 

//C++额外的头文件
#include //标准输入输出，就是cin，cout的使用
#include  //STL通用算法
#include 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

C++的bool变量

bool 变量有两个值， false 和 true ，以前⽤C语⾔的时候都是⽤ int 的 0 和 1 表示 false 和 true 的，现在C++⾥⾯引⼊了这个叫做 bool （布尔）的变量，⽽且C++把所有⾮零值解释为 true ，零值解释为 false。所以直接赋值⼀个数字给 bool 变量也是可以的～它会⾃动根据 int 值是不是零来决定给 bool 变量赋值 true 还是 false。

bool flag = true;
bool flag2 = -2; // flag2为true
bool flag3 = 0; // flag3为false
1
2
3

C++的const定义常量

之前C语⾔⾥⾯会⽤ #define 定义常量，但是C++⾥⾯⽤ const 这个限定符定义常量，这样做有个好处就是可以定义常量的类型，⽐如 int 类型的常量 a 这样定义：

const int N = 2333333;
1

C++的string类

C语言中char[] 的⽅式处理字符串很繁琐，C++中有优化后的string 类，

不过 string 只能⽤ cin 和 cout 处理，⽆法⽤ scanf 和 printf 处理,样例：

string s = "hello world"; // 赋值字符串
string s2 = s;
string s3 = s + s2; // 字符串拼接直接⽤+号就可以
string s4;
for(int i = 0;i < s.length();i++)cout << s[i];//下标访问单字符
cin >> s4; // 读⼊字符串
cout << s; // 输出字符串
1
2
3
4
5
6
7

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

s 的⻓度可以⽤ s.length() 获取，有⼏个字符就是⻓度多少，不存在什么末尾的’/0’的情况。

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

string s2 = s.substr(4); // 表示从下标4开始⼀直到结束
string s3 = s.substr(5, 3); // 表示从下标5开始，3个字符
1
2

C++的引⽤&和传值的区别

这个引⽤符号 & 要和C语⾔⾥⾯的取地址运算符 & 区分开来，两个符号并无关联

C++⾥⾯的引⽤是指在变量名之前加⼀个 & 符号，⽐如在函数传⼊的参数中 int &a ，那么对这个引⽤变量 a 做的所有操作都是直接对传⼊的原变量进⾏的操作，并没有像原来 int a ⼀样只是拷⻉⼀个副本（传值),举两个例⼦：

// 传⼊的是n的引⽤，直接对n进⾏了操作，只不过在func函数中换了个名字叫a
void func(int &a) { 
	a = 99; 
}
int main() 
{
	int n = 0;
	func(n); // n由0变成了99
} 


// 传⼊的是0这个值，并不会改变main函数中n的值
void func(int a) { 
	a = 99; 
}
int main() 
{
	int n = 0;
	func(n); //n还是0，不改变
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

C++ STL库

vector 、 stack 、 queue 、 map 、 set 这些在C++中都叫做容器，这些容器的⼤⼩都可以⽤ .size()获取到，就像 string s 的⻓度⽤ s.length() 获取⼀样。（ string 其实也可以⽤ s.size() ，不过对于vector 、 stack 、 queue 、 map 、 set 这样的容器我们⼀般讨论它的⼤⼩ size ，字符串⼀般讨论它的⻓度 length ～其实 string ⾥⾯的 size 和 length 两者是什么区别，都可以使用。

1.vector

C语⾔中使⽤ int arr[] 定义数组，缺点是数组的⻓度不能随⼼所欲的改变，⽽C++⾥⾯有⼀个能完全替代数组的动态数组 vector，它能够在运⾏阶段设置数组的⻓度、在末尾增加新的数据、在中间插⼊新的值、⻓度任意被改变。

它在头⽂件 vector ⾥⾯，也在命名空间 std ⾥⾯，所以使⽤的时候要引⼊头⽂件 #include 和 using namespace std;

#include 
#include 
using namespace std;
int main() 
{
	vector vec; // 定义⼀个vector vec，定义的时候没有分配⼤⼩
	cout << vec.size(); // 输出vector vec的⼤⼩，此处应该为0
	return 0; 
}
1
2
3
4
5
6
7
8
9

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

vector v(10); // 定义⻓度为10的int数组，默认这10个元素值都为0

// 或者

vector vec;
vec.resize(8); //先定义⼀个vector变量v1，然后将⻓度resize为8，默认这8个元素都是0

// 在定义的时候就可以对vector变量进⾏初始化
vector vec(100, 9);// 把100⻓度的数组中所有的值都初始化为9

// 访问的时候像数组⼀样直接⽤[]下标访问即可;
cout << v[0];
1
2
3
4
5
6
7
8
9
10
11
12

常⽤的 vector ⽅法:

a.push_back(i);
a.pop_back(i);
a.size();
a.front();
a.back();
a.begin() //指向容器的第⼀个元素
a.end() //指向容器的最后⼀个元素的后⼀个位置
1
2
3
4
5
6
7

2.set

set 是集合，set ⾥⾯的各元素是各不相同的且 set 会按照元素进⾏从⼩到⼤排序

以下是 set 的常⽤⽤法：

#include 
#include 
using namespace std;
int main() 
{
	set s; // 定义⼀个空集合s
	s.insert(1); // 向集合s⾥⾯插⼊⼀个1
	for (int i = 0; i < 6; i++) {
 		s.insert(i); // 向集合s⾥⾯插⼊i
 	}
	cout << endl << (s.find(2) != s.end()) << endl; 
// 查找集合s中的值，如果结果等于s.end()表示未找到 (因为s.end()表示s的最后⼀个元素的下⼀个元素所在的位置)
	cout << (s.find(10) != s.end()) << endl; // s.find(10) != s.end()表示能找到10这个元素
	s.erase(1); // 删除集合s中的1这个元素
	cout << (s.find(1) != s.end()) << endl; 
    // 这时候元素1就应该找不到啦～
 	return 0; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3.stack

数据结构栈的调用

常用方法：

#include 
#include 
using namespace std;
int main() 
{
	stack s; // 定义⼀个空栈s
	for (int i = 0; i < 6; i++) {
		s.push(i); // 将元素i压⼊栈s中
	}
	cout << s.top() << endl; // 访问s的栈顶元素
	cout << s.size() << endl; // 输出s的元素个数
	s.pop(); // 移除栈顶元素
	return 0; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4.queue

数据结构栈的调用

常用方法：

#include 
#include 
using namespace std;
int main() 
{
	queue q; // 定义⼀个空队列q
	for (int i = 0; i < 6; i++) {
		q.push(i); // 将i的值依次压⼊队列q中
	}
	cout << q.front() << " " << q.back() << endl; // 访问队列的队⾸元素和队尾元素
	cout << q.size() << endl; // 输出队列的元素个数
	q.pop(); // 移除队列的队⾸元素
	return 0; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

5.map(映射)

map 是键值对，⽐如⼀个⼈名对应⼀个学号，就可以定义⼀个字符串 string 类型的⼈名为“键”，学号 int 类型为“值”，如 map m; 当然键、值也可以是其它变量类型。map 会⾃动将所有的键值对按照键从⼩到⼤排序， map 使⽤时的头⽂件 #include

#include 
#include 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

6.unordered_map和unordered_set

unordered_map 在头⽂件 #include 中， unordered_set 在头⽂件 #include 中。

unordered_map 和 map （或者 unordered_set 和 set ）的区别是， map 会按照键值对的键 key 进⾏排序（ set ⾥⾯会按照集合中的元素⼤⼩进⾏排序，从⼩到⼤顺序），⽽ unordered_map （或者 unordered_set ）省去了这个排序的过程，如果偶尔刷题时候⽤ map 或者 set 超时了，可以考虑⽤ unordered_map （或者 unordered_set ）缩短代码运⾏时间、提⾼代码效率～⾄于⽤法和map 、 set 是⼀样的。

7.sort函数

#include 
#include 
#include 
using namespace std;
int main() {
	vector v(10);
    for (int i = 0; i < 10; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());//v从⼩到⼤排列
	int arr[10];
	for (int i = 0; i < 10; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + 10);
	return 0; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

auto声明（自动）

让编译器根据初始值类型直接推断变量的类型，例如：

auto x = 100; // x是int变量
auto y = 1.5; // y是double变量
1
2

基于范围的for循环

除了像C语⾔的for语句 for (i = 0; i < arr.size(); i++) 这样，C++11标准还为C++添加了⼀种新的 for 循环⽅式，叫做基于范围（range-based）的for循环，这在遍历数组中的每⼀个元素时使⽤会⽐较简便。⽐如想要输出数组 arr 中的每⼀个值，可以使⽤如下的⽅式输出：

int arr[4] = {0, 1, 2, 3};
for (auto i : arr)
cout << i << endl; // 输出数组中的每⼀个元素的值，每个元素占据⼀⾏
1
2
3

这种基于范围的 for 循环适⽤于各种类型的数组，将上述两段代码中的 int 改成其他变量类型如double 、 char 都是可以的。另外，这种 for 循环⽅式不仅可以适⽤于数组，还适⽤于各种STL容器，⽐如 vector 、 set 等。

// v是⼀个int类型的vector容器
for (auto i : v)
	cout << i << " ";
// 上⾯的写法等价于
for (int i = 0; i < v.size(); i++)
	cout << v[i] << " ";
1
2
3
4
5
6

to_string方法

将别的类型的变量转换为string类型的变量，例如：

#include 
#include 
using namespace std;
int main() {
	string s1 = to_string(123); // 将123这个数字转成字符串
	cout << s1 << endl;
	string s2 = to_string(456); // 将456这个数字转成字符串
	cout << s2 << endl;
	cout << s1 + s2 << endl; // 将s1和s2两个字符串拼接起来并输出
	return 0; 
}
1
2
3
4
5
6
7
8
9
10
11