STL 中 link 容器
数据结构基础-链表
实验介绍
我们这门课是算法,这里所讲的数据结构倾向于实战,大家不要拘泥于具体的写法,而重在学习原理,和使用方式,我们所需要的是简洁、实用和快速。我们这节课主要目标学会三种链表的原理与实现,学会灵活地运用,能够不依赖于模板根据题目独立写出各类链表。
我们不是数据结构教程,经典的数据结构采用 C 或 C++ 采用模板类进行编写,但是非常不适合竞赛使用,几行代码硬是能写成十几行,提高了复用性但是浪费了书写时间。所以并不适合竞赛,竞赛追求效率、accept 和简洁。
知识点
- 单链表实现原理与应用
- 双向链表实现原理与应用
- 循环链表实现原理与应用
为什么使用链表
相信大家在这之前已经学过数组,无论是 C++,Java,Python 还是其它语言大都会有数组这一概念,好用吗?很好用,所谓数组其实就是线性表的顺序存储形式的原理,我们来看一下链表的定义并对比一下链式存储与顺序存储的存储方式。
什么是链表
链表是线性表的链式存取的数据结构,是一种链式存取的数据结构,是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:数据域(数据元素的映象)+ 指针域(指示后继元素存储位置),数据域就是存储数据的存储单元,指针域就是连接每个结点的地址数据。 相比于线性表顺序结构,操作复杂。
似乎定义是有些晦涩难懂,我们用两张图来对比一下数组也就是线性表的顺序存储结构和链表在内存中存储 1-9 号元素的形式:
- 顺序存储
- 链式存储
思考一下:
线性表的数据存储方式的内存地址是顺序的,链式存储的数据的内存地址的有什么规律呢?
事实上链式存储的内存地址的是随机分配的,他们每个节点地址之间是没有任何关联的。而且在每个新的节点在产生之前,我们都是不知道他的地址的。
链表初体验
通过上面的介绍,大家可能还是不太能理解为什么要使用链表或者还不懂什么是链表,我们用一个题目来引入。
小王子有一天迷上了排队的游戏,桌子上有标号为 1-10 按顺序摆放的 10 个玩具,现在小王子想将它们按自己的喜好进行摆放。小王子每次从中挑选一个好看的玩具放到所有玩具的最前面。已知他总共挑选了 M 次,每次选取标号为 X 的玩具放到最前面,求摆放完成后的玩具标号。
给出一组输入,M=8 共计排了 8 次,这 8 次的序列为 9,3,2,5,6,8,9,8。 求最终玩具的编号序列。
我们首先梳理一下基本的模拟方法的思路,这个题该怎么去解答:
- 首先我们要开一个长度为 11 的数组,因为下标要从 1 开始所以 0 — 10 共计 11 个元素。
1 | a[11]={0,1,2,3,4,5,6,7,8,9,10} |
- 然后根据题意我们要写一个查找函数:
1 | //伪代码形式 |
我们简单描述一下这个过程:
首先是步进查找比如查找值为 5 元素的下标:
找到元素后返回下标,值为 5。
- 最后我们找到元素后要进行插入操作。
1 | void Function 移动(L) |
我们还是以 5 为例,要把 5 移到到首位,肯定不是把 5 放到第一位就行。
讲到这里,大部分同学肯定会写出如下代码:
1 | //伪代码形式 |
这样每次调用移动函数即可,M=8 调用 8 次函数,每次传入 X 找到位置后,即可得到正确答案。
如果我们规定每次循环的时间复杂度为 1 的话,这次花费了我们多少时间呢?
- X=9 查找 9 循环了 9 次 移动花费了 9 次 此时序列为 9,1,2,3,4,5,6,7,8,10
- X=3 查找 3 循环了 4 次 移动花费了 4 次 此时序列为 3,9,1,2,4,5,6,7,8,10
我们看到每次都花费了大量时间去移动。如果我们采用链表去存储呢,会是什么样子呢。
我们来模拟一下过程:
- 这是初始序列
第一次输入 X=9:
- 执行查询操作:
- 执行删除操作
给 9 前面结点的指针赋值为 9 的指针,再将 9 删除。
- 执行插入操作:
新建一个结点, data 部分为 9 ,将结点插入链表的首部
相比之下后者执行的操作更少,速度更快,那我们给出该题目的一个标准的答案及详细解析。
题目解析
我们学了前面那么多的知识点,我们来动手解答一下小王子的问题了。
- 首先,我们使用链表的话,要先给出结点的定义,上面讲到链表的形式。
结点定义:
1 | struct Node |
- 第二步,我们要先构成一个这样的链表:
head-> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10
1 | Node * head=new Node; //先生成头结点 |
- 第三步,我们要写一个插入函数
1 | void insert(int x) |
- 第四步我们要写一个删除函数,通过遍历链表删掉想要的数字
1 | void del(int x) |
- 第五步我们写一个遍历输出函数,形式接近于删除函数
1 | void show(int i) |
- 最后一步我们编写主函数
1 | int main() |
我们带入之前的样例进行测试:N=8 X= 9 3 2 5 6 8 9 8。
完整代码如下:
C++写法:
1 |
|
Python 写法

Java 写法

1 | class Node: |
1 | import java.util.Scanner; |
以上为带有头结点的单链表,相应的还有没有头结点的单链表,有兴趣的同学可以自行查阅资料。在比赛中我们常用 STL 中 link 容器而很少会去定义和使用,这一章节我们主要是学会原理和使用,原理学会之后无论是什么样的链表都是可以设计出来的。
头结点: 如果链表有头节点,则链式结构中的第一个节点称为头结点,其数据域可以存储一些附加信息,如链表长度;其指针域指向链表中的第一个节点。 经过上面对小王子这个题的讲解,相信大家都对这个链表的有点有了一个初步的认识,我们看到链表的使用确实很方便,在我们不需要随机访线性表里面的元素时,使用链表确实要方便很多,无论是时间复杂度还是空间复杂度都十分优秀。下面我们对线性表的两种存储方式的对比。
链表与顺序表优缺点对比
经过上面的讲解,大家应该都已经对线性表存储数据有了一定的了解,线性表是编写程序中的最常见数据结构,对于顺序和链式两种存储结构我们到底该在何时选择哪一种存储方式? 我们对两种存储方式做一个对比。
顺序表
优点:
- 无需为表示结点间的逻辑关系而增加额外的存储空间(因为逻辑上相邻的元素其存储的物理位置也是相邻的);
- 可方便地随机存取表中的任一元素:
由于顺序表每个元素的大小相等,且知道第几个元素就可以通过计算得到任意元素的地址,既可以随机存取任一元素。
缺点:
- 插入或删除运算不方便:
除表尾的位置外,在表的其它位置上进行插入或删除操作都必须移动大量的结点,其效率较低;
如在 8、9 之 间插入 X 元素,那我们为了保证其顺序性需要把 8 和 9 向后移动一位,再将 X 放到 8 的位置。
这样的存储方式增加了处理器和 IO 资源的消耗代价,这是我们不愿意看到的,至于删除其原理相同,我们不再进行赘述。
- 难以匹配存储规模:
由于顺序表要求占用连续的存储空间,存储分配只能预先进行静态分配,因此当表长变化较大时,难以确定合适的存储规模。
时间复杂度
查找操作为 O(1),插入和删除操作为 O(n)。
时间复杂度的计算:
时间复杂度不是一个具体的数字,而是一个量级。
常见的时间复杂度量级如下:
常数阶 O(1) < 对数阶 O(log2n) < 线性阶 O(n) < 线性对数阶 O(n log_{2}n)O(nlo**g2n) < 平方阶 O(n^{2})O(n2) < 方阶 O(n^{3})O(n3) < k 次方阶 O(n^{K})O(n**K) < 指数阶 O(2^{n})O(2n) < 阶乘阶O(n!)O(n!) < O(n^{n})O(n**n)
具体的计算方法其他章节会进行讲述,这里大家简单知道时间复杂度量级的大小即可。
链表
优点:
- 插入和删除速度快,保留原有的物理顺序,在插入或者删除一个元素的时候,只需要改变指针指向即可;
- 没有空间限制, 存储元素无上限, 只与内存空间大小有关;
- 动态分配内存空间,不用事先开辟内存;
- 使内存的利用率变高。
缺点:
- 占用额外的空间以存储指针,比较浪费空间,不连续存储,Malloc 函数开辟空间碎片比较多;
- 查找速度比较慢,因为在查找时,需要循环遍历链表。
时间复杂度:
查找操作为 O(n), 插入和删除操作为 O(1)。
使用循环链表解决约瑟夫环问题
将单链表或者双链表的头尾结点链接起来,就是一个循环链表。不增加额外存储花销,却给不少操作带来了方便从循环表中任一结点出发,都能访问到表中其他结点。
循环链表的组成
特点:
- 首尾相接的链表。
- 可以从任一节点出发,访问链表中的所有节点。
- 判断循环链表中尾结点的特点:
q->next==first
通过观察不难发现,循环链表与单链表的差别就是最后的指针一个为空一个与 First 相等,其他的都没有什么变化,也就是多了一个循环遍历的过程。
约瑟夫环问题
设有 n 个人围坐在圆桌周围,现从某个位置 k(1≤k≤n) 上的人开始报数,报数到 m 的人就站出来。下一个人,即原来的第 m+1 个位置上的人,又从 1 开始报数,再报数到 m 的人站出来。依次重复下去,直到全部的人都站出来为止。试设计一个程序求出这 n 个人的出列顺序。
- 要求一:采用循环链表解决
- 要求二:可以使用模拟法,模拟循环链表
- 要求三:可以不使用循环链表类的定义使用方式
大家可以先思考一下如何实验,在 OJ 或者右侧的环境中动手完成。
具体实验步骤
思路分析
首先要通过循环链表模拟一整个过程,然后再寻找删除位置。
删除位置的计算:
从线性表中起始位置 index 出发开始计数,当计数到 m 时(间隔 m-1 个数据),删除该位置上的元素;同时该位置又是下一次计数的起始位置:index=(index+k-1)
代码编写
- C++解法:
第一步:定义循环链表的结点结构体
1 | //头文件与命名空间 |
第二步:定义主函数直接进行解题:
- 信息输入,和所续变量的声明
1 | int n, k, m, i; //n个人从k位置开始报数,数到m出列 |
- 依据题目构造循环链表,可以看出我们直接把插入的函数,拿到了这里来使用。
1 | first = (Node *)new Node; |
- 寻找报数的起点
1 | p = first; |
- 按照顺序依次出链表
1 | while (p != p->pNext) //只剩下一个结点的时候停止 |
完整代码:
1 | //头文件与命名空间 |
Java 解法

Python 解法

双向链表再求解小王子问题
单链表的主要不足之处是 link 字段仅仅指向后继结点,不能有效地找到前驱。双链表弥补了上述不足之处,增加一个指向前驱的指针 。
由于在双向链表中既有前向链又有后向链,寻找任一个结点的直接前驱结点与直接后继结点变得非常方便。设指针 p 指向双链表中某一结点,则有下式成立:
1 | p-> llink->rlink = p = p->rlink->llink |
双向链表的实现
还记得我们在小王子那一题目中所定义前驱变量吗?
因为单链表只能单向遍历所以我们要定义临时变量,如果我们改成双向链表这个题目这里就可以进行优化。
- 首先,我们使用链表的话,要先给出结点的定义,上面讲到链表的形式。
1 | struct Node |
- 第二步,我们要先构成一个这样的链表:
head <-> 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 <-> 7 <-> 8 <-> 9 <-> 10
1 | void insert(int x) |
- 第三步我们要写一个删除函数,通过遍历链表删掉想要的数字
1 | void del(int x) |
- 第四步我们写一个遍历输出函数,形式接近于删除函数
1 | void show(int i) |
- 最后一步我们编写主函数
1 | int main() |
我们带入之前的样例进行测试:N=8 X= 9 3 2 5 6 8 9 8。
我们可以看到这里的删除非常简单,这么写的话大大简化删除了过程,所以在不同题目下灵活地选取链表能够使得解题变得简单。
完整代码如下:
1 |
|
Java 解法:

Python 解法

1 | iimport java.util.Scanner; |
1 | class Node: |
实验总结
关于链表的定义方式,在各种教科书上和网站都有着各个不同版本的定义方式,我们应该学习的实现原理,具体实现都是大同小异,通常在算法中我们只定义结点,在 Main 函数中直接使用结点组成新的链表而不去写链表的结构体,这样可以减少代码量的使用,提高编程的速度,在程序竞赛中的使用的比较多,但是相应的也降低了代码的复用性,不适合用于项目开发中,还需大家理解差异。不要拘泥于写法,注重的是应用和原理,我们学习这门课的目的是为了 accept 题目,而不是写一堆无用的代码浪费时间。
本次实验,我们学习了三种最常见的链表的原理与使用方式,诚然链表的种类是千变万化的,像是循环链表与双向链表的结合形成的双向循环链表,存储图的十字链表等,我们学好这基础的三种链表,以不变应万变才是正确的面对方式。作者在早期学习链表的时侯只会单链表,在比赛的时候临场写出了双向链表,成功 AC 题目,其实链表的类的定义方式也是我在上文写的是最复杂的一种方式,将每种功能封装,诚然这样的代码复用性会很高,当作模板可以,但是在赛场上的时候,我们没有那么多时间去写代码,都是用什么功能再去写什么功能直接在主函数中完成,追求简洁高效。
刷题1
「约瑟夫环」
1 |
|
「小王子双链表」
1 |
|
STL 中的 queue 容器
数据结构基础-队列
实验介绍
我们这门课主要是深入算法,这里所讲的数据结构倾向于实战,大家不要拘泥于具体的写法,而重在学习原理和使用方式,我们所需要的是简洁、实用和快速。这节课主要目标学会两种队列的原理与实现,学会灵活地运用,能够不依赖于模板,可以直接据题目独立写出各类队列。
经典的数据结构通常采用 C 或 C++ 模板类进行编写,非常不适合竞赛使用,代码复用性高但是浪费了书写时间。竞赛追求效率、AC 和简洁。本节课程,我们主要讲解基本数据结构的队列这一部分,虽然这一部分相对简单但非常重要。
知识点
- 普通队列实现原理与应用
- 循环队列实现原理与应用
为什么使用队列
我们之前已经学过数组和链表,相信对数据的存储方式也有了新的认知,但是数据的组织方式远不止一种,我们今天要讲一种数据组织方式,常用于特殊题目的模拟中。在后续相对高级的算法中,队列将是一种不可或缺的工具,单独使用次数可能不多,但是在其他算法的实现中,不借助队列的逻辑可能会导致一些算法的实现变得复杂。
什么是队列
如果说链表和顺序表是对数据的存取位置的组织方式,那么队列就是一种对于存取方式限制的组织方式。换一种方式描述的话就是,队列既可以采用链表来表示,也可以采用数组(线性表)来表示,我们限制的是对于存放数据的存取方式。
似乎定义是有些晦涩难懂,我们来用图来介绍一下队列,什么是队列。队列如其名,就是按照队列的方式来存取,什么是队列呢,我们举一张打饭的图作为例子。
很显然我们对数据的组织也是以这种方式进行的。当然数据存储方式还是有两种,一种是顺序存储,一种是链式存储。
- 顺序存储
- 链式存储
思考一下:
为什么链式存储的方式的队列首尾指针与链表头尾刚好相反,是什么原因呢?
其实我们知道链表的表头是用来插入数据的,表尾处的数据才是最先插入的,先入先出原则,所以表尾出的数据最先出列,也就是队列的头啦!听到这里,可能有人迷糊了,什么头什么尾的?链表是数据存储的组织方式,他只是决定了数据在内存中怎么存储,而队列是说我们是按照什么顺序存储。可以理解为一群人排队,队列告诉他们先来的先吃饭,后来的得排队,而链表或顺序表是说,你可以站着排队蹲着排队等等。
我们再复习一下单链表,上一节中我们已经学习过这张图:
我们这节课不讲链式存储的队列,只用掌握顺序存储的队列,后边的课程中会讲解 C++ 的 STL、Java 的实列和 Python 的 Queue 包,大家到时候就不用再自己写这些数据结构了,这节课我们主要理解原理即可。
队列初体验
通过上面的介绍,大家已经基本了解了队列的原理,下面我们用一个题目来体验如何使用“队列”。
银行排队问题,CLZ 银行只有两个接待窗口,VIP 窗口和普通窗口,VIP 用户进入 VIP 用户窗口,剩下的进入普通窗口排队。
现在有以下输入:
1 | 第一行 M 次操作(M<1000) |
我们先分析一下这道题目的思路:
- 第一步,创建两个队列,以及两个队列的首尾指针
1 | V队列 |
- 第二步,我们要写入队函数:
- 按照队列的定义使用尾指针模拟即可
- 还要设置 Type 位来表示是哪一个队列
1 | in(Name ,type) |
- 第三步,我们要写出队函数:
- 按照队列的定义使用头指针模拟即可
- 仍需设置 Type 位来表示是哪一个队列
1 | out(type) |
- 第四步,写出获取队头元素的代码,队列我们只关心谁排在第一个
- 按照队列的定义使用头指针模拟即可
- 仍需设置 Type 位来表示是哪一个队列
1 | getHead(type) |
- 第五步:主函数代码
1 | 输入M |
给大家演示一下样例,大家是不是觉得非常简单。
队列
相信大家已经都学会了,开始偷笑这节课比上节课简单多了,那现在我们正式开始讲解相关的定义和知识了。
队列的逻辑结构
- 队列:只允许在一端进行插入操作,而另一端进行删除操作的线性表。
- 空队列:不含任何数据元素的队列。
- 允许插入(也称入队、进队)的一端称为队尾,允许删除(也称出队)的一端称为队头。
- 队列的操作特性:先进先出(FIFO),后入后出(LILO)。
时间复杂度
- getHead() 查找操作时间复杂度为 O(1)
- in() 入队操作时间复杂度为 O(1)
- out() 出队操作时间复杂度为 O(1)
题目解析
分析完了基本思路,也了解了相关的知识,下面我们尝试动手解决一下 CLZ 银行的问题,如果已经提前写完代码了,大家可以跟着下面的解题步骤,对一下答案。
- 第一步
首先我们要先建存放队列数据结构,我们这里采用顺序表,因为主要存放的数据是名字,也就是常说的字符串,我们可以按照如下方式,进行构建:
1 | String Vqueue[1005]; //V队列 |
你会发现,这和数组很像。对,我们确实采用线性表进行存放的,看起来很简单,但是原理是比较复杂的。
- 第二步
我们要写入队函数:
- 按照队列的定义使用尾指针模拟即可;
- 还需要设置 Type 位来表示是哪一个队列。
1 | void in(string name,string type) |
- 第三步
我们要写出队函数:
- 按照队列的定义使用头指针模拟即可;
- 仍需设置 Type 位来表示是哪一个队列
1 | bool out(string type) |
- 第四步
写出获取队头元素的代码,队列我们只需要关心谁排在第一个:
- 按照队列的定义使用头指针模拟即可;
- 仍需设置 Type 位来表示是哪一个队列。
1 | string getHead(string type) |
- 第五步 主函数代码:
1 | int main() |
完整代码
下面我们将会给出本题三种语言实现的完整代码。
C++ 写法
1 |
|
运行结果如下图所示:
Python 写法
Vqueue = []
Vhead = 0
Vtail = 0
Nqueue = []
Nhead = 0
Ntail = 0
def inque(name, type):
global Vhead, Vtail, Nhead, Ntail,Vqueue ,Nqueue
if (type == ‘V’):
Vqueue.append(name)
Vtail += 1
else:
Nqueue.append(name)
Ntail += 1
# print(Vqueue)
def getHead(type):
global Vhead, Vtail, Nhead, Ntail,Vqueue ,Nqueue
if (type == ‘V’):
# print(Vhead)
return Vqueue[Vhead]
else:
# print(Nhead)
return Nqueue[Nhead]
def outque(type):
global Vhead, Vtail, Nhead, Ntail,Vqueue ,Nqueue
if (type == ‘V’):
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">if</span> (Vhead == Vtail):
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">return</span> <span class="hljs-literal" style="box-sizing: border-box; color: rgb(174, 129, 255);">None</span>
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">else</span>:
s = getHead(<span class="hljs-built_in" style="box-sizing: border-box; color: rgb(230, 219, 116);">type</span>)
Vhead += <span class="hljs-number" style="box-sizing: border-box; color: rgb(174, 129, 255);">1</span>
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">return</span> s
else:
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">if</span> (Nhead == Ntail):
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">return</span> <span class="hljs-literal" style="box-sizing: border-box; color: rgb(174, 129, 255);">None</span>
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">else</span>:
s= getHead(<span class="hljs-built_in" style="box-sizing: border-box; color: rgb(230, 219, 116);">type</span>)
Nhead += <span class="hljs-number" style="box-sizing: border-box; color: rgb(174, 129, 255);">1</span>
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">return</span> s
if name == ‘main’:
M = 0
M = int(input())
while M > 0:
M -= 1
op = input().split()
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(117, 113, 94);"># print(op[0])</span>
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">if</span> op[<span class="hljs-number" style="box-sizing: border-box; color: rgb(174, 129, 255);">0</span>] == <span class="hljs-string" style="box-sizing: border-box; color: rgb(230, 219, 116);">'IN'</span>:
inque(op[<span class="hljs-number" style="box-sizing: border-box; color: rgb(174, 129, 255);">1</span>], op[<span class="hljs-number" style="box-sizing: border-box; color: rgb(174, 129, 255);">2</span>])
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(117, 113, 94);"># print('in')</span>
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">else</span>:
outque(op[<span class="hljs-number" style="box-sizing: border-box; color: rgb(174, 129, 255);">1</span>])
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(117, 113, 94);"># print('out')</span>
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(117, 113, 94);"># print("VVVVV",Vqueue)</span>
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(117, 113, 94);"># print("NNNN",Nqueue)</span>
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(117, 113, 94);"># print(M)</span>
s = outque(‘V’)
while s!=None:
print(s)
s = outque(‘V’)
s = outque(‘N’)
while s != None:
print(s)
s = outque(‘N’)

运行结果如下图所示:
Java 写法
import java.util.Scanner;
public class Main {
static String Vqueue[] = new String[1000]; // V队列
static int Vhead = 0; // 首指针
static int Vtail = 0; // 尾指针
static String Nqueue[] = new String[1000]; // N队列
static int Nhead = 0; // 首指针
static int Ntail = 0; // 尾指针
static void in(String name, String type) {
if (type.contains( “V”)) {
Vqueue[Vtail] = name;
Vtail++;
} else {
Nqueue[Ntail] = name;
Ntail++;
}
}
static boolean out(String type) {
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">if</span> (type.contains( <span class="hljs-string" style="box-sizing: border-box; color: rgb(230, 219, 116);">"V"</span>)) {
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">if</span> (Vhead == Vtail) {
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(117, 113, 94);">// 队伍没有人不能在出队了。</span>
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">return</span> <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">false</span>;
} <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">else</span> {
Vhead++;<span class="hljs-comment" style="box-sizing: border-box; color: rgb(117, 113, 94);">// head前的数据都是无效数据,无需删除,逻辑明确即可。</span>
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">return</span> <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">true</span>;
}
} <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">else</span> {
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">if</span> (Nhead == Ntail) {
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(117, 113, 94);">// 队伍没有人不能在出队了。</span>
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">return</span> <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">false</span>;
} <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">else</span> {
Nhead++;<span class="hljs-comment" style="box-sizing: border-box; color: rgb(117, 113, 94);">// head前的数据都是无效数据,无需删除,逻辑明确即可。</span>
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">return</span> <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">true</span>;
}
}
}
static String getHead(String type) {
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">if</span> (type.contains( <span class="hljs-string" style="box-sizing: border-box; color: rgb(230, 219, 116);">"V"</span>)) {
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">return</span> Vqueue[Vhead];
} <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">else</span> {
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">return</span> Nqueue[Nhead];
}
}
public static void main(String[] args) {
int M;
Scanner in=new Scanner(System.in);
M=in.nextInt();
while(M>0) //
{
M–;
String op,name,type;
op=in.next();
// System.out.println(“op”+op);
if(op.contains(“IN”))
{
name=in.next();
type=in.next();
in(name,type);
// System.out.println(“name:”+name+“type:”+type);
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(117, 113, 94);">// System.out.println(Vqueue);</span>
}
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">else</span>
{
type=in.next();
out(type);
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(117, 113, 94);">// System.out.println("type"+type);</span>
}
}
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(117, 113, 94);">// System.out.println(Nhead);</span>
String s=getHead(<span class="hljs-string" style="box-sizing: border-box; color: rgb(230, 219, 116);">"V"</span>);
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">while</span>(out(<span class="hljs-string" style="box-sizing: border-box; color: rgb(230, 219, 116);">"V"</span>))
{
System.out.println(s);
s=getHead(<span class="hljs-string" style="box-sizing: border-box; color: rgb(230, 219, 116);">"V"</span>);
}
s=getHead(<span class="hljs-string" style="box-sizing: border-box; color: rgb(230, 219, 116);">"N"</span>);
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">while</span>(out(<span class="hljs-string" style="box-sizing: border-box; color: rgb(230, 219, 116);">"N"</span>))
{
System.out.println(s);
s=getHead(<span class="hljs-string" style="box-sizing: border-box; color: rgb(230, 219, 116);">"N"</span>);
}
}
}

运行结果如下图所示:
以上是带有顺序表结构的队列,相应的还有链表所对应的序列,有兴趣的同学可以自行查阅资料。在比赛时我们常用 STL 中的 queue 容器,很少会去自己单独定义和使用队列。
这一节我们主要是学习原理和如何使用,在掌握原理之后,其实无论是什么样的队列都是可以自己设计出来的,同学们也可以自己尝试使用上一章链表的知识设计一个队列并完成上面的题目。
使用循环队列解决 CLZ 银行的问题
我们上面讲解了队列的定义及使用,会发现一个很大的问题,就是“随着不断地入队出队,我们的队列的容量会不断降低”,如下图所示:
可以看到,队头和队尾是单调向后移动的,因为之前我们的容量足够大所以不需要判定是否队列满,但是当所需入队的数据很大时,我们空间一定时,那么普通队列对空间的低效率利用就显得很蹩脚,所以提出了循环队列的方式。(链式队列就没有这个缺点,所以后续课程中我们讲的容器或者类都采用链式队列的方式实现。
下面我们用一张动图来展示普通队列在不断出队入队时,空间利用效率低这一缺点:
可以看到经过出队后,图中打叉位置的元素已经访问不到,存储单元也浪费掉了,为了很好的解决这个问题,将会使用循环队列。
循环队列的组成
逻辑上是首尾相连的数组,可是在数组中其实不存在这样的数组,所以在物理实现上是不存在的,那么我们需要怎么做呢?
其实对于不存在物理上实现的循环结构,我们可以用软件方法实现(采用求模方式):
-
tail=(tail+1)% MAXSIZE
-
head=(head+1) % MAZSIZE
出现了几个关于循环队列所必须解决的问题:
-
如何判断循环队列队为空?
队空:
head == tail
跟之前一样。 -
如何判断循环队列队为满
队满:(tail+1) mod QueueSize==head
-
如何获得队列中的元素数量
1
length=(tail-head+QueueSize)%Queuesize
由于顺序存储队列必须预先确定一个固定的长度,所以存在存储元素个数的限制和空间浪费的问题。
现在让我们尝试使用循环队列完成上面 CLZ 银行 的题目。
思路分析
思路跟之前的解法一样,假如现在队列中最多同时存在 10000 个元素,需要我们采用循环队列进行解答。
先要说明的是,我们在 Python 中的是是采用 List 实现的,所以它的空间可以近似的看作无限的。那么 Python 的代码中只需要加一个删除即可达最大利用率,我们利用 C++ 和 Java 完成题目时,采用循环队列去解决,Python 采用优化写法。
- 第一步,我们先编写队列定义的代码
1 | int QueueSize=10005; |
- 第二步,进行编写入队代码
我们先写一个普通循环队列的入队代码。如下所示:
1 | string queue[QueueSize]; |
然后我们结合题目改写我们刚刚写的入队代码,如下所示:
1 | bool in(string name,string type) |
- 第三步,进行出队函数的编写
同样,我们还是先写普通循环队列的代码:
1 | bool out(){ |
然后结合题目,改写上面的代码:
1 | bool out(string type) |
- 第四步,编写获取队头元素的代码
照例,我们还是先写普通循环队列的代码:
1 | string getHead() |
然后结合题目改写代码:
1 | string getHead(string type) |
好了,基本的代码我们已经完成了,大家试试先不看后面的完整代码答案,尝试自己动手把写好的代码组织起来。
完整代码编写
C++解法
1 |
|
Java 解法
import java.util.Scanner;
public class Main {
static int QueueSize=10005;
static String Vqueue[] = new String[QueueSize]; // V队列
static int Vhead = 0; // 首指针
static int Vtail = 0; // 尾指针
static String Nqueue[] = new String[QueueSize]; // N队列
static int Nhead = 0; // 首指针
static int Ntail = 0; // 尾指针
static boolean in(String name, String type) {
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">if</span>(type.contains(<span class="hljs-string" style="box-sizing: border-box; color: rgb(230, 219, 116);">"V"</span>)){
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">if</span> ((Vtail+<span class="hljs-number" style="box-sizing: border-box; color: rgb(174, 129, 255);">1</span>) % QueueSize ==Vhead) <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">return</span> <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">false</span>;
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(117, 113, 94);">//队列以达到容量上限满了,所以不能再插入了返回错误;</span>
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">else</span>{
Vtail=(Vtail+<span class="hljs-number" style="box-sizing: border-box; color: rgb(174, 129, 255);">1</span>) % QueueSize;
Vqueue[Vtail]=name;
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">return</span> <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">true</span>;
}
}
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">else</span>
{
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">if</span> ((Ntail+<span class="hljs-number" style="box-sizing: border-box; color: rgb(174, 129, 255);">1</span>) % QueueSize ==Nhead) <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">return</span> <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">false</span>;
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(117, 113, 94);">//队列以达到容量上限满了,所以不能再插入了返回错误;</span>
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">else</span>{
Ntail=(Ntail+<span class="hljs-number" style="box-sizing: border-box; color: rgb(174, 129, 255);">1</span>) % QueueSize;
Nqueue[Ntail]=name;
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">return</span> <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">true</span>;
}
}
}
static boolean out(String type) {
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">if</span>(type.contains(<span class="hljs-string" style="box-sizing: border-box; color: rgb(230, 219, 116);">"V"</span>)){
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">if</span> (Vtail==Vhead) <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">return</span> <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">false</span>;
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(117, 113, 94);">//空队列不能出队列了</span>
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">else</span> {
Vhead=(Vhead+<span class="hljs-number" style="box-sizing: border-box; color: rgb(174, 129, 255);">1</span>) % QueueSize;
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(117, 113, 94);">//不是空队列,但是因为是循环的,如果到了数组末尾也要调整到前面去。</span>
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">return</span> <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">true</span>;
}
}
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">else</span>
{
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">if</span> (Ntail==Nhead) <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">return</span> <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">false</span>;
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(117, 113, 94);">//空队列不能出队列了</span>
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">else</span> {
Nhead=(Nhead+<span class="hljs-number" style="box-sizing: border-box; color: rgb(174, 129, 255);">1</span>) % QueueSize;
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(117, 113, 94);">//不是空队列,但是因为是循环的,如果到了数组末尾也要调整到前面去。</span>
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">return</span> <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">true</span>;
}
}
}
static String getHead(String type) {
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">if</span>(type.contains(<span class="hljs-string" style="box-sizing: border-box; color: rgb(230, 219, 116);">"V"</span>)){
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">if</span> (Vtail==Vhead) <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">return</span> <span class="hljs-string" style="box-sizing: border-box; color: rgb(230, 219, 116);">""</span>;<span class="hljs-comment" style="box-sizing: border-box; color: rgb(117, 113, 94);">//空队列返回空</span>
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">else</span> {
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">return</span> Vqueue[Vhead+<span class="hljs-number" style="box-sizing: border-box; color: rgb(174, 129, 255);">1</span>];
}
}
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">else</span>
{
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">if</span> (Ntail==Nhead) <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">return</span> <span class="hljs-string" style="box-sizing: border-box; color: rgb(230, 219, 116);">""</span>;<span class="hljs-comment" style="box-sizing: border-box; color: rgb(117, 113, 94);">//空队列返回空</span>
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">else</span> {
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">return</span> Nqueue[Nhead+<span class="hljs-number" style="box-sizing: border-box; color: rgb(174, 129, 255);">1</span>];
}
}
}
public static void main(String[] args) {
int M;
Scanner in=new Scanner(System.in);
M=in.nextInt();
while(M>0) //
{
M–;
String op,name,type;
op=in.next();
// System.out.println(“op”+op);
if(op.contains(“IN”))
{
name=in.next();
type=in.next();
in(name,type);
// System.out.println(“name:”+name+“type:”+type);
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(117, 113, 94);">// System.out.println(Vqueue);</span>
}
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">else</span>
{
type=in.next();
out(type);
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(117, 113, 94);">// System.out.println("type"+type);</span>
}
}
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(117, 113, 94);">// System.out.println(Nhead);</span>
String s=getHead(<span class="hljs-string" style="box-sizing: border-box; color: rgb(230, 219, 116);">"V"</span>);
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">while</span>(out(<span class="hljs-string" style="box-sizing: border-box; color: rgb(230, 219, 116);">"V"</span>))
{
System.out.println(s);
s=getHead(<span class="hljs-string" style="box-sizing: border-box; color: rgb(230, 219, 116);">"V"</span>);
}
s=getHead(<span class="hljs-string" style="box-sizing: border-box; color: rgb(230, 219, 116);">"N"</span>);
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">while</span>(out(<span class="hljs-string" style="box-sizing: border-box; color: rgb(230, 219, 116);">"N"</span>))
{
System.out.println(s);
s=getHead(<span class="hljs-string" style="box-sizing: border-box; color: rgb(230, 219, 116);">"N"</span>);
}
}
}

Python 解法
Python 的是在原来基础上进行优化:
Vqueue = []
Nqueue = []
def inque(name, type):
global Vqueue ,Nqueue
if (type == ‘V’):
Vqueue.append(name)
else:
Nqueue.append(name)
def outque(type):
global Vqueue ,Nqueue
if (type == ‘V’):
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">if</span>(<span class="hljs-built_in" style="box-sizing: border-box; color: rgb(230, 219, 116);">len</span>(Vqueue)==<span class="hljs-number" style="box-sizing: border-box; color: rgb(174, 129, 255);">0</span>):
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">return</span> <span class="hljs-literal" style="box-sizing: border-box; color: rgb(174, 129, 255);">None</span>
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">else</span>:
s=Vqueue[<span class="hljs-number" style="box-sizing: border-box; color: rgb(174, 129, 255);">0</span>]
Vqueue.remove(Vqueue[<span class="hljs-number" style="box-sizing: border-box; color: rgb(174, 129, 255);">0</span>])
<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(249, 38, 114);">return</span> s
else:
if (len(Nqueue)==0):
return None
else:
s = Nqueue[0]
Nqueue.remove(Nqueue[0])
return s
if name == ‘main’:
M = 0
M = int(input())
while M > 0:
M -= 1
op = input().split()
# print(op[0])
if op[0] == ‘IN’:
inque(op[1], op[2])
# print(‘in’)
else:
outque(op[1])
# print(‘out’)
# print(“VVVVV”,Vqueue)
# print(“NNNN”,Nqueue)
# print(M)
s = outque(‘V’)
while s!=None:
print(s)
s = outque(‘V’)
s = outque(‘N’)
while s != None:
print(s)
s = outque(‘N’)

关于队列的定义方式,跟链表一样在各种教科书上和网站都有着各个不同版本的定义方式,具体实现都是大同小异。本次课程,我们主要对标大赛,注意把握其中的实现原理,追求更简单高效的解答问题方式。
实验总结
本次实验,我们学习了普通队列和循环队列两种队列的实现方式,了解了队列的原理与基本的实现方式。随着我们课程的深入,我们只需要掌握原理即可,这些工具和数据结构,我们都不会再自己定义使用,而是直接使用各类编程语言已经写好的库模板。
另外,大家从我们上面写过的代码可以看出,其中设置了很多输出,用于调试代码,满是代码调试的痕迹。其实每个人写代码都不是一蹴而就的,在后续的学习中,希望大家在觉得复杂困难的部分,要想办法解决,不要因为困难就放弃。
刷题2
「CLZ 的银行普通队列」
1 |
|
「CLZ 的银行循环队列」
1 |
|
stack 堆栈
数据结构基础-栈
实验介绍
我们这门课所讲的数据结构倾向于实战,大家不要拘泥于具体的写法,而重在学习原理,和使用方式,我们所需要的是简洁、实用和快速。本次实验主要目标是学会栈的原理与实现,学会灵活地运用,能够不依赖于模板根据题目独立写出各类栈。
我们本次讲解数据结构栈这一部分,这一部分比队列要少很多,但是会在后面的搜索等算法中使用,即使这一部分简单,但也是同等重要。还是要提及的一点,不管你在你的数据结构课上怎么背的你的代码,在我们这门课,我们不再追求复用性,我们要的是你学会原理,追求效率。
知识点
- 栈的实现原理与应用
为什么使用栈
我们在这之前已经学过了部分数据结构,相信对数据的存储方式也有了新的认知,但是数据的组织方式我们只学习了队列这一种,我们今天要讲另外一种数据组织方式,同样常用于特殊题目的模拟中,诚然在后续相对高级的算法中,栈是一种不可或缺的工具,单独使用可能不会太多次数,当然这一实验会比队列简单,还是希望大家能够好好学习。
什么是栈
我们之前学过了队列这一种对于存取方式的限制的组织方式,我们今天要讲另一种,同样栈既可以采用链表来表示,也可以采用数组(顺序表)来表示,我们限制的是对于存放数据的存取方式。
如果觉得看不懂定义,我们来用图来介绍一下栈,什么是栈,栈如其名,就是按照栈的方式来存取,什么是栈呢,我们举一张糖葫芦的图作为例子。
很显然我们对数据的组织也是以这种方式进行的。当然数据存储方式还是有两种,一种是顺序存储,一种是链式存储。而我们常用的存储方式还是顺序表因为方便简单,在语言自带的程序中用的是链式存储,但是实现相对复杂,我们后期课程中会教大家直接使用,所以我们没必要学会去实现,有余力的同学可以自行实现,使用第一次课的知识加上本次可得知识,即可轻松实现,相应的他也有优点就是节省空间。
- 顺序存储
- 链式存储
思考一下:
为什么链式存储的方式的栈栈顶指针与队列队头的指针相反,是什么原因呢?
其实我们知道链表的表头是用来插入数据的,表头处的数据才是最后插入的,先入后出原则,所以表头处的数据最先出栈,也就是栈的顶啦!听到这里,有人迷糊了,什么头什么尾的,队列跟栈傻傻分不清… 链表是数据存储的组织方式,他只是决定了数据在内存中怎么存储,而栈和队列是说我们是按照什么方式存储。栈可以理解为整理衣服,先放进箱子里的,要想拿出来得把后放进箱子里的衣服先拿出来。而链表或顺序表是说,我究竟是放进了箱子还是放进了衣柜还是放进了异度空间。
我们再复习一下单链表,就放个图给你们吧,省的你们回上一讲去翻。
当然大家不会也没有关系,因为我们这节课不讲链式存储的栈,顺序存储的栈足够用,而且后边的课程中会讲 C++ 的 STL、Java 的实列和 Python 的 Stack 包,大家到时候就不用在自己写这些数据结构了,这节课我们主要是理解原理即可。
栈的初体验
通过上面的介绍,大家已经基本了解了栈的原理,关于栈的使用我们也要必须学会,我们用一个题目来引入。
小邋遢的衣橱
小邋遢 MS.Jinlin 是个爱打扮的公主,他有很多晚礼服如"LALA" “NIHAOMA”、“WOBUHAO”、"NIHAOBUHAO"等众多衣服,可是由于衣服太多他要把它们装进箱子,但是作为公主,肯定是会突发奇想觉得哪件衣服好看,就把他拿了出来,当然那件衣服上面的衣服也被拿出来了,而且会弄乱了,小邋遢在经过几次的叠衣服和取衣服后,他想知道箱子里最上面的衣服是哪一件,如果箱子为空的话,就告诉她 Empty ,如果有多件一样的衣服,肯定是取走最上面的那一件啦。
输入:
1 | 第 1 行,输入N,代表共计进行了几次操作 |
现在有以下样例输入:
样例 1:
1 | 输入: |
样例 2:
1 | 输入: |
先说思路,答案在后边公布。
第一步:
创建一个栈,以及一个栈的栈顶指针
1 | 顺序栈 栈 1 |
第二步:
我们要声明并定义入栈函数:
- 按照栈的定义使用栈顶指针模拟即可
- 需要传入一个参数来表示放什么数据
1 | in(Name) |
第三步:
我们声明并定义判空函数:
通过栈顶指针大小即可判断。
1 | isEmpty() |
第四步:
我们要声明并定义出栈函数:
- 按照栈的定义使用栈顶指针模拟即可
- 返回一个数据表示出栈元素。
1 | out() |
第五步:
我们声明并定义取栈顶函数:
- 只需要将栈顶元素取出即可
- 先判断是否为空
1 | string getTop() |
第六步:
主函数代码:
1 | 输入N |
给大家演示一下样例,大家是不是觉得非常简单。
栈
相信大家已经都学会了,开始偷笑这节课比上节课简单多了,那现在我开始给大家讲以下正式的定义和知识了。
栈的逻辑结构
- 栈:只允许在一端进行插入、删除操作的线性表。
- 空栈:不含任何数据元素的栈。
- 允许插入(也称进栈、压栈、入栈)、删除(也称出栈)的一端称为栈顶。
时间复杂度
- isEmpty() 查找操作时间复杂度为 O(1)
- in() 入队操作时间复杂度为 O(1)
- out() 出队操作时间复杂度为 O(1)
题目解析
学完了知识我们要亲自动手解决一下小邋遢的衣橱的问题了,提前写完代码的同学们也要对对答案了。
第一步:
首先我们要先建存放栈数据结构,我们这里采用顺序表。 因为主要存放数据为名字即字符串,我们可以如下构建:
1 | String stack[1005]; //栈 |
你会发现,这好像就是数组,又好像长得像是队列,他就是这么简单,难的是原理!
第二步:
我们要声明并定义入栈函数:
- 按照栈的定义使用栈顶指针模拟即可
- 需要传入一个参数来表示放什么数据
1 | bool in(string name) |
第三步:
我们声明并定义判空函数:
通过栈顶指针大小即可判断。
1 | bool isEmpty(){ |
第四步:
我们要声明并定义出栈函数:
- 按照栈的定义使用栈顶指针模拟即可
- 返回一个数据表示出栈元素。
1 | bool out() |
第五步:
我们声明并定义取栈顶函数:
- 只需要将栈顶元素取出即可
- 先判断是否为空
1 | string getTop() |
第六步:
主函数代码:
1 | int main () |
完整代码如下:
C++写法:
1 |
|
以上为带有顺序表结构的栈,相应的还有链表所对应的栈,但是因为实现复杂,如果在比赛中使用这种解法,会花费更多的时间,失去了我们提高解题效率的初衷,所以我们就不再赘述了,有兴趣的同学可以自行查阅资料。
下面我们就来介绍如何使用 C++、Java、Pyhton 中定义好的内置栈模版进行解答,从而提高解题效率,实现更加快捷方便的解题。
C++ 的内置栈模板
我们先看一下 C++ 中栈的定义及相应的函数内容.
LIFO stack 堆栈,它是一种容器适配器,专门设计用于在 LIFO 上下文(后进先出)中操作,其中元素仅从容器的一端插入和提取。
stack 被实现为容器适配器 它们是使用特定容器类的封装对象作为其类底层容器的 ,提供一组特定的成员函数来访问其元素。元素推入 / 弹出 从 的 “后面” 特定容器 ,这被称为 的顶部堆栈。
底层容器可以是任何标准容器类模板或一些其他专门设计的容器类。
容器应支持以下操作:
以上引用自 C++的 API,当然现在大家理解起来可能有些困难,不用担心,下面我们将会教大家如何定义,并且如何调用相关的函数。
在 C++ 的 stack 模板定义了如下操作:
-
top():
返回一个栈顶元素的引用,类型为 T&。如果栈为空,返回值未定义。
-
push(const T& obj):
可以将对象副本压入栈顶。这是通过调用底层容器的 push_back() 函数完成的。
-
push(T&& obj):
以移动对象的方式将对象压入栈顶。这是通过调用底层容器的有右值引用参数的 push_back() 函数完成的。
-
pop():
弹出栈顶元素。
-
size():
返回栈中元素的个数。
大家看的有点迷糊也没有问题,看名字的话大家也都能猜出是什么意思,在上文中,我也都给大家讲了,所以大家对照着看一下。接下来我们采用 C++ 定义好的模板类给大家改写上面的 C++程序,让大家好好学习一下。
第一步:
引入模板类,并定义声明一个栈类
1 |
|
第二步:
我们要声明并定义入栈函数:
- 按照栈的定义使用栈顶指针模拟即可
- 需要传入一个参数来表示放什么数据
这里我们 C++ 的 stack 模版中已经为我们声明并定义好了,所以我们不需要写,这一步可以省略。
第三步:
我们声明并定义判空函数:
这里我们 C++ 的 stack 模版中已经为我们声明并定义好了,所以我们不需要写,这一步可以省略。
第四步:
需要要声明并定义出栈函数:
- 按照栈的定义使用栈顶指针模拟即可
- 返回一个数据表示出栈元素。
这里我们 C++ 的 stack 模版中已经为我们声明并定义好了,所以我们不需要写,这一步可以省略。
第五步:
我们声明并定义取栈顶函数:
- 只需要将栈顶元素取出即可
- 先判断是否为空
这里我们 C++ 的 stack 模版中已经为我们声明并定义好了,所以我们不需要写,这一步可以省略。
第六步:
主函数代码:
1 | int main () |
完整代码如下,你会发现十分简单,就是直接拿来用的,非常方便,但是建议大家也还是要学会自己写,这样使用起来会更加熟练。
1 |
|
Java 的内置栈类
我们先看一下 Java 中栈的定义及相应的函数.
- 栈是 Vector 的一个子类,它实现了一个标准的后进先出的栈,至于什么是 Vector,大家可以理解为能力超强的数组,在后面的课程中,我们会进行讲解。
- 堆栈定义了默认构造函数,用来创建一个空栈。
大家可能理解起来有困难,不必担心,咱们现阶段知道如何定义,并且如何调用函数后,之后在不断的实践中,就会慢慢理解了。
在 Java 的 stack 模板定义了如下操作流程:
-
push():
执行 push 时(即,将元素推入栈中),是通过将元素追加的数组的末尾中。
-
peek():
执行 peek 时(即,取出栈顶元素,不执行删除),是返回数组末尾的元素。
-
pop():
执行 pop 时(即,取出栈顶元素,并将该元素从栈中删除),是取出数组末尾的元素,然后将该元素从数组中删除。
-
empty():
继承于 Vector,返回是否为空
-
size():
继承 Vector,返回元素的个数。
那么若使用 Java 的内置栈类,我们的实现流程会有什么不同呢:
我们只需引入模板类,并定义声明一个栈类:
1 | import java.util.Scanner; |
主函数代码:
1 | public static void main(String[] args) |
可以看到,使用 Java 的内置栈类,可以帮我们省略以下流程:
- 声明并定义入栈函数
- 声明并定义入判空函数
- 声明并定义出栈函数
- 声明并定义出取栈顶函数
使用起来非常方便,我们再看一下整体的代码。
1 | import java.util.Scanner; |
Python 的实现
由于 Python 没有现成的栈的定义,要想使用,我们只能进行自己模拟,模拟方法大家可以使用我上面使用的方法,也可以看一下我下面讲的高级点的方法,声明并定义一个栈类的方法,推荐使用下面的方法,上面的代码还是主要讲理论使用。
第一步:
声明一个类,并设置一个类型为 list 的元素来保存数据。
1 | class MyStack: |
第二步:
我们要声明并定义入栈函数:
1 | def push(self, elem): |
第三步:
我们声明并定义判空函数:
1 | def is_empty(self): |
第四步:
我们要声明并定义出栈函数:
1 | def pop(self): |
第五步:
我们声明并定义取栈顶函数:
1 | def top(self): |
第六步:
主函数代码:
1 | if __name__=='__main__': |
完整的代码如下:
1 | class MyStack: |
实验总结
关于栈的定义方式,跟前面两讲一样在各种教科书上和网站都有着各个不同版本的定义方式,我们主要是学习该数据结构的实现原理,虽然实现可能千奇百怪但是我们理解原理就好,对于实现我们还是要追求简单高效即可。
本次实验,我们学习了栈的实现方式,了解了栈的原理与基本的实现方式,学有余力的同学们可以使用链表自己声明并定义链式栈,但是我们后续用不到,可以当作对自己编码能力的提升。随着我们课程的深入这些工具数据结构我们都不会再自己定义使用了,各类编程语言都给了现成的库模板等,我们都可以拿来直接而用,非常方便,这里给大家讲了,使用各语言的特性简化了自己写的代码,非常方便。
刷题3
「小邋遢的衣橱」
1 | #include<iostream> |
选取最接近表长且小于等于表长的最大素数
b 常用 131,h 常用 1e9+7=999983
C++ 中有一个 UnorderedMap,可以方便我们的解题过程;
数据结构基础-散列表(Hash)
实验介绍
我们本次实验主要目标是学会散列表(hash 算法)的原理与实现,学会灵活的运用,能够不依赖于模板根据题目独立写出各类散列表。数据结构 Hash 属于查找算法中的一部分,在比赛中通常也会占据一定的比例,相对较难也比较重要,大家一定要认真学习哦。
知识点
- Hash 的概念
- 构造方法
- 冲突处理
为什么使用哈希表
我们上面所提到的查找算法,简单来说,就是判断现有数据集合中是否有这个元素,或者是否有满足条件的元素。
其中的 Hash 算法则可以帮助我们判断是否有这个元素,虽然功能简单,但是其 O(1) 时间复杂度是具有高性能的。通过在记录的存储地址和它的关键码之间建立一个确定的对应关系。这样,不经过比较,一次读取就能得到所查元素的查找方法。相比普通的查找算法来说,仅仅在比较的环节,就会大大减少查找或映射所需要的时间。
什么是哈希表(散列表)
我们采用散列技术将记录存储在一块连续的存储空间中,这块连续的存储空间即称为散列表。下面用一张图给大家展示一下散列表的实现过程:
如果还是不太明白的话,我们可以理解为数学函数,Y=F(X),X 为自变量也就是这里的 Key, F( ) 对应图中的 H( ),也就是一个映射关系,Y 因变量也就是对应的值的 存放位置,此处一定要注意哦。
此处让我们思考一下:
-
散列技术仅仅是一种查找技术吗?
应该说,散列既是一种查找技术,也是一种存储技术。
-
散列是一种完整的存储结构吗?
散列只是通过记录的关键码定位该记录,没有完整地表达记录之间的逻辑关系,即通过关键码能推出 Key 值,但是通过关键码对应的值(即位置处的值)不能推出关键码,所以散列存储的关键码和值之间并不对称,因此散列主要是面向查找的存储结构。
散列表的初体验
通过上面的介绍,大家已经基本了解了散列表的原理。下面我们就来学习一下关于散列表的使用方式,下面我们用一个题目来引入。
弗里的语言
小发明家弗里想创造一种新的语言,众所周知,发明一门语言是非常困难的,首先你就要克服一个困难就是,有大量的单词需要处理,现在弗里求助你帮他写一款程序,判断是否出现重复的两个单词。
要求:有重复的单词,就输出重复单词,没有重复单词,就输出 NO,多个重复单词输出最先出现的。
输入输出如下面示例所示:
首先输入:
1 | 第 1 行,输入 N,代表共计创造了多少个单词 |
现在有以下样例输入。
样例 1:
1 | 输入: |
样例 2:
1 | 输入: |
下面我们来分析一下解题思路,请大家跟着下面的思路一步一步实现,然后再对比后面给出的答案。
第一步,首先我们需要创建一个散列表和一个公共溢出区。
1 | 散列表 |
即使你现在不知道什么是散列表和溢出区,没关系!我们后边会做详细的讲解。
第二步,需要定义插入散列表函数。
- 按照散列表的映射方式设计即可
- 需要传入一个参数来表示放什么数据
1 | in(Name) |
第三步:定义查询函数。
1 | isAt() |
4. 第四步,定义散列表映射函数。
此处我们采用除留余数法即可,不了解这个方法的同学别担心,后面在写解题代码的时候,我会具体为大家介绍。
1 | int out(string s) |
第五步,编写主函数代码。
1 | 输入 N |
大致的代码逻辑就是这样,相信大家已经都学会了。可能有的小伙伴已经在嘀咕了“这有什么难的”,先别急,咱们继续往下看。
这道题的代码思路其实并不难,但是代码应该如何来写呢,大家是否还摸不着头脑?在比赛中我们为了追求高效率,必须熟知咱们所使用到的每一个函数的优缺点,做到“扬长避短”,所以在写代码前,我们先来聊聊散列表的优缺点。前面咱们已经了解到了,散列表具有高性能,查找效率高等优点,下面就主要了解一下它的缺陷。
散列表的缺陷
散列表并不是适用于所有的需求场景,那么哪些情况下不适合使用呢?
-
散列技术一般不适合在允许多个记录有同样关键码的情况下使用。
因为这种情况下,通常会有冲突存在,将会降低查找效率,体现不出散列表查找效率高的优点。
并且如果一定要在这个情况下使用的话,还需要想办法消除冲突,这将花费大量时间,那么就失去了 O(1) 时间复杂度的优势,所以在存在大量的冲突情况下,我们就要弃用散列表。
-
散列方法也不适用于范围查找,比如以下两个情况。
-
查找最大值或者最小值
因为散列表的值是类似函数的,映射函数一个变量只能对应一个值,不知道其他值,也不能查找最大值、最小值,RMQ(区间最值问题)可以采用 ST 算法、树状数组和线段树解决。
-
也不可能找到在某一范围内的记录
比如查找小于 N 的数有多少个,是不能实现的,原因也是映射函数一个变量只能对应一个值,不知道其他值。
散列技术的关键问题
在使用散列表的时候,我们有两个关键的技术问题需要解决:
- 散列函数的设计,如何设计一个简单、均匀、存储利用率高的散列函数?
- 冲突的处理,如何采取合适的处理冲突方法来解决冲突。
如何设计实现散列函数
在构建散列函数时,我们需要秉持两个原则:
- 简单
- 散列函数不应该有很大的计算量,否则会降低查找效率。
- 均匀:
- 函数值要尽量均匀散布在地址空间,这样才能保证存储空间的有效利用并减少冲突。
散列函数实现三种方法
1. 直接定址法。
散列函数是关键码(Key)的映射的线性函数,形如:
H(key) = a * key + bH(key)=a∗key+b
来看一个小案例:
如果关键码的集合已知且为 [11,22,33,66,88,44,99]
H(key) = \frac{1}{11} * key + 0H(key)=111∗key+0
如图:
缺点:
- 我们是看到了这个集合,然后想到他们都是 11 的倍数才想到这 Hash 函数。我们在平常的使用中一般不会提前知道 Key 值集合,所以使用较少。
适用范围:
- 事先知道关键码,关键码集合不大且较为连续而不离散。
2. 除留余数法。
H(key)=key \ mod \ pH(key)=key mod p
来个小例子:
H(key)=key \ mod \ 21H(key)=key mod 21
会发现产生了很多相同的 H(K),这就是发生冲突,因为一个位置只能放一个数,有两个值对应这里一个位置,是不可以的。
这种方法是最常用的方法,这个方法的关键在于如何选取 P,使得利用率较高并且冲突率较低,一般情况下,我们会选取最接近表长且小于等于表长的最大素数。
缺点:
- P 选取不当,会导致冲突率上升。
适用范围:
- 除留余数法是一种最简单、也是最常用的构造散列函数的方法,并且不要求事先知道关键码的分布。
这个方法非常常用,我们后面题目的展开就是使用的这个方法。在大部分的算法实现中也都是选取的这一种方式。
代码实现:
1 | C++ |
3. 数字分析法。
比如我将我的集合全部转化为 16 进制数,根据关键码在各个位上的分布情况,选取分布比较均匀的若干位组成散列地址。或者将 N 位 10 进制数,观察各各位的数字分布,选取分布均匀的散列地址。
举个小例子:
首先我们考虑一位作为散列函数,发现都是很多冲突,选取两位时,百位和十位组合最适宜,分布均匀且没有冲突。
当然,我们说的是这一方法的一个具体实列,既然叫做数字分析法,那么只有对于不同数据的不同分析,才能写出更是适配的 H(x)。
另外还有两种平时使用极少的方法,分别是平方取中法和折叠法,我们就不再做过多的讲解,感兴趣的小伙伴可以在网上自行查找相关的资料了解哦。
冲突的处理方法
-
开散列方法:
open hashing 也称为拉链法,separate chaining 称为链地址法,简单来说,就是由关键码得到的散列地址一旦产生了冲突,就去寻找下一个空的散列地址,并将记录存入。
寻找下一个空的散列地址的方法:
- 线性探测法
当发生冲突时,从冲突位置的下一个位置起,依次寻找空的散列地址。
对于键值 key,设 H(key)=d,闭散列表的长度为 m,则发生冲突时,寻找下一个散列地址的公式为:
Hi=(H(key)+di)\ MOD \ m(di=1,2,… ,m-1)H**i=(H(key)+d**i) MOD m(d**i=1,2,…,m−1)
堆积现象:
在处理冲突的过程中出现的非同义词之间对同一个散列地址争夺的现象。
例子:
Key 集合为 47, 7, 29, 11, 27, 92, 22, 8, 3。
P 值为 11,进行 Hash 映射,采用线性探测法处理冲突。
- 二次探测法
即当发生冲突时,寻找下一个散列地址的公式为:
H_i=(H(key)+d_i)% mH**i=(H(key)+d**i)
其中( d_i=12,-12,22,-22,… ,q2,-q2 且 q≤m/2)其中(d**i=12,-12,22,-22,…,q2,-q2且q≤m/2)
-
随机探测法
当发生冲突时,下一个散列地址的位移量是一个随机数列,即寻找下一个散列地址的公式为:
Hi=(H(key)+round)% mH**i=(H(key)+round)
其中 round 为随机数其中round为随机数
- 再 hash 法
注意:用开放定址法处理冲突得到的散列表叫闭散列表。
-
闭散列方法
closed hashing 也称为开地址方法,open addressing 开放地址法,开放地址法中涵盖了以下两种实现方式;
-
拉链法(链地址法)
将所有散列地址相同的记录即 Key 值相同的项目,坠成一个链表,每个链表的头指针存放位置为 Key 值对应的位置。
举一个小例子:
-
建立公共溢出区
散列表包含基本表和溢出表两部分(通常溢出表和基本表的大小相同),将发生冲突的记录存储在溢出表中。
查找时,如果在基本表里找的到就返回成功,没找到就在溢出区顺序查找,注意这里不再是映射而是顺序查找,放置时也是按照顺序的方式。
-
算法流程
- 假设给定的值为 K,根据所设定的散列函数 h,计算出散列地址 h(K);
- 如果将该地址中的值与 K 比较,若相等则检索成功,跳转到第 5 步;
- 否则,按建表时设定的处理冲突方法查找探查序列的下一个地址,反复执行并检查
- 如果某个地址空间未被占用(查找不成功,可以插入),跳转到第 5 步;
- 如果关键码比较相等(有重复记录,不需要插入)为止 ,跳转到第 5 步;
- 如果探测完整个 hash 表,都没有进行插入或查找失败,跳转到第 5 步;
- end 算法结束。
虽然在解题过程中,如果依据表长质数 h 设置得当,则很少会出现冲突情况,但是基本的解决方法我们也须得掌握,根据笔者的实战经验来看,公共溢出区的方式更加简洁高效率(在冲突次数远小于元素数量时),所以本节实验中,我们主要掌握如何设置公共溢出区的方法。
至此我们已经学完了散列表的相关知识,下面我们结合建立公共溢出区的方式,亲自动手解决一下“弗里的语言”这个问题。
题目解析
第一步,我们需要创建一个散列表和一个公共溢出区:
1 | const long long h=1e8+7; |
第二步,我们要定义散列表映射函数:
我们这里介绍一种在算法竞赛中特别常用的字符串映射成数字的方式。
实现原理:
-
将字符串中的每一个字母都看做是一个数字(例:从 a-z ,视为 1-26 );
-
选取两个合适的互质常数 b 和 h,其中 h 要尽可能的大一点,为了降低冲突的概率。b 常用 131,h 常用 1e9+7,这里我们需要设置公共溢出区所以,我们需要随便找一个 string 数组能开出来的数字,这里选取 999983。
-
定义哈希函数:
处理方式:
- C 代表一个字符串,用 C =c1 c2 c3 c4…cm 表示该字符串,其中 ci 表示从前向后数的第 i 个字符;
- C 当做 b 进制数 来处理,b 是基数;
- 关于对 h 取模,若 b、h 有公因子,那么不同的字符串取余之后的结果发生冲突的几率将大大大增加(冲突:不同的字符串但会有相同的 hash 值)。
举一个例子:
现在有一字符串 S=s_1s_2s_3s_4s_5s1s2s3s4s5
h a s h[ 1 ] = s 1 has**h[1]=s1
h a s h [ 2 ] = s 1 ∗ p + s 2has**h[2]=s1∗p+s2
h a s h [ 3 ] = s 1 ∗ p 2 + s 2 ∗ p + s 3has**h[3]=s1∗p2+s2∗p+s3
h a s h [ 4 ] = s 1 ∗ p 3 + s 2 ∗ p 2 + s 3 ∗ p + s 4has**h[4]=s1∗p3+s2∗p2+s3∗p+s4
h a s h [ 5 ] = s 1 ∗ p 4 + s 2 ∗ p 3 + s 3 ∗ p 2 + s 4 ∗ p + s 5has**h[5]=s1∗p4+s2∗p3+s3∗p2+s4∗p+s5
所以 S 的哈希值为 Hash[5]
实现
1 | const long long h = 999983; |
在比赛按此方法设计 Hash 函数一般不需要设置冲突的公共溢出区,这里我们为了方便讲解,才进行设置,在比赛中我们不用设置溢出区,所以可以设置很大的 h,避免出现冲突。
第三步,我们定义查询函数:
通过散列表顶指针大小即可判断。
1 | bool isAt(string s) |
第四步,定义插入散列表函数:
- 按照散列表的映射方式设计即可;
- 需要传入一个参数来表示放什么数据。
1 | bool in(string s) |
第五步,编写主函数代码:
主函数代码我们有三种定义方式
- 法一
中规中矩定义法,设置 flag 变量用于跳过找到答案后的输入处理。
1 | int main() |
- 法二
由于我们设置的插入函数也具有查询功能,插入成功即为没有重复值,插入失败即为有重复值,我们这里不存在单独查询的操作,所以我们可以将查询省略。
1 | int main() |
- 法三
在法二的基础上,利用 OJ 的特性,OJ 是判定输出的答案是否与答案相同进行判定,当我们知道答案之后直接输出,结束程序那么就会使得程序运行时间大幅度减少。
1 | int main() |
完整解题代码
C++实现方法:
1 |
|
最后总结给大家一个小窍门,在解题过程中可以使用:
- C++ 中有一个 UnorderedMap,可以方便我们的解题过程;
- Python 和 Java 中都有提前定义好的 Hash 函数,也可以直接使用。
实验总结
本次实验,我们学习了散列表的实现方式,了解了散列表的原理与基本的实现方式,学了各种的冲突处理方式和散列函数的构造方式,我们还讲了一种竞赛常用的字符串 hash 的方式,我们都要多加练习并熟练使用。
刷题4
「弗里的的语言」
1 |
|
指针数组和数组指针
c语言,c++函数返回一个数组,二维数组
数据结构之排序算法
实验介绍
信息获取后通常需要进行处理,处理后的信息其目的是便于人们的应用。信息处理方法有多种,通常有数据的排序、查找、插入、删除等操作。本章主要介绍几种简单的数据排序算法和高效的排序算法.
在比赛中,排序算法是必不可少的。虽然我们可能会直接使用 sort 等函数直接进行排序,但在有些特殊题目中,我们仍需使用到排序算法。
知识点
- 选择排序的原理以及代码编写
- 冒泡排序的原理以及代码编写
- 桶排序的原理以及代码编写
- 插入排序的原理以及代码编写
- 理解希尔排序
- 快速排序
- 归并排序的原理
时间复杂度分析
我们本节实验先学习所有的排序算法以及他们的实现,再结合做题目实战。
简单排序算法
简单排序算法包括选择排序、冒泡排序、桶排序和插入排序,本节重点介绍以上四种简单排序算法。
选择排序
- 基本思想
每一趟从待排序的数据元素中选出最小(或最大)的一个元素,按照顺序放在待排序的数列的最前,直到全部待排序的数据元素排完。
- 排序过程
例如:
1 | 初始:[5 4 6 8 7 1 2 3] |
- 对应代码
C++ 实现
1 |
|
Java 实现

Python 实现

冒泡排序
- 基本思想
所谓冒泡排序就是依次将两个相邻的数进行比较,大的在前面,小的在后面。
- 即先比较第一个数和第二个数,大数在前,小数在后,然后比较第 2 个数和第 3 个数,直到比较最后两个数
- 第一趟排序结束后,最小数的数一定在最后
- 第二趟排序在第一趟的基础上重复上述操作
由于排序过程中总是大数在前,小数在后,相当于气泡上升,所以叫冒泡排序。
- 大数在前,小数在后排序后得到的是降序
- 小数在前,大数在后排序后得到的是升序结果
- 排序过程(降序)
1 | 初始数据:4 5 6 1 2 3 |
可以发现,第二趟排序结束后,所有数据已经排好序了。实际上,我们在对于一组数据进行冒泡排序时,假如需要排列的数据个数为 n 个,那么 n-1 趟一定能排好序,比如因为第 2 趟都会有前 2 个小的数排序好,n-1 趟前 n-1 小的数已排好序,最后一个数自然也排好序了。
对应代码:
C++ 实现:
1 |
|
Java 实现

Python 实现

桶排序
- 基本思想
桶排序的思想是,若待排序的记录的关键字在一个明显有限范围内时,可设计有限个有序桶,每个桶只能装与之对应的值,顺序输出各桶的值,将得到有序的序列。简单来说,在我们可以确定需要排列的数组的范围时,可以生成该数值范围内有限个桶去对应数组中的数,然后我们将扫描的数值放入匹配的桶里的行为,可以看作是分类,在分类完成后,我们需要依次按照桶的顺序输出桶内存放的数值,这样就完成了桶排序。
例如,要求我们输入 n 个 0~9 之间的整数,由小到大排序输出,我们可以准备 10 个桶依次编号为 0~9。那么,输入的数 0 则入 0 号桶,1 入 1 号桶,依次类推。
- 如图所示
如上图琐事,我们已准备好 10 个空桶并编号。
下面我们依次输入 8 个整数,分别是 2,5,6,8,5,2,9,6,我们每输入一个数值就将其放入对应的桶。
输入完毕后桶内数据如图所示:
桶排序过程:
- 如上图所示,2 号桶内有两个数字 2,5 号桶内有两个数字 5,6 号桶内有两个数字 6,8 号桶内有一个数字 8,9 号桶内有一个数字 9
- 然后我们按桶编号从小到大的顺序将桶内数字输出,得到 2,2,5,5,6,6,8,9,至此桶排序完成。
注意,桶排序需要注意适用范围,在已知所需排序数据的范围下可以使用,另外本次课程我们只讨论整型的情况,其他数据类型的情况下如何使用,感兴趣的小伙伴可以当作课外内容,自行了解哦。
实现代码
C++ 实现方式:
1 | int maxN=10; //题目出现的数据的最大值 |
Java 实现方式
Python 实现方式
插入排序
基本思想
插入排序是一种简单的排序方法,时间复杂度为 O(n*n),适用于数据已经排好序,插入一个新数据的情况。其算法的基本思想是,假设待排序的数据存放在数组 a[1…n] 中,增加一个节点 x 用于保存当前数据,进行比较,a[1]即作为有序区,a[2…n] 作为无序区。
- 从 i=2 起直至 i=n 为止,通过循环遍历,将 a[i] 放在恰当的位置,使 a[1…i] 数据序列有序
1 | x=a[i] 将 x 与前 i-1 个数比较 |
例如,我们现在有一个数组 a=[3 2 4 1 6 5 2 7],需要使用插入排序进行排列。
排序过程:
1 | 第0步:[3] 2 4 1 6 5 2 7 |
实现代码
C++ 实现
1 |
|
Java 实现

Python 实现

高效排序算法
前面,我们介绍了简单的排序算法,但在实际应用中,简单的排序算法很难达到效率的要求,所以本节介绍了两种高效的排序算法,使排序时间复杂度大大减少。
快速排序
- 基本思想
快速排序是一种采用分治法解决问题的一个典型应用,也是冒泡排序的一种改进。它的基本思想是,通过一轮排序将待排记录分割成独立的两部分,其中一部分均比另一部分小,则可分别对这两部分继续进行排序,已达到整个序列有序。排序的时间复杂度为 O(nlogn),相比于简单排序算法,运算效率大大提高。
- 算法步骤
- 从序列中取出一个数作为中轴数;
- 将比这个数大的数放到它的右边,小于或等于他的数放到它的左边;
- 再对左右区间重复第二步,直到各区间只有一个数。
例如,对以下 10 个数进行快速排序:
1 | 6 1 2 7 9 3 4 5 10 8 |
以第一个数为基准数,在初始状态下,数字 6 在序列的第 1 位,我们的目标是将 6 挪到序列中间的某个位置,假设这个位置是 k 。
现在就需要寻找这个 k ,并且以第 k 位为分界点,左边的数都≤6,右边的数都≥6。那么如何找到这个位置 k 呢?
我们要知道,快速排序其实是冒泡排序的一种改进,冒泡排序每次对相邻的两个数进行比较,这显然是一种比较浪费时间的。
而快速排序是分别从两端开始”探测”的,先从右往左找一个小于 6 的数,再从左往右找一个大于 6 的数,然后交换他们。这里可以用两个变量 i 和 j ,分别指向序列最左边和最右边。
我们为这两个变量起个好听的名字哨兵 i 和哨兵 j。
- 我们首先让哨兵 i 指向序列的最左边,指向数字 6;让哨兵 j 指向序列的最右边,指向数字 8,如下图所示。
- 首先哨兵 j 开始出动。因为此处设置的基准数是最左边的数,所以需要让哨兵 j 先出动,这一点非常重要。
- 哨兵 j 一步一步地向左挪动,直到找到一个小于 6 的数停下来
- 然后哨兵 i 再一步一步向右挪动,直到找到一个数大于 6 的数停下来
- 最后哨兵 j 停在了数字 5 面前,哨兵 i 停在了数字 7 面前,如下图所示:
- 现在交换哨兵 i 和哨兵 j 所指向元素的值,交换之后的序列如下:
- 到此,第一次交换结束。接下来开始哨兵 j 继续向左挪动(再友情提醒,每次必须是哨兵 j 先出发)。他发现了 4<6,停下来。哨兵 i 也继续向右挪动的,他发现了 9>6,停下来。此时再次进行交换,交换之后的序列如下
- 第二次交换结束。哨兵 j 继续向左挪动,他发现了 3<6,又停下来。
- 哨兵 i 继续向右移动,此时哨兵 i 和哨兵 j 相遇了,哨兵 i 和哨兵 j 都走到 3 面前。
说明此时“探测”结束。我们将基准数 6 和 3 进行交换。交换之后的序列如下。
到此第一轮“探测”真正结束。
现在基准数 6 已经归位,此时以基准数 6 为分界点,6 左边的数都小于等于 6,6 右边的数都大于等于 6。
现在我们将第一轮“探测”结束后的序列,以 6 为分界点拆分成两个序列,左边的序列是“3 1 2 5 4”,右边的序列是“9 7 10 8”。接下来还需要分别处理这两个序列,因为 6 左边和右边的序列目前都还是混乱的。不过不要紧,我们已经掌握了方法,接下来只要模拟刚才的方法分别处理 6 左边和右边的序列即可。
实际上快速排序的每一轮处理其实就是将这一轮的基准数归为,直到所有的数都归为为止,排序就结束了。
实现代码
C++ 实现:
1 |
|
Java 实现

Python 实现

归并排序
- 基本思想
归并排序是由递归实现的,主要是分而治之的思想,也就是通过将问题分解成多个容易求解的局部性小问题来解开原本的问题的技巧。
归并排序在合并两个已排序数组时,如果遇到了相同的元素,只要保证前半部分数组优先于后半部分数组, 相同元素的顺序就不会颠倒。所以归并排序属于稳定的排序算法。
每次分别排左半边和右半边,不断递归调用自己,直到只有一个元素递归结束,开始回溯,调用 merge 函数,合并两个有序序列,再合并的时候每次给末尾追上一个最大 int 这样就不怕最后一位的数字不会被排序。
- 排序过程
- 代码实现
C++ 实现:
1 |
|
Java 实现

Python 实现

希尔排序
-
基本思想
希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法,同时也突破了之前内排序算法复杂度为 O(n2)的限制。
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
- 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率.
- 插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位
该方法的基本思想是:
先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。
因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高。
其中增量序列的选择是非常关键的,但通常我们取步长为 n/2(数组长度的一般)然后一直取半直到 1。
实现代码:
C++ 实现:
1 |
|
Java 实现

Python 实现
练习
在我们编译语言中,都是预先设置好排序算法的,我们只需要直接调用即可。但是有些情况是不能调用排序算法的,比如特殊的结构体排序而且要求是稳定的这种情况,所以需要我们在上面各种排序算法的原理的基础上进行改写。大部分情况下我们都是可以直接调用的。
下面我们通过一道题目练习一下上面所学到的知识。
排序初步
1 | 题目: |
C++ 实现
我们将使用 sort 函数解决该问题,由于 sort 在 algorithm 头文件里面,所以使用前先要调入头文件。
用法 sort(首地址,尾地址后面一个位置)
尾地址后面一个位置,即首地址+长度
比如我想排序 a 的第五个元素到第八个元素,共四个元素
那么首地址为 a+5,尾地址后面的一个地址为 a+5+4
尾地址后面一个位置这么描述是为了好理解,其实很多函数都是这么定义的,先这样记住就行,后边就写成 sort(a,a+n)。
或者是 sort(a,a+n,cmp) ,其中 cmp 是比较函数可以根据所比较的数据类型写出比较函数。返回值为 bool 值即可。
1 |
|
我们自己写一个比较函数:
1 |
|
Java 实现

Python 实现
Python 的cmp对象在Python 3 中已经删除了,所以如果我们需要对类对象排序,不能使用cmp函数,最简单的方式就是重载类对象的lt(selfm,other)函数
1 | class student(): |
实验总结
本次实验,我们学习了各种排序的实现方式,了解了各种排序方式的原理与基本的实现方法,在最后,我们还讲讲解了一种简单快捷的排序的方式。本次实验中我们提到的排序方式,大家都需要多加练习,并学会熟练使用
刷题5
1 |
|
内置模板
我们前面讲了很多数据结构相关的知识,本节课程,我们主要讲解怎么不自己定义,而是使用我们所使用的编程语言中,已经定义好的数据结构。
之前我们在栈那一节已经讲过栈的内置数据结构的使用,我们本章就不再进行讲解,我们这节课仍然采用那种方式进行讲解。
知识点
- 迭代器讲解
- 线性表的使用
- 队列的使用
- 集合(set)的使用
- 映射(map)的使用
迭代器(Iterator)
首先,明确一点迭代器是 C++ 的知识,并不适用于 Java 和 Python 这两种语言,但是下面讲容器就要用到这一点,所以我们必须要提前讲一下。迭代器的知识点很复杂,了解即可,当然有余力可以深究,了解就能做题,实现方式看容器讲解。
对于数组我们可以采用指针进行访问,但是对于其他的存储空间连续的数据结构或者说是存储单元我们就需要找到另一种方式来替代指针的行为作用,从而达到对于非数组的数据结构的访问和遍历,于是我们定义了一种新的变量叫做迭代器。
定义:
迭代器是一种检查容器内元素并遍历元素的数据类型。
迭代器提供对一个容器中的对象的访问方法,并且定义了容器中对象的范围。
迭代器和指针的区别:
容器和 string 有迭代器类型同时拥有返回迭代器的成员。
如:容器有成员 .begin() 和 .end(),其中 .begin() 成员复制返回指向第一个元素的迭代器,即指向第一个元素的“地址”,而 .end() 成员返回指向容器尾元素的下一个位置的迭代器。
即 .begin() 指向的是第一个合法元素的位置,.end() 指向是容器后第一个不合法元素的地址。
相应的还有容器反向迭代器成员 .rbegin() .rend(), .rbegin() 返回容器的元素前最后一个不合法的地址,rend() 返回容器的最后一个合法地址。
容器迭代器的使用
每种容器类型都定义了自己的迭代器类型:
1 | 如 vector:vector< int>:: iterator iter;//定义一个名为iter的变量 |
数据类型是由 vector< int> 定义的 iterator 类型。简单说就是容器类定义了自己的 iterator 类型,用于访问容器内的元素。每个容器定义了一种名为 iterator 的类型,这种类型支持迭代器的各种行为。
我么们先讲一下各种迭代器的类型,在讲容器所用的迭代器类型,就可以明白怎么操作。
容器
写在前面,由于 Python 的语言的特点,所有的数据结构大部分都需要自己实现,但是其 List 功能较强,用起来比较简单,当然我们也会再说一遍怎么实现。
在 Java 中各种数据结构都是继承于 list,所以 Java 的 list 功能也很强,它的功能有很多,由于篇幅原因我们会挑比较重要的讲解,其他的还需要同学们多去使用。
Vector 容器(类)
线性表中有 Vector 和 list,两者作用比较相似。
Vector 的主要作用就是可变长度的数组,就把他当成数组使用即可。
至于为甚我们我选择讲 Vector 而不是 List,因为 Vector 可以当作数组使用,用起来非常简单,也非常方便。
我们先讲解一下 c++ 的 Vector 使用:
1 |
|
具体操作如下:
1 | a.size() //返回实际长度(元素个数),O(1)复杂度 |
遍历的方式有两种:
- 迭代器使用与指针类似,可如下遍历整个容器。
1 | for ( vector<int>::iterator it=a.begin() ; it!=a.end() ; it++ ) |
- 当成数组使用。
1 | for( int i=0;i<a.size();i++) cout<<a[i]<<endl; |
上面我们讲解了 C++ 的实现方式,下面我们了解一下 java 的。
1 | //第一种构造方法创建一个默认的向量,默认大小为 10: |
以下为 Java Vector 的 Api。
修饰符和类型 | 方法和说明 |
---|---|
boolean | add(E e)将指定的元素附加到此 Vector 的末尾。 |
void | add(int index, E element)在此 Vector 的指定位置插入指定元素。 |
boolean | addAll(Collection<? extends E> c)将指定集合中的所有元素追加到末尾 这个向量,按照它们由指定的返回的顺序 集合的迭代器。 |
boolean | addAll(int index, Collection<? extends E> c)将指定 Collection 中的所有元素插入到此 指定位置的向量。 |
void | addElement(E obj)将指定的组件添加到此向量的末尾, 将其大小增加一。 |
int | capacity()返回此向量的当前容量。 |
void | clear()从此 Vector 中删除所有元素。 |
Object | clone()返回此向量的克隆。 |
boolean | contains(Object o)退货 true 如果此向量包含指定的元素。 |
boolean | containsAll(Collection<?> c)如果此 Vector 包含所有元素,则返回 true 指定的集合。 |
void | copyInto(Object[] anArray)将此向量的分量复制到指定的数组中。 |
E | elementAt(int index)返回指定索引处的组件。 |
Enumeration | elements()返回此向量的组件的枚举。 |
void | ensureCapacity(int minCapacity)如有必要,增加此向量的容量,以确保它至少可以容纳由指定的组件数量最小容量参数。 |
boolean | equals(Object o)比较指定的 Object 与此 Vector 是否相等。 |
E | firstElement()返回第一个组件(索引处的项目 0) 的这个向量。 |
E | get(int index)返回此 Vector 中指定位置的元素。 |
int | hashCode()返回此 Vector 的哈希码值。 |
int | indexOf(Object o)返回指定元素第一次出现的索引 在此向量中,如果此向量不包含该元素,则为 -1。 |
int | indexOf(Object o,int index)返回指定元素第一次出现的索引这个向量,从 index, 或返回 -1 如果 未找到该元素。 |
void | insertElementAt(E obj, int index)将指定对象作为组件插入此向量中的 指定的 index. |
boolean | isEmpty()测试此向量是否没有组件。 |
Iterator | iterator()以适当的顺序返回此列表中元素的迭代器 |
E | lastElement()返回向量的最后一个组件。 |
int | lastIndexOf(Object o)返回指定元素最后一次出现的索引在此向量中,如果此向量不包含该元素,则为 -1。 |
int | lastIndexOf(Object o, int index)返回指定元素最后一次出现的索引这个向量,从 index, 或返回 -1 如果 未找到该元素。 |
ListIterator | listIterator()返回此列表中元素的列表迭代器(在适当的顺序)。 |
ListIterator | listIterator(int index)返回此列表中元素的列表迭代器(在适当的序列),从列表中的指定位置开始。 |
E | remove(int index)移除此 Vector 中指定位置的元素。 |
boolean | remove(Object o)移除此 Vector 中第一次出现的指定元素如果 Vector 不包含该元素,则它保持不变。 |
boolean | removeAll(Collection<?> c)从此 Vector 中删除其包含在指定的集合。 |
void | removeAllElements()从此向量中删除所有组件并将其大小设置为零。 |
boolean | removeElement(Object obj)删除参数的第一个(最低索引)出现从这个向量。 |
void | removeElementAt(int index)删除指定索引处的组件。 |
protected void | removeRange(int fromIndex, int toIndex)从此列表中删除索引介于两者之间的所有元素 fromIndex,包括在内,和 toIndex, 独家的。 |
boolean | retainAll(Collection<?> c)仅保留此 Vector 中包含在指定的集合。 |
E | set(int index, E element)将此 Vector 中指定位置的元素替换为指定的元素。 |
void | setElementAt(E obj,int index)将组件设置在指定的位置 index 这个的向量是指定的对象。 |
void | setSize(int newSize)设置此向量的大小。 |
int | size()返回此向量中的组件数。 |
List | subList(int fromIndex,int toIndex)返回此列表中 fromIndex 之间的部分的视图 |
Object[] | toArray()返回一个包含此 Vector 中所有元素的数组以正确的顺序。 |
T[] | toArray(T[] a)返回一个包含此 Vector 中所有元素的数组正确的顺序; 返回数组的运行时类型指定数组。 |
String | toString()返回此 Vector 的字符串表示形式,包含 每个元素的字符串表示。 |
void | trimToSize()将此向量的容量修剪为向量的电流 尺寸。 |
遍历 Vector
1 | Enumeration vEnum = v.elements(); |
Python 中,我们直接使用 list 即可来实现。
题目解析
快递员需要对快递进行分拣,现在小李是一名快递员,他想要你帮他设计一个程序用于快递的分拣,按城市分开。
现在有以下输入:
1 | 单号 省份 |
样例如下:
1 | 输入 |
下面我们来分析一下解题思路。
首先我们要知道中国城市肯定在 1000 个以内,但是单号我们不确定,我们不可能每个数组开 10000 个,那样内存不够,所以这时候我们就用到了我们的 vector,他的容量是动态申请的,在比赛中我们可以理解为无限制。
- 第一步:我们创建一个 vector 用于保存地址
1 | vector<string> city; |
- 第二步:我们创建一个 vector 组用于存放单号
1 | vector<string> dig[1000]; |
- 第三步:我们定义一个映射函数,因为你的城市可能会再次出现,你需要知道之前有没有。
- 第四步:我们开始读入操作并按照顺序进行存放
完整代码
C++ 解题代码:
1 |
|
Java 解题代码

Python 实现方式

队列 Queue
队列的讲解在之前的课程中已经讲过了,忘记的快回去复习。
我们直接开始看操作吧。
C++ 中的队列
定义方式:在 C++ 里所有容器的定义方式基本一致。
1 | queue<string> myqueue; |
成员函数:
- front():返回 queue 中第一个元素的引用。
- back():返回 queue 中最后一个元素的引用。
- push(const T& obj):在 queue 的尾部添加一个元素的副本。
- pop():删除 queue 中的第一个元素。
- size():返回 queue 中元素的个数。
- empty():如果 queue 中没有元素的话,返回 true。
Java 中的队列
Python 中的队列
题目回顾
CLZ 的银行。
1 | 第一行 M 次操作(M<1000) |
具体的题目讲解,我们之前就已经讲解过了,这里我们主要是来看一下预置代码的方便性。
完整代码
C++实现:
1 |
|
Java 实现

Python 实现
Map 映射
在之前我们学习散列表的时候我们就接触过了映射,这里我们要讲的是一种类似的数据结构。
map 是一个关联容器,它提供一对一的 hash。
- 第一个可以称为关键字(key),每个关键字只能在 map 中出现一次
- 第二个可能称为该关键字的值(value)
map 以模板(泛型)方式实现,可以存储任意类型的数据,包括使用者自定义的数据类型。Map 主要用于资料一对一映射(one-to-one)的情況,map 在 C++ 的內部的实现自建一颗红黑树,这颗树具有对数据自动排序的功能。在 map 内部所有的数据都是有序的。
比如,像是管理班级内的学生,Key 值为学号,Value 放其他信息的结构体或者类。
C++ 中的 map
定义方式:
1 | map<char, int> mymap1; |
一般用法:
- 看容量。
1 | int map.size();//查询map中有多少对元素 |
- 插入。
1 | map.insert(make_pair(key,value)); |
- 取值。
1 | map<int, string> map; |
- 遍历操作
1 | map<string, string>::iterator it; |
- 查找操作
1 | m.count(key)://由于map不包含重复的key,因此m.count(key)取值为0,或者1,表示是否包含。 |
Java 中的 map
Python 字典
题目演练
《弗里石的的语言》
小发明家弗里想创造一种新的语言,众所周知,发明一门语言是非常困难的,首先你就要克服一个困难就是,有大量的单词需要处理,现在弗里求助你帮他写一款程序,判断是否出现重复的两个单词。
有重复就输出重复单词,重复就输出 NO,多个重复输出最先出现的哪一个。
输入:
1 | 第 1 行,输入N,代表共计创造了多少个单词 |
现在有以下样例输入:
样例 1
1 | 输入: |
样例 2
1 | 输入: |
这个题的思路在前面我们已经讲过了,这里我们换一种方式解题。
使用映射和字典解题,是的原来的代码减少了超过一半,但是思路还是一样,可以说是非常的巧妙且省力。
C++ 解法
1 |
|
Java 解法

Python 解法
打表法和模拟法
模拟法是比赛中最常用的方法,使用各种算法大都离不开模拟,而对于一些只是需要结果的题目来说打表法是一个非常好的解决方案,而且对于数论等其他需要找规律的题目来说,打表法是一个非常有用的方法。
模拟法和打表法,经常会同时出现,因为打表就要按照题目的意思去模拟。今天我们就从蓝桥杯的真题出发,给大家讲解一下,打表法和模拟法的应用。
知识点
- 打表法的使用与简单举例
- 模拟法的使用与简单举例
算式问题
这是 2012 年蓝桥杯国赛 的一道问题。
1 | 题目描述: |
题目分析
首先我们能了解到这道题只需要答案,那么对于时间要求就等于无限,那我们可以使用模拟方法,因为只需要输出答案即可,只要能够在比赛的时长里跑出来即可。
接下来我们将采用模拟法进行问题的求解,注意既然我们不需要考虑时间问题和代码问题,我们一定要将代码设计的具有较高的逻辑性和准确性。
这个题的正解是搜索算法,但是既然只要答案我们求快、求简单,在这里我们使用另一种方式进行解答。
- 这里有三个数字 我们称 A + B = C 且各个位上的数字不同。
- 我们这里借助桶排序的思想来判断 1-9 这些数字有没有占用。
所以我们定义一个判断函数,用于判断 A B C 三个数字是否符合要求。
然后暴力枚举:
- A 从 123 到 987 开始枚举
有很多同学开始抬杠 111-999 岂不是更简单,因为 123 是最小的符合要求的数字,可以减少枚举的次数,987 是最大的符合要求的数字。
- B 从 123 到 987-A 枚举
这时候又会有很多同学来问,为什么不直接枚举与 A 不一样的数字呢,那么又得考虑每一位的问题,这样的模拟已经不是暴力法了,我们要做的就是在不改变完成难度的情况下,减少复杂度。所以要分清注次。
- C = A + B 这时候只要检查 A B C 是否符合要求即可。
代码解答
C++ 实现:
1 |
|
运行结果:
1 | 124 + 659 = 783 |
注意
题目要求是只输出答案,我们讲模拟的代码提交是一分不得的,所以按照题目要求,以下才是正确答案。
1 |
|
有的题目是让你输出答案,有的是让你填空,所以务必审清题目,减少不必要的丢分。
Python 解法

Java 解法


求值
这是 蓝桥杯 2019 国赛 的一道题目。
1 | 题目描述: |
题目分析
这道题乍一看,是一道数论题目,实际上他确实一道数论题目,但是由于是道填空题,所以我们采用模拟法打表做。
题目中的描述是找约数,那我们定义个找约束个数的函数,然后枚举即可。
这样不考虑时间复杂度,我们采取暴力法,尽快完成题目,让程序去跑答案,节省下时间来去做其他的题目。
我们可以这样暴力写约束计数函数。
c++ 与 java 写法相同:
1 | int cnt(int a){ |
Python 解决方法

约数函数定义完成之后,就可以开始枚举了,反正是个很大的数,从几开始都无所谓,300、500 都行,当然也可以从 1 开始。
代码解答
C++ 解题代码:
1 |
|
运行代码部分:
1 | ...... |
提交代码:
1 |
|
Java 解题代码


Python 解题代码

在实测中 C++ 跑的最快,其次是 Java,最慢的是 Python 跑了约 30s,大家要耐心等待一下。
既约分数
这是 2020 年省赛 的一个题目。
1 | 题目描述: |
例如 \frac{3}{4} ,\frac{1}{8} ,\frac{7}{1}43,81,17, 都是既约分数。
1 | 请问,有多少个既约分数,分子和分母都是 1 到 2020 之间的整数(包括 1 和 2020)? |
题目解析
我们看到这种题,现在一眼就知道只是到纯暴力的题目,即暴力枚举然后依据题目要求模拟即可。
但是这种简单题在比赛中是来送分的,我们要花很少的时间做完,才有时间做其他的题目,这就要求我们对这种题目的熟练度极高,要做到,看到题目,想到思路手里能直接写出来才可以。
这里有一个巧妙的方法是因为分子与分母是对称的我们可以少枚举一半,不过有些同学可能没想明白,没关系,我们用普通的办法,只要能够快速的编程并找到答案,思路正确性能够保证的话,其他的都是可有可无的。
这题目我们首先要两个数是否互质,即最小公约数为 1,我们就定义一个 GCD() 求最小公约数的算法,这里我们采用的是递归的方法。
一般我们按照如下写法,方便。
1 | int GCD(int a,int b) |
也可以同义的替换成一下写法:
1 | int GCD(int a,int b) |
当让也可以按照算法的字面意思进行编写:
1 | int gcd(int a,int b) |
然后这个题目我们就可以进行枚举了。
- 外层循环为 a,假设是分母,内层循环是 b 这样就可以进行枚举
- a 和 b 都是 1 到 2020 那这个题,就非常简单了
代码解答
C++ 实现:
1 |
|
提交代码:
1 |
|
Java 解题代码


Python 解题代码

天干地支
这个题目是 2020 国赛的模拟题。
1 | 题目描述: |
题目解析
这个题目是模拟法中最讨厌也最常见的一种,可能还有比这更复杂的,但这道题,已经初具代表性。
他的种类比较多,天干就有 10 种 ,地支有 12 种
现在我们知道了 2020 年是庚子年,我们这里既可以是除留余数来判断 N 年是什么天干和什么地支,我们也可以直接暴力使用循环做,这样的话 9999 的复杂度也跑不了多久。实现起来很简单,我们讲这个比较难的。
我们先判断 0000 年的天干 和地支 。
- 根据题意 0000 年 距 2020 年 早了 2020 年 。
- 已知天干 有 10 个, 那么 2020%10=0 剩下的都是整个轮回,即到了 0000 年 是庚 X 年,即天干是 庚 。
再按照这个方法算地支 是 2020%12=4 及还要向前推四年 地支为申。
即 0000 年为庚申年,那么根据模拟法可知。
N%10=0 时 天干为庚
N%10=1 时 天干为辛
…
以此类推
N%12=0 时 地支为申
N%12=1 时 地支为酉 …
以此类推:
那我们很容易就能实现判断代码的编写:
1 | string tg(int n) |
这样写谁都会写,但是写起来过于太复杂了。我们换一种优雅的实现方式。
代码解答
C++ 方式:
1 |
|
Java 解题代码

Python 解题代码
总结
对于这种简单的模拟题,不需要借助算法,只要暴力的题目,我们都可以打表模拟,然后提交答案,在比赛时有的是输出答案,填空,比赛时注意分辨。
这章难度较低,但是对于熟练度要求较高。
多做简单的思维题,进行训练才能为后期的算法学习打下良好的基础,无论你学了多厉害的算法,如果思维训练不够,到了考场也是两眼一黑,手足无措。
而那些思维很好的同学,即使某一道题的算法我不会,但是我会有新的想法能接触这道题,我们现在所接触的所有算法,不都是某一个大牛,在不经意间发现,经过各种优化到我们手里的吗。
算法是工具,思维才是最重要的,我们这门课程不仅讲算法,还希望能够让各位提高思维能力。
递推法与递归法
递推法:
递推法是一种非常重要的数学方法,不仅在数学领域有着广泛的运用,在其他领域也有着较高的实用性。在计算机中,递推法是用于数值求解的一个重要算法。
知识点
- 递推算法
- 递归算法
递推算法的特点
一个问题的求解需要大量重复计算,在已知的条件和所求问题之间总存在着某种相互联系的关系,在计算时,我们需要找到这种关系,进行计算(递推关系式)。
即递推法的关键,就是找到递推关系式,这种处理方式能够将复杂的计算过程,转化为若干步骤的简单重复运送,充分利用计算机运行程序时的时间局部性和空间局部性。
递推算法的思想:
- 首要问题是先找到各个相邻数据项之间的递推关系;
- 递推关系避开了求通项公式的麻烦,且有些题目的通项公式很难求,或者不能进行求解;
- 将复杂问题分解为若干步骤的简单运算;
- 一般来说递推算法就是一种特殊的迭代算法。
递推算法解题的基本思路:
- 将复杂计算转换为简单重复运算;
- 通过找到递推关系式进行简化运算;
- 利用计算机的特性,减少运行时间。
递推算法的一般步骤:
- 根据题目确定数据项,并找到符合要求的递推关系式;
- 根据递推关系式设计递推程序;
- 根据题目找到递推的终点;
- 单次查询可以不进行存储,多次查询都要进行存储;
- 按要求输出答案即可。
递归算法:
递归算法是一种从自顶向下的算法,实际上是通过不停的直接调用或者间接的调用自身的函数,通过每次改变变量完成多个过程的重复计算,直到到达边界之后,结束调用。
与递推法相似的是,递归与递推都是将一个复杂过程分解为几个简单重复步骤进行计算。
递归算法的实现的核心是分治策略,即分而治之,将复杂过程分解为规模较小的同类问题,通过解决若干个小问题,进而解决整个复杂问题。
递归算法的思想:
- 将复杂计算过程转换为简单重复子过程;
- 找到递归公式,即能够将大问题转化为小问题的公式;
- 自上而下计算,在返回完成递归过程。
递归算法设计的一般步骤:
- 根据题目设计递归函数中的运算部分;
- 根据题目找到递归公式,题目可能会隐含给出,也可能需要自己进行推导;
- 找到递归出口,即递归的终止条件。
递归法的和递推法的思路也给大家讲的差不多了,我们结合真实大赛题目给大家进行讲解。
斐波纳契数列 fibonacci 问题
在一定情况下,同一个问题可以使用用递归也可以使用递推解答。一般一个问题的递推关系和递归关系都好求的话就都可以解题。
当然如果题目只有一个关系好求,那就最好采用关系好求的办法。
题目描述:
1 | 斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”。 |
样例:
1 | 输入样例 |
对于上面的样例我们进行了如下计算;
1 | [0]=0 |
运行限制:
1 | 1. 最大运行时间:1s |
题目解析:
- 这个题给出递推式 F(n) = F(n-1) + F(n-2)
- 转化为可用的递推关系,即 F(n) + F(n+1) = F(n+2)
这一通过从 n=1 开始循环即可完成递推,当然也可以使用递归法。
首先我们写找出递归式,F(n)= F(n-1) + F(n-2)。
1 | F(n)= F(n-1) + F(n-2) |
这样我们找到了递归式,然后我们应该找到递归出口。
我们可以知道 F(n)=0 n=0 ,F(n)=1 n=1 这就是递归出口,能让递归停止的条件。
递归算法的通用框架如下:
1 | do(a,b,c...) |
这道题不是多次询问问题,不需要存储直接计算的复杂度是最低的。
答案解析
C++ 代码:
- 递推算法代码
1 |
|
- 递归算法代码
1 |
|
Python 解题代码

Java 解题代码


存储型的递推与递归
我们在开始就讲过题目十分存储和非存储的,上面那个题目就是此询问,如果改为多次询问我们该怎么办,我们会采用存储的方式,存储的方式适用于大部分的的多次查询问题。
我们看一下修改后的题目。
题目描述:
1 | 斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”。 |
样例:
1 | 输入样例 |
运行限制:
1 | 1. 最大运行时间:1s |
题目解析:
这道题跟上面一道题的算法原理相同,只是增加了多次查询的复杂度,所以仅需修改这一点即可。
再有的是有的同学担心自己的输入输出是在一个屏幕上的,评测的时候会不会出现问题。
类似这样的情况,这一点是不用担心的,只要不是交互题,评测机的输入与输出是分开的,只有你的输出会用来跟答案比较,所以我们只用关心我们的输出即可。
比如有一道题让你计算 x+y 的值,如果你知道每答案,就可以直接输出,都不用进行读入。
然后我们来看一下需要多次询问的题目该怎么解决。
答案解析
C++ 代码:
- 递推算法代码
1 |
|
存储答案的递推法,才是最常使用的递推法。
- 递归算法代码
1 |
|
Python 解题代码


Java 解题代码


数字三角形问题
题目描述:
1 | 如图数字三角形。如下所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径,使该路径所经过的数字总和最大。只要求输出总和。 |
样例:
1 | 输入: |
运行限制:
1 | 1. 最大运行时间:1s |
题目分析:
解决该题目的方式有很多,包括动态规划, 枚举都可以解决这个问题。
我们从递推的思想出发,假设我们从顶层沿着某条路径已经走到了第 i 层,正向着 i+1 层前进, 两条可行路径中我们肯定会选择最大的方向前进,为此我们可以采用递推中的反向递推,即逆推的方式解决,设 a[i][j] 存放从 i,j 出发到达第 n 层的最大值。
我们可以写出递推式:
1 | a[i][j] = max{a[i][j]+a[i+1][j],a[i][j]+a[i+1][j+1]} |
则 逆推到出发点 a[1][1] 为题目所求答案,即第一层到第 N 层的最大值。
答案解析
C++ 代码:
1 |
|
Python 解题代码
Java 解题代码

总结
我们这节课讲了递推与递归的知识点,并且也讲了何时采用递归设计程序,何时采用递推设计程序。对于多次询问的题目,也为大家展示了一种解决方法。
对于递推算法,我们覆盖了正推和逆推两种方式。无论是递推和递归的关键在于找到关系式。
希望同学能够独立完成题目进行练习。并且在后面的学习中会多次用到递归与递推设计其他算法。
枚举法
之前的课,给大家讲解过打表法与模拟法的暴力方式,说到暴力,我们大家最先想到一定是枚举,但是枚举真的是一门技术,怎么样把所有情况一个不落下的枚举出来是比较难的,所以我们这节课给大家讲解一下枚举法。
知识点
- 简单型枚举
- 组合型枚举
- 排列型枚举
- 指数型枚举
枚举法
枚举算法的思想:
将问题的所有可能成为答案的解一一列举,然后根据问题所给出的条件判断此解是否合适,如果合适就保留,反之则舍弃。
枚举算法解题的基本思路:
- 确定枚举解的范围,以及判断条件
- 选取合适枚举方法,进行逐一枚举,此时应注意能否覆盖所有的可能的解
- 在枚举时使用判断条件检验,留下所有符合要求的解。
枚举算法的一般步骤:
- 根据题目确定枚举的范围,并选取合适的枚举方式,不能遗漏任何一个真正解,同时避免重复。
- 为了提高解决问题的效率,看题目是否存在优化,将可能成为解的答案范围尽可能的缩小。
- 根据问题找到合理并、准确好描述并且好编码的验证条件。
- 枚举并判断是否符合第三步确定的的条件,并保存符合条件的解。
- 按要求输出枚举过程中留下的符合条件的解。
枚举法也是有很多技巧和方法的,这节课我们将从如下几种方法为大家进行讲解。
简单型枚举
简单型枚举就是可以通过简单的 for 循环嵌套就可以解决的问题。我们之前的课讲的题目都算是简单型枚举的范畴,所以简单型枚举是比较简单,也是大家接触最多的一种枚举方式。
这种枚举方式没有特定的固定枚举方式,而且都比较简单,按照题目的要求进行设计代码即可完成解题。
我们用一个题复习一下。
42 点问题
题目描述:
1 | 众所周知在扑克牌中,有一个老掉牙的游戏叫做24点,选取4张牌进行加减乘除,看是否能得出24这个答案。 |
样例:
1 | 输入: |
对于上面的样例我们进行了如下计算;
1 | 1. K*A=K 即 13*1=13 |
运行限制:
1 | 最大运行时间:1s |
题目解析:
这个题目我们可以依次枚举数字,然后在枚举数字间的符号即可。由于到结果之间进行了三步计算,所以我们这里需要进行一个递归操作,利用了上节课讲解的知识。
两重循环即可解决问题,伪代码如下:
1 | op1 赋值为 第一个数 |
但是这样写,思路感觉很清晰,写起来却非常的复杂,我们使用我们讲过的 Vector 来优化这个枚举方式。
我们创建 5 个 Vector ,分别用来存放 1-5 次的运算结果,非常简单。我们答案就采用这种方式。
答案解析
C++ 代码:
1 |
|
Python 解题代码
Java 解题代码

组合型枚举
排列组合相信大家都学习过,组合型枚举就是让你在 n 个中,随机选出 m 个,问你有多少种方案,而且每一种方案选择了哪 m 个,这就是组合型枚举。
即组合型枚举就是寻找 cnmc_{n}^mcnm 问题。
组合型枚举有固定的流程,即有着固定的算法模板,这个需要大家去记忆一下。
1 | int n;//共计N个数 |
Python 写法

Java 写法

大家有个疑虑,我这里全是数字而且是从 1 开始的能好用吗,我题目要是字母怎么办,那么请看下面的题目。
公平抽签
题目描述:
1 | 小A的学校,蓝桥杯的参赛名额非常有限,只有m个名额,但是共有n个人报名,其中m<=n。作为老师非常苦恼,他不知道该让谁去,他在寻求一个绝对公平的方式。于是他准备让大家抽签决定,即m个签是去,剩下的是不去。 |
样例:
1 | 输入: |
运行限制:
1 | 1. 最大运行时间:1s |
题目解析:
实际上还是组合型枚举,但是输出元素为人名,我们可以将人名存起来,输出的时候,根据数字下标找到提前存好的人名,直接输出即可。
答案解析
C++ 代码:
1 |
|
Python 解题代码

Java 解题代码

排列型枚举
上面说过,组合型枚举就是让你在 n 个中,随机选出 m 个 ,问你有多少种方案,而且每一种方案选择了哪 m 个,这就是组合型枚举。
而排列型枚举相对组合型枚举就简单了一点,就是 n 个的全排列,即从 n 个中选取 n 个但是关心内部的顺序。
相比较组合只关心有多少个集合,而排列是关心集合内的排列方式。即排列型枚举就是寻找 A_{n}^nAnn 问题。
而且排列型枚举也是有着比较成熟的模板需要大家进行记忆。
1 | int n; //共计N个数 |
Python 写法

Java 写法

不少同学问我 20 够不够,排列问题是阶乘阶的时间复杂度,如果超过这个复杂度,那么这个题也就不用做了,算不出来。
所以肯定够用。
1 | 4 |
4 的排列就已经这么多了,大家可以尝试跑一下 10。
同样,我们再来看一个的问题来进行加深理解。
座次问题
题目描述:
1 | 小 A 的学校,老师好不容易解决了蓝桥杯的报名问题,现在老师又犯愁了。现在有 N 位同学参加比赛,但是老师想给他们排座位,但是排列方式太多了。老师非常想弄明白最后的排座次的结果是什么样子的,到底有多少种结果。 |
样例:
1 | 输入: |
运行限制:
1 | 1. 最大运行时间:1s |
题目解析:
实际上还是排列型枚举,但是输出元素为人名,我们可以将人名存起来,输出的时候,根据数字下标找到提前存好的人名,就是按照上一道题的方式处理即可。
答案解析
C++ 代码:
1 |
|
Python 解题代码

Java 解题代码

实验总结
我们讲了三种的枚举方式,普通枚举和排列组合枚举,其实还是有其他的枚举方式,可以借助我们排列组合进行组合实现,并且在后面的课程中我们将进行搜索的讲解,搜索算法能够作为补充进行其他的枚举。
基本所有的枚举情况我们都涵盖到了,希望大家多加练习,熟练运用。
差分与前缀和
差分与前缀和是一对互逆的操作,常常用于处理区间问题,差分法是解决区间加减问题,前缀和是解决区间求和问题的常用办法。
知识点
- 差分算法
- 前缀和算法
差分法
差分法的应用主要是用于处理区间问题。当某一个数组要在很多不确定的区间,加上相同的一个数。我们如果每个都进行加法操作的话,那么复杂度 O(nm) 是平方阶的,非常消耗时间。
如果我们采用差分法,将数组拆分,构造出一个新的拆分数组,通过对数组区间的端点进行加减操作,最后将数组和并就能完成原来的操作。
这样处理后,时间复杂度降低为 O(N),虽然感觉操作变得更加复杂了,但是只用对边界操作确实比操作一整个区间的方法要优秀的多。
听到这里也是吊足了胃口,那到底怎么对区间操作呢,请大家跟随我的讲解,慢慢理解。
差分法的特点:
- 将对于区间的加减操作转化为对于端点的操作;
- 时间复杂度为 O(n);
- 用于维护区间的增减但不能维护乘除;
- 差分后的序列比原来的数组序列多一个数。
差分算法解题的基本思路:
- b[1]=a[1];
- 从第 2 项到 n 项,利用 b[i]=a[i]-a[i-1]b[i]=a[i]−a[i−1] 差分式;
- 对于区间端点操作加减;
- 差分还原(前缀和)。
- 注意是从1开始,从0开始还有讨论i=0 的情况,使用1的话 b[1]=a[1]-a[0]=a[1]-0;
递推算法的一般步骤:
1 | 首先假设有一个数组: |
差分与前缀和是逆操作,常在一起出现,但是先做差分还是先做前缀和就是两种不同的算法,做不做另一种操作也决定了算法不同,所以大家要根据题目分析,具体学会使用。
大学里的树木要打药
题目描述:
1 | 教室外有 N 棵树,根据不同的位置和树种,学校要对其上不同的药。 |
输入:
1 | 输入描述: |
样例:
1 | 输入样例 |
运行限制:
1 | 1. 最大运行时间:1s |
题目解析:
-
利用b[i]=a[i]-a[i-1]b[i]=a[i]−a[i−1] 差分式。
这里由于开始时都是 0,可以用,但是用完都还是 0,所以没有意义,所以直接跳过即可。
-
依次读入区间的值,然后将对于区间的操作转化为对于区间端点操作加减。 由于我们从1开始,所以数目整体区间要右移1位。
对于每个 [l,r] 区间的加减操作都转化为对端点 l,r+1 的操作。
-
差分还原(前缀和)。
1
2
3for (int i = 1; i < n; i++)
b[i] = a[i] - a[i - 1]
差分算法解决区间加减问题通用框架如下:
1 | //读入原始数据 n,m,a |
答案解析
C++ 代码:
1 |
|
Python 解题代码
Java 解题代码

前缀和
前缀和法的应用主要也是用于处理区间问题。
前缀和是指某序列的前 n 项和,可以把它理解为数学上的数列的前 n 项和。当对于某一数组区间进行多次询问,[L,r] 的和时,如果正常处理,那么我们每次都要 [l,r]。查询 N 次,那么时间复杂度也是 O(nm) 也是平方阶的。
如果我们采用前缀和,构造出一个前缀和数组,通过对于端点的值的减法操作就能 O(1) 的求出 [l,r] 的和。然后 N 次查询的,就将复杂度降低为 O(n)
同差分一样,感觉操作变得更加复杂了,但是只用对端点值的操作确实比一整个区间相加的方法要优秀的多。听到这里大家很期待了,我们接着进行讲解。
前缀和的特点:
- 将对于区间的求和操作转化为对于端点值的减法的操作;
- 区间求和操作的时间复杂度为 O(1);
- 数组存放时要从 1 开始;
- 前缀和数组比原来的数组序列多一个数,第 0 个
前缀和算法解题的基本思路:
- 利用 sum[i]=a[i]+sum[i-1]sum[i]=a[i]+sum[i−1] 差分式;
- 从第 1 项到 n 项,且第 0 项无数据默认为 0;
- 对于区间求和的操作转化为端点值相减。
前缀和的一般解题过程:
1 | 首先假设有一个数组: |
大学里的树木要维护
题目描述:
1 | 教室外有 N 棵树,根据不同的位置和树种,学校已经对其进行了多年的维护。因为树的排列成线性,且非常长,我们可以将它们看作一条直线给他们编号。 |
样例:
1 | 输入样例 |
运行限制:
1 | 1. 最大运行时间:1s |
题目解析:
- 利用sum[i]=a[i]+sum[i-1]sum[i]=a[i]+sum[i−1] 前缀和式在输入时求出前缀和;
- 依次读入区间的值,然后将对于区间的求和操作转化为对于区间端点操作加减,对于每个 [l,r] 区间的求和操作都转化为对端点[r]-[l-1]的操作。
- 输出答案。
前缀和一般解题过程:
1 | 输 入 N 和 M |
答案解析
C++ 代码:
1 |
|
这个代码有个问题,虽然是能通过的,但是他是一个输入对应一个输出的,我们之前讲过,这对大部分的测评机是没问题。
终端输出:
1 | 10 3 |
但是如果有想要规规矩矩的处理,或者说题目要求必须全部读入后输出。我们可这样操作。
1 |
|
终端输出:
1 | 10 3 |
都可以,大家看自己需求和心情选择即可。
Python 解题代码
Java 解题代码


实验总结
我们这节课讲了差分和前缀和的知识点,并且也讲了怎样使用差分,怎样使前缀和,也讲了差分和前缀和最常见的两种情况。
差分和前缀和是很多思维题的解题技巧,必须要掌握熟练才能拿到简单题目的全部分数。
二分查找算法
知识点
- 二分查找原理讲解
- 在单调递增序列 a 中查找 x 或 x 的后继
- 在单调递增序列 a 中查找 x 或 x 的前驱
二分查找算法讲解
枚举查找也就是顺序查找。
实现原理就是逐个比较 a[0:n-1] 中的元素,直到找出元素 x 或搜索遍整个数组后确定 x 不在其中,或者说符合要求的元素在不在数组中。
最坏的情况下需要比较 N 次,时间复杂度是 O(n) 线性阶。
二分查找也就是折半查找。折半查找是将 N 个元素分成大致相同的两部分。选取中间元素与查找的的元素比较,或者与查找条件相比较,找到或者说找到下一次查找的半区。每次都将范围缩小至\frac{1}{2}21 所以时间复杂度是 O(log2n),但是二分查找的前提是有序的,一般是从小到排列。
折半查找的基本思想:
在有序表中(low,high,low<=high),取中间记录即 [(high+low)/2] 作为比较对象。
- 若给定值与中间记录的关键码相等,则查找成功
- 若给定值小于中间记录的关键码,则在中间记录的左半区继续查找
- 若给定值大于中间记录的关键码,则在中间记录的右半区继续查找
不断重复上述过程,直到查找成功,或所查找的区域无记录,查找失败。
二分查找的特征:
- 答案具有单调性;
- 二分答案的问题往往有固定的问法,比如:令最大值最小(最小值最大),求满足条件的最大(小)值等。
折半查找一般过程:
1 | Step 1: |
整数二分法常用算法模板
C++ 语言描述
1 | // 在单调递增序列a中查找>=x的数中最小的一个(即x或x的后继) |
Python 语言描述
Java 语言描述
此处我们先分整数的二分查找法的常用模版,关于实数的部分,我们后面再讲。
下面可能会有同学会疑问道:为什么采用这一套代码的而不是采用查找等于的 X?
是因为这样的适用范围更广,当有 X 时这套代码就返回 X 的位置。如果没有 X,就返回 <=x 的数中最大的一个或者 >=x 的数中最小的一个。
分巧克力
题目描述:
1 | 儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。小明一共有 N 块巧克力,其中第 i 块是 Hi×Wi 的方格组成的长方形。为了公平起见,小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足: |
要求输入:
1 | 输入描述: |
要求输出:
1 | 输出描述: |
样例:
1 | 输入样例 |
运行限制:
1 | 最大运行时间:1s |
题目分析
简单思路,边长的最大规模为 100000;我们可以枚举出所有的情况。按从大到小的顺序进行切割,直到找到满足要求的巧克力边长。
在判断边长是否满足条件时:求一块长方形(h * w)最多被分成的正方形(len * len)巧克力个数为:
1 | cnt = (h / len) \* (w / len) |
但是使用朴素算法枚举时间复杂度 O(n)*O(n) =O(n2) 会超时,所以改用 2 分查找法,这找到符合要求的最大的一个。
即用在单调递增序列 a 中查找 <=x 的数中最大的一个(即 x 或 x 的前驱)即可,原本这里的条件是 <=x ,我们将其换成验证即可。
代码解答
C++ 实现:
1 |
|
查找上界这里可以直接输入的时候查询,这道题实际上是可以少次操作的,代码如下。
Python 实现

Java 实现

M 次方根
题目描述:
1 | 小A最近在学高等数学,他发现了一道题,求三次根号下27。现在已知,小 A 开始计算,1 的三次方得1,2 的三次方得 8,3 的三次方得 27,然后他很高兴的填上了 3。 |
要求输入:
1 | 输入描述: |
要求输出:
1 | 输出描述: |
样例:
1 | 输入样例: |
运行限制:
1 | 最大运行时间:1s |
题目分析
前面讲的都是整数二分,其实二分法还是可以用于实数。这个题目比较难,很多同学可能想不明白,想不明白就多读题,写写画画理解一下。这个题还有很多解法,现在告诉你了这道理用二分可以解答,请设计一个二分程序。
首先是这道题我们怎么下手:
根据前面的知识,我们要找到一个具有单调性的数列,去二分。这个题的关键是我们要去二分什么,这里可以二分的是 a^M 中的 a,所以我们要先想办法设计出用于处理实数二分的代码。
这里给大家两个模板,都可以大家选择一个使用即可:
C++ 模版:
1 | //模版一:实数域二分,设置eps法 |
Python 模版
Java 模版
模板讲完了,然后我们就要考虑判定条件了,怎样判定是否存在满足大于平均值的区间。当然这个题你可以使用语言中自带开方软件,但是我们还是联系一下实数的二分代码。
关于判定条件,我们应该设计一个代码用于比较 a^m 和 N 的大小关系。
在我们代码中:
1 | if (pd(mid)) |
pd 成功的情况,一定是 pd 的 mid 符合条件,且小于 mid 的一定符合条件。因此我们要在大于 mid 中继续查找,找到更大的 mid。
所以我们可以设计出如下判定条件:
1 | double pd(double a,int m) |
代码解答
C++ 实现:
1 |
|
查找上界这里可以直接输入的时候查询,这道题实际上是可以少次操作的,代码如下。
Python 实现

Java 实现

实验总结
二分的题目主要是必须要求是单调的,一般会有条件等字眼。做这种题目主要还是找到递增或者递减的序列,然后关于序列的判定条件。或者通过观察时间复杂度来看是否可以使用二分,二分法的题目相对来说比较明显,设计起来也比较简单,模板不用死记硬背,理解一下,很快就可以独立写出来。
贪心算法
贪心算法(Greedy algorithm),又称贪婪算法。是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而使得问题得到全局最优解。
贪心的算法的设计就是要遵循某种规则,不断地选取当前最优解的算法设计方法。这节实验将会通过多个问题的来讲解贪心算法。
知识点
- 贪心算法的基本概念
- 贪心算法的适用范围
- 贪心算法的设计步骤
- 贪心算法的题目讲解
贪心算法基本概念
贪心算法与枚举法的不同之处在于每个子问题都选择最优的情况,然后向下继续进行,且不能回溯,枚举法是将所有情况都考虑然后选出最优的情况。
贪心算法,在对问题求解时,不从整体考虑,而是采用一叶障目的选择方式,只选择某种意义上的局部最优解。并且,贪心算法是没有固定的模板可以遵循的,每个题目都有不同的贪心策略,所以算法设计的关键就是贪心策略的选择。
贪心算法有一个必须要注意的事情。贪心算法对于问题的要求是,所有的选择必须是无后效性的,即当前的选择,不能影响后续选择对于结果的影响。
贪心算法主要适用于最优化问题,如:MST 问题。有时候贪心算法并不能得到最优答案,但是能得到精确答案的近似答案。有时可以辅助其他算法得到不是那么精确的结果。
适用范围
符合贪心策略:
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。
所谓的贪心选择性质就是,该问题的每一步选择都在选择最优的情况下能够导致最终问题的答案也是最优。
或者说是无后效性,如果该问题的每一步选择都对后续的选择没有影响,就可以是应用贪心算法。
贪心算法的设计步骤
按照定义设计:
- 证明原问题的最优解之一可以由贪心选择得到。
- 将最优化问题转化为这样一个问题,即先做出选择,再解决剩下的一个子问题。
- 对每一子问题一一求解,得到子问题的局部最优解;
- 把子问题的解局部最优解合成原来解问题的一个解
伪代码:
关于 Question Q:
1 | while(Q.hasNextStep) |
贪心相关题目讲解
我们在正式将题目前,聊一个大家都懂的常见的知识,也是一个常见的题目。
找零问题
题目如下:
1 | 假设商店老板需要找零 n 元钱。 |
输入:
1 | 输入解法: |
输出:
1 | 输出解法 |
运行限制:
1 | 最大运行时间:1s |
题目解析:
关于这个题,如果是正常人都知道从大的钱开始找钱。这就是一种贪心的思想,将大问题转化为一个个小的子问题,每次选择最大的钱数使得总量最小。
其实再生活中贪心思想的例子还有很多,像是“自助餐“这种的都是贪心算法的印证。贪心算法其实离我们很近,掌握不会很困难的。
我们先看一下上一道题目的代码题解是什么。
答案解析:
C++ 解法:
1 |
|
Python 解法

Java 解法

活动选择型问题之小 B 的宿舍
题目如下:
1 | 小 B 的宿舍楼沿着走廊南北向的两边各有 200 个房间。 |
输入:
1 | 输入解法: |
输出:
1 | 输出解法 |
运行限制:
1 | 最大运行时间:1s |
题目解析:
该题属于贪心算法,因为它尽可能使搬运行李同时进行,以便使单独安排的搬运次数最少。这样用的时间最少,即所用最少时间为不能同时搬运行李的次数,进而转化为寻找某一段走廊使用次数最多(贪心标准),由于走廊可以同行 2 人,所以除 2,有余数再加 1 即可,即使最多的搬运次数,再乘以 10,即为最少搬运时间。
首先将二维问题转化成一维问题。
不难发现,相对应的两个房间其实是占用一段走廊的,我们可以将将房间号映射为走廊号,然后再考虑上面的解析。
答案解析:
C++ 解法:
1 |
|
Python 解法
Java 解法

可拆分背包问题之贪心的自助餐
题目如下:
1 | 小 B 同学呢,想去吃自助餐,但是他是那种比较节俭的的人,既不想浪费食物,又想尽可能吃的贵一点,他于是私下里做了调查。 |
输入:
1 | 输入解法 |
输出:
1 | 输出解法 |
运行限制:
1 | 最大运行时间:1s |
题目解析:
可拆分背包的一般解法为:
这里有 n 种不同值 v[i] 和权重 w[i] 的对象(如果选择该对象的 w[i] 可以获得值 v[i])。
你有一个容器来挑选它们。你可以根据自己的需要把它们分成任意大小的碎片。可以拾取的对象的最大重量给定为 w。请计算您能得到的最大值。
就像是这个题目,要想吃回本就要捡着贵的吃,但是贵只是一方面,人会饱,所以用价格除以质量所获的价格商才是贪心准则,应按照价格商优先进行选取。
于是这个题,就要用的我们之前学的知识了。这里因为要整体排序,所以要先创建一个类,然后自定义 cmp 函数,在使用 sort 排序。
答案解析:
C++ 解法:
1 |
|
Python 解法

Java 解法

实验总结
贪心算法的最主要的特征就是无后效性,就像是自助餐那个题目,如果说吃了某一样食物,就不能吃另一个食物了,那么这就有了后效性,那就不能使用贪心算法进行解决问题了。
本节课举了三个贪心算法的例子进行讲解,贪心算法是算法竞赛中最入门的算法。没接触过感觉很深奥,接触过了也就那样,简单的贪心伸伸手就可以写出来,其实非常简单,大家也不要过分的担心。
蓝桥杯真题精讲之一
在前面实验中,我们为了快速提高对每一个实验的知识点快速理解,所做的实战题目都是使用对应知识点解答的题目,导致题目知识点或者说用到的算法比较单一,实战意义还不充足。
本节实验主要是融汇贯穿前面我们学习过的知识点,通过 4 道蓝桥杯真题进行实战讲解,带领大家学以致用。
知识点
- 2020 年蓝桥杯国赛真题–答疑
- 2012 年蓝桥杯省赛真题–鲁卡斯队列
- 2015 年蓝桥杯模拟真题–金币
- 最大化股票交易的利润
答疑
本题出自于 2020 年蓝桥杯国赛真题。
题目描述
1 | 有 n 位同学同时找老师答疑。每位同学都预先估计了自己答疑的时间。 |
输入
1 | 输入描述: |
输出
1 | 输出描述: |
运行限制
1 | 最大运行时间:1s |
题目解析
本题是一个贪心问题,要想使得所有的时刻之和最小,就要使得每一个时刻尽可能少,根据题目我们可以得到每位同学的时刻=每位同学的等待时间+进门时间+答疑时间。
由于答疑时间是已知的,要使得每位同学的时刻最小,那么就要使得每位同学的等待时间最小。如何使得等待时间最小的呢?
如果这么考虑这道题是做不出来的,我们应该考虑的是使得每位同学等待的时间和最小。
1 | 每位同学的时刻 = 每位同学的等待时间 + 进门时间 + 答疑时间 |
设第 i 位同学的等待时间为 Ti,则有:
- 第一位同学等待时间 S1=T1=0 -----(1)
- 第二位同学等待时间 S2=T1+T2=T2 -----(2)
- 第三位同学等待时间 S3=T1+T2+T3=T2+T3 -----(3)
…
- 那么第 N 位同学等待时间 Sn=T1+T2+T3+T4+T5+…+Tn-1 -----(n)
将 1 到 n-1 式带入 n 式得,
1 | Sn=T1*n+T2\*(n-1)+T3\*(n-1)+....+Tn |
由此可知前面的系数是最大的,所以要使前面的时间最小,于是得出了贪心策略进而解决问题。
使用贪心算法后,我们可以得出结论是,每位同学的等待时间(前一位同学的等待时间 + 前一位同学的进门时间 + 答疑时间 + 前一位同学的收拾东西的时间)最小。
但是如果相同的时候,两者前后关系是什么?
- 因为是答疑结束后就发消息,而不是出门之后发消息,所以两者存在前后关系,谁先答疑结束谁就先执行。
- 我们还要进一步考虑,如果进门时间+答疑时间相同,即答疑同时结束,既然答疑同时结束,那么谁先谁后结果是相同的,所以不用继续考虑,到此,贪心策略完整的生成。
即:我们选取最小的进门时间+答疑时间+收拾东西时间之和最小的人在前,且当进门时间 + 答疑时间 + 收拾东西时间的和相同时,选择最小的进门时间 + 答疑时间。
答案解析
C++ 描述:
1 |
|
Python 描述

Java 描述

鲁卡斯队列
本题出自 2012 年蓝桥杯省赛真题。
题目描述:
1 | 本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。 |
输入:
1 | 输入描述: |
输出:
1 | 输出描述: |
运行限制:
1 | 最大运行时间:1s |
题目解析:
这道题是基于前缀和的模拟题,我们按照要求进行模拟即可。
答案解析:
C++ 描述:
1 |
|
stringstream 类:
这里给出的 C++ 代码描述,会写的相对繁琐一些,目的是为了给大家讲一种新的字符串使用技巧。C++ stringstream 类是一种十分有用的类,特别是当我们需要在程序中使用字符串和数字数据互相转换的时候。
要想在程序中使用 stringstream 类,我们需要在源程序文件中包含头文件include<sstream>
。
stringstream 对象的使用方法与 cout 对象和 cin 的使用方法基本相同。>> 这个符号就很形象,比如:
cin>>a
可以理解为将数据流流入到 a 中cout<<a
则是将数据流流入到 cout 中,归根结底还是数据流
可能对于底层的描述不太恰当,但是大家记住 >> 指向谁,则是将数据给到谁,stringstream 当成 cin cout 用即可。在我上面给出的代码中,大家可以看到我还将数据还进行了转化处理,在 C++ 中数据类型的转化使用 stringstream 也是不错的选择。
Python 描述

Java 描述

金币
本题出自 2015 年蓝桥杯模拟真题。
题目描述:
1 | 国王将金币作为工资,发放给忠诚的骑士。 |
输入:
1 | 输入描述: |
输出:
1 | 输出描述: |
运行限制:
1 | 最大运行时间:1s |
题目解析:
这道题是前缀和的变种,变种的方式可以通过模拟解决,时间复杂度为 O(N2),但是题目的范围为 1e4,不超时方法可行。
答案解析
C++ 描述:
1 |
|
Python 描述

Java 描述

最大化股票交易的利润
本题是来自蓝桥云课题库中的模拟题。
-题目链接
题目描述:
1 | 实现一个算法寻找最大化股票交易利润的策略。介绍如下: |
输入:
1 | 输入描述: |
输出:
1 | 输出描述: |
运行限制:
1 | 最大运行时间:1s |
题目解析:
这个题目是个模拟题目,按照题目要求即可。
这个题目获得最大利润的方式,就是存在 A,B 两天,A 在 B 前一天,使得 B—A 的值最大。
答案解析:
C++ 描述
1 |
|
Python 描述
Java 描述

实验总结
我们复习了之前的讲的几个知识点,然后我们又讲了几道题目,希望大家能够发散思维,不要局限方式方法,能做出来即可。
蓝桥杯真题精讲之二
实验介绍
本节实验,我们将延续上一节实验的真题精讲,继续继续分析蓝桥杯真题,通过精讲,让大家对学过的知识点达到学以致用。
知识点
- 2021 年蓝桥杯模拟赛真题-谈判
- 优先队列
- 2008 年 NOIP 普及组真题-排座椅
谈判
题目描述:
1 | 题目描述 |
输入:
1 | 输入的第一行包含一个整数 nnn,表示部落的数量。 |
输出:
1 | 输出一个整数,表示最小花费。 |
输入输出样例
1 | 示例 1 |
运行限制:
1 | 最大运行时间:1s |
题目解析:
这题是一个贪心问题,要想使得花费金额之和最小,就要使得每一次的花费尽可能少。
根据题目我们可以得到,合成的新部落的花费=人数为原来两个部落的人数之和。
如何使得等待时间最小的呢?
如果这么考虑这道题是做不出来的,应该考虑的是使得每位同学等待的时间和最小。我们回忆一下答疑拿到题目:
1 | 第一位同学等待时间 S1=T1=0 -----(1) |
这道题目还是按照人数排序吗,然而不是这样的,我们看一组样例:
1 | 4 |
所以这里贪心原则是维护最小的值,但是每次都会进行更新,每次更新后就要重新排序,时间复杂度是 Nlog(n) 的复杂度,这里是可以通过的,当然我们也可以使用优先队列解题。
优先队列的使用方式跟队列是一模一样的,优先队列会自动进行排序而已。
普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出(first in, largest out)的行为特征。通常采用堆数据结构来实现。
C++中的优先队列:
首先要包含头文件 #include<queue>
,他和 queue 不同的就在于我们可以自定义其中数据的优先级,让优先级高的排在队列前面,优先出队。
优先队列具有队列的所有特性,包括队列的基本操作,只是在这基础上添加了内部的一个排序,它本质是一个堆实现的。
常用的成员函数:
- top 访问队头元素
- empty 队列是否为空
- size 返回队列内元素个数
- push 插入元素到队尾 (并排序)
- emplace 原地构造一个元素并插入队列
- pop 弹出队头元素
- swap 交换内容
队列的定义有两种:
1 | //升序队列,小顶堆 |
Python 优先队列
Java 优先队列

简单排序答案
这个题我们会采取两种解题策略,一种是简单的多次排序,另一种就是上面讲的优先队列。
C++ 描述:
1 |
|
Python 描述
Java 描述

优先队列答案
C++ 描述:
1 |
|
Python 描述
Java 描述

这道题的做法,变成了一种数据结构叫做哈夫曼树,后面的课程我们会讲到。
排座椅
题目描述:
1 | 上课的时候总有一些同学和前后左右的人交头接耳,这是令小学班主任十分头疼的一件事情。 |
输入:
1 | 输入第一行,有 5 各用空格隔开的整数,分别是 M,N,K,L,D(2≤N,M≤1000,0≤K<M,0≤L<N,D≤2000)。 |
输出:
1 | 输出共两行。 |
输入输出样例:
1 | 示例 1 |
运行限制:
1 | 最大运行时间:1s |
题目解析:
样例说明:
上图中用符号 *、※、+ 标出了 3 对会交头接耳的学生的位置,图中条粗线的位置表示通道,图示的通道划分方案是唯一的最佳方案。
首先这道题是说前后左右有交头接耳的同学,我们通过设置设置了 K 条横向的通道,L 条纵向的通道使得交头接耳的同学组数最少。
本题的主要算法为贪心,要使上课时交头接耳的学生对数最少,每条通道的划分应该使得分开的交头接耳同学的对数最多。
因此我们可以使用桶排序解决这个问题,通过定义一系列的桶来记录每条通道的交头接耳的学生对数。
关于桶排序的过程:
我们先定义两个数组 x,y。
- x[1] 表示如果在第一列与第二列中间划分过道能够分开几组说话的同学,x[2] 则是第二列与第三列… 直到 x[n-1]。
- 同理,y[1] 表示第一行与第二行,y[2] 表示第二行与第三行,直到 y[m-1]。
如果纵坐标相同,即这两个同学在一列,那么设两个同学横坐标分别为 a,b。
- a 和 b 之间一定存在着大小关系,如果
a\<b
那么根据题目可以知道 a+1=b,那么 a 与 b 之间通道的编号就是 a。 - 同理,如果横坐标相同,即这两个同学在一行,那么设两个同学纵坐标分别为 a,b。
- 那么,a 和 b 之间一定存在着大小关系,如果
a\<b
那么根据题目可以知道 a+1=b,那么 a 与 b 之间通道的编号就是 a。
这样我们就能进行桶排序,并且经过排序过后,就可以在横向通道和纵向通道中找到前 K 和前 L 个即可,最后输出答案。
需要注意的是,
1 | 第一行包含 K 个整数,a1,a2,⋯aK,表示第 a1a_1a1 行和 a1+1a_1+1a1+1 行之间、第 a2 行和第 a2+1 行之间、…、第 aK 行和第 aK+1 行之间要开辟通道,其中 ai<ai+1,每两个整数之间用空格隔开(行尾没有空格)。 |
所以输出需划分的通道时,要先将通道按编号由小到大排序后再输出 。
答案解析:
C++ 描述
1 |
|
Python 描述
Java 描述

实验总结
这节课我们围绕着贪心展开,讲了排序,用到了 Vector、桶排序,可见在真正的竞赛中,像这样各种知识的混着出题,才是常见的。单一知识点出题,我们称作签到题,就是所有人都会做的。当然在蓝桥杯省赛中,能够将前面的知识学会学好,省二是没有问题,想要冲击更高的奖项,基础篇只是打好了基础,后面的课程会带你认识更多的算法,体验算法之美。