一、队列基础知识
1. 队列概念
- 略
二、队列知识扩展
1. 队列的知识
- 略。
队列题目 | 队列的应用
题目一:滑动窗口的平均值
请实现如下类型MovingAverage
,计算滑动窗口中所有数字的平均值,该类型构造函数的参数确定滑动窗口的大小,每次调用成员函数next
时都会在滑动窗口中添加一个整数,并返回滑动窗口中所有数字的平均值。
public MovingAverage {
public MovingAverage (int size);
public double next(int val);
}
例如,假设滑动窗口的大小为3。第1次调用next函数时在滑动窗口中添加整数1,此时窗口中只有一个数字1,因此返回平均值1。第2次调用next函数时添加整数2,此时窗口中有两个数字1和2,因此返回平均值1.5。第3次调用next函数时添加数字3,此时有3个数字1、2、3,因此返回平均值2。第4次调用next函数时添加数字4,由于受到窗口大小的限制,滑动窗口中最多只能有3个数字,因此第1个数字1将滑 出窗口,此时窗口中包含3个数字2、3、4,返回平均值3。
题目分析
难度: 略
思路: 略
参考代码
Tips:2024-06-14 17:02
题目二:最近请求次数
题目:请实现如下类型RecentCounter
,它是统计过去3000ms
内的请求次数的计数器。该类型的构造函数RecentCounter
初始化计数器,请求数初始化为0;函数ping(int t)
在时间t添加一个新请求(t
表示以毫秒为单位的时间),并返回过去3000ms
内(时间范围为[t-3000,t]
)发生的所有请求数。假设每次调用函数ping
的参数t
都比之前调用的参数值大。
public RecentAverage {
public RecentAverage ();
public int ping(int t);
}
例如,在初始化一个RecentCounter
计数器之后,ping(1)
的返回值是1
,因为时间范围[-2999,1]
只有1个请求;ping(10)
的返回值是2
,因为时间范围[-2990,10]
有2
个请求;ping(3001)
的返回值是3
,因为时间范围[1,3001]
有3
个请求;ping(3002)
的返回值是3
,因为时间范围[2,3002]
有3
个请求,发生在时间1
的请求已经不在这个时间范围内。
题目分析
难度: 略
思路: 略
参考代码
Tips:2024-08-06 18:00
队列题目 | 二叉树的广度优先搜索
题目一:在完全二叉树中添加节点
题目:在完全二叉树中,除最后一层之外其他层的节点都是满 的(第n
层有2n-1
个节点)。最后一层的节点可能不满,该层所有的 节点尽可能向左边靠拢。例如,图中的4棵二叉树均为完全二叉 树。实现数据结构CBTInserter
有如下3
种方法。
- 构造函数
CBTInserter (TreeNode root)
,用一棵完全二叉树的根节点初始化该数据结构。 - 函数
insert (int v)
在完全二叉树中添加一个值为v的节点,并返回被插入节点的父节点。例如,在如图(a)
所示的完全二叉树中添加一个值为7
的节点之后,二叉树如图(b)
所示,并返回节点3
。在如图(b)
所示的完全二叉树中添加一个值为8
的节点之后,二叉树如图(c)
所示,并返回节点4
。在如图(c)
所示 的完全二叉树中添加节点9
会得到如图(d)
所示的二叉树并返回节点4
。 - 函数
get_root()
返回完全二叉树的根节点。
题目分析
难度: 略
思路: 略
参考代码
Tips:2024-08-06 18:16
题目二:二叉树中每层的最大值
题目:输入一棵二叉树,请找出二叉树中每层的最大值。例如,输入图中的二叉树,返回各层节点的最大值[3,4,9]。
题目分析
难度: 略
思路: 略
参考代码
Tips:2024-09-02 15:05
题目三:二叉树最低层最左边的值
题目:如何在一棵二叉树中找出它最低层最左边节点的值?假设二叉树中最少有一个节点。例如,在如图所示的二叉树中最低层最左边一个节点的值是5。
题目分析
难度: 略
思路: 略
参考代码
Tips:2024-09-02 15:05
题目四:二叉树的右侧视图
题目:给定一棵二叉树,如果站在该二叉树的右侧,那么从上到下看到的节点构成二叉树的右侧视图。例如,图7.6中二叉树的右侧视图包含节点8、节点10和节点7。请写一个函数返回二叉树的右侧视图节点的值。
题目分析
难度: 略
思路: 略
参考代码
Tips:2024-09-02 15:05
三、章节小结
略