10.8队列安排,最少找字典次数,表达式转换与计算模拟(栈、队列)

队列安排1160

灵活的插入与删除

用队列实现的话,就是双端队列,

第一阶段是要找到对应编号的同学,然后根据p的取值决定是怎么插入

第二阶段也是要找到对应编号同学,之后就删除,如果找不到就返回

思路是这个思路,可以用数组来实现,第一阶段不变,第二阶段可以优化为,如果输入了对应的编号,就让那个编号的同学不输出,最后在统一遍历输出时,就只会输出那些没有被打上标记的人

?既然用数组实现,怎么能按逻辑顺序遍历?

可以用一个数组0号元素,它的右侧就是第一个元素,遍历的终点是右侧遇到了0 

    cha(1, 0, 1);for (int i = num[0].r; i != 0; i = num[i].r) {if (num[i].flag == 1) {cout << i << " ";}}

这一段是精髓 

    struct peo {int l, r;int flag = 1;}num[10005];void cha(int i, int k, int p) {//k是被插的,i是新来的if (p == 1) {//i插在k的右边num[i].r = num[k].r;num[i].l = k;num[k].r = i;num[num[i].r].l = i;}else if (p == 0) {num[i].l = num[k].l;num[i].r = k;num[k].l = i;num[num[i].l].r = i;}}int n, k, p, m, x;cin >> n;cha(1, 0, 1);for (int i = 2; i <= n; i++) {cin >> k >> p;cha(i, k, p);}cin >> m;for (int i = 1; i <= m; i++) {cin >> x;num[x].flag = 0;}for (int i = num[0].r; i != 0; i = num[i].r) {if (num[i].flag == 1) {cout << i << " ";}}

机器翻译1540(队列)

感觉和滑动窗口差不多

用一个长度为m的窗口去滑动n的长度,如果n<m直接返回n,

考虑到前m个可能有重复的情况,用左右指针,不好用,还是队列

然后往后遇到数字时,如果前面记录过这个数字就接着走,如果没有,就让队头出队,然后这个元素入队,并且cnt++,最后输出cnt,即入队时cnt++,一旦到了内存,就一直会是满内存的状态

问题关键在于怎么检索是否遇到这个数字,总不能每次都从头到尾,那就是nm的复杂度?

思想是队列的思想,实现还是用数组更优。用两个数组,一个数组a模拟当前内存,一个数组b模拟当前内存中存入的单词情况,遇到元素时,查找b数组上记录的值是否为1,是1就遇到过,直接向后,是0就是没遇到过,要入队,同时在b里置为1,表示现在遇到了,同时如果满内存了,就要让最先遇到的元素的b再置为0

就是遇到有的单词时,如果内存里有,就都不动,接着向后移动

遇到新单词时,就让a数组的第一个元素去掉(用左指针实现,为左指针右移一个单位)

?用两个数组,怎么确定当前的内存长度?

a数组的左右指针,右指针只有在遇到新单词时才会移动,并修改内存,内存也是如此,而一旦到了内存的最大,就会一直是最大,不会往下掉

?既然删除,怎么处理模拟数组中的相同元素,删除首个元素后,如果后面都是这个元素,那怎么找到第二个遇到的不同的元素?

a数组只记录不重复元素,

因为模拟的内存,只有在遇到新元素时才会扩大内存或修改内存,如果一直遇到相同元素,那么内存就会一直不变,就是可以理解内存为记录不同的单词的数量,其最多为m,而不是实际的长度

这样左指针右移时遇到的就一定不是相同的元素,而是下一个最近的不同单词

改错:前置后置的思考 

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int n, m, x, ans = 0, l = 0, r = 0, a[1005], b[1005];
int main()
{cin >> m >> n;l = 0; r = 0;//初始化两个指针for (int i = 1; i <= n; i++) {cin >> x;if (b[x] == 0) {//内存中没有,要查找a[r++] = x;ans++;b[x] = 1;if (r > m - 1) {b[a[l++]] = 0;}}}cout << ans;return 0;
}

这样写有问题,因为如果内存为1时,会输出5,因为m-1=0,会一直右移左指针

问题不出在前置或者后置++,而在于r>m-1,应该就是r>m,无论是前置还是后置

之前想的是如果后置,那就是让数组第一位存数时,那么此时r就代表内存大小,事实也是如此,因为r=1时,就代表有一个单词,r=2就代表有两个单词,只不过是从0开始记录

如果前置,就是从i=1开始计数,r=1时有一个数

只不过前置时,每次结束时右指针指向的是有值的,后置时,右指针指向的是没值,但实际上指向的位置是同一个位置,因为前置就是从1开始记录,后置就是从0开始记录,相当于往前推了一点

也就是说无论前置后置,遇到两个新数,那么前置后置结果都是r=2, 所以r代表的就是长度,和前置后置无关,只是记录的数据位置不同,最后的数都是一样的

表达式转换1175(栈,中缀转后缀,并模拟计算过程,辅助栈应用,正逆序)

它是要转化为字符串

?计算前中后的结果简单,但怎么由中缀转为后缀表达式的字符串?

不改变数字出现的相对顺序,改变的只是符号的出现顺序

?怎么改变符号的出现顺序,规则是?

定义优先级,如果此时符号栈中的栈顶元素优先级比自己高,那就让栈顶元素出来,表示先让程序算它,知道遇到优先级不比自己高的

如果比自己优先级低或相等,就直接入栈,这样在算的时候也是先算自己这个优先级比栈下面都更高的操作符,如果都相等,就是遵循从右到左的运算顺序

不对,应该出的是所有大于等于自己优先级的,不是从右到左,对加和乘没区别,但是对减和除有区别,就应该是从左到右,所以应该是出掉所有优先级大于等于自己的,让栈里的下个元素是优先级比自己小的

括号不参与比较,括号只是起隔绝的作用

?遇到括号怎么处理?

遇到括号时就是同样入栈,先遇到左括号,后遇到右括号,在遇到右括号时,就要在符号栈里依次出元素,知道遇到左括号结束,左右括号不输出 

括号不参与优先级比较,遇到括号就直接进,知道遇到右括号才出

第一问解决 

//输入,并演示一步一步的转变过程
//先是输入一个原始字符串,然后转为后缀表达式
//转为原始的后缀表达式后,就开始模拟计算,每行一步
//就是遇到数字就进栈,然后遇到第一个符号就出栈两个,算完入栈一个,接着继续入栈后续的原栈元素,最后再输出
//直到只有一个元素string s;int p(char s) {switch (s) {case '+':return 1;case '-':return 1;case '*':return 2;case '/':return 2;case '^':return 3;default:return -1;}}bool flag = 1;stack<char>op;stack<char>str;void change(string s) {for (int i = 0; i < s.size(); i++) {if (s[i] == ' ') { continue; }if (isdigit(s[i])) {str.push(s[i]);}//遇到数字else if (s[i] == '(') {op.push('(');}//特判遇到左括号else {//遇到操作符if (s[i] == ')') {while (op.top() != '(') {str.push(op.top());op.pop();}op.pop();//此时出循环后栈顶元素为左括号,出掉}else {while (!op.empty() && p(op.top()) >= p(s[i])) {//只要栈顶的元素优先级比自己高,就让它先出去,直到遇到同优先级,遵循从右到左计算str.push(op.top());//这里出问题是因为op里有左括号,但是它却返回不出来一个数,然后就会报错op.pop();}op.push(s[i]);}}}while (!op.empty()) {str.push(op.top());op.pop();}//最后要把遗留在符号栈里的操作符都移出来//这个函数是用来把中缀表达式转变为后缀表达式}cin >> s;//while (s.size()) {change(s);s = "";while (!str.empty()) {s += str.top();s += " ";str.pop();}reverse(s.begin(), s.end());cout << s << endl;while (s.size()) {//接下来就是不断遇到两个数,和一个操作符后进行计算,使s的长度不断减小,最后只剩下一个字符,即最后结果}// }

 完整版

怎么输出是重点,每行怎么输出,怎么保证顺序的一致,辅助栈的应用,栈之间的来回倒

需要确定哪个栈里是正序,

输出的时候要正序的栈

stack<char>dat, op;
stack<int>num, dat2;
int p(char c) {switch (c) {case'+':return 1;case'-':return 1;case'*':return 2;case'/':return 2;case'^':return 3;default:return -1;}
}
void change(string s) {for (int i = 0; i < s.size(); i++) {if (isdigit(s[i])) {dat.push(s[i]);}else if (s[i] == '(') {op.push(s[i]);}else {if (s[i] == ')') {while (op.top() != '(') {dat.push(op.top());op.pop();}op.pop();}else {if (!op.empty()) {while (!op.empty() && p(s[i]) <= p(op.top())) {//这样主要是考虑到减法和除法的次序问题if (p(s[i]) == p(op.top()) && s[i] == '^') {//但相等时如果是幂运算,其不需要考虑,一方面是因为为最高级,另一方面因为需要考虑次序问题//但连起来的幂运算和连起来的减除运算方向不同,对减除是从左到右,即被减数减减数//幂运算是要从右到左,即把幂上幂上幂……转为幂上一个数,即是需要同运算级从右向左运算的,所以不需要移出来先算,而是最后计算时让其模拟中缀的从右往左算break;//直接退出,不必再做条件判断}else {dat.push(op.top());op.pop();}}}op.push(s[i]);}}}while (!op.empty()) {dat.push(op.top());op.pop();}while (!dat.empty()) {op.push(dat.top());dat.pop();}//利用两个栈完成一次对栈空间元素的倒置输出while (!op.empty()) {cout << op.top() << " ";dat.push(op.top());//这个是为了保存当前的数据,不然的话打印一个必须要删除一个才能打印下一个,就不能完成后续的操作了op.pop();//此时dat直接输出是逆序的,即第一个数最后一个输出}cout << endl;
}

第二问,输出的格式化 

int jisuan(int x, int y, char t) {switch (t) {case'+':return x + y;case'-':return x - y;case'*':return x * y;case'/':return x / y;case'^':return pow(x, y);}
}
void cal() {while(!dat.empty()){op.push(dat.top());dat.pop();//}//再倒回去,目的是为了得到正序,从而模拟计算//即此时op里的数是正序的,第一个数第一个输出,但是又进了Num栈,这就导致第一个访问到的不是最早的数//而是最新入num栈的数,即被减数减数的关系中,op栈里是被减数在上面,先输出,是正序的//而从op栈转到Num栈里,就变成了被减数在下面,减数在上面,此时直接运算,就是逆序,是错误的,所以在计算时需要注意while (!op.empty()) {if (isdigit(op.top())) {num.push(op.top() - '0');op.pop();}else {//遇到操作符的必要条件就是已经遇到了至少两个操作数,即可以肯定在遇到第一个操作符时已经可以进行运算//而目的就是接下来每行只计算一个操作符int x = num.top();num.pop();int y = num.top();num.pop();num.push(jisuan(y, x, op.top()));//这里就完成了本行的任务,就不需要再继续用numop.pop();//此时num是一个逆序状态,可以再倒到一个辅助栈里,使其成为正序,进行一下输出//这里就是接下来每行的输出,在这个方法中其由两部分组成,一部分为从Num倒到辅助栈里后的正序顺序输出//这个可以保证是第一个操作符之前的部分,然后就是op栈里的部分,这是遇到此时剩下的首个操作符之后的其他部分//整个过程,大的循环就是op循环,即不断根据op里剩下的首个操作符位置划分的过程//每op循环一次,就是一行的结束,当op里没元素时,就没有了操作符,计算结果也进入了num数组,输出就可以了while (!num.empty()) {//这个辅助栈必须和Num同类型,都为int型dat2.push(num.top());num.pop();}while (!dat2.empty()) {cout << dat2.top() << " ";num.push(dat2.top());//由于已经从字符转为整数型,所以应再倒回num栈里,以进行下个Op循环dat2.pop();}//两部分,一部分是首个操作符之前的,另一部分是其之后的while (!op.empty()) {cout << op.top() << " ";dat.push(op.top());op.pop();}//是为了输出op剩下的部分,由于op此时已经是正序,所以直接输出即可,但是为了保存,还需要用到辅助栈dat,char类型的,最后还要再复原回去while (!dat.empty()) {op.push(dat.top());dat.pop()}cout << endl;//标志着本次op循环的结束}}
}
string s;
cin >> s;
change(s);
cal();

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/151820.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

为什么团队需要实时协作?该如何实现?

协作是任何组织成功的关键部分&#xff0c;通过明确定义的愿景和使命并基于透明度和持续沟通来执行。 实时的协作是指员工之间就不同的项目、任务、文件或文档进行同步、无缝的互动和协作&#xff0c;他们几乎不受任何地理边界的限制&#xff0c;即时沟通和分享反馈、想法和信…

【AI视野·今日Robot 机器人论文速览 第四十七期】Wed, 4 Oct 2023

AI视野今日CS.Robotics 机器人学论文速览 Wed, 4 Oct 2023 Totally 40 papers &#x1f449;上期速览✈更多精彩请移步主页 Interesting: &#x1f4da;基于神经网络的多模态触觉感知, classification, position, posture, and force of the grasped object多模态形象的解耦(f…

从零开始的C++(七)

1.malloc、free和new、delete的区别&#xff1a; 1、.malloc、free是函数&#xff0c;new、delete是运算符。 2、malloc不会调用构造函数&#xff0c;new可以调用构造函数。 3、malloc开辟失败返回NULL&#xff0c;new失败会捕捉异常。 4、malloc不会自动计算类型大小&…

好奇喵 | PT(Private Tracker)——什么是P2P,什么是BT,啥子是PT?

前言 有时候会听到别人谈论pt&#xff0c;好奇猫病又犯了&#xff0c;啥子是pt&#xff1f; PT——你有pt吗&#xff1f;啥是pt&#xff1f; 从BT开始 BitTorrent是一种点对点&#xff08;P2P&#xff09;文件共享协议&#xff0c;用于高速下载和上传大型文件。它允许用户通…

钡铼BL124PN:简单快速转换Profinet到Ethernet/IP

钡铼技术BL124PN是一款高性能的Profinet转Ethernet/IP网关设备。该网关专为工业自动化领域设计&#xff0c;用于实现不同协议之间的互连和通信。BL124PN采用可靠稳定的硬件和先进的通信技术&#xff0c;具有以下主要特点&#xff1a; 协议转换能力&#xff1a;BL124PN能够将Pr…

暴力破解及验证码安全

1.暴力破解注意事项 1、破解前一定要有一个有郊的字典&#xff08;Top100 TOP2000 csdn QQ 163等密码&#xff09; https://www.bugku.com/mima/ 密码生成器 2、判断用户是否设置了复杂的密码 在注册页面注册一个,用简单密码看是否可以注册成功 3、网站是…

RabbitMQ-网页使用消息队列

1.使用消息队列 几种模式 从最简单的开始 添加完新的虚拟机可以看到&#xff0c;当前admin用户的主机访问权限中新增的刚添加的环境 1.1查看交换机 交换机列表中自动新增了刚创建好的虚拟主机相关的预设交换机。一共7个。前面两个 direct类型的交换机&#xff0c;一个是…

TDengine+OpenVINO+AIxBoard,助力时序数据分类

时间序列数据分析在工业&#xff0c;能源&#xff0c;医疗&#xff0c;交通&#xff0c;金融&#xff0c;零售等多个领域都有广泛应用。其中时间序列数据分类是分析时序数据的常见任务之一。本文将通过一个具体的案例&#xff0c;介绍 Intel 团队如何使用 TDengine 作为基础软件…

019 基于Spring Boot的教务管理系统、学生管理系统、课表查询系统

基于Spring Boot的教务管理系统、学生管理系统、课表查询系统 一、系统介绍 本作品主要实现了一个课表查询系统&#xff0c;采用了SSM&#xff08;Spring SpringMVC MyBatis&#xff09;的基础架构。 二、使用技术 spring-bootspring-MVCthymeleafmybatis-plusdruidLombo…

windows 远程连接 ubuntu桌面xrdp

更新 sudo apt update安装组件 sudo apt-get install xorg sudo apt-get install xserver-xorg-core sudo apt-get install xorgxrdp sudo apt install xfce4 xfce4-goodies xorg dbus-x11 x11-xserver-utilsxrdp sudo apt install xrdp sudo systemctl status xrdp sudo …

数据统计--图形报表--ApacheEcharts技术 --苍穹外卖day10

Apache Echarts 营业额统计 重点:已完成订单金额要排除其他状态的金额 根据时间选择区间 设计vo用于后端向前端传输数据,dto用于后端接收前端发送的数据 GetMapping("/turnoverStatistics")ApiOperation("营业额统计")public Result<TurnoverReportVO…

「专题速递」JPEG AI、端到端图像编码的标准化及产品落地、深度学习

从最初的追随者到如今的领跑者&#xff0c;中国的超高清视频编解码技术已经走过20年的漫长征程。从开始制定不同的视频编解码标准&#xff0c;如H.264/265、AV1、VVC、AVS&#xff0c;再到积极地探索基于AI的视频编码技术。视频编解码——这一将视频数据高效压缩、传输和解码还…

mybatis-plus 多数据源配置

1. 双数据库创建 两个数据库各有一张表 2. yml中配置双数据库 下面的配置来源于mybatis-plus官网 spring:datasource:dynamic:primary: master #设置默认的数据源或者数据源组,默认值即为masterstrict: false #严格匹配数据源,默认false. true未匹配到指定数据源时抛异常,fal…

k8s-10 ingress-nginx 特性

TLS加密 创建证书 测试 auth认证 创建认证文件 rewrite重定向 进入域名 会自动重定向hostname.html 示例二&#xff1a; 测试 后面必须跟westos 这个关键字 canary金丝雀发布 基于header灰度 场景&#xff1a;版本的升级迭代&#xff0c;比如一个service 升级到另…

基于SpringBoot的房屋租赁管理系统的设计与实现

目录 前言 一、技术栈 二、系统功能介绍 屋主管理 房屋信息管理 房屋租赁公告 租用订单管理 房屋信息管理 保洁管理 房屋信息 租用订单管理 取消订单管理 三、核心代码 1、登录模块 2、文件上传模块 3、代码封装 前言 互联网发展至今&#xff0c;无论是其理论还是…

分布式数据库(林子雨慕课课程)

文章目录 4. 分布式数据库HBase4.1 HBase简介4.2 HBase数据模型4.3 HBase的实现原理4.4 HBase运行机制4.5 HBase的应用方案4.6 HBase安装和编程实战 4. 分布式数据库HBase 4.1 HBase简介 HBase是BigTable的开源实现 对于网页搜索主要分为两个阶段 1.建立整个网页索引&#xf…

【juc】future并行执行并获取返回值

目录 一、截图示例二、代码示例2.1 接口示例2.2 调用示例 一、截图示例 二、代码示例 2.1 接口示例 package com.learning.controller;import lombok.extern.slf4j.Slf4j; import org.springframework.web.bind.annotation.GetMapping; import org.springframework.web.bind.…

Flink+Doris 实时数仓

Flink+Doris 实时数仓 Doris基本原理 Doris基本架构非常简单,只有FE(Frontend)、BE(Backend)两种角色,不依赖任何外部组件,对部署和运维非常友好。架构图如下 可以 看到Doris 的数仓架构十分简洁,不依赖 Hadoop 生态组件,构建及运维成本较低。 FE(Frontend)以 Java 语…

c++中的map和set

文章目录 1. 关联式容器2. 键值对3. 树形结构的关联式容器3.1 set3.1.1 set的介绍3.1.2 set的使用 3.2 map3.2.1 map的介绍3.2.2 map的使用 3.3 multiset3.3.1 multiset的介绍3.3.2 multiset的使用 3.4 multimap3.4.1 multimap的介绍3.4.2 multimap的使用 1. 关联式容器 在初阶…

使用弹性盒子flex对html进行布局和动态计算视口高度

使用弹性盒子flex对html进行布局的一个练习 height: calc(100vh - 4px); # vh表示视口高度的百分比&#xff0c;所以100vh表示整个视口的高度。 .mytxt { text-indent: 2em; /* 首航缩进2字符 */ line-height: 2; /* 2倍行高 */ padding: 8px; /* 内容与边框的距离 */ } …