2023年10月16日,补充数据结构:链表、哈希表。补充算法:递归、广搜
2023年11月6日,补充排序算法:冒泡排序、选择排序、桶排序。优化了部分排版显示
2024年2月3日,新增了程序优化,补充递归算法、递推算法
梦开始的地方
// 基本框架
#include<iostream>
using namespace std;
int main(){
return 0;
}
程序优化
将以下代码加到程序第一行(头文件前面),可以实现时间上的优化
1、指令优化,评测机指令架构可能不一样,有可能产生RE错误,慎用!!!
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
2、编译优化,也就是常说的O2优化,主要分为O1,O2,O3三种,只推荐开到O2即可,O3没必要!!!
// 一般只写这一句就会有很大的效果了
#pragma GCC optimize(2)
最后附上我常用的优化代码
#pragma GCC target ("avx")
#pragma GCC optimize (2, 3, "Ofast", "inline", "-ffast-math")
第一章:IO
数据输出:
cout & printf
// 输出指令:cout
// 输出运算符:<< (两个小于)
// 换行指令:endl
cout<<"这是一个输出样例:"<<endl;
cout<<"hello world!";
// C语言格式化输出: printf("<格式化字符串>", <参量表>)
// 常用:%d 整形、%lld 长整型、%c 字符型、%f 浮点型、%lf 高精度浮点、%.3f 保留三位小数
double pi = 3.1415926;
printf("保留小数位数:%.2lf %.3lf", pi, pi);
更多格式化字符串:请点这里
数据输入:
cin & scanf
// 输入指令:cin
// 输入运算符:>> (两个大于)
// 输入数据前,需要先定义变量来接收
int a;
cin>>a;
// C语言格式化输入: scanf("<格式化字符串>", &<参量表>)
// 使用时变量前面一定要加上取址符 & 对应的格式化字符串类型不能写错
// 常用:%d 整形、%lld 长整型、%c 字符型、%f 浮点型
double pi;
scanf("%lf", &pi);
做题时的文件IO:
做题时只需要正常写在main主函数最开始的地方
// 从文件中读取输入,文件名C.in
freopen("C.in", "r", stdin);
// 将答案写入文件,文件名C.out
freopen("C.out", "w", stdout);
第二章:基本语法
分支结构
if语句
// 第一个if语句必须写,另外两个非必须,根据需求来写
if(){}
else if(){}
else{}
三目运算符
基本格式:
如果表达式1为真,那么语句返回的值就是表达式2,否则返回表达式3的值
int a=10, b=10;
// 如果a>b为真,c=a,否则c=b
int c = a>b?a:b;
switch语句
// 小括号只能传整形 和 字符类型。break必须写,不写就会合并多个情况
switch (1) {
case 1:
// 第一个选择
break;
case 2:
// 第二个选择
break;
default:
// 以上都没出现的选择
break;
}
循环结构
for循环
// 从0开始,到100结束
for(int i=0;i<=100;i++){
cout<<i<<" ";
}
while循环
// 小括号为运行的条件,只要条件为真就会执行循环
while(1){}
// 当小括号里面为1,表示死循环,不会主动结束,需要使用break来结束循环
// continue语句:跳过本次循环
do-while循环
// 优先级t10086,学了就没用过,了解就行
do{
// 代码,(和while没啥区别,这个是先循环一次,再去判断条件)
}while(1);
goto语句(牛马语句)自行百度了解
函数:封装代码,提高代码复用率
// 函数是一种固定的代码,可以让代码被重复利用,降低冗余
// 函数定义五个步骤
// 1、函数的返回值类型,即调用了这个函数后,你想要得到的数据类型(关联第5点),没有返回值就是void
// 2、函数名,随便定义,只要满足变量命名规则即可
// 3、函数的参数,需要传给函数的变量(可有可无)
// 4、函数的功能(核心代码)
// 5、函数的返回值,函数处理完的结果(关键字:return),只要第一点写的不是void,就必须要写return返回值
// 例:定义找两个整数最大值的函数
// 1、函数返回值类型:两个数的最大值,返回值为int类型
// 2、函数名:my_max
// 3、函数的参数:需要传入两个整数a,b
// 4、函数的功能:找两个整数的最大值:a>b?a:b
// 5、函数的返回值:直接返回最大的值即可
int my_max(int a, int b){
return a>b?a:b;
}
结构体:可以自己创建数据类型 (不考虑高级用法)
// 结构体关键字:struct
struct xxx{ // 结构体名称:xxx
string name; // 结构体属性1
int age; // 结构体属性2
int score; // 结构体属性3
}a,b,c; // 定义结构体的时候可以声明结构体变量,写不写都可以
// 使用结构体创建变量,和创建int变量一样: 数据类型 变量名;
xxx aa; // 创建了一个结构体变量aa
struct xxx bb; // 结构体专属写法,我的评价是不如上面那种。。
// 结构体变量赋值
// 1、在创建时赋值(列表化赋值),必须严格按照结构体定义时的顺序来赋值
xxx aa = {"小明", 12, 250};
// 2、指定属性赋值,可以根据需求指定属性赋值,没有顺序要求
bb.age = 12;
bb.name = "小明";
bb.score = 250;
// 输出结构体时,要指明属性,不能直接输出结构体变量
cout<<aa.name<<" "<<aa.age<<" "<<aa.score;
第三章:数据结构
1、数组
// 相同数据类型的元素按一定顺序排列的集合,就是把有限个类型相同的变量用一个名字命名
// 数据类型 数组名[元素个数];
int a[100]; // 100个元素的int数组,也可以理解为100个变量
a[0] = 999; // 通过索引访问元素
cout<<a[0];
1、数组的索引从零开始
2、数组的最大索引是长度减一
2、栈
一种数据结构,特点是先进后出
#include<stack> // 使用时需要导入头文件
// 创建栈
stack<int> st; // 创建了一个名为st的栈,里面只能存放int类型的数据
stack<Node> st1; // 创建了一个名为st1的栈,里面只能存放Node类型的数据 Node:自己的定义的结构体类型
// 栈的常用操作
st.push(1); // 往st栈顶添加一个元素1
st.pop(); // 把st栈顶元素弹出(删除、出栈)
st.top(): // 获取st栈顶元素
st.size(); // 获取st栈的元素个数
st.empty(); // 判断st栈是否为空,为空则返回1
3、队列
一种数据结构,特点是先进先出(生活中的排队)
#include<queue> // 使用时需要导入头文件
// 创建栈
queue<int> st; // 创建了一个名为st的队列,里面只能存放int类型的数据
queue<Node> st1; // 创建了一个名为st1的队列,里面只能存放Node类型的数据 Node:是自己的定义的结构体类型
// 队列的常用操作
st.push(1); // 往队尾添加一个元素
st.pop(); // 把队首元素出队(删除)
st.front(): // 获取队首元素
st.back(); // 获取对尾元素
st.size(); // 获取队列中的元素个数
st.empty(); // 判断队列是否为空,为空则返回1
4、链表(结构体+指针)
链表是一种用于存储数据的数据结构,通过如链条一般的指针来连接元素。
它的特点是插入与删除数据十分方便,但寻找与读取数据的表现欠佳。
链表分类主要有 单链表 和 双链表
单链表:
struct Node{
int val; // 链表的值
Node *next; // 下一个节点的地址
};
双链表
struct Node{
int val; // 链表的值
Node *left; // 上一个节点的地址
Node *right; // 下一个节点的地址
};
链表的实现涉及到指针和动态内存管理,篇幅有限就不贴代码了
5、哈希表(集合)
哈希表又称散列表,一种以「key-value」形式存储数据的数据结构,可以简单看成python中的字典。
#include<map> // 使用时需要导入头文件
// 创建,前一个类型是键的类型,后一个是值的类型
map<int, int> p; // 创建了一个哈希表变量,键的类型是int,值的类型也是int
map<char, int> p2; // 创建了一个哈希表变量,键的类型是char,值的类型是int
map<string, int> p3; // 创建了一个哈希表变量,键的类型是string,值的类型是int,可以用来统计字符串出现的数量(比结构体好用)
// 使用
// 1、键不存在:
p2['A'] = 100; // 添加一个数据,键为'A',值为100
// 2、键存在:正常调用即可
cout<<p2['A'];
第四章:基础算法
排序算法
冒泡排序
排序的过程就像冒泡一样,每次都会把待排序数组中最大(最小)的元素冒泡到数组的末尾,排序的核心就是循环比较和交换
例:对数组:12,3,25,99,21,1,33,17,进行冒泡升序排序。
从第一个元素开始,依次对相邻的两个元素进行比较判断,并把最大的元素交换到后面去
第一次冒泡,99被交换到末尾,完成排序
3,12,25,21,1,33,17,99
第二次冒泡,33被交换到末尾,完成排序
3,12,21,1,25,17,33,99
第三次冒泡,25被交换到末尾,完成排序
3,12,1,21,17,25,33,99
...... (一直重复这个过程,直到排序结束)
// 排序n个元素,只需要冒泡n-1次即可
for(int i=1;i<=n-1;i++){
// 每完成一次冒泡排序,就可以少比较一次(排好序的元素越来越多)
for(int j=1;j<=n-i;j++){
// 把较大的元素排序到末尾
if(a[j]>a[j+1]) swap(a[j], a[j+1]);
}
}
选择排序
本质上和冒泡差不多,选择排序每次都会从待排序数组中选择一个最大(最小)的值,然后放到数组的最前面,相比冒泡排序减少了很多交换次数
例:对数组:12,3,25,99,21,1,33,17,进行选择升序排序。
第一次选择,最小值1被交换到待排序数组的最前方
1,3,25,99,21,12,33,17
第二次选择,最小值3被交换到待排序数组的最前方
1,3,25,99,21,12,33,17
第二次选择,最小值12被交换到待排序数组的最前方
1,3,12,99,21,25,33,17
...... (一直重复这个过程,直到排序结束)
// 每次选择一个最小(最大)的元素,放到待排序数组前面
for(int i=1;i<=n-1;i++){
// 找待排序数组中的最小值
int k = i, minn = a[i]; // 初始化最小值的信息
for(int j=i;j<=n;j++){
if(a[j] < minn){ // 比较找最小值
k = j; // 更新最小值索引
minn = a[j]; // 更新最小值
}
}
swap(a[i], a[k]); // 把当前的最小值和待排序数组第一个元素交换
}
桶排序
桶排序,是一种用桶数组来辅助的排序算法,适用于数据数据范围较小的情况,且只能对整数排序,去重和排序都比较方便
桶数组:是一个标记数组,用于标记某个数字是否出现,或者统计某个数字的出现次数。因为不管某个数字是否出现,都会占用一个数组空间(数组是连续的),所以数据范围太大的话,桶排序无法完成。(可以考虑用哈希表来优化桶数组)
例:对数组:12,3,25,99,21,1,33,17,进行桶排序(升序)。
// 初始化桶,数据中的最大值是99,所以桶的容量必须大于99
// 类型根据是否要去重来选择,去重就用bool数组标记,不去重就int数组统计
int tong[100] = {0};
int t;
for(int i=1;i<=n;i++){
cin>>t;
tong[t]++; // 每获取一个数据,t的次数+1
}
// 桶的索引就是题目输入的数据
// 最后根据桶的索引输出排序后的数组即可
for(int i=0;i<=100;i++){ // 升序
// 不去重的排序,根据统计出现的次数来输出
for(int j=1;j<=tong[i];j++){
cout<<i<<" ";
}
// 要去重的话,桶数组就用bool类型,标记元素是否出现
// 每个元素出现了,就输出一次即可
// if(tong[i] == 1) cout<<i<<" ";
}
递归
传送门:算法笔记-递归
递给你一个乌龟
递归:是一种函数直接或者间接调用自己的算法,主要特点就是套娃似的调用自己。在解递归类的题目时,核心思路就是把大问题拆分为很多小问题,然后继续拆分每一个小问题,直到拆分的问题能直接求解为止。学了树结构的同学,可以多画一下递归调用树,很快就能理解啦。
递归解题三要素:
1、递归函数的定义,递归最重要的就是明白函数的功能是什么,充分的理解自己定义的函数。
2、递归表达式,递归是自己调用自己的逻辑,也就是说会把目标问题分成其他的更小、更容易解决的问题,这个过程就是递归表达式。
3、递归边界,可以把递归比作一个循环,不设定结束的条件就会陷入'死循环'。
例:求1~n全部整数之和。
// 1、函数定义:sum(n)表示1~n的全部整数之和,sum(5)=15
// 2、递归表达式:sum(n) = sum(n-1)+n,把要解决的问题拆成了范围更小的问题
// 3、递归边界:当n=1时,可以直接得出sum(1)=1,不需要继续递归了
int sum(int n){
if(n == 1) return 1;
return sum(n-1) + n;
}
递归的优化
递归的优化主要集中在记忆化递归和尾递归上面。
记忆化递归:就是用一个数组来保存每一次递归计算的结果,当递归到某个值时,先去数组里面找这个值之前有没有计算过,计算过直接获取之前计算的值;没有计算过就计算了再放入数组中。
尾递归:一个函数中所有递归形式的调用都出现在函数的末尾,即递归调用都写在return语句里面
递推
递推是一种数学上的方法,也是计算机中比较重要的基础算法。
递推算法的特点是:在求一个问题时,已知条件和要求的结果之间存在某种联系,这个联系就是递推式,找到递推的关系式后。从问题推导到已知条件叫做逆推;从已知条件推导到问题叫做顺推。
代码太多,经典题目总结好了,自己看(^_^) 传送门:递推笔记
第五章:进阶算法
搜索:深搜(深度优先)(可以简单理解为一条路走到底)
深搜的基础是递归,通过遍历每一种可能找到最优解,属于暴力的算法,能通过的数据范围有限(一般不会超过20)。
例1:排列组合,从n个数中选择k个数的全排(组合)
#include <iostream>
using namespace std;
// 从n个数中选k个数全排(组合)
int n,k;
int res[15]; // 答案数字
bool vis[15]; // 标记数组,0表示没被选过,1表示被选
// 函数作用:表示当前选的是第几个数(总共要选k个数)
void dfs(int x){
// 当前选的数超过k个,就结束搜索(x等于k,即dfs(k)表示选第k个数)
if(x>k){
// 输出答案,有k个数字所以要用循环
for(int i=1;i<=k;i++){
cout<<res[i]<<" ";
}
cout<<endl;
return;
}
// 从1~n个数中选
for(int i=1;i<=n;i++){
// 全排列:没有数字大小限制,只有一个条件:数字没被选过即可
// if(vis[i] != 1){
// 组合:数字没被选过 && 当前选的数字不能小于前一个数字
// 也就是说,1 2 3 和 2 3 1是一种方案
if(vis[i] != 1 && res[x-1]<i){
res[x] = i; // 把这个数字记录到答案数组中
vis[i] = 1; // 标记这个数字,后面的搜索中不能再选了
dfs(x+1); // 递归搜索下一个数字
vis[i] = 0; // 回溯,本次搜索完后,后续的其他搜索中也可能有这个数字
}
}
}
int main(){
cin>>n>>k;
dfs(1);
return 0;
}
搜索:广搜(宽度优先、广度优先)(每次都会访问同一层的节点,访问完了再访问下一层)
和深搜不同,广搜需要借助队列来完成,解题过程就是先把起点入队,然后在循环出队,每次出队一个元素,就把能从这个点一次能到的点全部入队,循环操作,直到结束
例:有一个n*m的迷宫地图,上面用字符来描述迷宫的情况,其中'.'表示空地,'#'表示墙,'S'表示起点,'T'表示出口。现在你需要找到从起点到出口最少需要走的步数
#include <iostream>
#include<queue> // 队列头文件
using namespace std;
// 迷宫格结构体,当前格子的坐标(x,y),以及从起点到当前格子的最少步数step
struct pos{
int x,y,step;
};
queue<pos> q; // 广搜队列
char map[105][105]; // 地图数组
int vis[105][105]; // 标记数组,用于标记已经被走过的点
int dx[4] = {0,1,0,-1}; // x方向位移数组:右、下、左、上
int dy[4] = {1,0,-1,0}; // y方向位移数组:右、下、左、上
// 地图大小
int n,m,ans=0;
int sx,sy; // 起点坐标
int ex,ey; // 终点坐标
// 广搜
void bfs(){
// 起点格子
pos t = {sx,sy,0};
vis[sx][sy] = 1; // 标记起点
q.push(t); // 起点入队,开始广搜
while(!q.empty()){
t = q.front(); // 队首元素出队
q.pop(); // 队首已经在下面被访问,所以可以先删掉
// 走到终点结束
if(t.x == ex && t.y == ey){
ans = t.step;
return;
}
// 从当前队首的格子能走到的四个方向上的格子
for(int i=0;i<4;i++){
int xx = dx[i] + t.x;
int yy = dy[i] + t.y;
// 不能超过迷宫边界 遇到墙不能走 走过的不能走
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&map[xx][yy]!='#'&&vis[xx][yy]!=1){
q.push({xx,yy,t.step+1}); // 上下左右能走的入队,并更新最少步数step
vis[xx][yy] = 1; // 下个格子被走过了,标记
}
}
}
}
int main() {
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>map[i][j];
if(map[i][j] == 'S') sx = i, sy = j;
if(map[i][j] == 'T') ex = i, ey = j;
}
}
bfs(); // 调用广搜
cout<<ans;
return 0;
}
共 13 条回复
6
6
支老师我们永远会记住你的
老师
支老师我们永远会记住你的
喵星人
6
我直接看成了梦开始的地方
非常实用
好用————666!!!