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

数据结构和算法笔记5:堆和优先队列

今天来讲一下堆,在网上看到一个很好的文章,不过它实现堆是用Golang写的,我这里打算用C++实现一下:

Golang: Heap data structure

1. 基本概念

  • 满二叉树(二叉树每层节点都是满的):

在这里插入图片描述

  • 完全二叉树:叶子节点只出现在最后一层或倒数第二层,并且节点都是向左聚拢
  • 非完全二叉树:下面的二叉树不满足完全二叉树的节点都向左聚拢,所以是非完全二叉树

在这里插入图片描述

堆也是一颗完全二叉树。

  • 小顶堆:根节点是最小值,并且子节点大于等于父节点
  • 大顶堆:根节点是最大值,并且子节点小于等于父节点
    在这里插入图片描述

由于树的特性,堆可以用数组索引的形式表示,以小顶堆为例,在下面的小顶堆里,依次从上到下从左往右给节点编号,根节点的编号是0,:

在这里插入图片描述

对应的数组为:

在这里插入图片描述
对比数组和堆,堆的索引有以下的性质:

  1. 根节点索引是0
  2. 若当前节点索引为i,如果它有父节点,父节点的索引是(i-1)/2(C++向下取整)
  3. 若当前节点索引为i,如果它有左节点,左节点的索引是2*i+1,如果它有右节点,右节点的索引是2*i+2
  4. 设数组的长度为len,最后一个非叶子节点的索引是(len-2)/2,比如上面的K是9,最后一个非叶子节点的索引是(9-2)/2=3
    在这里插入图片描述

2. 堆的基本操作

C++有heapn内置函数来实现,具体看c++重拾 STL之heap(堆)。这里我们讲解原理,下面以小顶堆为例描述堆的相关操作

2.0 交换节点操作

我们先定义交换节点的操作,为后面调整为堆做准备:

void HeapSwap(vector<int> &minHeap, int curIndex, int swapIndex)
{int t = minHeap[curIndex];minHeap[curIndex] = minHeap[swapIndex];minHeap[swapIndex] = t;
}

2.1 下浮操作

下浮操作是通过下浮的方式把一个完全二叉树调整为堆,具体的步骤是将它与它的左儿子,右儿子比较大小,如果不满足小顶堆的性质(当前节点的值大于等于左右孩子的节点的值),当前节点需要与左右孩子的最小值节点交换位置(否则不满足堆的性质),递归的完成这个过程。(时间复杂度是log(n))

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
我们定义一个swapIndex,记录需要交换调整的节点索引,如果需要调整,这个索引是当前节点和左右子节点索引的最小值,这个过程要注意判断边界条件:

void HeapSiftDown(vector<int> &minHeap, int curIndex)
{int leftChildIndex = 2 * curIndex + 1;  // 左孩子节点的索引int rightChildIndex = 2 * curIndex + 2; // 右孩子节点的索引int swapIndex = curIndex;               // 定义调整的节点索引// 判断左右孩子是否小于当前元素,如果是把swapIndex赋值为孩子索引if (leftChildIndex < minHeap.size() && minHeap[leftChildIndex] < minHeap[swapIndex])swapIndex = leftChildIndex;if (rightChildIndex < minHeap.size() && minHeap[rightChildIndex] < minHeap[swapIndex])swapIndex = rightChildIndex;// 判断交换索引和当前索引是不是一样,如果不一样说明要交换,然后继续SiftDown,直到到最后一个节点if (curIndex != swapIndex){HeapSwap(minHeap, curIndex, swapIndex);HeapSiftDown(minHeap, swapIndex);}
}

2.2 上浮操作

上浮操作是通过上浮的方式把一个完全二叉树调整为堆,具体的步骤是将它与它的父亲节点比较大小,如果不满足小顶堆的性质(父亲的节点的值大于等于当前节点的值),当前节点与父亲节点交换位置(否则不满足堆的性质),递归的完成这个过程。(时间复杂度是log(n))

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
我们类似上浮操作定义一个swapIndex,记录需要交换调整的节点索引,如果需要调整,这个索引是父亲节点的索引,这个过程要注意判断边界条件:

void HeapSiftUp(vector<int> &minHeap, int curIndex)
{int parentIndex = (curIndex - 1) / 2;//父亲节点的索引int swapIndex = curIndex;// 定义调整的节点索引// 判断左右孩子是否小于当前元素,如果是把swapIndex赋值为孩子索引if (parentIndex >= 0 && minHeap[curIndex] < minHeap[parentIndex])swapIndex = parentIndex;// 判断交换索引和当前索引是不是一样,如果不一样说明要交换,然后继续SiftUp,直到到最后一个节点if (curIndex != swapIndex){HeapSwap(minHeap, curIndex, swapIndex);HeapSiftUp(minHeap, swapIndex);}
}

2.3 给定一个数组建堆

建堆有上浮和下浮两种方法:

如果是下浮的方法,可以直接从最后一个不是叶节点的节点开始往上下浮(叶子节点没有左右孩子一定不需要交换)。这里使用了前面堆索引性质的第四条:

设数组的长度为len,最后一个非叶子节点的索引是(len-2)/2

void HeapBuild(vector<int> &array)
{int lastNoLeafIndex = (array.size() - 2) / 2;for (int i = lastNoLeafIndex; i >= 0; i--)//从最后一个不是叶节点的节点开始往上下浮HeapSiftDown(array, i);
}

如果是上浮的方法,则从索引为1节点开始往下上浮(根节点没有父亲节点一定不需要交换)。

void HeapBuild(vector<int> &array)
{for (int i = 1; i < array.size(); ++i)//从索引为1节点开始往下上浮HeapSiftUp(array, i);
}

使用下浮建堆的时间复杂度是O(n),而使用上浮建堆的时间复杂度是O(nlogn),建议使用下浮建堆。关于复杂度参考How can building a heap be O(n) time complexity?
在这里插入图片描述

2.4 Pop操作

pop操作是把根节点弹出返回,并重新调整剩余元素构成的数组为堆,数组的长度为len,这里我们把根节点和最后一个节点交换,中间要保留根节点的值,然后把数组调整为len-1(因为弹出一个元素了),重新用下浮调整为堆,然后返回堆的根节点的值。时间复杂度是log(n)

int HeapPop(vector<int> &minHeap)
{int value = minHeap[0];//保留堆的根节点的值int len = minHeap.size();//记录堆的大小HeapSwap(minHeap, 0, len - 1);//把堆的根节点和最后一个节点交换minHeap.resize(len - 1);//调整数组长度为len-1HeapSiftDown(minHeap, 0);//下浮调整为堆return value;//返回堆的根节点的值
}

2.5 Push操作

push操作是在数组末尾加入元素num,然后重新调整成堆。相比pop操作,push操作就简单很多了,我们先在数组末尾加入元素num,然后从最后一个元素的索引开始使用上浮即可。时间复杂度是log(n)

void HeapPush(vector<int> &minHeap, int num)
{minHeap.push_back(num);//在数组末尾加入元素numHeapSiftUp(minHeap, minHeap.size() - 1);//从最后一个元素的索引开始使用上浮
}

测试:

完整代码:

#include <iostream>
#include <vector>
using namespace std;void HeapSiftDown(vector<int> &minHeap, int curIndex);
void HeapSiftUp(vector<int> &minHeap, int curIndex);
void HeapSwap(vector<int> &minHeap, int curIndex, int swapIndex);
void HeapBuild(vector<int> &array);
void HeapPush(vector<int> &minHeap, int num);void HeapBuild(vector<int> &array)
{int lastNoLeafIndex = (array.size() - 2) / 2;for (int i = lastNoLeafIndex; i >= 0; i--)HeapSiftDown(array, i);
}void HeapSiftDown(vector<int> &minHeap, int curIndex)
{int leftChildIndex = 2 * curIndex + 1; int rightChildIndex = 2 * curIndex + 2;int swapIndex = curIndex;               if (leftChildIndex < minHeap.size() && minHeap[leftChildIndex] < minHeap[swapIndex])swapIndex = leftChildIndex;if (rightChildIndex < minHeap.size() && minHeap[rightChildIndex] < minHeap[swapIndex])swapIndex = rightChildIndex;if (curIndex != swapIndex){HeapSwap(minHeap, curIndex, swapIndex);HeapSiftDown(minHeap, swapIndex);}
}void HeapSiftUp(vector<int> &minHeap, int curIndex)
{int parentIndex = (curIndex - 1) / 2;int swapIndex = curIndex;if (parentIndex >= 0 && minHeap[curIndex] < minHeap[parentIndex])swapIndex = parentIndex;if (curIndex != swapIndex){HeapSwap(minHeap, curIndex, swapIndex);HeapSiftUp(minHeap, swapIndex);}
}
void HeapSwap(vector<int> &minHeap, int curIndex, int swapIndex)
{int t = minHeap[curIndex];minHeap[curIndex] = minHeap[swapIndex];minHeap[swapIndex] = t;
}int HeapPop(vector<int> &minHeap)
{int value = minHeap[0];int len = minHeap.size();HeapSwap(minHeap, 0, len - 1);minHeap.resize(len - 1);HeapSiftDown(minHeap, 0);return value;
}void HeapPush(vector<int> &minHeap, int num)
{minHeap.push_back(num);HeapSiftUp(minHeap, minHeap.size() - 1);
}int main()
{vector<int> array{9, 31, 40, 22, 10, 15, 1, 25, 91};cout << "The origin array is " << endl;for (auto &t : array)cout << t << " ";cout << endl<< "---------------------------------------------------" << endl;// 建堆HeapBuild(array);cout << "After build the heap, the array is " << endl;for (auto &t : array)cout << t << " ";cout << endl<< "---------------------------------------------------" << endl;// pop元素int top = HeapPop(array);cout << "The pop value is " << top << endl;cout << "After pop, the array is " << endl;for (auto &t : array)cout << t << " ";cout << endl<< "---------------------------------------------------" << endl;// push元素HeapPush(array, 1);cout << "After push, the array is " << endl;for (auto &t : array)cout << t << " ";cout << endl<< "---------------------------------------------------" << endl;
}

在这里插入图片描述

可以自行印证上面满足小顶堆。大顶堆的思路和小顶堆的思路差不多。读者可以自己实现一下。

3. 堆的相关使用

3.1 堆排序

堆排序基本的思路是:

  1. 初始化:数组建堆
  2. 数组的根节点和堆的最后一个节点交换
  3. 剩余元素重新排成堆(堆的长度减1),然后继续第2步操作直到数组的长度为1

这里也放一个算法导论的截图(不过它的根节点的索引是1),思路是差不多的:

在这里插入图片描述

我们这里使用小顶堆,小顶堆的根节点是最小值,每次第2步和后面的节点做交换,所以最后排序是从大到小(最小值根节点都放到数组的后面)。

前面的建堆是对整个数组来说的,但是对于堆排序,我们需要划定要排序数组的范围,所以我们对建堆和下浮两个操作另外定义一个函数:

  • HeapSiftDown函数

注意这里的数组越界处理改为了传入的heapLength,我们只需要对0-heapLength-1范围的数组做下浮的操作

void HeapSiftDown(vector<int> &minHeap, int curIndex, int heapLength)
{int leftChildIndex = 2 * curIndex + 1;  // 左孩子节点的索引int rightChildIndex = 2 * curIndex + 2; // 右孩子节点的索引int swapIndex = curIndex;               // 定义和当前索引交换的索引// 判断左右孩子是否小于当前元素,如果是把swapIndex换给孩子索引,注意这里的数组越界处理改为了传入的heapLength if (leftChildIndex < heapLength && minHeap[leftChildIndex] < minHeap[swapIndex])swapIndex = leftChildIndex;if (rightChildIndex < heapLength && minHeap[rightChildIndex] < minHeap[swapIndex])swapIndex = rightChildIndex;// 判断交换索引和当前索引是不是一样,如果不一样说明要交换,继续SiftDown,直到到最后一个节点if (curIndex != swapIndex){HeapSwap(minHeap, curIndex, swapIndex);HeapSiftDown(minHeap, swapIndex, heapLength);}
}
  • HeapBuild函数

注意这里的计算最后一个非叶子节点的索引使用了传入的heapLength,相当于对0-heapLength-1范围的数组建堆

void HeapBuild(vector<int> &array, int heapLength)
{int lastNoLeafIndex = (heapLength - 2) / 2;//注意这里最后一个非叶子节点的索引使用的是传入的heapLengthfor (int i = lastNoLeafIndex; i >= 0; i--)HeapSiftDown(array, i, heapLength);
}

OK我们可以写堆排序了,传入一个数组:

void HeapSort(vector<int> &array)
{int heapLength = array.size();//建堆的长度int len = array.size();//数组的长度HeapBuild(array, heapLength);for (int i = len - 1; i >= 1; --i)//遍历到索引1就行,索引0不需要遍历,因为只有一个数了{HeapSwap(array, 0, i);//把索引0(根节点)和索引i节点交换heapLength--;//建堆的长度减1HeapBuild(array, heapLength);//再次对0~heapLength-1的数组建堆}
}

测试堆排序

#include <iostream>
#include <vector>
using namespace std;
void HeapBuild(vector<int> &array, int heapLength);
void HeapSort(vector<int> &array);void HeapBuild(vector<int> &array, int heapLength)
{int lastNoLeafIndex = (heapLength - 2) / 2;//注意这里最后一个非叶子节点的索引使用的是传入的heapLengthfor (int i = lastNoLeafIndex; i >= 0; i--)HeapSiftDown(array, i, heapLength);
}
void HeapSort(vector<int> &array)
{int heapLength = array.size();//建堆的长度int len = array.size();//数组的长度HeapBuild(array, heapLength);for (int i = len - 1; i >= 1; --i)//遍历到索引1就行,索引0不需要遍历,因为只有一个数了{HeapSwap(array, 0, i);//把索引0(根节点)和索引i节点交换heapLength--;//建堆的长度减1HeapBuild(array, heapLength);//再次对0~heapLength-1的数组建堆}
}
int main()
{vector<int> array{9, 31, 40, 22, 10, 15, 1, 25, 91};cout << "The origin array is " << endl;for (auto &t : array)cout << t << " ";cout << endl<< "---------------------------------------------------" << endl;// sort元素HeapSort(array);cout << "After sort, the array is " << endl;for (auto &t : array)cout << t << " ";return 0;
}

可以看到从大到小进行了排序,如果用大顶堆,就是从小到大排序。
在这里插入图片描述

3.2 优先队列

优先级队列虽然也叫队列,但是和普通的队列还是有差别的。普通队列出队顺序只取决于入队顺序,而优先级队列的出队顺序总是按照元素自身的优先级。可以理解为,优先级队列是一个排序后的队列。

堆和优先级队列非常相似,一个堆就可以看作一个优先级队列。往优先级队列中插入一个元素,就相当于往堆中插入一个元素;从优先级队列中取出优先级最高的元素,就相当于取出堆顶元素(大顶堆–最大值;小顶堆–最小值)。不过优先级我们还可以自己额外定义。C++有priority_queue来实现,具体可以看c++优先队列(priority_queue)用法详解。

所以优先队列有两个操作,分别是pop弹出和push加入,pop即弹出根节点,push即把新的元素加入优先队列,两种操作过后要保证剩余的元素构成的还是一个堆。直接使用前面所说的pop和push操作即可。

4. 典型例题

347. 前 K 个高频元素

在这里插入图片描述
前K个元素,先用哈希表记录元素的频率,然后可以使用小根堆,如果队列元素超过K可以弹出根节点(最小的元素),遍历完以后,队列里剩下的就是前K大的元素。

class Solution {
public:static bool cmp(pair<int, int>& a, pair<int, int>& b){return a.second > b.second;}vector<int> topKFrequent(vector<int>& nums, int k) {vector<int> ans;unordered_map<int, int> mp;for (auto& t: nums)mp[t]++;priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> que(cmp);for (auto it = mp.begin(); it != mp.end(); ++it){que.push(*it);if (que.size() > k)que.pop();}while (!que.empty()){ans.push_back(que.top().first);que.pop();}return ans;}
};

关于priority_queue的比较函数cmp也可以使用仿函数:

class Solution {
public:class cmp {public:bool operator() (const pair<int, int> &lhs, const pair<int, int> &rhs) {return lhs.second > rhs.second;}};vector<int> topKFrequent(vector<int>& nums, int k) {vector<int> ans;unordered_map<int, int> mp;for (auto& t: nums)mp[t]++;priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> que;for (auto it = mp.begin(); it != mp.end(); ++it){que.push(*it);if (que.size() > k)que.pop();}while (!que.empty()){ans.push_back(que.top().first);que.pop();}return ans;}
};

内置类型比如int的话cmp可以直接使用greater<int>(小根堆)和less<int>(大根堆),如果比较自定义的Node类型,可以在Node里重载<

#include <queue>
#include <iostream>
using namespace std;
struct Node
{int x, y;bool operator<(const Node &rhs) const{return this->x > rhs.x; // 用x比较,这里是>,是小根堆}
};
int main()
{priority_queue<Node> que;que.push(Node{1, 2});que.push(Node{2, 1});que.push(Node{4, 2});while (!que.empty()){cout << que.top().x << " " << que.top().y << endl;que.pop();}
}

在这里插入图片描述

215. 数组中的第K个最大元素

和上题类似,我们使用一个小顶堆,遍历完整个数组,最后剩下的根节点就是第K大元素了。

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int, vector<int>, greater<int>> que;for (auto& t:nums){que.push(t);if (que.size() > k){que.pop();}}return que.top();}
};

295. 数据流的中位数

维护一个大根堆和一个小根堆,大根堆queMin记录小于等于中位数的那些数,小根堆queMax记录大于中位数的那些数。

大根堆queMin: 大<-小
小根堆queMax:小->大

findMedian:小根堆的元素个数比大根堆的元素的个数大1或两者相等,如果是奇数直接取小根堆的根节点元素,如果是偶数取两个堆的根节点的平均值(注意返回是double,所以除以2不行,要除以2.0)

addNum:由于小根堆的元素个数比大根堆元素个数大1或两者相等,所以我们优先处理小根堆:

  • 如果queMax的维度和queMin的维度是一样的,那么先往queMax里push num,然后queMin添加queMax的堆顶元素,queMax弹出元素。
  • 如果queMax的维度比queMin的维度小(这时候是小1),那么先往queMin里push num,然后queMax添加queMin的堆顶元素,queMin弹出元素。
class MedianFinder {
public:MedianFinder() {}void addNum(int num) {if (queMin.size() == queMax.size()){queMax.push(num);queMin.push(queMax.top());queMax.pop();}else{queMin.push(num);queMax.push(queMin.top());queMin.pop();}}double findMedian() {if (queMin.size() > queMax.size())return queMin.top();return (queMin.top() + queMax.top()) / 2.0;}
private:priority_queue<int, vector<int>, less<int>> queMin;priority_queue<int, vector<int>, greater<int>> queMax;};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/

相关文章:

数据结构和算法笔记5:堆和优先队列

今天来讲一下堆&#xff0c;在网上看到一个很好的文章&#xff0c;不过它实现堆是用Golang写的&#xff0c;我这里打算用C实现一下&#xff1a; Golang: Heap data structure 1. 基本概念 满二叉树&#xff08;二叉树每层节点都是满的&#xff09;&#xff1a; 完全二叉树&a…...

第8章 SpringBoot任务管理

学习目标 熟悉SpringBoot整合异步任务的实现 熟悉SpringBoot整合定时任务的实现 熟悉SpringBoot整合邮件任务的实现 开发web应用时,多数应用都具备任务调度功能。常见的任务包括异步任务,定时任务和发邮件任务。我们以数据库报表为例看看任务调度如何帮助改善系统设计。报表可…...

Qt5 基于OpenGL实现六轴机械臂三维仿真

需求 在Qt中通过OPenGL方式加载三维模型STL文件&#xff0c;然后将多个结构的STL文件类型的模型进行组装&#xff0c;形成6轴机械臂三维模型的显示&#xff0c;并且可以对每个关节进行关节角度的控制。 新建一个C类STLFileLoader&#xff0c;用于加载STL文件&#xff0c;并进…...

路由进阶

文章目录 1.路由的封装抽离2.声明式导航 - 导航链接3.声明式导航-两个类名自定义匹配的类名 4.声明式导航 - 跳转传参查询参数传参动态路传参两种传参方式的区别动态路由参数可选符 5.Vue路由 - 重定向6.Vue路由 - 4047.Vue路由 - 模式设置8.编程式导航 - 两种路由跳转9.编程式…...

分类预测 | Matlab实现SCN-Adaboost随机配置网络模型SCN的Adaboost数据分类预测/故障识别

分类预测 | Matlab实现SCN-Adaboost随机配置网络模型SCN的Adaboost数据分类预测/故障识别 目录 分类预测 | Matlab实现SCN-Adaboost随机配置网络模型SCN的Adaboost数据分类预测/故障识别分类效果基本描述程序设计参考资料 分类效果 基本描述 1.Matlab实现SCN-Adaboost随机配置网…...

鸿蒙(HarmonyOS)项目方舟框架(ArkUI)之TextPicker组件

鸿蒙&#xff08;HarmonyOS&#xff09;项目方舟框架&#xff08;ArkUI&#xff09;之TextPicker组件 一、操作环境 操作系统: Windows 10 专业版、IDE:DevEco Studio 3.1、SDK:HarmonyOS 3.1 二、TextPicker组件 TextClock组件通过文本将当前系统时间显示在设备上。支持不…...

linux中vim的操作

(码字不易&#xff0c;关注一下吧w~~w) 命令模式&#xff1a; 当我们按下esc键时&#xff0c;我们会进入命令模式&#xff1b;当使用vi打开一个文件时也是进入命令模式。 光标移动&#xff1a; 1 保存退出&#xff1a;ZZ 2 代码格式化&#xff1a;ggG 3 光标移动&#xff…...

《统计学习方法:李航》笔记 从原理到实现(基于python)-- 第5章 决策树

文章目录 第5章 决策树5.1 决策树模型与学习5.1.1 决策树模型5.1.2 决策树与if-then规则5.1.3 决策树与条件概率分布5.1.4 决策树学习5.2 特征选择5.2.1 特征选择问题5.2.2 信息增益5.2.3 信息增益比5.3.1 ID3算法5.3.2 C4.5的生成算法5.4 决策树的剪枝5.5 CART算法5.5.1 CART生…...

【C++11(一)】列表初始化and右值引用

一、 统一的列表初始化 1.1 &#xff5b;&#xff5d;初始化 在C98中&#xff0c;标准允许 使用花括号{}对数组或者结构体元素 进行统一的列表初始值设定 C11扩大了用大括号 括起的列表(初始化列表)的使用范围 使其可用于所有的内置类型和 用户自定义的类型 使用初始化列表时…...

为什么SSL会握手失败?SSL握手失败原因及解决方案

随着网络安全技术的发展&#xff0c;SSL证书作为网站数据安全的第一道防线&#xff0c;被越来越多的企业选择。SSL证书使用的是SSL协议&#xff0c;而SSL握手是SSL协议当中最重要的一部分。当部署SSL证书时&#xff0c;如果服务器和客户端之间无法建立安全连接&#xff0c;就会…...

STM32——智能小车

STM32——智能小车 硬件接线 B-1A – PB0 B-1B – PB1 A-1A – PB2 A-1B – PB10 其余接线参考51单片机小车项目。 1.让小车动起来 motor.c #include "motor.h" void goForward(void) {// 左轮HAL_GPIO_WritePin(GPIOB, GPIO_PIN_2, GPIO_PIN_SET);HAL_GPIO…...

开源:基于Vue3.3 + TS + Vant4 + Vite5 + Pinia + ViewPort适配..搭建的H5移动端开发模板

vue3.3-Mobile-template 基于Vue3.3 TS Vant4 Vite5 Pinia ViewPort适配 Sass Axios封装 vconsole调试工具&#xff0c;搭建的H5移动端开发模板&#xff0c;开箱即用的。 环境要求&#xff1a; Node:16.20.1 pnpm:8.14.0 必须装上安装pnpm&#xff0c;没装的看这篇…...

缩略图保持加密(thumbnail-preserving encryption, TPE)的理论基础

这涉及到一些视觉心理学等方面知识: 1、参考文献: 云存储图像缩略图保持的加密研究进展(中国图像图形学报) 一些视觉心理学的研究为TPE的成功实现提供了理论基础。Potter(1975, 1976)的研究表明人类的视觉系统能够在100 ms内从一个新场景中提取出相应的语义信息;250 ms内…...

nodejs+vue+mysql校园失物招领网站38tp1

本高校失物招领平台是为了提高用户查阅信息的效率和管理人员管理信息的工作效率&#xff0c;可以快速存储大量数据&#xff0c;还有信息检索功能&#xff0c;这大大的满足了用户和管理员这两者的需求。操作简单易懂&#xff0c;合理分析各个模块的功能&#xff0c;尽可能优化界…...

GEDepth:Ground Embedding for Monocular Depth Estimation

参考代码&#xff1a;gedepth 出发点与动机 相机的外参告诉了相机在世界坐标系下的位置信息&#xff0c;那么可以用这个外参构建一个地面基础深度作为先验&#xff0c;后续只需要在这个地面基础深度先验基础上添加offset就可以得到结果深度&#xff0c;这样可以极大简化深度估…...

校园圈子论坛系统--APP小程序H5,前后端源码交付,支持二开!uniAPP+PHP书写!

随着移动互联网的快速发展&#xff0c;校园社交成为了大学生们日常生活中重要的一部分。为了方便校园内学生的交流和互动&#xff0c;校园社交小程序逐渐走入人们的视野。本文将探讨校园社交小程序的开发以及其带来的益处。 校园社交小程序的开发涉及许多技术和设计方面。首先&…...

VMware vCenter告警:vSphere UI运行状况警报

vSphere UI运行状况警报 不会详细显示告警的具体内容&#xff0c;需要我们自己进一步确认告警原因。 vSphere UI运行状况警报是一种监控工具&#xff0c;用于检测vSphere环境中的潜在问题。当警报触发时&#xff0c;通常表示系统遇到了影响性能或可用性的问题。解决vSphere UI…...

C# 引用同一个dll不同版本的程序集

因为项目需要所以必须在项目中引用不同版本的同一程序集 我要引用的文件是newtonsoft.json.dll 两个版本为12.0.0.0 和4.0.0.0 1.如果已经先引入了newtonsoft.json 12.0.0.0版本的程序集&#xff0c;如果直接引入另一个版本的程序集的话会提示不成功&#xff0c;所以先将另一个…...

单机搭建hadoop环境(包括hdfs、yarn、hive)

单机可以搭建伪分布式hadoop环境&#xff0c;用来测试和开发使用&#xff0c;hadoop包括&#xff1a; hdfs服务器 yarn服务器&#xff0c;yarn的前提是hdfs服务器&#xff0c; 在前面两个的基础上&#xff0c;课可以搭建hive服务器&#xff0c;不过hive不属于hadoop的必须部…...

LEETCODE 170. 交易逆序对的总数

class Solution { public:int reversePairs(vector<int>& record) {if(record.size()<1)return 0;//归并 递归int left,right;left0;rightrecord.size()-1;int nummergeSort(left,right,record);return num;}int mergeSort(int left,int right, vector<int>…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...

mac:大模型系列测试

0 MAC 前几天经过学生优惠以及国补17K入手了mac studio,然后这两天亲自测试其模型行运用能力如何&#xff0c;是否支持微调、推理速度等能力。下面进入正文。 1 mac 与 unsloth 按照下面的进行安装以及测试&#xff0c;是可以跑通文章里面的代码。训练速度也是很快的。 注意…...