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

【数据结构练习】栈的面试题集锦

目录

前言:

1.进栈过程中可以出栈的选择题

2.将递归转化为循环

3.逆波兰表达式求值

4.有效的括号

5. 栈的压入、弹出序列

6. 最小栈 


前言:

数据结构想要学的好,刷题少不了,我们不仅要多刷题,还要刷好题!为此我开启了一个必做好题锦集的系列,此为第一篇选择题篇,该系列会不定期更新敬请期待!

栈(Stack)的详解_WHabcwu的博客-CSDN博客


1.进栈过程中可以出栈的选择题

1. 若进栈序列为 1,2,3,4 ,进栈过程中可以出栈,则下列不可能的一个出栈序列是()
A: 1,4,3,2                 B: 2,3,4,1                 C: 3,1,4,2               D: 3,4,2,1
A选项进出入栈顺序:
push(1)->pop() 出1;
push(2)->push(3)->push(4)->pop() 出4;
pop() 出3;
pop() 出2;
B C D步骤相同,通过分析可知C明显错误;
选C

2.将递归转化为循环

比如:逆序打印链表
使用栈的方法解决:
        public void printfList(Node head) {if (head == null) {return;}Node cur=head;Stack<Node> stack = new Stack<>();while (cur!=null){stack.push(cur);cur=cur.next;}while(!stack.empty()){System.out.println(stack.pop().val);}}

3.逆波兰表达式求值

逆波兰表达式求值icon-default.png?t=N7T8https://leetcode.cn/problems/evaluate-reverse-polish-notation/

 

要想彻底的掌握这道题,必先清楚的理解后缀表达式

 总结:

(1)遍历数字,依此压栈

(2)遇到' + ' ' - ' ' * ' ' / '就出栈2数,第一次出栈的数做为右操作数, 第二次出栈的数做为左操作数

(3)再把(2)运算的数压栈

(4)重复(1)(2)(3)

故代码: 

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for (String x : tokens) {if (!isoperation(x)) {stack.push(Integer.parseInt(x));} else {int x1 = stack.pop();int x2 = stack.pop();switch (x) {case "+":stack.push(x2 + x1);break;case "-":stack.push(x2 - x1);break;case "*":stack.push(x2 * x1);break;case "/":stack.push(x2 / x1);break;}}}return stack.pop();}public boolean isoperation(String x) {if (x.equals("+")  || x.equals("-") || x.equals("*") || x.equals("/")) {return true;}return false;}
}

4.有效的括号

有效的括号icon-default.png?t=N7T8https://leetcode.cn/problems/valid-parentheses/

 

class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for (int i = 0; i < s.length(); i++) {char x=s.charAt(i);if(x=='('||x=='{'||x=='['){stack.push(x);}else{if(stack.empty()){return false;}char y=stack.peek();if(y=='('&&x==')'||y=='{'&&x=='}'||y=='['&&x==']'){stack.pop();}else{return false;}}}if(!stack.empty()){return false;}return true;}}

 解析:

(1)遍历给定的字符串,由于后遇到的左括号要先闭合,因此我们可以将这个左括号放入栈顶。

(2)当我们遇到一个右括号时,我们可以取出栈顶的左括号并判断它们是否是相同类型的括号,栈为空返回flase,不为空但不是相同的类型,也返回 false。

(3)在遍历结束后,如果栈中没有左括号,返回 false。


5. 栈的压入、弹出序列

 

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param pushV int整型一维数组 * @param popV int整型一维数组 * @return bool布尔型*/public boolean IsPopOrder (int[] pushV, int[] popV) {Stack<Integer> stack = new Stack<>();int j=0;for (int i = 0; i < pushV.length; i++) {stack.push(pushV[i]);while(j<popV.length&&!stack.empty()&&stack.peek().equals(popV[j])){stack.pop();j++;}}return stack.empty();}
}

解析:


6. 最小栈 

 最小栈icon-default.png?t=N7T8https://leetcode.cn/problems/min-stack/

 

import java.util.Stack;public class MinStack {private Stack<Integer> stack;private Stack<Integer> minstack;public MinStack() {this.stack = new Stack<>();this.minstack = new Stack<>();}public void push(int val) {stack.push(val);if (minstack.empty()) {minstack.push(val);} else {if (minstack.peek() >= val) {minstack.push(val);}}}public void pop() {if(!stack.empty()){int x = stack.pop();if (x == minstack.peek()) {minstack.pop();}}}public int top() {return stack.peek();}public int getMin() {return minstack.peek();}
}

 解析:

辅助栈法:

(1)一个用来正常存放数据->stack

(1)一个用来存放最小数据->minstack

  private Stack<Integer> stack;
    private Stack<Integer> minstack;

 push:

stack无差别入栈,对于minstack进行判断,若为空,直接入栈,若不为空,则需要与栈顶元素进行比较,若小于等于则入栈。

其余过于简单,无需多讲。


以上为我个人的小分享,如有问题,欢迎讨论!!! 

都看到这了,不如关注一下,给个免费的赞 

 

相关文章:

【数据结构练习】栈的面试题集锦

目录 前言&#xff1a; 1.进栈过程中可以出栈的选择题 2.将递归转化为循环 3.逆波兰表达式求值 4.有效的括号 5. 栈的压入、弹出序列 6. 最小栈 前言&#xff1a; 数据结构想要学的好&#xff0c;刷题少不了&#xff0c;我们不仅要多刷题&#xff0c;还要刷好题&#x…...

简单工厂模式概述和使用

目录 一、简单工厂模式简介1. 定义2. 使用动机 二、简单工厂模式结构1.模式结构2. 时序图 三、简单工厂的使用实例四、简单工厂模式优缺点五、简单工厂模式在Java中的应用 一、简单工厂模式简介 原文链接 1. 定义 简单工厂模式(Simple Factory Pattern)&#xff1a;又称为静…...

软件工程概述

软件工程概述 软件工程指的是应用计算机科学、数学及管理科学等原理&#xff0c;以工程化的原则和方法来解决软件问题的工程&#xff0c;目的是提高软件生产效率、提高软件质量、降低软件成本。 1. 计算机软件 计算机软件指的是计算机系统中的程序及其文档。程序是计算任务的…...

国际网页短信软件平台搭建定制接口说明|移讯云短信系统

国际网页短信软件平台搭建定制接口说明|移讯云短信系统 通道路由功能介绍 支持地区通道分流&#xff0c;支持关键字&#xff0c;关键词通道分流&#xff0c;支持白名单独立通道&#xff0c;支持全网通道分流&#xff0c;支持通道可发地区设置&#xff0c;通道路由分组&#x…...

Java“牵手”阿里巴巴店铺所有商品API接口数据,通过店铺ID获取整店商品详情数据,阿里巴巴店铺所有商品API申请指南

阿里巴巴平台店铺所有商品数据接口是开放平台提供的一种API接口&#xff0c;通过调用API接口&#xff0c;开发者可以获取阿里巴巴整店的商品的标题、价格、库存、月销量、总销量、库存、详情描述、图片、价格信息等详细信息 。 获取店铺所有商品接口API是一种用于获取电商平台…...

【Sql】把数据库字段用函数根据逗号分裂成列表,然后判断列表中是否包含目标值

【Sql】把数据库字段用函数根据逗号分裂成列表&#xff0c;然后判断列表中是否包含目标值 【1】问题描述【2】Oracle内置函数解决【3】mysql的内置函数INSTR()【4】mysql的内置函数FIND_IN_SET() 【1】问题描述 数据库中【库信息db】和【集群信息cluster】是一对多的关系&…...

docker基本命令记录

Docker 是一个开源的容器技术,它允许开发人员将应用程序及其所有依赖项打包到一个容器中,然后轻松地在任何地方部署和运行。以下是 Docker 的一些基本操作: 基础操作: 启动 Docker:service docker start停止 Docker:service docker stop查看 Docker 信息:docker info容器操作…...

web之利用延迟实现复杂动画、animation

文章目录 效果图htmlstyleJavaScript 效果图 html <div class"container"><div class"ball"></div><input type"range" min"0" max"1" step"0.01" /> </div>style body {display…...

TCP 和 UDP 的区别、TCP 是如何保证可靠传输的?

先来介绍一些osi七层模型 分为应用层、表示层、会话层、运输层、网络层、链路层、物理层。 应用层(数据)&#xff1a;确定进程之间通信的性质以及满足用户需要以及提供网络和用户应用&#xff0c;为应用程序提供服务&#xff0c;DNS&#xff0c;HTTP&#xff0c;HTTPS&#xf…...

鼠标悬停阴影的效果被旁边div挡住的解决办法

出现的问题 需求要求鼠标悬停某个图片上有阴影效果&#xff0c;但阴影被旁边相邻的div挡住了&#xff0c;如图所示 解决方案 给悬停的这块div增加2个css属性 $(this).css(position, relative); $(this).css(z-index, 200);新的效果如图所示 一直写后端&#xff0c;前端的…...

Go用两个协程交替打印100以内的奇偶数

方式1&#xff08;使用无缓冲的channel&#xff09; package mainimport ( "fmt" "time")var flagChan make(chan int)func wokr1() { for i : 1; i < 100; i { flagChan <- 666 // 塞入 if i%2 1 { fmt.Println("协程1打印:", i) …...

css 文字单行多行超出长度后显示 ...

0.超出… 1、单行文本超出 <div class"content">测试数据&#xff1a;css单行文本超出显示省略号--------</div><style> .content{width: 200px;height: 200px;overflow:hidden;white-space: nowrap;text-overflow: ellipsis;-o-text-overflow:el…...

C++将派生类赋值给基类

在 C/C++ 中经常会发生数据类型的转换,例如将 int 类型的数据赋值给 float 类型的变量时,编译器会先把 int 类型的数据转换为 float 类型再赋值;反过来,float 类型的数据在经过类型转换后也可以赋值给 int 类型的变量。 数据类型转换的前提是,编译器知道如何对数据进行取舍…...

海外问卷调查是做什么的?

大家好&#xff0c;我是橙河。现在我来给大家简单讲解一下海外问卷调查是做什么的&#xff1f; 多年以前&#xff0c;人们就开始在网上进行海外问卷调查了。最常见的方法是通过问卷网站、做问卷或者论坛进行调查&#xff0c;现在则更多地使用各种渠道进行调查。海外国家对于问…...

Redis——数据结构介绍

Redis是一个key-value的数据库&#xff0c;key一般是String类型&#xff0c;不过value的类型是多样的&#xff1a; String&#xff1a;hello wordHash&#xff1a;{name:"Jack",age:21}List&#xff1a;[A -> B -> C -> D]Set&#xff1a;{A,B,C}SortedSet…...

附录2-将三国演义按章节存储为不同的txt(bs4)

地址 《三国演义》全集在线阅读_史书典籍_诗词名句网 目录 1 项目分析 2 代码 1 项目分析 我们可以在首页中找到所有的章节 每一个章节是一个a标签&#xff0c;a标签连接到该章节的内容 但这个网站他有bug&#xff0c;章节都是乱套的&#xff0c;我们无视这种错误&#…...

现代C++中的从头开始深度学习:【6/8】成本函数

现代C中的从头开始深度学习&#xff1a;成本函数 一、说明 在机器学习中&#xff0c;我们通常将问题建模为函数。因此&#xff0c;我们的大部分工作都包括寻找使用已知模型近似函数的方法。在这种情况下&#xff0c;成本函数起着核心作用。 这个故事是我们之前关于卷积的讨论的…...

Vue——vue3中的ref和reactive数据理解以及父子组件之间props传递的数据

ref()函数 这是一个用来接受一个内部值&#xff0c;返回一个响应式的、可更改的 ref 对象&#xff0c;此对象只有一个指向其内部值的属性 .value。 作用&#xff1a;创建一个响应式变量&#xff0c;使得某个变量在发生改变时可以同步发生在页面上。 模板语句中使用这个变量时…...

新手如何备考PMP考试?

回头看来&#xff0c;从战略上来说&#xff1a; 备考第一重点&#xff1a;要有一个清晰的目标——我要过&#xff01; 第二重点&#xff1a;足够重视它——把它的优先级调整到仅次于工作&#xff1a;万籁俱寂&#xff0c;唯有学习。 第三重点&#xff1a;自律——有了第一点…...

FPGA输出lvds信号点亮液晶屏

1 概述 该方案用于生成RGB信号&#xff0c;通过lvds接口驱动逻辑输出&#xff0c;点亮并驱动BP101WX-206液晶屏幕。 参考&#xff1a;下面为参考文章&#xff0c;内容非常详细。Xilinx LVDS Output——原语调用_vivado原语_ShareWow丶的博客http://t.csdn.cn/Zy37p 2 功能描述 …...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

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

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

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...