Python数据结构-队列与广度优先搜索(Queue)

Python012

Python数据结构-队列与广度优先搜索(Queue),第1张

队列(Queue) :简称为队,一种线性表数据结构,是一种只允许在表的一端进行插入操作,而在表的另一端进行删除操作的线性表。

我们把队列中允许插入的一端称为 「队尾(rear)」 ;把允许删除的另一端称为 「队头(front)」 。当表中没有任何数据元素时,称之为 「空队」

广度优先搜索算法(Breadth First Search) :简称为 BFS,又译作宽度优先搜索 / 横向优先搜索。是一种用于遍历或搜索树或图的算法。该算法从根节点开始,沿着树的宽度遍历树或图的节点。如果所有节点均被访问,则算法中止。

广度优先遍历 类似于树的层次遍历过程 。呈现出一层一层向外扩张的特点。先看到的节点先访问,后看到的节点后访问。遍历到的节点顺序符合「先进先出」的特点,所以广度优先搜索可以通过「队列」来实现。

力扣933

游戏时,队首始终是持有土豆的人

模拟游戏开始,队首的人出队,之后再到队尾(类似于循环队列)

传递了num次之后,将队首的人移除

如此反复,直到队列中剩余一人

多人共用一台打印机,采取“先到先服务”的队列策略来执行打印任务

需要解决的问题:1 打印系统的容量是多少?2 在能够接受的等待时间内,系统可容纳多少用户以多高的频率提交打印任务?

输入:abba

输出:False

思路:1 先将需要判定的词从队尾加入 deque2从两端同时移除字符并判断是否相同,直到deque中剩余0个(偶数)或1个字符(奇数)

内容参考: https://algo.itcharge.cn/04.%E9%98%9F%E5%88%97/01.%E9%98%9F%E5%88%97%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86/01.%E9%98%9F%E5%88%97%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86/

广度优先这个是图论中概念。在一个图中,遍历有两种一种是广度优先,一种是深度优先,如果从一个节点开始 优先遍历子节点的兄弟(同层)节点那么是广度优先,如果优先遍历子节点的子节点那么是深度优先

大树满足条件的和 等于 每个子树满足条件的数的和之和

result = 0 + 10 + 15 + 18

深度优先搜索必然会使用到 递归

必须使用到辅助队列,用于判断

找到共同的祖先

对相同像素的相邻位置进行渲染

给定一个包含了一些 0 和 1 的非空二维数组 grid 。

一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿,则返回面积为 0 。)