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

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...

PostgreSQL——环境搭建

一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在&#xff0…...

小木的算法日记-多叉树的递归/层序遍历

&#x1f332; 从二叉树到森林&#xff1a;一文彻底搞懂多叉树遍历的艺术 &#x1f680; 引言 你好&#xff0c;未来的算法大神&#xff01; 在数据结构的世界里&#xff0c;“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的&#xff0c;它…...

区块链技术概述

区块链技术是一种去中心化、分布式账本技术&#xff0c;通过密码学、共识机制和智能合约等核心组件&#xff0c;实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点&#xff1a;数据存储在网络中的多个节点&#xff08;计算机&#xff09;&#xff0c;而非…...