当前位置: 首页 > 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 软件安装的建议事项 (如何移除…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

Razor编程中@Html的方法使用大全

文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...

Axure 下拉框联动

实现选省、选完省之后选对应省份下的市区...

WEB3全栈开发——面试专业技能点P7前端与链上集成

一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染&#xff08;SSR&#xff09;与静态网站生成&#xff08;SSG&#xff09; 框架&#xff0c;由 Vercel 开发。它简化了构建生产级 React 应用的过程&#xff0c;并内置了很多特性&#xff1a; ✅ 文件系…...