算法刷题-二叉树的锯齿形层序遍历、用栈实现队列 栈设计、买卖股票的最佳时机 IV
文章目录
- 二叉树的锯齿形层序遍历(树、广度优先搜索)
- 用栈实现队列(栈、设计)
- 买卖股票的最佳时机 IV(数组、动态规划)
二叉树的锯齿形层序遍历(树、广度优先搜索)
给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
例如:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回锯齿形层序遍历如下:
[ [3], [20,9], [15,7] ]
解答:
public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}
}
class Solution {public List<List<Integer>> zigzagLevelOrder(TreeNode root) {List<List<Integer>> list = new LinkedList<>();if (root == null) {return list;}Stack<TreeNode> stack1 = new Stack<>();stack1.push(root);boolean postive = true;while (!stack1.isEmpty()) {Stack<TreeNode> stack2 = new Stack<>();List<Integer> subList = new LinkedList<>();while (!stack1.isEmpty()) {TreeNode current = stack1.pop();subList.add(current.val);if (postive) {if (current.left != null) {stack2.push(current.left);}if (current.right != null) {stack2.push(current.right);}} else {if (current.right != null) {stack2.push(current.right);}if (current.left != null) {stack2.push(current.left);}}}postive = !postive;stack1 = stack2;list.add(subList);}return list;}
}
用栈实现队列(栈、设计)
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):
实现 MyQueue 类:
- void push(int x) 将元素 x 推到队列的末尾
- int pop() 从队列的开头移除并返回元素
- int peek() 返回队列开头的元素
- boolean empty() 如果队列为空,返回 true ;否则,返回 false
说明:
- 你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
- 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
进阶:
- 你能否实现每个操作均摊时间复杂度为 O(1) 的队列?换句话说,执行 n 个操作的总时间复杂度为 O(n) ,即使其中一个操作可能花费较长时间。
示例:
输入: ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []] 输出: [null, null, null, 1, 1, false]
解释: MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false
提示:
- 1 <= x <= 9
- 最多调用 100 次 push、pop、peek 和 empty
- 假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)
解答:
class MyQueue {Stack<Integer> s1;Stack<Integer> s2;/** Initialize your data structure here. */public MyQueue() {s1 = new Stack<Integer>();s2 = new Stack<Integer>();}/** Push element x to the back of queue. */public void push(int x) {while (!s1.empty())s2.push(s1.pop());s1.push(x);while (!s2.empty())s1.push(s2.pop());return;}/** Removes the element from in front of queue and returns that element. */public int pop() {return s1.pop();}/** Get the front element. */public int peek() {int ret = s1.pop();s1.push(ret);return ret;}/** Returns whether the queue is empty. */public boolean empty() {return s1.empty();}
}
/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = new MyQueue();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.peek();* boolean param_4 = obj.empty();*/
买卖股票的最佳时机 IV(数组、动态规划)
给定一个整数数组 prices ,它的第_ i 个元素 prices[i] 是一支给定的股票在第 i _天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
**注意:**你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1:
输入:k = 2, prices = [2,4,1] 输出:2 解释:在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得利润 = 4-2 = 2 。
示例 2:
输入:k = 2, prices = [3,2,6,5,0,3] 输出:7 解释:在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。 随后,在第 5 天 (股票价格 = 0) 的时候买入,在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
提示:
- 0 <= k <= 100
- 0 <= prices.length <= 1000
- 0 <= prices[i] <= 1000
解答:
class Solution {public int maxProfit(int k, int[] prices) {if (k < 1)return 0;if (k >= prices.length / 2)return greedy(prices);int[][] t = new int[k][2];for (int i = 0; i < k; ++i)t[i][0] = Integer.MIN_VALUE;for (int p : prices) {t[0][0] = Math.max(t[0][0], -p);t[0][1] = Math.max(t[0][1], t[0][0] + p);for (int i = 1; i < k; ++i) {t[i][0] = Math.max(t[i][0], t[i - 1][1] - p);t[i][1] = Math.max(t[i][1], t[i][0] + p);}}return t[k - 1][1];}private int greedy(int[] prices) {int max = 0;for (int i = 1; i < prices.length; ++i) {if (prices[i] > prices[i - 1])max += prices[i] - prices[i - 1];}return max;}
}
本文内容到此结束了,
如有收获欢迎点赞👍收藏💖关注✔️,您的鼓励是我最大的动力。
如有错误❌疑问💬欢迎各位指出。
主页:共饮一杯无的博客汇总👨💻保持热爱,奔赴下一场山海。🏃🏃🏃
相关文章:
算法刷题-二叉树的锯齿形层序遍历、用栈实现队列 栈设计、买卖股票的最佳时机 IV
文章目录二叉树的锯齿形层序遍历(树、广度优先搜索)用栈实现队列(栈、设计)买卖股票的最佳时机 IV(数组、动态规划)二叉树的锯齿形层序遍历(树、广度优先搜索) 给定一个二叉树&…...
华为OD机试 - 最小传递延迟(Python)| 代码编写思路+核心知识点
最小传递延迟 题目 通讯网络中有 N 个网络节点 用 1 ~ N 进行标识 网络通过一个有向无环图进行表示 其中图的边的值,表示节点之间的消息传递延迟 现给定相连节点之间的延时列表 times[i]={u,v,w} 其中 u 表示源节点,v 表示目的节点,w 表示 u 和 v 之间的消息传递延时 请计…...
集中供热调度系统天然气仪表内网仪表图像识别案例
一、项目需求 出于能耗采集与冬季集中供暖工作的节能和能耗分析需要,要采集现场的6块天然气表计,并存储进入客户的mySQL数据库中,现场采集的表计不允许接线,且网络环境为内网环境,需要采集表计数据并存入数据库&#…...
笔试题-2023-复旦微-数字IC设计【纯净题目版】
回到首页:2023 数字IC设计秋招复盘——数十家公司笔试题、面试实录 推荐内容:数字IC设计学习比较实用的资料推荐 题目背景 笔试时间:2022.07.26应聘岗位:数字前端工程师笔试时长:120min笔试平台:赛码题目类型:基础题(10道)、选做题(10道)、验证题(5道)主观评价 难…...
【Linux】冯诺依曼体系结构和操作系统概念
文章目录🎪 冯诺依曼体系结构🚀1.体系概述🚀2.CPU和内存的数据交换🚀3.体系结构中数据的流动🎪 操作系统概念理解🚀1.简述🚀2.设计目的🚀3.定位🚀4.理解🚀5.管…...
HTML5之HTML基础学习笔记
列表标签 列表的应用场景 场景:在网页中按照行展示关联性的内容,如:新闻列表、排行榜、账单等特点:按照行的方式,整齐显示内容种类:无序列表、有序列表、自定义列表 这是老师PPT上的内容, 列表…...
FreeRTOS信号量 | FreeRTOS十
目录 说明: 一、信号量 1.1、信号量简介 1.2、信号量特点 二、二值信号量 2.1、二值信号量简介 2.2、获取与释放二值信号量函数 2.3、二值信号量使用过程与相关API函数 2.4、创建二值信号量函数了解 2.5、释放二值信号量了解 2.6、获取二值信号量了解 三…...
【SpringBoot】SpringBoot常用注解
一、前言首先这里说的SpringBoot常用注解是指在我们开发项目过程中,我们经常使用的注解,包含Spring、SpringBoot、SpringCloud、SpringMVC等这些框架中的注解,而不仅仅是SpringBoot中的注解。这里只是作一个注解列举,每个注解具体…...
数据一致性
目录一、AOP 动态代理切入方法(1) Aspect Oriented Programming(2) 切入点表达式二、SpringBoot 项目扫描类(1) ResourceLoader 扫描类(2) Map 的 computeIfAbsent 方法(3) 反射几个常用 api① 创建一个测试注解② 创建测试 PO 类③ 反射 api 获取指定类的指定注解信息(4) 返回…...
Docker不做虚拟化内核,对.NET有什么影响?
引子前两天刷抖音,看见了这样一个问题。问题:容器化不做虚拟内核,会有什么弊端?Java很多方法会跟CPU的核数有关,这个时候调用系统函数,读到的是宿主机信息,而不是我们限制资源的大小。思考&…...
HTML总结
CSS代码风格 空格规范: 1. 属性值前面,冒号后面,保留一个空格; 2. 选择器(标签)和大括号中间保留空格。 基本语法概述: 1.HTML标签是由尖括号包围的关键词,如<html> 2.HTM…...
ByteHouse:基于ClickHouse的实时数仓能力升级解读
更多技术交流、求职机会,欢迎关注字节跳动数据平台微信公众号,回复【1】进入官方交流群 ByteHouse是火山引擎上的一款云原生数据仓库,为用户带来极速分析体验,能够支撑实时数据分析和海量数据离线分析。便捷的弹性扩缩容能力&…...
[SSD固态硬盘技术 15] FTL映射表的神秘面纱
为什么需要映射表?固态硬盘的存储器件采用的是闪存[5],具有以下几个特点: (1)读写基本单位是以页(Page)为单位,擦除是以块(Block)为单位。...
浅析依赖注入框架的生命周期(以 InversifyJS 为例)
在上一篇介绍了 VSCode 的依赖注入设计,并且实现了一个简单的 IOC 框架。但是距离成为一个生产环境可用的框架还差的很远。 行业内已经有许多非常优秀的开源 IOC 框架,它们划分了更为清晰地模块来应对复杂情况下依赖注入运行的正确性。 这里我将以 Inv…...
HER2靶向药物研发进展-销售数据-上市药品前景分析
HER2长期作为肿瘤领域的热门靶点之一,其原因是它在多部位、多种形式的癌症中均有异常的表达,据研究表明HER2除了在胃癌、胆道癌、胆管癌、乳腺癌、卵巢癌、结肠癌、膀胱癌、肺癌、子宫颈癌、子宫浆液性子宫内膜癌、头颈癌、食道癌中的异常表达还存在于多…...
【第38天】不同路径数问题 | 网格 dp 入门
本文已收录于专栏🌸《Java入门一百例》🌸学习指引序、专栏前言一、网格模型二、【例题1】1、题目描述2、解题思路3、模板代码4、代码解析5.原题链接三、【例题2】1、题目描述2、解题思路3、模板代码4、代码解析5.原题链接三、推荐专栏四、课后习题序、专…...
LINUX之链接命令
链接命令学习目标能够说出软链接的创建方式能够说出硬链接的创建方式1. 链接命令的介绍链接命令是创建链接文件,链接文件分为:软链接硬链接命令说明ln -s创建软链接ln创建硬链接2. 软链接类似于Windows下的快捷方式,当一个源文件的目录层级比较深&#x…...
1628_MIT 6.828 xv6_chapter0操作系统接口
全部学习汇总: GreyZhang/g_unix: some basic learning about unix operating system. (github.com) 这本书最初看名字以为是对早期unix的一个解读,但是看了开篇发现 不完全是,只是针对JOS教学OS系统来做的一些讲解。 Xv6是对UNIX v6的重新实…...
使用 Sahi 实现 Web 自动化测试
Sahi 是 Tyto Software 旗下的一个基于业务的开源 Web 应用自动化测试工具。Sahi 运行为一个代理服务器,并通过注入 JavaScript 来访问 Web 页面中的元素。Sahi 支持 HTTPS 并且独立于 Web 站点,简单小巧却功能强大。它相对于 Selenium 等自动化测试工具…...
天津菲图尼克科技携洁净及无菌防护服解决方案与您相约2023生物发酵展
BIO CHINA 生物发酵产业一年一度行业盛会,由中国生物发酵产业协会主办,上海信世展览服务有限公司承办,2023第10届国际生物发酵产品与技术装备展览会(济南)于2023年3月30-4月1日在山东国际会展中心(济南市槐…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...
搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...
C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...
jmeter聚合报告中参数详解
sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample(样本数) 表示测试中发送的请求数量,即测试执行了多少次请求。 单位,以个或者次数表示。 示例:…...
Golang——7、包与接口详解
包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...
