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

【LeetCode-经典面试150题-day12】

20.有效的括号

题意:

给定一个只包括 '('')''{''}''['']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

【输入样例】s="({})"

【输出样例】true

解题思路:

经典的栈思想,用数组模拟栈,从头开始遍历字符串,遇到左括号进栈,遇到右括号弹出栈顶,并匹配,看是否能匹配上,如果匹配不上直接return false;

class Solution {public boolean isValid(String s) {if(s.length() %2 ==1){//长度为奇数,肯定不匹配return false;}Map<Character,Character> map = new HashMap<Character,Character>();map.put(')','(');map.put('}','{');map.put(']','[');List<Character> stack = new ArrayList<>();for(int i=0;i<s.length();++i){if(!map.containsKey(s.charAt(i))){//左括号入栈stack.add(s.charAt(i));}else{//右括号要出栈匹配//栈为空或者栈顶元素与当前右括号不匹配if(stack.isEmpty() || map.get(s.charAt(i)) != stack.get(stack.size()-1)){return false;}//匹配上,要弹出栈顶元素stack.remove(stack.size()-1);}}return stack.isEmpty();}
}

时间: 击败了50.23%

内存: 击败了28.36%

71.简化路径

题意:

给你一个字符串 path ,表示指向某一文件或目录的 Unix 风格 绝对路径 (以 '/' 开头),请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (..) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠(即,'//')都被视为单个斜杠 '/' 。 对于此问题,任何其他格式的点(例如,'...')均被视为文件/目录名称。

请注意,返回的 规范路径 必须遵循下述格式:

  • 始终以斜杠 '/' 开头。
  • 两个目录名之间必须只有一个斜杠 '/' 。
  • 最后一个目录名(如果存在)不能 以 '/' 结尾。
  • 此外,路径仅包含从根目录到目标文件或目录的路径上的目录(即,不含 '.' 或 '..')。

返回简化后得到的 规范路径 。

【输入样例】path="/home/"

【输出样例】"/home"

解题思路:

1. 根据‘/’将给定字符串进行分割,分割之后有三种情况:空字符串,一个点(.)和两个点(..);

2.遍历分割的字符串,将目录名存入到栈中。

遇到空字符串跳过,因为空字符串是由于多个/出现在一个;

3. 遇到'.'不处理,表示当前目录本身

4. 遇到'..‘弹出栈顶目录,切换到上一级

class Solution {public String simplifyPath(String path) {String[] splitPath = path.split("/");List<String> stack = new ArrayList<>();for(String current:splitPath){if("..".equals(current)){//出栈,切换到上一级目录,要不为空if(!stack.isEmpty()){stack.remove(stack.size()-1);}}else if(current.length() > 0 && !".".equals(current)){//当前的字符串长度大于0,表示不是空字符串,当前的字符也不是·,进栈stack.add(current);}}//拼接,空的时候也要返回一个/StringBuffer result = new StringBuffer();if(stack.isEmpty()){result.append("/");}else{//不为空,一直读出,直到空int n = 0;while(n<stack.size()){result.append("/");result.append(stack.get(n));++n;}}return result.toString();}
}

时间: 击败了94.43%

内存: 击败了77.54%

 155.最小栈

题意:

设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

【输入样例】

["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

【输出样例】

[null,null,null,null,-3,null,0,-2]

解题思路:

这道题目初看,嗯好像没啥难点,其实最主要的是在获取最小值这个函数的实现;

刚拿到的时候,想着我就定义一个全局变量min,然后每次push的时候进行比较,这样就可以存储到最小的值了。但是,忽略了出栈的时候,保存的最小值可能会被弹出,这个时候,min怎么更新呢?

正确的做法是新开一个额外的栈,存储栈在剩余k个数据时的最小值;

1.minStack先存Integer.MAX_VALUE;

2.stack执行push操作的时候,minStack也要存储此时的最小值,Math.min(minStack.peek(), val);

3. stack执行pop操作的时候,minStack也要执行pop操作,这样才能做到一致。

class MinStack {Deque<Integer> stack;Deque<Integer> minStack;public MinStack() {stack = new LinkedList<Integer>(); minStack = new LinkedList<Integer>(); minStack.push(Integer.MAX_VALUE);}public void push(int val) {stack.push(val);minStack.push(Math.min(minStack.peek(), val));}public void pop() {stack.pop();minStack.pop();}public int top() {return stack.peek();}public int getMin() { return minStack.peek();}
}

时间: 击败了95.54%

内存: 击败了48.09%

 150.逆波兰表达式求值

题意:

给你一个字符串数组 tokens ,表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意:

  • 有效的算符为 '+''-''*' 和 '/' 。
  • 每个操作数(运算对象)都可以是一个整数或者另一个表达式。
  • 两个整数之间的除法总是 向零截断 。
  • 表达式中不含除零运算。
  • 输入是一个根据逆波兰表示法表示的算术表达式。
  • 答案及所有中间计算结果可以用 32 位 整数表示

【输入样例】token=["2","1","+","3","*"]

【输出样例】9    (2+1)*3=9

解题思路:

逆波兰表达式,也叫后缀表达式,就是运算符在两个运算数后面,ab* --> a*b

1. 用栈实现,遇到是运算数,进栈

2. 遇到操作符+-*/ 的时候,弹出栈顶和次栈顶的值,注意,运算的顺序是 次栈顶 操作符 栈顶;计算完结果后要将计算结果存入栈中;

class Solution {public int evalRPN(String[] tokens) {Deque<Integer> num = new LinkedList<Integer>();int a,b,temp;for(String str : tokens){//注意,存入数据的时候,将其转成int形。方便计算if(isNumber(str)){num.push(Integer.parseInt(str));}else{b = num.pop();a = num.pop();switch(str){case "+":num.push(a+b);break;case "-":num.push(a-b);break;case "*":num.push(a*b);break;case "/":num.push(a/b);break;}}}return num.peek();}public boolean isNumber(String str){return !("+".equals(str) ||"-".equals(str) ||"*".equals(str) ||"/".equals(str));}
}

时间: 击败了92.77%

内存: 击败了79.78%

 

相关文章:

【LeetCode-经典面试150题-day12】

20.有效的括号 题意&#xff1a; 给定一个只包括 (&#xff0c;)&#xff0c;{&#xff0c;}&#xff0c;[&#xff0c;] 的字符串 s &#xff0c;判断字符串是否有效。 有效字符串需满足&#xff1a; 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括…...

TCP机制-延迟应答,捎带应答

在看本篇博客前推荐先看TCP中窗口和滑动窗口的含义以及流量控制 延迟应答和捎带应答都是TCP用于提高网络传输效率的机制 延迟应答 当发送端发送数据给接收端了以后&#xff0c;按道理接收端的内核会立即返回ACK&#xff08;应答报文&#xff09;给发送端&#xff0c;而且ACK&a…...

【Redis从头学-8】Redis中的ZSet数据类型实战场景之用户积分榜

&#x1f9d1;‍&#x1f4bb;作者名称&#xff1a;DaenCode &#x1f3a4;作者简介&#xff1a;啥技术都喜欢捣鼓捣鼓&#xff0c;喜欢分享技术、经验、生活。 &#x1f60e;人生感悟&#xff1a;尝尽人生百味&#xff0c;方知世间冷暖。 &#x1f4d6;所属专栏&#xff1a;Re…...

Springboot内嵌SQLite配置使用

版本号 MacOS Apple M1 | Jdk17 | Maven 3.8.5 | SpringBoot 2.6.9 | SQLite 3.42.0.0 pom.xml <dependencies><dependency><groupId>org.xerial</groupId><artifactId>sqlite-jdbc</artifactId><version>3.42.0.0</version&g…...

【微服务学习笔记】认识微服务

【微服务学习笔记】认识微服务 单体架构 分布式架构 微服务架构 SpringCloud 服务拆分和注意事项 服务拆分的案例demo 各个服务之间的数据库都是相互独立的&#xff0c;你不能直接访问对方的数据库&#xff0c;只能从一个服务像另外一个服务发起远程调用 在订单模块的服务中 …...

基于Android R快速编译recovery-ramdisk.img

Android默认没有单编recovery-ramdisk.img的命令&#xff0c;我们可以自己修改Makefile实现 修改&#xff1a;build/core/Makefile 添加&#xff1a; .PHONY: recovery-ramdisk-nodeps recovery-ramdisk-nodeps: $(MKBOOTFS) | $(COMPRESSION_COMMAND_DEPS)echo "make …...

Redis分布式缓存

分布式缓存 -- 基于Redis集群解决单机Redis存在的问题 单机的Redis存在四大问题&#xff1a; 1.Redis持久化 Redis有两种持久化方案&#xff1a; RDB持久化 AOF持久化 1.1.RDB持久化 RDB全称Redis Database Backup file&#xff08;Redis数据备份文件&#xff09;&#x…...

最大公约数和最小公倍数

最大公约数&#xff1a; 概念&#xff1a; 公约数中最大的称为最大公约数。 对任意的若干个正整数&#xff0c;1总是它们的公因数。 公约数与公倍数相反&#xff0c;就是既是A的约数同时也是B的约数的数&#xff0c;12和15的公约数有1&#xff0c;3&#xff0c;最大公约数就是…...

数据结构——二叉搜索树(附带C++实现版本)

文章目录 二叉搜索树概念 二叉树的实际应用二叉树模拟实现存储结构二叉搜索树构成二叉搜索树的查找插入操作中序遍历二叉树的删除循环(利用左子树最右节点&#xff09;递归(利用右子树根节点) 二叉树拷贝二叉树资源的销毁 二叉树实现完整代码总结 二叉搜索树 概念 二叉搜索树…...

C++(3)C++对C的扩展Extension

类型增强 1、类型更加严格 不初始化&#xff0c;无法通过编译&#xff1b;C不初始化&#xff0c;则随机赋值 #include <iostream> #include <stdlib.h>int main() {const int a 100; //真正的const,无法修改 // int *p &a; 报错const int *p…...

在vscode(idea)使用GitHub账号、Copilot异常

在idea使用GitHub账号、Copilot异常 登录GitHub显示 Invalid authentication data.Connection refused: connect或者副驾驶显示 Failed to initiate the GitHub login process. Please try again.一般网上的方法推荐使用token登录&#xff0c;或者降级副驾驶 经过研究&#x…...

新的后端渲染:服务器驱动UI

通过API发送UI是一种彻底的新方法&#xff0c;将改变传统的UI开发。 一项正在改变我们对用户界面 (UI) 的看法的技术是通过 API 发送 UI&#xff0c;也称为服务器驱动UI。这种方法提供了新水平的活力和灵活性&#xff0c;正在改变 UI 开发的传统范例。 服务器驱动 UI 不仅仅是…...

Postman如何做接口自动化测试?

前言 什么是自动化测试 把人对软件的测试行为转化为由机器执行测试行为的一种实践。 例如GUI自动化测试&#xff0c;模拟人去操作软件界面&#xff0c;把人从简单重复的劳动中解放出来。 本质是用代码去测试另一段代码&#xff0c;属于一种软件开发工作&#xff0c;已经开发完…...

excel文本函数篇2

本期主要介绍LEN、FIND、SEARCH以及后面加B的情况&#xff1a; &#xff08;1&#xff09;后缀没有B&#xff1a;一个字节代表一个中文字符 &#xff08;2&#xff09;后缀有B&#xff1a;两个字节代表一个中文字符 1、LEN(text)&#xff1a;返回文本字符串中的字符个数 2、…...

【MyBatis】动态SQL > 重点:${...}和#{...}与resultMap和resultType的区别

目录 一、MyBatis动态sql 1.1 动态sql的作用 1.2 动态sql作用论证 1.2.1 条件判断&#xff1a;<if> 1.2.2 循环迭代&#xff1a;<foreach> 1.2.3 SQL片段重用 1.2.4 动态条件组合&#xff1a;<choose><when><otherwise> 1.2.5 <where…...

什么是BEM命名规范?为什么要使用BEM命名规范?

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ BEM命名规范⭐ 为什么使用BEM命名规范&#xff1f;⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅&#xff01;这个专栏是为…...

JavaScript:交集和差集的应用场景

在集合A和集合B中&#xff0c;属于集合A&#xff0c;同时也属于集合B的元素组成的集合&#xff0c;就是交集。 在A中所有不属于集合B元素&#xff0c;组合成集合&#xff0c;就是差集。 那么在平时的开发中&#xff0c;如何使用差集和交集来解决问题呢&#xff1f; 现在有这…...

达梦数据库表空间创建和管理

概述 本文将介绍在达梦数据库如何创建和管理表空间。 1.创建表空间 1.1表空间个数限制 理论上最多允许有65535个表空间&#xff0c;但用户允许创建的表空间 ID 取值范围为0~32767&#xff0c; 超过 32767 的只允许系统使用&#xff0c;ID 由系统自动分配&#xff0c;ID不能…...

三、MySQL 数据库安装集

一、CentOS—YUM 1. MySQL—卸载 # 1、查看存在的MySQL。 rpm -qa | grep -i mysql rpm -qa | grep mysql# 2、删除存在的MySQL。 rpm -e –-nodeps 包名# 3、查找存在的MySQL目录。 find / -name mysql# 4、删除存在的MySQL目录。 rm -rf 目录# 5、删除存在的MySQL配置文件。…...

【BASH】回顾与知识点梳理(三十九)

【BASH】回顾与知识点梳理 三十九 三十九. make、tarball、函数库及软件校验39.1 用 make 进行宏编译为什么要用 makemakefile 的基本语法与变量 39.2 Tarball 的管理与建议使用原始码管理软件所需要的基础软件Tarball 安装的基本步骤一般 Tarball 软件安装的建议事项 (如何移除…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会

在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...

消防一体化安全管控平台:构建消防“一张图”和APP统一管理

在城市的某个角落&#xff0c;一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延&#xff0c;滚滚浓烟弥漫开来&#xff0c;周围群众的生命财产安全受到严重威胁。就在这千钧一发之际&#xff0c;消防救援队伍迅速行动&#xff0c;而豪越科技消防一体化安全管控平台构建的消防“…...

起重机起升机构的安全装置有哪些?

起重机起升机构的安全装置是保障吊装作业安全的关键部件&#xff0c;主要用于防止超载、失控、断绳等危险情况。以下是常见的安全装置及其功能和原理&#xff1a; 一、超载保护装置&#xff08;核心安全装置&#xff09; 1. 起重量限制器 功能&#xff1a;实时监测起升载荷&a…...

OpenGL-什么是软OpenGL/软渲染/软光栅?

‌软OpenGL&#xff08;Software OpenGL&#xff09;‌或者软渲染指完全通过CPU模拟实现的OpenGL渲染方式&#xff08;包括几何处理、光栅化、着色等&#xff09;&#xff0c;不依赖GPU硬件加速。这种模式通常性能较低&#xff0c;但兼容性极强&#xff0c;常用于不支持硬件加速…...

更新 Docker 容器中的某一个文件

&#x1f504; 如何更新 Docker 容器中的某一个文件 以下是几种在 Docker 中更新单个文件的常用方法&#xff0c;适用于不同场景。 ✅ 方法一&#xff1a;使用 docker cp 拷贝文件到容器中&#xff08;最简单&#xff09; &#x1f9f0; 命令格式&#xff1a; docker cp <…...

今日行情明日机会——20250609

上证指数放量上涨&#xff0c;接近3400点&#xff0c;个股涨多跌少。 深证放量上涨&#xff0c;但有个小上影线&#xff0c;相对上证走势更弱。 2025年6月9日涨停股主要行业方向分析&#xff08;基于最新图片数据&#xff09; 1. 医药&#xff08;11家涨停&#xff09; 代表标…...

AI书签管理工具开发全记录(十八):书签导入导出

文章目录 AI书签管理工具开发全记录&#xff08;十八&#xff09;&#xff1a;书签导入导出1.前言 &#x1f4dd;2.书签结构分析 &#x1f4d6;3.书签示例 &#x1f4d1;4.书签文件结构定义描述 &#x1f523;4.1. ​整体文档结构​​4.2. ​核心元素类型​​4.3. ​层级关系4.…...