羊村懒王

这个屌丝很懒，什么也没留下！

热门标签

蓝桥杯（C/C++）知识点------杂

作者：羊村懒王 | 2024-05-03 07:38:56

踩

蓝桥杯知识点（杂）

一、二分查找

1、普通的二分查找

使用二分查找的前提就是必须是有序的数组

关于二分查找，首先需要注意的是，所给的区间，一般情况下有两种，第一种就是两头都是闭区间，第二种就是左闭右开的区间

第一种

/*
[1,mid],[mid+1,size]
*/


int BinarySelect(int* arr, int n, int target) {
    int left = 0;
    int right = n - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;
        if (arr[mid] > target) {
            right = mid - 1;
        }
        else if (arr[mid] < target) {
            left = mid + 1;
        }
        else {
            return mid;
        }
    }

    return -1;
}


int main() {

    int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
    
    int n = sizeof(arr) / sizeof(int);
    //所找的元素，则我们返回的就是他的下标
    int target = 8;

    int index = BinarySelect(arr, n, target);
    
    printf("index = %d\n", index);

    return 0;
}
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
27
28
29
30
31
32
33
34
35
36
37
38
39

第二种

/*
[1,mid-1],[mid,size]

*/

int BinarySelect(int* arr, int n, int target) {
    int left = 0;
    int right = n - 1;
    while (left < right) {
        int mid = (left + right) >> 1;
        if (arr[mid] > target) {
            right = mid;
        }
        else if (arr[mid] < target) {
            left = mid + 1;
        }
        else {
            return mid;
        }
    }

    return -1;
}


int main() {

    int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
    
    int n = sizeof(arr) / sizeof(int);
    //所找的元素，则我们返回的就是他的下标
    int target = 10;

    int index = BinarySelect(arr, n, target);
    
    printf("index = %d\n", index);

    return 0;
}
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
27
28
29
30
31
32
33
34
35
36
37
38
39

2、二分查找的列题

在这里插入图片描述

Demo：

#define  _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <stdbool.h>

//数组中的数为num,要查找的数是x
bool isBlue1(int num, int x) {
	if (num < x) {
		return true;
	}
	else {
		return false;
	}
}

//数组中的数为num,要查找的数是x
bool isBlue2(int num, int x) {
	if (num <= x) {
		return true;
	}
	else {
		return false;
	}
}

int binary_select1(int* arr,int n,int x) {
	int left = -1, right = n;
	while (left + 1 != right) {
		int mid = (left + right) >> 1;
		if (isBlue1(arr[mid], x)) {
			left = mid;
		}
		else {
			right = mid;
		}
	}
	if (arr[right] == x) {
		return right;
	}
	else {
		return -1;//找不到返回-1
	}
}

int binary_select2(int* arr,int n,int x) {
	int left = -1;
	int right = n;

	while (left + 1 != right) {
		int mid = (left + right) >> 1;
		if (isBlue2(arr[mid],x)) {
			left = mid;
		}
		else {
			right = mid;
		}
	}

	if (arr[left] == x) {
		return left;
	}
	else {
		return -1;//找不到返回-1
	}
}

int main() {

	int arr[] = { 0 };
	//n为数组中的元素的个数，q为要查询元素的个数
	int  n, q;
	scanf("%d %d", &n, &q);

	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}

	//x表示就是要查询的数
	int x;

	while (q--) {
		scanf("%d", &x);

		//index1就是要查询的数第一次出现的位置（下标）
		int index1 = binary_select1(arr, n, x);
		//index2就是要查询的数最后一次出现的位置（下标）
		int index2 = binary_select2(arr, n, x);

		printf("index1 = %d , index2 = %d\n", index1, index2);
	}
	return 0;
}
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

3、浮点数的二分查找

/*
求出一个数开三次方
思想：就是在一个区间中使用二分法，去找出那个数的三次方等于我们输入的那个数
*/
#define  _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <stdbool.h>

int n = 0;

bool check(double mid) {
	if (mid * mid * mid <= n) {
		return true;
	}
	else {
		return false;
	}
}


int main() {
	
	scanf("%d", &n);

	double left = -100, right = 100;
	while (right - left > 1e-8) {
		double mid = 1.0*(left + right) / 2;

		if (check(mid)) {
			left = mid;
		}
		else {
			right = mid;
		}
	}

	printf("%lf\n", left);
	printf("%lf\n", right);

	return 0;
}

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

二、二进制

在给定的二进制数中，找到其中1的个数

int main() {

        int BinaryNum = 0;
        scanf("%d", &BinaryNum);

        int count = 0;

        while (BinaryNum) {
            //在底层是用的补码进行&运算，&：表示两个1才为1，其他就是0
            if (BinaryNum & 1 == 1) {
                count++;
            }
            BinaryNum = BinaryNum >> 1;

        }
    
        printf("count = %d\n", count);
        return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

求二进制数中的第k位的数值是什么

int main() {

        int BinaryNum = 0;
        scanf("%d", &BinaryNum);

        //你想知道第几位的值
        int k = 3;

        printf("%d\n", BinaryNum>>(3-1)&1);
        return 0;
}
1
2
3
4
5
6
7
8
9
10
11

三、前缀和

关于前缀和就是在一个数组中，前n个数的和，但是在这里我们介绍一个题目，使用前缀和的思想，可以快速求解，并且不会超时

1、快速求出两个区间的数的总和

关于这里，很多同学可能都是想到的是暴力，虽然可以通过，但是如果我们输入的数很多的话就可能会超时，达不到提交的要求

先使用暴力写一遍

Demo：

#define  _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

int main(){
	int num = 0;
	int seekNum = 0;
	int arr[] = { 0 };
	int sum = 0;
	scanf("%d%d", &num, &seekNum);

	for (int i = 0; i < num; i++) {
		scanf("%d", &arr[i]);
	}

	while (seekNum--) {
		int left = 0;
		int right = 0;
		scanf("%d%d", &left, &right);
		sum = 0;
		for (int i = left; i <= right; i++) {
			sum += arr[i];
		}
		printf("sum = %d\n", sum);
	}
	return 0;
}
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
27

再使用前缀和的思想

关于使用前缀和的思想，这里采用的下标是从1开始的，比如输入的数组为：4 2 1 3 5，right=1,left=5,则sum = 15，就是输入right和left就是下标

#define  _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

int main(){
	int num = 0;
	int seekNum = 0;
	int arr[] = { 0 };
	int sum[] = {0};
	scanf("%d%d", &num, &seekNum);

	for (int i = 1; i <= num; i++) {
		scanf("%d", &arr[i]);
        //使用sum数组将每一个数的前缀和保存起来
		sum[i] = sum[i - 1] + arr[i];
	}

	while (seekNum--) {
		int left = 0;
		int right = 0;
		scanf("%d%d", &left, &right);
		//这里看不懂的，可以画一个数组，再根据代码细看
		printf("sum = %d\n", sum[right]-sum[left-1]);
	}
	return 0;
}

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
27

2、再二维数组中使用前缀和求出两个坐标点之间的元素的总和

在这里插入图片描述

这个公式是由画图直接得出来的

注意：公式的有一个位置是写错了的，最后的s[x1-1] [y2-1]应该改成s[x1-1] [y1-1]

Demo：

#define  _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h> 
#include <stdbool.h>

int main(){
	int row = 0;
	int col = 0;
	int seekNum = 0;
	int arr[][10000] = { 0 };
	int sum[][10000] = { 0 };

	scanf("%d%d%d", &row, &col, &seekNum);

	for (int i = 1; i <= row; i++) {
		for (int j = 1; j <= col; j++) {
			scanf("%d", &arr[i][j]);
			sum[i][j] = arr[i][j] + sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1];	
		}
	}

	while (seekNum--) {
		int x1, x2, y1, y2;
		scanf("%d%d%d%d", &x1, &x2, &y1, &y2);

		printf("sum = %d\n", sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1]);
	}

	return 0;
}
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
27
28
29
30
31
32
33

3、给定一个目标值，在两个数组中分别使用一个元素，让这两个数的和等于这个目标值

这里就要使用到，双指针的技巧了。首先在使用之前，我们要使用的是一个在头一个在尾的双指针，这样就是一个单调的（控制变量）

Demo：（不知道为什么我的会超出数组范围）

#define  _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h> 
#include <stdbool.h>

int main(){
	int arr1[] = { 0 };
	int arr2[] = { 0 };
	int num1 = 0;
	int target = 0;
	int num2 = 0;
	
	scanf("%d%d%d", &num1, &num2, &target);

	for (int i = 0; i < num1; i++) {
		scanf("%d", &arr1[i]);
	}

	for (int j = 0; j < num2; j++) {
		scanf("%d", &arr2[j]);
	}
	
	for (int i = 0, j = num2 - 1; i < num1; i++) {
		while (j >= 0 && arr1[i] + arr2[j] > target) {
			j--;
		}

		if (arr1[i] + arr2[j] == target) {
			printf("index1 = %d,index2 = %d\n", i, j);
			return 0;
		}

	}
	return 0;
}
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
27
28
29
30
31
32
33
34
35
36
37
38

四、双指针

关于双指针的问题，在上面的问题中已经提到了，我们在这里就简单提一下，双指针的问题，可以分为两个指针在同一的起点，也可以分为一前一后，也就是对撞指针

1、递增三元组

题目描述：

给定三个整数数组

A=[A1,A2,…AN]
,
B=[B1,B2,…BN]
,
C=[C1,C2,…CN]
,

请你统计有多少个三元组 (i,j,k)
 满足：

1≤i,j,k≤N
Ai<Bj<Ck
输入格式
第一行包含一个整数 N
。

第二行包含 N
 个整数 A1,A2,…AN
。

第三行包含 N
 个整数 B1,B2,…BN
。

第四行包含 N
 个整数 C1,C2,…CN
。

输出格式
一个整数表示答案。

数据范围
1≤N≤105
,
0≤Ai,Bi,Ci≤105
输入样例：
3
1 1 1
2 2 2
3 3 3
输出样例：
27
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

==思路分析1：==在这道题中可以使用我们之前提到的二分查找法，就是将去遍历中间的那个数，使中间的这个数满足题目的要求

但是在使用二分查找法的时候，必须将数组进行排序，二分查找法只针对有序数组

五、关于DFS（深度优先算法）

一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。属于盲目搜索,最糟糕的情况算法时间复杂度为O(!n)。

1、全排列问题

题目描述
按照字典序输出自然数 
1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入格式
一个整数 
n。

输出格式
由 1∼n 组成的所有不重复的数字序列，每行一个序列。

每个数字保留 
5
5 个场宽。

输入输出样例
输入 
3
输出 
    1    2    3
    1    3    2
    2    1    3
    2    3    1
    3    1    2
    3    2    1
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

做这道题的话就是可以使用画图的方式，先将大概的思路写清楚，再结合代码

在这里插入图片描述

Demo：

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;


const int N = 10;
bool st[N];//true表示选过这个数，false表示没有选过这个数

int arr[N];//存的是答案，即{1,2,3}
int n = 0;

void dfs(int x) {//x是当前枚举到了数组的哪个位置
		if (x > n) {
			for (int i = 1; i <= n; i++) {
				printf("%5d", arr[i]);
			}
			printf("\n");
			return;
		}		
		for (int i = 1; i <= n; i++) {
			if (!st[i]) {
				st[i] = true;//就是选了这个数
				arr[x] = i;//让数组记录下这个数
				dfs(x + 1);//再进行选择下一个数
				st[i] = false;//再把状态置空，即当回溯时，会回到上一个状态
				arr[x] = 0;
			}
		}
}


int main() {
	scanf("%d", &n);
	dfs(1);
	return 0;
}

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

2、组合的输出

题目描述
排列与组合是常用的数学方法，其中组合就是从 n 个元素中抽出 r 个元素（不分顺序且 r≤n），我们可以简单地将 n 个元素理解为自然数1,2，···n，从中取出r个数 
现要求你输出所有组合。

例如 n=5,r=3，所有组合为：

123
,
124
,
125
,
134
,
135
,
145
,
234
,
235
,
245
,
345
123,124,125,134,135,145,234,235,245,345。

输入格式
一行两个自然数 n,r(1<n<21,0≤r≤n)。

输出格式
所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。

注意哦！输出时，每个数字需要 
3
3 个场宽。以 C++ 为例，你可以使用下列代码：

cout << setw(3) << x;
输出占 3 个场宽的数,注意你需要头文件 iomanip。

输入输出样例
输入 
5 3 
输出 
  1  2  3
  1  2  4
  1  2  5
  1  3  4
  1  3  5
  1  4  5
  2  3  4
  2  3  5
  2  4  5
  3  4  5
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

这道题跟上面的那道题差不多，都是选数，但是就是说这道题是组合，而上面那道题就是排列，排列要考虑顺序，组合就不需要考虑顺序，还是可以先画出深度搜索图，

在这里插入图片描述

Demo：

 #define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n, r;
const int N = 21;
int arr[N];

/*
int x;//记录枚举到了哪个位置
int arr[];//用来记录存了哪些数据
int start;//用来记录当前位置从几开始枚举·
*/


void dfs(int x, int start) {
	//退出搜索
	if (x > r) {
		for (int i = 1; i <= r; i++) {
			printf("%3d", arr[i]);
		}
		printf("\n");
		return;
	}

	for (int i = start; i <= n; i++) {
		arr[x] = i;
		dfs(x + 1, i + 1);
		arr[x] = 0;
	}
}

int main() {
	scanf("%d%d", &n, &r);

	dfs(1,1);

	return 0;
}

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

3、跳台阶

一个楼梯共有 n 级台阶，每次可以走一级或者两级，问从第 00 级台阶走到第 n 级台阶一共有多少种方案。

输入格式

共一行，包含一个整数 n。

输出格式

共一行，包含一个整数，表示方案数。

数据范围

1≤n≤15

输入样例：

5
1

输出样例：

8
1

Demo：

#include <stdio.h> 

int dfs(int n){ 
	if(n==1){
		return 1;
	}else if(n==2){
		return 2;
	}else{
		return dfs(n-1)+dfs(n-2);
	}
	
}

int main(){
	
	int n = 0;
	int ret = 0;
	scanf("%d",&n); 
	ret = dfs(n);
	printf("%d",ret);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

4、递归实现指数型枚举

从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式

输入一个整数 n。

输出格式

每行输出一种方案。

同一行内的数必须升序排列，相邻两个数用恰好 11 个空格隔开。

对于没有选任何数的方案，输出空行。

本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

数据范围

1≤n≤15

输入样例：

3
1

输出样例：

Demo：

#include<iostream>
using namespace std;


const int N = 21; 
int st[N];//记录状态 ，1表示选，2表示不选，0表示还在考虑  
int n;

void dfs(int x){
	
	if(x>n){
		int i = 0;
		for(int i=1;i<=n;i++){
			if(st[i]==1){
				printf("%d ",i);
			}
			
		}
		printf("\n");
		return;
	} 
	
	
		//不选
		st[x] = 2;
		dfs(x+1);
		st[x] = 0;//恢复现场
		
		//选 
		st[x] = 1;
		dfs(x+1);
		st[x] = 0;//恢复现场  
	
}


int main()
{
    scanf("%d",&n);
    dfs(1);
    return 0;
}
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

5、递归实现排列型枚举

题目描述

按照字典序输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

一个整数 n。

输出格式

由1∼n 组成的所有不重复的数字序列，每行一个序列。

每个数字保留 5 个场宽。

输入输出样例

**输入 **

3
1

**输出 **

    1    2    3
    1    3    2
    2    1    3
    2    3    1
    3    1    2
    3    2    1
1
2
3
4
5
6

说明/提示

1≤n≤9。

Demo：

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;


const int N = 10;
bool st[N];//true表示选过这个数，false表示没有选过这个数

int arr[N];//存的是答案，即{1,2,3}
int n = 0;

void dfs(int x) {//x是当前枚举到了数组的哪个位置
		if (x > n) {
			for (int i = 1; i <= n; i++) {
				printf("%5d", arr[i]);
			}
			printf("\n");
			return;
		}		
		for (int i = 1; i <= n; i++) {
			if (!st[i]) {//表示如果这个数没有被选过就选择它
				st[i] = true;
				arr[x] = i;
				dfs(x + 1);
				st[i] = false;
				arr[x] = 0;
			}
		}
}


int main() {
	scanf("%d", &n);
	dfs(1);
	return 0;
}

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

6、递归实现组合型枚举

题目描述

排列与组合是常用的数学方法，其中组合就是从 n 个元素中抽出 r 个元素（不分顺序且r≤n），我们可以简单地将 n 个元素理解为自然数 1,2,…,n，从中任取 r 个数。

现要求你输出所有组合。

例如 n=5,r=3，所有组合为：

123,124,125,134,135,145,234,235,245,345123,124,125,134,135,145,234,235,245,345。

输入格式

一行两个自然数 n*,r(1<n<21,0≤r≤n)。

输出格式

所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，每个元素占三个字符的位置，所有的组合也按字典顺序。

注意哦！输出时，每个数字需要 33 个场宽。以 C++ 为例，你可以使用下列代码：

cout << setw(3) << x;
1

输出占 33 个场宽的数 x。注意你需要头文件 iomanip。

输入输出样例

**输入 **

5 3 
1

**输出 **

Demo：



#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n, r;
const int N = 21;
int arr[N];

/*
int x;//记录枚举到了哪个位置
int arr[];//用来记录存了哪些数据
int start;//用来记录当前位置从几开始枚举·
*/


void dfs(int x, int start) {
	//退出搜索
	if (x > r) {
		for (int i = 1; i <= r; i++) {
			printf("%3d", arr[i]);
		}
		printf("\n");
		return;
	}

	for (int i = start; i <= n; i++) {
		arr[x] = i;
		dfs(x + 1, i + 1);
		arr[x] = 0;
	}
}

int main() {
	scanf("%d%d", &n, &r);

	dfs(1,1);

	return 0;
}

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

六、关于蓝桥杯中常用的STL

①vector容器

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>  
#include <string>  
#include <vector>
using namespace std;

int main() {
    //创建一个int类型的vector数组，记得要包含头文件
    vector<int> arr;

    

    /*
    还有其他的定义方法：
    vector<int> a(3);//定义一个长度为3的vector  未初始化 输出》0 0 0

    vector<int> a(10, 3); //定义一个长度为10，且每个数赋值为3
    
    //将向量b中从下标0 1 2（共三个）的元素赋值给a，a的类型为int型
	//它的初始化不和数组一样 
	vector<int>a(b.begin(),b.begin+3);

    int b[7] = { 1,2,3,4,5,6,7 };
    vector<int> a(b, b + 7);//给a赋值1-7的数值
    */


    //尾插进去数据
    arr.push_back(1);
    arr.push_back(2);
    arr.push_back(3);
    arr.push_back(4);
    arr.push_back(5);

    //遍历数组中的元素，使用迭代器
    vector<int>::iterator it;
    for (it = arr.begin(); it != arr.end(); it++)
        printf("%d ", *it);

    //在任意的位置插入元素,在第i+1个元素前面插入数据10，即在第二个元素前面插入数据10
    arr.insert(arr.begin() + 1, 10);//1 10 2 3 4 5
  
    //删除元素：    
    arr.erase(arr.begin() + 2); //删除第i+1个元素,即删除第三个元素

    arr.erase(arr.begin() + 0, arr.end() + 4); //删除区间[i, j - 1]; 区间从0开始
   
    //删除尾部元素
    arr.pop_back();

    //求数组大小:
    arr.size();

    //清空
    arr.clear();

    return 0;
}

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

关于vector中最核心的也就是排序和逆序

（1）排序

//关于在vector中使用排序的方法，也是有直接封装好了的方法，直接可以调用
//注意使用<algorithm>头文件

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>   
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> arr = { 10,4,1,0,3,7,8 };
    sort(arr.begin(),arr.end());

    vector<int>::iterator it;
    for (it = arr.begin(); it != arr.end(); it++) {
        printf("%d ", *it);
    }

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

（2）逆序

//
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>   
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> arr = { 1,2,3,4,5 };
    
    reverse(arr.begin(), arr.end()); //将元素翻转，即逆序排列！

    vector<int>::iterator it;
    for (it = arr.begin(); it != arr.end(); it++) {
        printf("%d ", *it);
    }


    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

②map容器（有序的但是可以重复）

关于map容器和vector不一样，它通过键值对的形式存储数据的，一个key对应一个value，而且在存储的时候，不能存在相同的key，还有注意就是在使用map容器的时候要包含头文件

③set容器（有序但是不重复）

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>   
#include <set>
#include <algorithm>

using namespace std;

int main() {
    //创建一个set数组
    set<int> s;
    //插入数据，并且自动根据数据的大小进行排序
    s.insert(10);
    s.insert(40);
    s.insert(20);
    s.insert(40);
    s.insert(90);
    s.insert(60);
    //遍历set
    set<int>::iterator it;
    for (it = s.begin(); it != s.end(); it++) {
        printf("%d ", *it);
    }
    printf("\n");
    //删除起始位置的元素
    s.erase(s.begin());
    
    //根据元素删除
    s.erase(40);

    //查找元素是否存在，存在就返回它的迭代器，不存在就返回set.end();
    set<int>::iterator ret = s.find(90);
    printf("%d", *ret);

    //查找元素的个数
    int count = s.count(60);

    //清空
    s.clear();
    return 0;
}

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

④队列

queue<Type, Container> (<数据类型，容器类型>）
初始化时必须要有数据类型，容器可省略，省略时则默认为deque 类型

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>   
#include <queue>
#include <list>
#include <algorithm>

using namespace std;

int main() {

    /*默认为用deque容器实现的queue
    queue<int> q1;
    queue<double> q2;
    queue<char> q3;
    */


    //用list容器实现的queue 
    queue<char, list<char>> q1;
        
    //注意：不能使用vector去初始化队列
        
    //push() 在队尾插入一个元素
    q1.push(10);
    q1.push(20);
    q1.push(30);
    q1.push(40);
    q1.push(50);

    //pop() 删除队列第一个元素
    q1.pop();

    //size() 返回队列中元素个数
    int size = q1.size();

    //empty() 如果队列空则返回true
    bool flag = q1.empty();

    //front() 返回队列中的第一个元素
    int first = q1.front();

    //back() 返回队列中最后一个元素
    int tail = q1.back();

    //遍历队列
    for (int i = 0; i < size; i++) {   //myqueue_size 必须是固定值
        printf("%d ", q1.front());
        /*q1.push(q1.front());*/
        q1.pop();
    }


    return 0;
}

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

七、c++中常用的数学函数

	//求常数e的x次方。#define e 2.71828182845904523536
    exp(x);  
    //求x的y次方
    pow(x, y);  
    //开平方
    sqrt(x);
    
    //求e为底的对数 ln
    log(x);    
    //求10为底的对数 lg
    log10(x);    
    //求x为底的y的对数
    log(y) / log(x);  
    
    //整数型的绝对值
    int abs(x);   
    //浮点型的绝对值 
    double fabs(double x);
    
    //向上取整 返回的是大于或等于x的最小整数
    ceil(x);   

    //向下取整 返回的是小于或等于x的最大整数
    floor(x);    

    //朝零方向取整
    fix(x);    

    //四舍五入到最近的整数
    round(x);    

    //使用round保留2位小数
    double num = 3.1415926;
    double roundedNum = round(num * 100) / 100;
    cout << roundedNum << endl;     //输出 3.14  
    
    //产生一个在[0,50)区间内的随机数
	r = rand() % 50;    
	//产生[a,b]区间的随机数
	r = a + rand() % (b-a+1);   
	
	//三角函数
	sin(x);    //正弦
	cos(x);    //余弦。cos(π)=-1,故 π = acos(-1)
	tan(x);    //正切
 
	//反三角函数
	asin(x);    //反正弦 [−π/2, π/2]
	acos(x);    //反余弦 [0, π]
	atan(x);    //反正切（主值）   [−π/2, π/2]
	atan2(x);    //反正切（整圆值） [−π, π]
	
	
	//两个数比较
	min(a, b, comp);    //取最小值，comp为指定的比较规则，可缺省
	max(a, b, comp);
 
	//多个数比较，需加 { } 
	min({a,b,c,d}, comp);


	辗转相除法求最大公约数：

	int gcd(int a,int b){

         int temp;

         while(a%b!=0){

                  temp=a;

                  a=b;

                  b=temp%b;

         }

         return b;

	}

	辗转相除法最小公倍数：

	int lcm(int a,int b){

         int a1=a,b1=b,temp;

         while(a%b!=0){

                  temp=a;

                  a=b;

                  b=temp%b;
         }
         return a1/b*b1;
	  }

	杨辉三角：
	任意一行的所有元素

	C[0]=1;

	For(int i=1;i<=n;i++)         
        C[i]=C[i-1]*(n-i+1)/
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

八、常考知识点

1、优先队列

关于在c++中的优先队列就是可以拿出优先级最高的元素

Demo：这里默认使用的是大顶堆

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>   
#include <queue>
#include <list>
#include <algorithm>

using namespace std;

int main() {
    //定义一个存储int型的优先队列
    priority_queue<int> queue;//大顶堆

    //向队列中插入元素
    queue.push(1);
    queue.push(-3);
    queue.push(0);
    queue.push(5);
    queue.push(8);
    queue.push(10);

    //获取元素的数量
    int size = queue.size();

    //删除优先级最高的元素
    queue.pop();

    //访问优先级最高的元素
    queue.top();

    //0判断优先队列是否为空
    bool flag = queue.empty();


    while (!queue.empty()) {
        printf("%d ", queue.top());
        queue.pop();
    }
    return 0;
}

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

Demo：小顶堆

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>   
#include <queue>
#include <list>
#include <algorithm>

using namespace std;


int main() {
    //定义一个存储int型的优先队列
    priority_queue<int,vector<int>,greater<int>> queue;//就改成了小顶堆，大顶堆是less<int>

    //向队列中插入元素
    queue.push(1);
    queue.push(-3);
    queue.push(0);
    queue.push(5);
    queue.push(8);
    queue.push(10);

    //获取元素的数量
    int size = queue.size();

    //删除优先级最高的元素
    queue.pop();

    //访问优先级最高的元素
    queue.top();

    //0判断优先队列是否为空
    bool flag = queue.empty();


    while (!queue.empty()) {
        printf("%d ", queue.top());
        queue.pop();
    }
    return 0;
}

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/528511