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

机试_3_数据结构(一)_习题

数据结构(一)——练习题

学习完第三章-数据结构(一)之后,当然要做相应地练习啦~

注:上述习题都可以在牛客进行测试。

例如,第2题链接:计算表达式_牛客题霸_牛客网 (nowcoder.com),其他题目在“题目列表”中基本都可以找到。

另外,此文章仅仅是提供解题思路,并非最优解。


1、堆栈的使用–吉林大学

描述

堆栈是一种基本的数据结构。堆栈具有两种基本操作方式,push 和 pop。其中 push一个值会将其压入栈顶,而 pop 则会将栈顶的值弹出。现在我们就来验证一下堆栈的使用。(注:本题有多组输入,可以参考该网址:https://www.nowcoder.com/discuss/276)

输入描述:

对于每组测试数据,第一行是一个正整数 n(0 < n <= 10000)。而后的 n 行,每行的第一个字符可能是’P’或者’O’或者’A’;如果是’P’,后面还会跟着一个整数,表示把这个数据压入堆栈;如果是’O’,表示将栈顶的值 pop 出来,如果堆栈中没有元素时,忽略本次操作;如果是’A’,表示询问当前栈顶的值,如果当时栈为空,则输出’E’。堆栈开始为空。

输出描述:

对于每组测试数据,根据其中的命令字符来处理堆栈;并对所有的’A’操作,输出当时栈顶的值,每个占据一行,如果当时栈为空,则输出’E’。

示例1

输入:

3
A
P 5
A
4
P 3
P 6
O
A

输出:

E
5
3

题解:

#include <iostream>
#include <cstdio>
#include <stack>using namespace std;/*** 堆栈的使用* @return*/
int main() {int n;while (cin >> n) {stack<int> stack;for (int i = 0; i < n; ++i) {char instruction;cin >> instruction;if (instruction == 'P') {int num;cin >> num;stack.push(num);} else if (instruction == 'O') {if (!stack.empty()) {stack.pop();}} else {if (stack.empty()) {cout << "E" << endl;} else {cout << stack.top() << endl;}}}}return 0;
}

2、计算表达式–上海交通大学

描述

对于一个不存在括号的表达式进行计算

输入描述:

存在多组数据,每组数据一行,表达式不存在空格

输出描述:

输出结果

示例1

输入:

6/2+3+3*4

输出:

18

题解:

解题:
1. 在表达式的结尾加上"#",表示结束符,然后从左到右遍历计算式
2. 若为操作数num,则压入操作数栈中
3. 若为运算符,则依次弹出运算符栈中比当前运算符优先级高的运算符;同时,依次弹出操作数栈中的元素(注意:先弹出的为右操作数)然后,执行相应的计算,将计算结果压入到操作数栈中。最后,将当前的运算符压入到运算符栈中。
4. 若为结束符"#",依次弹出运算符栈中的运算符,依次弹出操作数栈中的元素,执行计算后将结果压入栈中
5. 最后栈中只剩一个元素,即为计算结果。
#include <iostream>
#include <cstdio>
#include <stack>
#include <string>
#include <map>using namespace std;/*** 计算运算符的操作结果* @param opera 运算符* @param leftNum 左操作数* @param rightNum 右操作数* @return*/
double calculate(char opera, double leftNum, double rightNum);/** map存放运算符的优先级*/
map<char, int> priority = {{'$', 0},{'+', 1},{'-', 1},{'*', 2},{'/', 2}
};/*** 计算表达式--上海交通大学* @return*/
int main() {string str;while (cin >> str) {/** 给表达式加上结束符*/str += "#";stack<char> operaStack;stack<double> numStack;string num = "";for (int i = 0; i < str.size(); ++i) {char cur = str[i];if (cur == '#') {/** 结束符* 1. 先将结束符#前面的num压入操作数栈中* 2. 依次弹出运算符栈中的运算符* 3. 依次弹出操作数栈中的操作符(注:先弹出的是右操作数)* 4. 执行相应计算,再将计算结构压入栈中*/if (num != "") {numStack.push(stod(num));num = "";}while (!operaStack.empty()) {char opera = operaStack.top();operaStack.pop();double rightNum = numStack.top();numStack.pop();double leftNum = numStack.top();numStack.pop();numStack.push(calculate(opera, leftNum, rightNum));}} else if ('0' <= cur && cur <= '9') {/** 0~9,将数字拼接到num中*/num += cur;} else {/** 操作符* 1. 先将操作符前面的num压入操作数栈中* 2. 依次弹出运算符栈中的运算符比当前运算符优先级高的运算符* 3. 依次弹出操作数栈中的操作符(注:先弹出的是右操作数)* 4. 执行相应计算,再将计算结构压入栈中* 5. 将当前的运算符压入运算符栈中*/if (num != "") {numStack.push(stod(num));num = "";}while (!operaStack.empty() && priority[operaStack.top()] >= priority[cur]) {char opera = operaStack.top();operaStack.pop();double rightNum = numStack.top();numStack.pop();double leftNum = numStack.top();numStack.pop();numStack.push(calculate(opera, leftNum, rightNum));}operaStack.push(cur);}}/** 此时,栈中有且只有一个元素,即为计算结果*/cout << numStack.top() << endl;}return 0;
}double calculate(char opera, double leftNum, double rightNum) {double res = 0;switch (opera) {case '+':res = leftNum + rightNum;break;case '-':res = leftNum - rightNum;break;case '*':res = leftNum * rightNum;break;case '/':res = leftNum / rightNum;break;default:break;}return res;
}

相关文章:

机试_3_数据结构(一)_习题

数据结构&#xff08;一&#xff09;——练习题 学习完第三章-数据结构&#xff08;一&#xff09;之后&#xff0c;当然要做相应地练习啦~ 注&#xff1a;上述习题都可以在牛客进行测试。 例如&#xff0c;第2题链接&#xff1a;计算表达式_牛客题霸_牛客网 (nowcoder.com)…...

《Hadoop篇》------HDFS与MapReduce

目录 一、HDFS角色职责总结 二、CheckPoint机制 三、Mapreduce序列化 四、Mapper 4.1、官方介绍 4.2、Split计算 4.3、Split和block对应关系 4.4、启发式算法 五、MapTask整体的流程 六、压缩算法 6.1、压缩算法适用场景 6.2、压缩算法选择 6.2.1、Gzip压缩 6.2…...

网络爬虫简介

前言 没什么可以讲的所以就介绍爬虫吧 介绍 网络爬虫&#xff08;英语&#xff1a;web crawler&#xff09;&#xff0c;也叫网路蜘蛛&#xff08;spider&#xff09;&#xff0c;是一种用来自动浏览万维网的网络机器人。其目的一般为编纂网络索引。 网路搜索引擎等站点通过…...

通过4个月的自动化学习,现在我也拿到了25K的offer

毕业后的5年&#xff0c;是拉开职场差距的关键时期。有人通过这5年的努力&#xff0c;实现了大厂高薪&#xff0c;有人在这5年里得到贵人的赏识&#xff0c;实现了职级的快速拔升&#xff0c;还有人在这5年里逐渐掉队&#xff0c;成了职场里隐身一族&#xff0c;归于静默。 而…...

分库分表了解

数据切分根据其切分类型&#xff0c;可以分为两种方式&#xff1a;垂直&#xff08;纵向&#xff09;切分和水平&#xff08;横向&#xff09;切分一&#xff1a;垂直&#xff08;纵向&#xff09;切分【基于表或字段划分&#xff0c;表结构不同】1&#xff1a;垂直分库根据业务…...

docker中 gitlab 安装、配置和初始化

小笔记&#xff1a;gitlab配置文件 /etc/gitlab/gitlab.rb 配置项jcLee95 的CSDN博客&#xff1a;https://blog.csdn.net/qq_28550263?spm1001.2101.3001.5343 邮箱 &#xff1a;291148484163.com 本文地址&#xff1a;https://blog.csdn.net/qq_28550263/article/details/1…...

有哪些好用的C++Json库?

文章目录RapidJSONJSON for Modern CBoost.PropertyTreeJanssonPicoJSONC REST SDKnlohmann json&#xff08;ky用的这个&#xff09;jsoncpp&#xff08;cw用的这个&#xff09;RapidJSON RapidJSON是一个快速、高效的C JSON解析器和生成器&#xff0c;支持SAX和DOM两种解析模…...

Docker 快速上手学习入门教程

目录 1、docker 的基础概念 2、怎样打包和运行一个应用程序&#xff1f; 3、如何对 docker 中的应用程序进行修改&#xff1f; 4、如何对创建的镜像进行共享&#xff1f; 5、如何使用 volumes 名称对容器中的数据进行存储&#xff1f;// 数据挂载 6、另一种挂载方式&…...

深度学习笔记:误差反向传播(1)

1 计算图 计算图使用图&#xff08;由节点和边构成的图&#xff09;来表达算式。 如图&#xff0c;我们用节点代表运算符号&#xff0c;用边代表传入的参数&#xff0c;即可算出购买苹果和橘子的总价格。 2 计算图的局部计算 局部计算意味着每个节点只处理和其相关的运算&…...

锁相环(1)

PLL代表相位锁定环。顾名思义&#xff0c;如下图所示&#xff0c;PLL是一种具有反馈循环的电路&#xff0c;可将反馈信号的相/频率保持与参考输入信号的相/频率相同&#xff08;锁定&#xff09;。 如下图所示&#xff0c;如果参考输入和反馈输入之间存在相位差&#xff0c;则…...

2023金三银四跳槽必会Java核心知识点笔记整理

现在互联网大环境不好&#xff0c;互联网公司纷纷裁员并缩减 HC&#xff0c;更多程序员去竞争更少的就业岗位&#xff0c;整的 IT 行业越来越卷。身为 Java 程序员的我们就更不用说了&#xff0c;上班 8 小时需要做好本职工作&#xff0c;下班后还要不断提升技能、技术栈&#…...

二十四节气—雨水,好雨知时节,当春乃发生。

雨水&#xff0c;是二十四节气之第2个节气。 雨水节气不仅表明降雨的开始及雨量增多&#xff0c;而且表示气温的升高&#xff0c;意味着进入气象意义的春天。 雨水节是一个非常富有想象力和人情味的节气&#xff0c;在这一天&#xff0c;不管下不下雨都充满着一种雨意蒙蒙的诗…...

为什么要使用数据库?

随着互联网技术的高速发展&#xff0c;预计2020 年底全世界网民的数量将达到 50 亿。网民数量的增加带动了网上购物、微博&#xff0c;网络视频等产业的发展。那么&#xff0c;随之而来的就是庞大的网络数据量。 大量的数据正在不断产生&#xff0c;那么如何安全有效地存储、检…...

【原创】java+swing+mysql图书管理系统设计与实现

图书管理系统是一个比较常见的系统&#xff0c;今天我们主要介绍如何使用javaswiingmysql去开发一个cs架构的图书管理系统&#xff0c;方便学生进行图书借阅。 功能分析&#xff1a; 宿舍报修管理系统的使用角色&#xff0c;一般分为管理员和学生&#xff0c;管理员主要进行学…...

图论 —— 强连通分量

概念 连通图 无向图 G G G 中,若对任意两点 V i , V j V_i, V_j V<...

计算机网络(二):物理层和链路层,通道复用,MAC地址,CSMA/CD协议,PPP点对点协议

文章目录一、物理层主机之间的通信方式通道复用技术常见的宽带接入技术二、链路层MAC地址和IP地址分别有什么作用为什么有了MAC地址之后还需要IP地址为什么有了IP地址还需要MAC地址以太网中的CSMA/CD协议数据链路层上的三个基本问题PPP协议一、物理层 主机之间的通信方式 单工…...

英语基础-定语从句的特殊用法及写作应用

1. 定语从句的引导词省略的情况 1. that 引导定语从句&#xff0c;从句中缺宾语/表语&#xff0c;that可省略&#xff1b; This is the book that he likes. I like the shirt that you gave me. We do not agree on the plan that you make. China is not the country th…...

[数据结构]---八大经典排序算法详解

&#x1f427;作者主页&#xff1a;king&南星 &#x1f3f0;专栏链接&#xff1a;c 文章目录一、八大排序算法复杂度对比二、基于比较的排序算法1.冒泡排序2.选择排序3.插入排序4.希尔排序5.直观感受四种算法的时间复杂度三、基于非比较的排序算法1.基数排序2.箱(桶)排序四…...

Go语言设计与实现 -- 反射

Go的反射有哪些应用&#xff1f; IDE中代码的自动补全对象序列化fmt函数的相关实现ORM框架 什么情况下需要使用反射&#xff1f; 不能明确函数调用哪个接口&#xff0c;需要根据传入的参数在运行时决定。不能明确传入函数的参数类型&#xff0c;需要在运行时处理任意对象。 …...

利用5G工业网关实现工业数字化的工业互联网解决方案

5G工业网关是一种用于将工业生产环境中的数据连接到工业互联网的解决方案。它可以利用高带宽、高速率、低时延的5G网络连接工业现场的PLC、传感器、工业设备和云端数据中心&#xff0c;从而实现工业数字化。 物通博联工业互联网解决方案 物通博联5G工业网关的使用步骤&#x…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu ​ 2、Hello World fn main() { println…...

[论文阅读]TrustRAG: Enhancing Robustness and Trustworthiness in RAG

TrustRAG: Enhancing Robustness and Trustworthiness in RAG [2501.00879] TrustRAG: Enhancing Robustness and Trustworthiness in Retrieval-Augmented Generation 代码&#xff1a;HuichiZhou/TrustRAG: Code for "TrustRAG: Enhancing Robustness and Trustworthin…...

k8s从入门到放弃之HPA控制器

k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率&#xff08;或其他自定义指标&#xff09;来调整这些对象的规模&#xff0c;从而帮助应用程序在负…...

Monorepo架构: Nx Cloud 扩展能力与缓存加速

借助 Nx Cloud 实现项目协同与加速构建 1 &#xff09; 缓存工作原理分析 在了解了本地缓存和远程缓存之后&#xff0c;我们来探究缓存是如何工作的。以计算文件的哈希串为例&#xff0c;若后续运行任务时文件哈希串未变&#xff0c;系统会直接使用对应的输出和制品文件。 2 …...