task04|队列与广度优先搜索|TeamStudy

task04|队列与广度优先搜索|TeamStudy

文章目录

队列基础知识

结构基本 *** 作顺序存储

一般队列的顺序存储循环队列的存储

防止假溢出的两种做法判断队列为空队列未满的方法循环顺序存储基本描述 链式存储队列的应用 622设计循环队列346数据流中的移动平均值255用队列实现栈队列与广度有限搜索

队列广度优先搜索实现步骤 广度优先搜索应用

463. 岛屿的周长完全平方数 752. 打开转盘锁

542 01矩阵322 零钱兑换剑指 Offer 13. 机器人的运动范围

队列基础知识 结构

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

线性表先进先出原则

基本 *** 作

初始化空队列：创建一个空队列，定义队列的大小 size，以及队头元素指针 front，队尾指针 rear。

判断队列是否为空：当队列为空时，返回 True。当队列不为空时，返回 False。一般只用于队列中删除 *** 作和获取队头元素 *** 作中。

判断队列是否已满：当队列已满时，返回 True，当队列未满时，返回 False。一般只用于顺序队列中插入元素 *** 作中。

插入元素（入队）：相当于在线性表最后元素后面插入一个新的数据元素。并改变队列顶指针 top 的指向位置。

删除元素（出队）：相当于在线性表最后元素后面删除最后一个数据元素。并改变队列顶指针 top 的指向位置。

获取队列队头元素：相当于获取线性表中最后一个数据元素。与插入元素、删除元素不同的是，该 *** 作并不改变队列顶指针 top 的指向位置。

顺序存储 一般队列的顺序存储

「顺序存储的队列」：利用一组地址连续的存储单元依次存放队列中从队头到队尾的元素，同时使用指针 front 指向**队头元素（出）在队列中的位置，使用指针 rear 指示队尾元素（入）**在队列中的位置。

初始化时：创建一个空队列 self.queue，定义队列大小 self.size。令队头指针 self.front 和队尾指针 self.rear 都指向 -1。即 self.front = self.rear = -1。判断队列为空：根据 self.front 和 self.rear 的指向位置关系进行判断。如果对头指针 self.front 和队尾指针 self.rear 相等，则说明队列为空。判断队列为满：如果 self.rear 指向队列最后一个位置，即 self.rear == self.size - 1，则说明队列已满。获取队头元素：先判断队列是否为空，为空直接抛出异常。如果不为空，因为 self.front 指向队头元素所在位置的前一个位置，所以队头元素在 self.front 后面一个位置上，返回 self.queue[self.front + 1]。获取队尾元素：先判断队列是否为空，为空直接抛出异常。如果不为空，因为 self.rear 指向队尾元素所在位置，所以直接返回 self.queue[self.rear]。入队 *** 作：先判断队列是否已满，已满直接抛出异常。如果不满，则将队尾指针 self.rear 向右移动一位，并进行赋值 *** 作。此时 self.rear 指向队尾元素。出队 *** 作：先判断队列是否为空，为空直接抛出异常。如果不为空，则将队头指针 self.front 指向元素赋值为 None，并将 self.front 向右移动一位。 循环队列的存储

在队列的顺序存储实现中，当队列中第 0 ~ size - 1 位置均被队列元素占用时，有 self.rear == self.size - 1，队列已满，再进行入队 *** 作就会抛出队列已满的异常。

此外，由于出队 *** 作总是删除当前的队头元素，将 self.front 进行右移，而插入 *** 作又总是在队尾进行。经过不断的出队、入队 *** 作，队列的变化就像是使队列整体向右移动。当队尾指针 self.rear == self.size - 1 时，此时再进行入队 *** 作就又抛出队列已满的异常。而之前因为出队 *** 作而产生空余位置也没有利用上，这就造成了「假溢出」问题。

防止假溢出的两种做法

为了解决「假溢出」问题，有两种做法：

第一种：每一次删除队头元素之后，就将整个队列往前移动 1 个位置
队头指针用不到了。因为队头指针总是在队列的第 0 个位置。但是因为删除 *** 作涉及到整个队列元素的移动，所以每次删除 *** 作的时间复杂度就从 O ( 1 ) O(1) O(1) 变为了 O ( n ) O(n) O(n) 。

第二种：将队列想象成为头尾相连的循环表，利用数学中的求模运算，使得空间得以重复利用，这样就解决了问题。

入队时，队尾指针循环前进 1 个位置，即 self.rear = (self.rear + 1) % self.size。

出队时，队头指针循环前进 1 个位置，即 self.front = (self.front + 1) % self.size。

判断队列为空队列未满的方法

方式 1：增加表示队列中元素个数的变量 self.count，用来以区分队列已满还是队列为空。在入队、出队过程中不断更新元素个数 self.count 的值。

队列已满条件为：队列中元素个数等于队列整体容量，即 self.count==self.size，队空为空条件为：队列中元素个数等于 0，即 self.count == 0。 方式 2：增加标记变量 self.tag，用来以区分队列已满还是队列为空。

队列已满条件为：self.tag ==1 的情况下，因插入导致 self.front ==self.rear。队列为空条件为：在 self.tag == 0 的情况下，因删除导致 self.front == self.rear。 方式 3：特意空出来一个位置用于区分队列已满还是队列为空。入队时少用一个队列单元，即约定以「队头指针在队尾指针的下一位置」作为队满的标志。

队列已满条件为：队头指针在队尾指针的下一位置，即 (self.rear + 1) % self.size == self.front。队列为空条件为：队头指针等于队尾指针，即 self.front == self.rear。 循环顺序存储基本描述

初始化时：创建一个空队列，定义队列大小为 s e l f . s i z e + 1 self.size + 1 self.size+1。令队头指针 self.front 和队尾指针 s e l f . r e a r self.rear self.rear 都指向 0。即 s e l f . f r o n t = s e l f . r e a r = 0 self.front = self.rear = 0 self.front=self.rear=0。
判断队列为空：根据 s e l f . f r o n t self.front self.front 和 s e l f . r e a r self.rear self.rear 的指向位置进行判断。根据约定，如果对头指针 s e l f . f r o n t self.front self.front 和队尾指针 s e l f . r e a r self.rear self.rear 相等，则说明队列为空。
判断队列为满：队头指针在队尾指针的下一位置，即 ( s e l f . r e a r + 1 ) (self.rear + 1) (self.rear+1) % s e l f . s i z e self.size self.size = = == == s e l f . f r o n t self.front self.front，则说明队列已满。
获取队头元素：先判断队列是否为空，为空直接抛出异常。如果不为空，因为 s e l f . f r o n t self.front self.front 指向队头元素所在位置的前一个位置，所以队头元素在 s e l f . f r o n t self.front self.front 后一个位置上，返回 s e l f . q u e u e [ self.queue[ self.queue[ ( s e l f . f r o n t + 1 ) (self.front + 1) (self.front+1) % s e l f . s i z e ] self.size] self.size]。
获取队尾元素：先判断队列是否为空，为空直接抛出异常。如果不为空，因为 self.rear 指向队尾元素所在位置，所以直接返回 s e l f . q u e u e [ s e l f . r e a r ] self.queue[self.rear] self.queue[self.rear]。
入队 *** 作：先判断队列是否已满，已满直接抛出异常。如果不满，则将队尾指针 self.rear 向右循环移动一位，并进行赋值 *** 作。此时 self.rear 指向队尾元素。
出队 *** 作：先判断队列是否为空，为空直接抛出异常。如果不为空，则将队头指针 self.front 指向元素赋值为 None，并将 self.front 向右循环移动一位。

链式存储

「链式存储的队列」：利用单链表的方式来实现队列。队列中元素按照插入顺序依次插入到链表的第一个节点之后，并使用队头指针 front 指向链表头节点位置，也就是队头元素，rear 指向链表尾部位置，也就是队尾元素。

我们约定：队头指针 self.front 指向队头元素所在位置的前一个位置，而队尾指针 self.rear 指向队尾元素所在位置。

初始化时：建立一个链表头节点 self.head，令队头指针 self.front 和队尾指针 self.rear 都指向 head。即 self.front = self.rear = head。判断队列为空：根据 self.front 和 self.rear 的指向位置进行判断。根据约定，如果对头指针 self.front 等于队尾指针 self.rear，则说明队列为空。获取队头元素：先判断队列是否为空，为空直接抛出异常。如果不为空，因为 self.front 指向队头元素所在位置的前一个位置，所以队头元素在 self.front 后一个位置上，返回 self.front.next.value。获取队尾元素：先判断队列是否为空，为空直接抛出异常。如果不为空，因为 self.rear 指向队尾元素所在位置，所以直接返回 self.rear.value。入队 *** 作：创建值为 value 的链表节点，插入到链表末尾，并令队尾指针 self.rear 沿着链表移动 1 位到链表末尾。此时 self.rear 指向队尾元素。出队 *** 作：先判断队列是否为空，为空直接抛出异常。如果不为空，则获取队头指针 self.front 下一个位置节点上的值，并将 self.front 沿着链表移动 1 位。如果 self.front 下一个位置是 self.rear，则说明队列为空，此时，将 self.rear 赋值为 self.front，令其相等。

注意：front 和 rear 的指向位置并不完全固定。有时候算法设计上的方便以及代码简洁，也会使 front 指向队头元素所在位置的前一个位置。rear 也可能指向队尾元素在队列位置的下一个位置。具体还是要看算法是如何实现的。

队列的应用

解决计算机的主机与外部设备之间速度不匹配的问题。

比如解决主机与打印机之间速度不匹配问题。主机输出数据给计算机打印，输出数据的速度比打印数据的速度要快很多，如果直接把数据送给打印机进行打印，由于速度不匹配，显然行不通。为此，可以设置一个打印数据缓存队列，将要打印的数据依次写入缓存队列中。然后打印机从缓冲区中按照先进先出的原则依次取出数据并且打印。这样即保证了打印数据的正确，又提高了主机的效率。 解决由于多用户引起的系统资源竞争的问题。

比如说一个带有多终端的计算机系统，当有多个用户需要各自运行各自的程序时，就分别通过终端向 *** 作系统提出占用 CPU 的请求。 *** 作系统通常按照每个请求在时间上的先后顺序将它们排成一个队列，每次把 CPU 分配给队头请求的用户使用；当相应的程序运行结束或用完规定的时间间隔之后，将其退出队列，再把 CPU 分配给新的队头请求的用户使用。这样既能满足多用户的请求，又能使 CPU 正常运行。再比如 Linux 中的环形缓存、高性能队列 Disruptor，都用到了循环并发队列。iOS 多线程中的 GCD、NSOperationQueue 都用到了队列结构。

622设计循环队列

https://leetcode-cn.com/problems/design-circular-queue/submissions/

设计你的循环队列实现。 循环队列是一种线性数据结构，其 *** 作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下 *** 作：

MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。

class MyCircularQueue {
private int front;//队头指针
private int[]queue;//队列底层结构
private int size;//队列最大可存放元素数量
private int count;//现在拥有的元素；判断是否为满为空，
//数组实现

    public MyCircularQueue(int k) {
front = 0;
size = k;
queue = new int[k];
count=0;
//初始化队列
    }
    
    public boolean enQueue(int value) {
if(count==size){
    return false;
}
queue[(front+count)%size]=value;
//队尾进栈
count+=1;
return true;
    }
    
    public boolean deQueue() {
if(count==0)return false;
//队头出栈
front = (front+1)%size;
count-=1;
return true;
    }
    
    public int Front() {
if(count==0)return -1;

return queue[front];
    }
    
    public int Rear() {
        if(count==0)return -1;
int tail = (front+count-1)%size;
return queue[tail];
    }
    
    public boolean isEmpty() {
     return count==0;
    }
    
    public boolean isFull() {
return count==size;
    }
}

346数据流中的移动平均值

题目
给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算其所有整数的移动平均值。

https://leetcode-cn.com/problems/moving-average-from-data-stream/

示例:
MovingAverage m = new MovingAverage(3);
m.next(1) = 1
m.next(10) = (1 + 10) / 2
m.next(3) = (1 + 10 + 3) / 3
m.next(5) = (10 + 3 + 5) / 3

class MovingAverage{
queueq;
int total = 0;
int cap;
public:
MovingAverage(int size){
cap = size;
}
double next(int val){
sum+=val;
q.push(val);
if(q.size()>cap{
sum-=q.front();
q.pop();
}
return sum/double(q.size());
}
}

255用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种 *** 作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本 *** 作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些 *** 作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列 *** 作即可

https://leetcode-cn.com/problems/implement-stack-using-queues/

class MyStack {
Queueq = new linkedList();
Queuep = new linkedList();

    public MyStack() {

    }
    
    public void push(int x) {
if(q==null){
q.offer(x);
}else{
p.offer(x);
while(!q.isEmpty()){
    p.offer(q.poll());
}
Queuetemp = q;
q = p;
p = temp;

}
    }
    
    public int pop() {
return q.poll();
    }
    
    public int top() {
return q.peek();
    }
    
    public boolean empty() {
return q.isEmpty();
    }
}

队列与广度有限搜索

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

队列广度优先搜索实现步骤

graph 为存储无向图的字典变量，start 为开始节点。然后定义 visited 为标记访问节点的 set 集合变量。定义 q 为存放节点的队列。首先将起始节点放入队列 q中，即 q.put(start)。并将其标记为访问，即 visited.add(start)。从队列中取出第一个节点 node_u。访问节点 node_u，并对节点进行相关 *** 作（看具体题目要求）。遍历与节点 node_u 相连并构成边的节点 node_v。

如果 node_v 没有被访问过，则将 node_v 节点放入队列中，并标记访问，即 q.append(node_v)，visited.add(node_v)。 重复步骤 4 ~ 5，直到 q 为空。

import collections

def bfs(graph, start):
    visited = set(start)
    q = collections.deque([start])
    
    while q:
        node_u = q.popleft()
        print(node_u)
        for node_v in graph[node_u]:
            if node_v not in visited:
                visited.add(node_v)
                q.append(node_v)

广度优先搜索应用 463. 岛屿的周长

给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0表示水域。

网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长

迭代的方法

class Solution {
int[][] d = {{-1,0},{0,-1},{1,0},{0,1}};
//direction
int ans=0;
    public int islandPerimeter(int[][] grid) {

int m = grid.length;
int n = grid[0].length;
for(int i=0;i=m||ty<0||ty>=n||grid[tx][ty]==0){
//如果是边界或者水域有边的贡献
    cnt+=1;
}
            }
        ans+=cnt;
        }
        
    }
}
return ans;
    }
}

广度优先搜索的方法

class Solution {

int[][] d = {{0,1},{1,0},{-1,0},{0,-1}};
//方向

int m=0,n=0;
int [][]grid;
int perimeter=0;
    public int islandPerimeter(int[][] grid) {
if(grid==null||grid.length==0){
    return 0;
}
//如果岛屿为空，周长为0
this.grid = grid;
 m = grid.length;
 n = grid[0].length;


//寻找初始入队点

Queuequeue = new linkedList<>(); 

for(int r=0;r=m||c<0||c>=n);

}

} 

完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

class Solution {
    public int numSquares(int n) {
Queuequeue = new linkedList<>();
Set visited = new HashSet<>();
//记录访问过的节点
queue.offer(0);
visited.add(0);

int level=0;
//统计有多少层
while(!queue.isEmpty()){
//每一层的节点数
int size=queue.size();
level++;
//遍历当前层的所有节点
for(int i=0;in){
        break;
    }
    if(!visited.contains(nodevalue)){
        queue.offer(nodevalue);
        visited.add(nodevalue);
    }
    }
    }
    }
return level;
}
}

752. 打开转盘锁

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，‘0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

class Solution {
    public int openLock(String[] deadends, String target) {
int ds = deadends.length;
int ts = target.length();

if("0000".equals(target))return 0;

Queuequeue = new linkedList<>();
Setdead = new HashSet();
Setvisited = new HashSet();
for(String deadend:deadends){
    dead.add(deadend);
}
if(dead.contains("0000")){
    return -1;
}

//初始状态
int level=0;
queue.offer("0000");
visited.add("0000");
while(!queue.isEmpty()){
    level++;
    //层数

int cnt=queue.size();
for(int i=0;i get(String status){
        List ret = new ArrayList();
        char []array = status.toCharArray();
        for(int i=0;i<4;i++){
            char num = array[i];
            //保存
            array[i]=numPrev(num);//上一个
            ret.add(new String(array));
            array[i] = numSucc(num);//下一个
            ret.add(new String(array));
            array[i]=num;
            //恢复
        }
        return ret;
    }
}

542 01矩阵

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

class Solution {
    static int[][] d = {{-1,0},{0,-1},{1,0},{0,1}};
boolean[][] visited;//默认为false
int m ,n;
int [][] dist;
    public int[][] updateMatrix(int[][] mat) {
 m = mat.length;
 n = mat[0].length;
  dist=new int[m][n];
//每个距离
 visited = new boolean[m][n];
Queuequeue = new linkedList();
//将所有的0添加进初始队列中
for(int i=0;i=0&&i=0&&j 
322 零钱兑换 
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
 
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
 
你可以认为每种硬币的数量是无限的。
 
class Solution {
    public int coinChange(int[] coins, int amount) {
if(amount==0)return 0;
//特殊情况排除
int n = coins.length;
Queue sum = new linkedList<>();
boolean[] visited = new boolean[amount+1];


sum.offer(0);
visited[0]=true;
int level=1;
Arrays.sort(coins);

while(!sum.isEmpty()){
int len = sum.size();

for(int i=0;i 
剑指 Offer 13. 机器人的运动范围 
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
 
class Solution {

    public int movingCount(int m, int n, int k) {
int d[][] = {{0,1},{1,0}};
//方向

        if(k==0)return 1;

boolean[][] visited = new boolean[m][n];
Queue queue= new linkedList();


int sum=1;
queue.offer(new int[]{0,0});
visited[0][0]=true;



while(!queue.isEmpty()){


//层次 遍历
int[] coor =  queue.poll();
for(int i=0;i<2;i++){
    int x = coor[0]+d[i][0];
    int y = coor[1]+d[i][1];
   if(x>=m||y>=n||visited[x][y]){
continue;
}
if(help(x,y,k)){
    continue;
}
        //如果可以进入方格
    sum++;
    visited[x][y]=true;
    queue.offer(new int[]{x,y});
    }
}
return sum;
    }
    public boolean help(int i, int j, int k) {
        int count = 0;
        while (i != 0) {
            count += i % 10;
            i /= 10;
        }
        while (j != 0) {
            count += j % 10;
            j /= 10;
        }
        return count > k;
    }



  
}
 
引用出处
 
 
 
https://leetcode-cn.com/problems/design-circular-queue/
 https://github.com/itcharge/LeetCode-Py/blob/main/Assets/Course/Course-Web-02.md
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5710763.html