免费网站建设排名wordpress欢迎页面模板下载

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

免费网站建设排名,wordpress欢迎页面模板下载,dz做分类网站,企业网站源码库纸上得来终觉浅#xff0c;绝知此事要躬行。大家好#xff01;我是霜淮子#xff0c;欢迎订阅我的专栏《算法系列》。 学习经典算法和经典代码#xff0c;建立算法思维#xff1b;大量编码让代码成为我们大脑的一部分。 ⭐️已更系列 1、基础数据结构 1.1、链表➡传送门 1… 纸上得来终觉浅绝知此事要躬行。大家好我是霜淮子欢迎订阅我的专栏《算法系列》。 学习经典算法和经典代码建立算法思维大量编码让代码成为我们大脑的一部分。 ⭐️已更系列  1、基础数据结构        1.1、链表➡传送门        1.2、队列➡本章 专栏直达《算法系列》 目录 前言 机器翻译洛谷P1540 问题描述 输入 输出 1.2、队列 1.2.1、STL queue 1.2.2、手写循环队列 1.2.3、双端队列和单调队列 1.2.4、优先队列 前言 机器翻译洛谷P1540 问题描述 假设内存中有 MM 个单元每单元能存放一个单词和译义。每当软件将一个新单词存入内存前如果当前内存中已存入的单词数不超过 M-1M−1软件会将新单词存入一个未使用的内存单元若内存中已存入 MM 个单词软件会清空最早进入内存的那个单词腾出单元来存放新单词。 假设一篇英语文章的长度为 NN 个单词。给定这篇待译文章翻译软件需要去外存查找多少次词典假设在翻译开始前内存中没有任何单词。 输入 共 22 行。每行中两个数之间用一个空格隔开。 第一行为两个正整数 M,NM,N代表内存容量和文章的长度。 第二行为 NN 个非负整数按照文章的顺序每个数大小不超过 10001000代表一个英文单词。文章中两个单词是同一个单词当且仅当它们对应的非负整数相同。 输出 一个整数为软件需要查词典的次数。 1.2、队列 队列中得数据存取方式是“先进先出”只能向队尾插入数据从对头移出数据。在我们的日常生活中很常见比如食堂打饭的队伍先到先服务。队列有两种实现的方式链队列和循环队列 链队列可以看作单链表的一种特殊情况用指针把各个节点连接在一起。 循环队列是一种顺序表使用一组连续的存储单元依次存放队列元素用两个指针head和tail分别指示对头元素和队尾元素当head和tail走到底的时下一步回到开始的位置从而在这组连续空间内循环。循环队列能解决溢出问题如果不循环head和tail一直往前走head和tali都一直往前走可能会走到存储空间之外导致溢出。 队列的主要问题是查找慢需要从头到尾一个个查找。在某些情况下可以使用优先队列让优先级最高最大的数或者最小的数先出队列。 队列的代码很容易实现如果使用简单环境最简单的手写队列代码如下 cont int N le5; //定义队列大小确保够用 int que[N],head,tail; //对头队尾指针队列大小为tail-head1 head; //弹出对头注意headtail que[head]; //读取对头数据 que[tail]data; //数据data入队尾指针加1注意不能溢出
这个队列不是循环的tail可能超过N导致溢出 1.2.1、STL queue STL queue的主要操作如下 1、queueTypeq:定义队列Type为数据类型如int、float、char等。 2、q.push(item):把item放进队列。 3、q.front( ):返回队首元素但不会删除。 4、q.pop( ):删除对首元素。 5、q.back( ):返回队尾元素。 6、q.size( ):返回元素个数。 7、q.empty( ):检查队列是否为空。 下面给出STL queue的代码 //洛谷P1540, STL queue #includebits/stdc.h using namespace std; int Hash[1003]{0}; //用哈希检查内存中有没有单词hash[i]1表示单词i在内存中 queueint mem; //用队列模拟内存 int main(){int m,n; scanf(%d%d,m,n);int cnt 0; //查词典的次数while(n–){ int en; scanf(%d,en); //输入一个英文单词 if(!Hash[en]){ //如果内存中没有这个单词 cnt; mem.push(en); //单词进队列放到队列尾部 Hash[en]1; //记录内存中有这个单词 while(mem.size()m){ //内存满了 Hash[mem.front()] 0; //从内存中去掉单词 mem.pop(); //从队头去掉}} } printf(%d\n,cnt); return 0; }1.2.2、手写循环队列 手写循环队列代码 #includebits/stdc.h #define N 1003 //队列大小 int Hash[N]{0}; //用Hash检查内存中有没有单词 struct myqueue{int data[N]; //分配静态空间/* 如果动态分配这样写 int *data; */int head, rear; //队头、队尾bool init(){ //初始化/*如果动态分配这样写Q.data (int *)malloc(N * sizeof(int)) ;if(!Q.data) return false; */head rear 0; return true;}int size(){ return (rear - head N) % N;} //返回队列长度 bool empty(){ //判断队列是否为空if(size()0) return true;else return false;}bool push(int e){ //队尾插入新元素。新的rear指向下一个空的位置if((rear 1) % N head ) return false; //队列满data[rear] e;rear (rear 1) % N;return true;}bool pop(int e){ //删除队头元素并返回它if(head rear) return false; //队列空e data[head];head (head 1) % N;return true;}int front(){ return data[head]; } //返回队首但是不删除
}Q; int main(){Q.init(); //初始化队列int m,n; scanf(%d%d,m,n);int cnt 0;while(n–){int en; scanf(%d,en); //输入一个英文单词if(!Hash[en]){ //如果内存中没有这个单词cnt;Q.push(en); //单词进队列放到队列尾部Hash[en]1;while(Q.size()m){ //内存满了int tmp; Q.pop(tmp); //删除队头Hash[tmp] 0; //从内存中去掉单词}}}printf(%d\n,cnt);return 0; }1.2.3、双端队列和单调队列 双端队列和单调队列的概念 双端队列deque是一种具有队列和栈性质的数据结构它支持在两端进行插入和删除操作。具体来说双端队列可以在队列的头部和尾部进行元素的添加和删除操作因此既可以作为队列使用也可以作为栈使用。 单调队列monotonic queue是一种特殊的队列它主要用于解决一类特殊的问题即滑动窗口问题。滑动窗口问题是指在一个固定大小的窗口中找到一些特定的元素或计算一些特定的值。单调队列主要用于维护滑动窗口中的元素使得队列中的元素满足一定的单调性单调递增或单调递减。 在实际应用中双端队列和单调队列都有广泛的应用。双端队列可以用于维护一个滑动窗口中的最大值或最小值而单调队列则可以用于求解滑动窗口中的最大值、最小值、中位数等问题。 1.2.4、优先队列 优先队列priority queue是一种特殊的队列它的每个元素都具有一个优先级。优先级高的元素先出队列优先级相同的元素按照其在队列中的先后顺序出队列。通常来说优先队列中元素的优先级是由一个可比较的关键字来确定的。 优先队列可以使用各种数据结构来实现包括数组、链表、堆等。其中二叉堆是一种经典的实现方式。二叉堆分为最大堆和最小堆最大堆的根节点元素是整个堆中的最大值而最小堆的根节点元素是整个堆中的最小值。在实际应用中最大堆常常用于维护一个动态数据集中的最小值而最小堆则常常用于维护一个动态数据集中的最大值。 优先队列的常见操作包括插入元素、删除元素、查找最大/最小元素等。其中插入元素和删除元素的时间复杂度通常是Olog n查找最大/最小元素的时间复杂度是O1。优先队列在很多算法中都有广泛的应用比如Dijkstra算法、Prim算法、Kruskal算法等。 -END-