LeetCode(剑指offer) Day1
1.用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail
和 deleteHead
,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead
操作返回 -1 )
解题过程记录:本题就是用两个栈,其中一个作为输入栈,另外一个作为输出栈,由于栈的特点是先进后出,有序数字全部进栈然后再出栈会使这个数字序列逆序,然后逆序数字序列再一次经过进栈出栈操作会再次逆序,经过这两次逆序,原本的数字序列的顺序会保持不变,符合队列先进先出的特点。
第一次提交未通过:出队列时,直接把输入栈的数字压入输出栈,忽略了此时输出栈中可能还会有数据,如果输出栈中有数据,序列顺序前后并不符合先进先出的特点。
class CQueue {Stack<Integer>s1=null,s2=null;public CQueue() {s1=new Stack<>();s2=new Stack<>();}public void appendTail(int value) {s1.push(value);}public int deleteHead() {while(!s1.isEmpty()){s2.push(s1.pop());}if (s2.isEmpty()){return -1;}return s2.pop();}
}
第二次提交未通过:调用appendTail函数出队列,先判断s1输入栈中是否有数据,如果有并且s2输出栈中为空,将s1的数据全部压入s2输出栈,两栈全为空返回-1。思路混乱错误
class CQueue {Stack<Integer>s1=null,s2=null;public CQueue() {s1=new Stack<>();s2=new Stack<>();}public void appendTail(int value) {s1.push(value);}public int deleteHead() {while(!s1.isEmpty()){if(s2.isEmpty()){s2.push(s1.pop());}}if (s2.isEmpty()){return -1;}return s2.pop();}
}
第三次提交通过: 只有出stack为空的时候,才将进stack的数据全部倒入出stack。
class CQueue {Stack<Integer>s1=null,s2=null;public CQueue() {s1=new Stack<>();s2=new Stack<>();}public void appendTail(int value) {s1.push(value);}public int deleteHead() {if (s2.isEmpty()){if(s1.isEmpty()){return -1;}while(!s1.isEmpty()){s2.push(s1.pop());}}return s2.pop();}
}
2.定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。示例:
inStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.min(); --> 返回 -2.
解法一:使用主栈s存储数字序列,用一个辅助栈stackTemp同步记录主栈中的最小值。具体来说,当一个元素要入栈时,我们取当前辅助栈的栈顶存储的最小值,与当前元素比较得出最小值,将这个最小值插入辅助栈中;当一个元素要出栈时,我们把辅助栈的栈顶元素也一并弹出;在任意一个时刻,栈内元素的最小值就存储在辅助栈的栈顶元素中。
class MinStack {/** initialize your data structure here. */Stack<Integer> s=null;Stack<Integer>stackTemp=null;public MinStack() {s=new Stack<>();stackTemp=new Stack<>();}public void push(int x) {s.push(x);if(stackTemp.isEmpty()){stackTemp.push(x);}else{stackTemp.push(Math.min(x,stackTemp.peek()));}}public void pop() {s.pop();stackTemp.pop();}public int top() {return s.peek();}public int min() {return stackTemp.peek();}
}/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.push(x);* obj.pop();* int param_3 = obj.top();* int param_4 = obj.min();*/
解法二:不使用辅助栈,保留当前最小值和差值,这种方法称为差值法。
解法思路讲解:差值法就是在向栈中插入数据的同时,同步记录并更新栈中的最小值,向栈中插入值x,栈中保存的不再是原值,而是x与最小值的差值即x-min。按照这种思路,push函数如下:
public void push(int x) {if (stack.isEmpty()) {stack.push(x);min = x;//栈为空,插入的第一个值作为当前最小值} else {stack.push(x - min);//栈不为空,后续插入栈中的值是x-minmin = Math.min(min, x);//每插入一个新值,需要同步更新最小值}}
入栈序列 | 5 | 2 | 3 | -2 | 1 |
栈实际保存的值 | 5 | -3 | 1 | -4 | 3 |
当前最小值 | 5 | 2 | 2 | -2 | -2 |
如果用min记录当前栈中的最小值,用min与栈中的元素进行运算就很容易复原原序列的真实值。通过上面的表格举个例子,入栈序列:5 2 3 -2 1 经过x-min运算存入栈中实际值为 5 -3 1 -4 3。此时栈顶元素为3,是一个整数即x-min>0,也即x>min,说明x不是最小值,如果此时查看栈顶元素,直接返回min+栈顶元素即可复原真实值;但是如果栈顶元素为负数,说明入栈的元素比当前栈中的最小值还要小,那么最小值min就是原值x;还有一种特殊情况,由于我们向栈中插入第一个元素的时候,没有做x-min操作而是直接将真实值插入栈中,并且将它作为最小值,所以当栈中仅有一个元素的时候,栈顶元素=min=真实值。综合上述三种情况,故top函数:
public int top() {if (stack.peek() < 0 || stack.size()==1) {return min;} else {return (min + stack.peek());}}
前面我们分析过,如果当前栈顶元素为正数,说明该元素不与最小值对应,可以直接pop,无需更新min;如果栈顶元素为负数,说明该元素与最小值对应,而且pop出的元素就是最小值,pop出后我们需要确定栈中剩余元素的最小值,假设push该元素的时候插入栈中的值为value,那么value=x-min,公式变形得min=x-value。经过上面的分析,pop函数为:
public void pop() {if (stack.peek() < 0) {min = min - stack.pop();} else {stack.pop();}}
我们回看push函数中的一行代码 stack.push(x - min)
这里题目要求传入的值x是int类型,假设x为Integer.MAX_VALUE,min为Integer.MIN_VALUE,这样x-min运算势必会溢出,因此min需要改为long 类型,相关的算数运算也要在long类型下进行,因此代码优化为:
import java.util.Stack;public class MinStack {Stack<Long> stack = null;long min;public MinStack() {stack = new Stack<>();}public void push(int x) {if (stack.isEmpty()) {stack.push((long)x);min = (long)x;} else {stack.push((long)(x - min));min = Math.min(min, x);}}public void pop() {if (stack.peek() < 0) {min = min - stack.pop();} else {stack.pop();}}public int top() {if (stack.peek() < 0 || stack.size()==1) {return (int)min;} else {return (int)(min + stack.peek());}}public int min() {return (int)min;}
}
相关文章:

LeetCode(剑指offer) Day1
1.用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 ) 解题过程记录:本题就是用两个栈&…...

1、MyBatis框架——JDBC代码回顾与分析、lombok插件的安装与使用
目录 一、JDBC基本操作步骤 二、JDBC代码 三、lombok插件的安装与使用 1、lombok插件的安装 2、lombok常用注解 Data Getter Setter ToString AllArgsConstructor NoArgsConstructor 3、lombok的使用 四、JDBC代码分析 一、JDBC基本操作步骤 1、导包mysql-connect…...
笔记-GPS设备定位方式
1. 背景 最近接触到的GPS设备有点多,逐渐明白大家定位的机理,也结合网上的文章《GPS、WiFi、基站、AGPS几种定位原理介绍与区别》 来做一个简单的总结。 2. 基于GPS定位 这是最基本的定位能力,它主要就是寻找卫星,利用光传播速度…...
2023秋招携程SRE算法岗面试经验分享
本专栏分享 计算机小伙伴秋招春招找工作的面试经验和面试的详情知识点 专栏首页:秋招算法类面经分享 主要分享计算机算法类在面试互联网公司时候一些真实的经验 面试code学习参考请看:...

4.9 内部类
文章目录1.内部类概述2.特点3.练习 : 内部类入门案例4.成员内部类4.1 练习 : 被private修饰4.2 练习 : 被static修饰5.局部内部类6.匿名内部类1.内部类概述 如果一个类存在的意义就是为指定的另一个类,可以把这个类放入另一个类的内部。 就是把类定义在类的内部的情…...
ncnn模型精度验证
验证ncnn模型的精度 1、进行pth模型的验证 得到ncnn模型的顺序为:.pth–>.onnx–>ncnn .pth的精度验证如下: 如进行的是二分类: model init_model(model, data_cfg, devicedevice, modeeval)###.pth转.onnx模型# #---# input_names …...

IB-PYP幼儿十大素质培养目标
作为IB候选学校,一直秉承IB教育的核心目标,贯彻在幼儿的学习生活中。IB教育之所以成为当今国际教育的领跑者,最主要的原因是IB教育是切切实实的“全人”教育,“素质”教育,拥有一套完整的教学服务体系。当我们走进IB“…...

02.13:监督学习中的分类问题
今天首先学习了监督学习中的分类问题,跑了两个代码。现在学起来感觉机器学习有很多不同的定理建立了不同的分类器,也就是所谓不同的方法。具体的数学原理我不太清楚。然后不同的应用场景有一个最优的分类器。 值得一提的应该就是终于清晰的明白了精度&am…...
leetcode刷题 | 关于二叉树的题型总结3
leetcode刷题 | 关于二叉树的题型总结3 文章目录leetcode刷题 | 关于二叉树的题型总结3题目连接递增顺序搜索树二叉搜索树中的中序后继把二叉搜索树转换为累加树二叉搜索树迭代器题目连接 897. 递增顺序搜索树 - 力扣(LeetCode) 剑指 Offer II 053. 二…...
设计模式-结构型
设计模式-结构型 结构型设计模式包含:代理模式、适配器模式、桥接模式、装饰模式、外观设计模式、享元模式、组合模式 代理模式 核心是在具体的功能类与使用者之间建立一个中介类作为代理,使用者通过代理对象对真实的功能类进行访问。 在iOS开发中&am…...
【新】华为OD机试 - 预订酒店(Python)| 运气好 会考到原题
预订酒店 题目 放暑假了,小明决定到某旅游景点游玩,他在网上搜索到了各种价位的酒店(长度为 n 的数组 A),他的心理价位是 x 元,请帮他筛选出 k 个最接近 x 元的酒店(n>=k>0),并由低到高打印酒店的价格。 输入 第一行:n, k, x 第二行:A[0] A[1] A[2]...A[n-…...

【编程基础之Python】4、安装Python开发工具
【编程基础之Python】4、安装Python开发工具安装Python开发工具为什么需要开发工具Anaconda自带的开发工具PyCharm安装PyCharm运行PyCharm并创建项目总结安装Python开发工具 为什么需要开发工具 通常情况下,为了提高开发效率,需要使用相应的开发工具&a…...

5. 最长回文子串
文章目录题目描述暴力法中心扩散法参考文献题目描述 给你一个字符串 s,找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。 示例 1: 输入:s “babad” 输出:“bab” 解释&a…...

内网渗透(二十四)之Windows协议认证和密码抓取-Mimikatz读取sam和lsass获取密码
系列文章第一章节之基础知识篇 内网渗透(一)之基础知识-内网渗透介绍和概述 内网渗透(二)之基础知识-工作组介绍 内网渗透(三)之基础知识-域环境的介绍和优点 内网渗透(四)之基础知识-搭建域环境 内网渗透(五)之基础知识-Active Directory活动目录介绍和使用 内网渗透(六)之基…...

【THREE.JS】网页中的炫酷3D
web3d一、前言粒子特效二维漫画可视化后期处理二、项目使用流程2.1 项目结构2.2 基本使用2.3 项目模板2.4 技术栈三、基础动画3.1 THREE.Clock3.2 GASP四、照相机8.1 正交相机8.2 透视相机4.3 相机控制器五、画布和全屏六、几何体七、Debug UI八、纹理贴图8.1 mipmapping8.2 放…...

Go语言之 下载安装go以及vscode配置go环境
上篇请移步到Go语言之 下载安装及第一个代码_水w的博客-CSDN博客 目录 一、下载安装以及配置go环境 1 下载安装go 2 配置go环境 二、安装配置git 一、在vscode上开发golang 1 配置 2 编写代码 解决报错:go: go.mod file not found in current directory or …...
RBAC权限 API声明四种kubernetes对象
RBAC API声明了四种kubernetes对象: Role ClusterRole RoleBinding ClusterRoleBinding Role: 名称空间内创建授权角色,指定空间名字 ClusterRole: 全局角色,集群范围,对所有名称空间有效 RoleBinding: 名称…...
CDGP仿真选择题4
CDGP仿真选择题13、指标(Metrics)可以用来衡量数据管理的效果。请从下列选项中选择正确的表述: (知识点: CDGP仿真题)A.指标是衡量或评估绩效、进度、质量、效率或其他影响的标准B.这些指标用于定义每个知识领域内完成工作的可量化事实C.指标也可以测量更抽象的特性,…...

典型相关分析与R语言实现
典型相关分析学习目标学习内容典型相关分析的原理典型相关分析的理论内容例子具体实现方法内容小结注意解决方法学习目标 我们所采用的学习内容来自B站的Lizongzhang老师的R语言的学习分享 今天学习的主要内容是关于 典型相关分析 学习内容 首先声明,典型相关分析的内容理解…...

【蓝桥集训】第一天——前缀和
作者:指针不指南吗 专栏:Acwing 蓝桥集训每日一题 🐾输出的时候,注意数据类型🐾 文章目录1.截断数组2.前缀和3.子矩阵的和4.k倍区间1.截断数组 给定一个长度为 n 的数组 a1a_1a1,a2a_2a2,…,ana_nan。 现在&…...

TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...

RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...

Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...

如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...