当前位置: 首页 > news >正文

【Java数据结构】优先级队列(堆)

【本节目标】
1. 掌握堆的概念及实现
2. 掌握 PriorityQueue 的使用

一. 优先级队列

1 概念

        前面学过队列,队列是一种先进先出 (FIFO) 的数据结构 ,但有些情况下, 操作的数据可能带有优先级,一般出队 列时,可能需要优先级高的元素先出队列 ,该中场景下,使用队列显然不合适,比如:在手机上玩游戏的时候,如果有来电,那么系统应该优先处理打进来的电话。
        在这种情况下,数据结构应该提供两个最基本的操作,一个是返回最高优先级对象,一个是添加新的对象 。这种数据结构就是优先级队列 (Priority Queue)

2. 优先级队列的模拟实现

        JDK1.8中的 PriorityQueue 底层使用了堆这种数据结构 ,而堆实际就是在完全二叉树的基础上进行了一些调整。

二、堆的概念

        如果有一个关键码的集合 K = {k0 k1 k2 kn-1} ,把它的所有元素 按完全二叉树的顺序存储方式存储 在一 个一维数组中 ,并满足: Ki <= K2i+1 Ki<= K2i+2 (Ki >= K2i+1 Ki >= K2i+2) i = 0 1 2… ,则 称为 小堆 ( 或大堆) 。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

1.堆的性质:

  • 堆中某个节点的值总是不大于或不小于其父节点的值;
  • 堆总是一棵完全二叉树。

2 堆的存储方式

        从堆的概念可知,堆是一棵完全二叉树,因此可以层序的规则采用顺序的方式来高效存储
注意:对于 非完全二叉树,则不适合使用顺序方式进行存储 ,因为为了能够还原二叉树, 空间中必须要存储空节 点,就会导致空间利用率比较低
将元素存储到数组中后,可以根据二叉树章节的性质 5 对树进行还原。假设 i 为节点在数组中的下标,则有:
  • 如果i0,则i表示的节点为根节点,否则i节点的双亲节点为 (i - 1)/2
  • 如果2 * i + 1 小于节点个数,则节点i的左孩子下标为2 * i + 1,否则没有左孩子
  • 如果2 * i + 2 小于节点个数,则节点i的右孩子下标为2 * i + 2,否则没有右孩子

3 堆的创建

1 堆向下调整

对于集合 { 27,15,19,18,28,34,65,49,25,37 } 中的数据,如果将其创建成堆呢?

仔细观察上图后发现:根节点的左右子树已经完全满足堆的性质,因此只需将根节点向下调整好即可
向下过程 ( 以小堆为例 )
1. parent 标记需要调整的节点, child 标记 parent 的左孩子 ( 注意: parent 如果有孩子一定先是有左孩子 )
2. 如果 parent 的左孩子存在,即 :child < size , 进行以下操作,直到 parent 的左孩子不存在
  • parent右孩子是否存在,存在找到左右孩子中最小的孩子,让child进行标记
  • parent与较小的孩子child比较,如果:
    • 否则:交换parent与较小的孩子child,交换完成之后,parent中大的元素向下移动,可能导致子
    • parent小于较小的孩子child,调整结束树不满足此性质,因此需要继续向下调整,即parent = childchild = parent*2+1; 然后继续2

    public void shiftDown(int parent,int usedSize){int child=parent*2+1;while(child<usedSize){// 如果右孩子存在,找到左右孩子中较大的孩子,用child进行标记if(child+1<usedSize&&elem[child]<elem[child+1]){child++;}if(elem[parent]<elem[child]){int tmp=elem[parent];elem[parent]=elem[child];elem[child]=tmp;}else {break;//如果孩子都比父母小}parent=child;child=2*parent+1;}}

注意:在调整以parent为根的二叉树时,必须要满足parent的左子树和右子树已经是堆了才可以向下调整。

时间复杂度分析:
最坏的情况 即图示的情况, 从根一路比较到叶子,比较的次数为完全二叉树的高度,即时间复杂度为O(logN)

2 堆的创建

那对于普通的序列 { 1,5,3,8,7,6 } ,即根节点的左右子树不满足堆的特性,又该如何调整呢?

 
 public void createHeap(){// 找倒数第一个非叶子节点,从该节点位置开始往前一直到根节点,遇到一个节点,应用向下调整for(int parent=(usedSize-1-1)/2;parent>=0;parent--){shiftDown(parent,usedSize);}}

3 建堆的时间复杂度

        因为堆是完全二叉树,而满二叉树也是完全二叉树,此处为了简化使用满二叉树来证明( 时间复杂度本来看的就是近似值,多几个节点不影响最终结果)

因此: 建堆的时间复杂度为 O(N)

4 堆的插入与删除

(1) 堆的插入
堆的插入总共需要两个步骤:
1. 先将元素放入到底层空间中 ( 注意:空间不够时需要扩容 )
2. 将最后新插入的节点向上调整,直到满足堆的性质
public boolean isFull(){if(elem.length>usedSize){return false;}else {return true;}
}
public void push(int val){//将结点插在最后,再向上调整建堆if(isFull()){elem= Arrays.copyOf(elem,2*elem.length);}elem[usedSize]=val;shiftUp(usedSize);usedSize++;
}
public void shiftUp(int child) {int parent=(child-1)/2;while(parent>=0){if(elem[parent]<elem[child]){int tmp=elem[parent];elem[parent]=elem[child];elem[child]=tmp;child=parent;parent=(child-1)/2;}else {break;}}
}

向上调整的时间复杂度为O(NlogN)

(2) 堆的删除
注意:堆的删除一定删除的是堆顶元素。 具体如下:
1. 将堆顶元素对堆中最后一个元素交换
2. 将堆中有效数据个数减少一个
3. 对堆顶元素进行向下调整

5 用堆模拟实现优先级队列

 public boolean isEmpty(){return usedSize==0;}public int poll( ) {if(isEmpty()){return -1;}int val=elem[0];swap(elem,0,usedSize-1);shiftDown(0,usedSize-1);usedSize--;return val;}public void swap(int[] elem,int start,int end){int tmp=elem[start];elem[start]=elem[end];elem[end]=tmp;}

常见习题:
1. 下列关键字序列为堆的是 :()
A: 100,60,70,50,32,65      B: 60,70,65,50,32,100    C: 65,100,70,32,50,60
D: 70,65,100,32,50,60      E: 32,50,100,70,65,60     F: 50,100,70,65,60,32
2. 已知小根堆为 8,15,10,21,34,16,12 ,删除关键字 8 之后需重建堆,在此过程中,关键字之间的比较次数是 ()
A: 1 B: 2 C: 3 D: 4
3. 最小堆 [0,3,2,5,7,4,6,8], 在删除堆顶元素 0 之后,其结果是 ()
A: [3 2 5 7 4 6 8]             B: [2 3 5 7 4 6 8]
C: [2 3 4 5 7 8 6]             D: [2 3 4 5 6 7 8]
[ 参考答案 ]
1.A                  2.C            3.C

三、常用接口介绍

1 PriorityQueue的特性

        Java集合框架中提供了 PriorityQueue PriorityBlockingQueue 两种类型的优先级队列, PriorityQueue 是线 程不安全的, PriorityBlockingQueue 是线程安全的 ,本文主要介绍 PriorityQueue

关于 PriorityQueue 的使用要注意:
  1. 使用时必须导入PriorityQueue所在的包,即: importjava.util.PriorityQueue;
  2. PriorityQueue中放置的元素必须要能够比较大小,不能插入无法比较大小的对象,否则会抛出 ClassCastException异常
  3. 不能插入null对象,否则会抛出NullPointerException
  4. 没有容量限制,可以插入任意多个元素,其内部可以自动扩容
  5. 插入和删除元素的时间复杂度为O(logN)
  6. PriorityQueue底层使用了堆数据结构
  7. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素

2 PriorityQueue常用接口介绍

1. 优先级队列的构造

此处只是列出了 PriorityQueue 中常见的几种构造方式,其他的学生们可以参考帮助文档。
 
(1) PriorityQueue()

(2) PriorityQueue(int  initialCapacity)

(3) PriorityQueue(Collection<? extends E> c)

观察上述三个构造方法可得:都调用了带两个参数的构造方法

    static void TestPriorityQueue(){
// 创建一个空的优先级队列,底层默认容量是11PriorityQueue<Integer> q1 = new PriorityQueue<>();
// 创建一个空的优先级队列,底层的容量为initialCapacityPriorityQueue<Integer> q2 = new PriorityQueue<>(100);ArrayList<Integer> list = new ArrayList<>();list.add(4);list.add(3);list.add(2);list.add(1);
// 用ArrayList对象来构造一个优先级队列的对象
// q3中已经包含了三个元素PriorityQueue<Integer> q3 = new PriorityQueue<>(list);System.out.println(q3.size());System.out.println(q3.peek());}

注意:默认情况下,PriorityQueue 队列是小堆,如果需要大堆需要用户提供比较器
// 用户自己定义的比较器:直接实现 Comparator 接口,然后重写该接口中的 compare 方法即可
 
 public int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}
}
public class Test {public static void main(String[] args) {PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(new intCom());priorityQueue.offer(1);priorityQueue.offer(2);priorityQueue.offer(3);System.out.println(priorityQueue.peek());}
}

此时创建出来的就是一个大堆。

2. 插入/删除/获取优先级最高的元素

函数名功能介绍
boolean offer(E e)插入元素e,插入成功返回true,如果e对象为空,抛出NullPointerException异常,时间复杂度O(logN),注意:空间不够时候会进行扩容
E peek()获取优先级最高的元素,如果优先级队列为空,返回null
E poll()移除优先级最高的元素并返回,如果优先级队列为空,返回null
int size()获取有效元素的个数
void clear()清空
boolean isEmpty()检测优先级队列是否为空,空返回true
 
 static void TestPriorityQueue2(){int[] arr = {4,1,9,2,8,0,7,3,6,5};
// 一般在创建优先级队列对象时,如果知道元素个数,建议就直接将底层容量给好
// 否则在插入时需要不多的扩容
// 扩容机制:开辟更大的空间,拷贝元素,这样效率会比较低PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);for (int e: arr) {q.offer(e);}System.out.println(q.size()); // 打印优先级队列中有效元素个数System.out.println(q.peek()); // 获取优先级最高的元素
// 从优先级队列中删除两个元素之和,再次获取优先级最高的元素q.poll();q.poll();System.out.println(q.size()); // 打印优先级队列中有效元素个数System.out.println(q.peek()); // 获取优先级最高的元素q.offer(0);System.out.println(q.peek()); // 获取优先级最高的元素
// 将优先级队列中的有效元素删除掉,检测其是否为空q.clear();if(q.isEmpty()){System.out.println("优先级队列已经为空!!!");
注意:以下是 JDK 1.8 中, PriorityQueue 的扩容方式:
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;private void grow(int minCapacity) {int oldCapacity = queue.length;
// Double size if small; else grow by 50%int newCapacity = oldCapacity + ((oldCapacity < 64) ?(oldCapacity + 2) :(oldCapacity >> 1));
// overflow-conscious codeif (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);queue = Arrays.copyOf(queue, newCapacity);}private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;}

优先级队列的扩容说明:

  • 如果容量小于64时,是按照oldCapacity2倍方式扩容的
  • 如果容量大于等于64,是按照oldCapacity1.5倍方式扩容的
  • 如果容量超过MAX_ARRAY_SIZE,按照MAX_ARRAY_SIZE来进行扩容

3 oj练习

top-k 问题:最大或者最小的前 k 个数据。比如:世界前 500 强公司

方法1:把所有元素都放去堆排序,然后取前K个
 
class Solution {public int[] smallestK(int[] arr, int k) {PriorityQueue<Integer> priorityQueue=new PriorityQueue<>();//O(NlogN)for(int i:arr){priorityQueue.offer(i);}int[] elem=new int[k];//O(klogN)for(int i=0;i<k;i++){elem[i]=priorityQueue.poll();}return elem;}
}

时间复杂度:O(NlogN+klogN)=O((N+k)logN)

该解法只是PriorityQueue的简单使用,并不是topK最好的做法,那topk该如何实现?下面介绍:


方法2:把前K个元素创建为大根堆,遍历剩下N-K个元素,和堆顶元素相比较,如果比堆顶元素小,就把堆顶元素删除,插入当前元素

  class intCom implements Comparator<Integer>{public int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}}
class Solution {public int[] smallestK(int[] arr, int k) {int[] elem=new int[k];if(k==0||arr==null){return elem;}PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(new intCom());//O(klogk)for(int i=0;i<k;i++){priorityQueue.offer(arr[i]);}//O((N-k)logk)for(int j=k;j<arr.length;j++){int peekval=priorityQueue.peek();if(arr[j]<peekval){priorityQueue.poll();priorityQueue.offer(arr[j]);}}for(int i=0;i<k;i++){elem[i]=priorityQueue.poll();}return elem;}
}

四. 堆的应用

1 PriorityQueue的实现

用堆作为底层结构 封装优先级队列

2 堆排序

堆排序即利用堆的思想来进行排序,总共分为两个步骤:
    public void shiftDown(int parent,int usedSize){int child=parent*2+1;while(child<usedSize){// 如果右孩子存在,找到左右孩子中较大的孩子,用child进行标记if(child+1<usedSize&&elem[child]<elem[child+1]){child++;}if(elem[parent]<elem[child]){int tmp=elem[parent];elem[parent]=elem[child];elem[child]=tmp;}else {break;//如果孩子都比父母小}parent=child;child=2*parent+1;}}

1. 建堆

升序:建 大堆
降序:建小堆
2. 利用堆删除思想来进行排序
建堆和堆删除中都用到了向下调整,因此掌握了向下调整,就可以完成堆排序。

时间复杂度:O(NlogN)
常见习题:

1. 一组记录排序码为 (5 11 7 2 3 17), 则利用堆排序方法建立的初始堆为 ()
A: (11 5 7 2 3 17) B: (11 5 7 2 17 3) C: (17 11 7 2 3 5)
D: (17 11 7 5 3 2) E: (17 7 11 3 5 2) F: (17 7 11 3 2 5)
答案: C

3 Top-k问题

TOP-K 问题:即求数据集合中前 K 个最大的元素或者最小的元素,一般情况下数据量都比较大
         比如:专业前10 名、世界 500 强、富豪榜、游戏中前 100 的活跃玩家等。
        对于Top-K 问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了 ( 可能数据都不能一下子全部加载到内存中) 。最佳的方式就是用堆来解决,基本思路如下:
1. 用数据集合中前 K 个元素来建堆
  • k个最大的元素,则建小堆
  • k个最小的元素,则建大堆
2. 用剩余的 N-K 个元素依次与堆顶元素来比较,不满足则替换堆顶元素
        将剩余N-K 个元素依次与堆顶元素比完之后,堆中剩余的 K 个元素就是所求的前 K 个最小或者最大的元素。
时间复杂度:O((N-k)logk)  树高logk

相关文章:

【Java数据结构】优先级队列(堆)

【本节目标】 1. 掌握堆的概念及实现 2. 掌握 PriorityQueue 的使用 一. 优先级队列 1 概念 前面学过队列&#xff0c;队列是一种先进先出 (FIFO) 的数据结构 &#xff0c;但有些情况下&#xff0c; 操作的数据可能带有优先级&#xff0c;一般出队 列时&#xff0c;可…...

图书个性化推荐系统|基于springBoot的图书个性化推荐系统设计与实现(附项目源码+论文+数据库)

私信或留言即免费送开题报告和任务书&#xff08;可指定任意题目&#xff09; 目录 一、摘要 二、相关技术 三、系统设计 四、数据库设计 五、核心代码 六、论文参考 七、源码获取 一、摘要 本论文主要论述了如何使用JAVA语言开发一个图书个性化推荐系统&…...

通用车牌正则校验

要编写一个正则表达式来包含所有类型的车牌号&#xff0c;我们需要考虑以下几种常见的车牌类型&#xff1a; 1. 普通汽车车牌&#xff08;蓝牌/黄牌&#xff09; 规则&#xff1a;1个汉字 1个字母 5个字母或数字示例&#xff1a;京A12345、粤B5678X 2. 新能源车牌&#xf…...

使用 SSH 连接 GitLab 的常见问题及解决方案

使用 SSH 连接 GitLab 的常见问题及解决方案 在使用 SSH 连接到 GitLab 服务器时&#xff0c;可能会遇到类似于以下的错误信息&#xff1a; git192.168.xx.xxx: Permission denied (publickey).这个错误通常表示 SSH 无法验证你的公钥&#xff0c;导致无法访问 GitLab 仓库。…...

泛微E9开发 校验日期型字段是否符合要求

校验日期型字段是否符合要求 1、需求分析及展示效果1.1、需求确认1.2、展示效果 2、实现方法3、扩展知识——js日期相关函数 1、需求分析及展示效果 1.1、需求确认 “填报时间”是一个日期型字段&#xff0c;用户提出需求只能选择每个月的第二个周二&#xff0c;选择其他日期…...

ubuntu安装Vim和net-tools和htop

合并安装&#xff0c;快捷方便 sudo apt update sudo apt install net-tools vim htop在Ubuntu中安装Vim可以通过终端使用以下命令完成&#xff1a; sudo apt update sudo apt install vim这两条命令首先更新了本地的包索引&#xff0c;然后安装了Vim文本编辑器。 安装完成后…...

每天10个js面试题(六)

1、js数组方法&#xff1f; Array.push()此方法是在数组的后面添加新加元素&#xff0c;此方法改变了数组的长度Array.pop()此方法在数组后面删除最后一个元素&#xff0c;并返回数组&#xff0c;此方法改变了数组的长度 Array.shift()此方法在数组后面删除第一个元素&#xf…...

AIGC技术的学习 系列二

文章目录 前言一、AIGC是什么?1.1. 基本概念1.2机器学习分类二、 语言模型2.1. 基于统计的语言模型。2.2. 基于神经网络的语言模型。2.3. 基于预训练机制的的语言模型/大语言模型三、读入数据3.1. 不得不说的Transformer3.2. 影响力3.3. 根据人类反馈的强化学习3.4. 生成式AI3…...

惊艳!AI模型DIAMOND可模拟《反恐精英》,单张RTX 3090就能运行

最近&#xff0c;研究人员开发了一种名为 DIAMOND&#xff08;Diffusion for World Modelling&#xff09;的 AI 模型&#xff0c;它能够在神经网络中模拟著名的电脑游戏《反恐精英:全球攻势》(CS:GO)。 这个模型在一张 Nvidia RTX3090显卡上运行&#xff0c;能够达到每秒10帧…...

中波长线天线耦合的一个方法

围绕窗外墙外牵了10米的室外天线。 短波&#xff0c;fm都是很简单&#xff0c;一个夹子直接夹在拉杆天线上面&#xff0c;效果已经很好。 今天偶尔听到中波前面大约510khz的地方有个摩尔斯码。是成都附近机场的NDB。这个平时要在楼顶或者很空旷的地方才能收到。音量比较小&am…...

Java基础(6)

深拷贝和浅拷贝区别了解吗&#xff1f;什么是引用拷贝&#xff1f;关于深拷贝和浅拷贝区别&#xff0c;我这里先给结论&#xff1a;浅拷贝&#xff1a;浅拷贝会在堆上创建一个新的对象&#xff08;区别于引用拷贝的一点&#xff09;&#xff0c;不过&#xff0c;如果原对象内部…...

[JAVAEE] 线程安全问题

目录 一. 什么是线程安全 二. 线程安全问题产生的原因 三. 线程安全问题的解决 3.1 解决修改操作不是原子性的问题 > 加锁 a. 什么是锁 b. 没有加锁时 c. 加锁时 d. 死锁 e. 避免死锁 3.2 解决内存可见性的问题 > volatile关键字 (易变的, 善变的) a. 不加…...

k8s 集群给用户生成 kubeconfig 文件

在 k8s 集群的 RBAC 里有用到用户、组的概念&#xff0c;但是它又不直接管理这些资源&#xff0c;而是通过外部身份验证机制&#xff08;Authentication Mechanisms&#xff09;来管理和定义的&#xff0c;比如证书进行签名时&#xff0c;将其配置为 Subject: O system:master…...

(八)Proteus仿真STM32单片机GPIO驱动数码管

1&#xff0c;参考上篇&#xff0c;将LED点阵屏更换成数码管如下图 2&#xff0c;修改驱动函数&#xff0c;数组seg[14]前10个是0-9数字的编码&#xff0c;后四个是空格&#xff0c;点&#xff0c;横线&#xff0c;下划线 char seg_decode(char num)//数字解码 {const char se…...

Python进阶知识1

Python函数 定义一个函数 1.什么是函数&#xff1a;函数是可以重复执行的语句块&#xff0c;可以重复调用 2.作用&#xff1a;用于封装语句块, 提高代码的重用性。 函数是面向过程编程的最小单位 def 语句 1.作用&#xff1a;用来定义&#xff08; 创建&#xff09;函数 2…...

单片机设计|基于STM32实现具有室内定位功能的智能手环的设计

作者简介&#xff1a;Java领域优质创作者、CSDN博客专家 、CSDN内容合伙人、掘金特邀作者、阿里云博客专家、51CTO特邀作者、多年架构师设计经验、多年校企合作经验&#xff0c;被多个学校常年聘为校外企业导师&#xff0c;指导学生毕业设计并参与学生毕业答辩指导&#xff0c;…...

计算机网络——运输层(可靠传输、超时重传、选择确认、流量控制和拥塞控制、TCP连接和释放)

TCP可靠传输的实现 我们假定数据传输只在一个方向进行&#xff0c;即A发送数据&#xff0c;B给出确认。这样的好处是使讨论限于两个窗口&#xff0c;即发送方A的发送窗口和接收方B的接收窗口。 以字节为单位滑动窗口 发送方构造窗口 窗口前沿和后沿的移动情况 描述发送窗口的状…...

Web安全实践

前言 安全无小事&#xff0c;成败在细节&#xff0c;网络有风险&#xff0c;灾难弹指间。 安全一般情况下看不见&#xff0c;在你周围漂浮着&#xff0c;显现出来后&#xff0c;往往会刻骨铭心。正因为安全看不见&#xff0c;所以往往不受重视&#xff0c;因为感知到的概率真…...

【算法篇】动态规划类(2)——01背包+完全背包(笔记)

目录 一、理论基础 1. 问题类型 2. 01背包问题 3. 完全背包问题 4. 解题步骤 &#xff08;1&#xff09;确定dp数组&#xff08;dp table&#xff09;以及下标的含义。 &#xff08;2&#xff09;确定递推公式。 &#xff08;3&#xff09;dp数组如何初始化。 &#x…...

基于SpringBoot的“社区医院管理服务系统”的设计与实现(源码+数据库+文档+PPT)

基于SpringBoot的“社区医院管理服务系统”的设计与实现&#xff08;源码数据库文档PPT) 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;SpringBoot 工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 系统展示 系统首页界面图 用户注册界面图 医生界面…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

基于SpringBoot在线拍卖系统的设计和实现

摘 要 随着社会的发展&#xff0c;社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统&#xff0c;主要的模块包括管理员&#xff1b;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...

4. TypeScript 类型推断与类型组合

一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)

macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 &#x1f37a; 最新版brew安装慢到怀疑人生&#xff1f;别怕&#xff0c;教你轻松起飞&#xff01; 最近Homebrew更新至最新版&#xff0c;每次执行 brew 命令时都会自动从官方地址 https://formulae.…...

Xela矩阵三轴触觉传感器的工作原理解析与应用场景

Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知&#xff0c;帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量&#xff0c;能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度&#xff0c;还为机器人、医疗设备和制造业的智…...

算法—栈系列

一&#xff1a;删除字符串中的所有相邻重复项 class Solution { public:string removeDuplicates(string s) {stack<char> st;for(int i 0; i < s.size(); i){char target s[i];if(!st.empty() && target st.top())st.pop();elsest.push(s[i]);}string ret…...

41道Django高频题整理(附答案背诵版)

解释一下 Django 和 Tornado 的关系&#xff1f; Django和Tornado都是Python的web框架&#xff0c;但它们的设计哲学和应用场景有所不同。 Django是一个高级的Python Web框架&#xff0c;鼓励快速开发和干净、实用的设计。它遵循MVC设计&#xff0c;并强调代码复用。Django有…...

C#中用于控制自定义特性(Attribute)

我们来详细解释一下 [AttributeUsage(AttributeTargets.Class, AllowMultiple false, Inherited false)] 这个 C# 属性。 在 C# 中&#xff0c;Attribute&#xff08;特性&#xff09;是一种用于向程序元素&#xff08;如类、方法、属性等&#xff09;添加元数据的机制。Attr…...