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

LeetCode 每日一题 Day 32 ||递归单调栈

2487. 从链表中移除节点

给你一个链表的头节点 head 。

移除每个右侧有一个更大数值的节点。

返回修改后链表的头节点 head 。

示例 1:
在这里插入图片描述

输入:head = [5,2,13,3,8]
输出:[13,8]
解释:需要移除的节点是 5 ,2 和 3 。

  • 节点 13 在节点 5 右侧。
  • 节点 13 在节点 2 右侧。
  • 节点 8 在节点 3 右侧。

示例 2:

输入:head = [1,1,1,1]
输出:[1,1,1,1]
解释:每个节点的值都是 1 ,所以没有需要移除的节点。

提示:

给定列表中的节点数目在范围 [1, 105] 内
1 <= Node.val <= 1e5

既然题目要倒着看最大值,明显可以用到递归,利用递归确定每个数右侧都是比他大的:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* removeNodes(ListNode* head) {if(head -> next == nullptr) {return head;}ListNode* node = removeNodes(head -> next);if(node -> val > head -> val) {return node;}head -> next = node;return head;}
};

看完题解后还有另外的解法,也就是单调栈

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* removeNodes(ListNode* head) {ListNode* dummy = new ListNode(0, head);ListNode* cur = head;vector<ListNode*> stk;for (ListNode* cur = head; cur; cur = cur->next) {while (stk.size() && stk.back()->val < cur->val) {stk.pop_back();}if (stk.size()) {stk.back()->next = cur;} else {dummy->next = cur;}stk.push_back(cur);}return dummy->next;}
};

灵神题解中还用了迭代来做:

class Solution {ListNode *reverseList(ListNode *head) {ListNode *pre = nullptr, *cur = head;while (cur) {ListNode *nxt = cur->next;cur->next = pre;pre = cur;cur = nxt;}return pre;}
public:ListNode *removeNodes(ListNode *head) {head = reverseList(head);ListNode *cur = head;while (cur->next) {if (cur->val > cur->next->val) {cur->next = cur->next->next;} else {cur = cur->next;}}return reverseList(head);}
};

相关文章:

LeetCode 每日一题 Day 32 ||递归单调栈

2487. 从链表中移除节点 给你一个链表的头节点 head 。 移除每个右侧有一个更大数值的节点。 返回修改后链表的头节点 head 。 示例 1&#xff1a; 输入&#xff1a;head [5,2,13,3,8] 输出&#xff1a;[13,8] 解释&#xff1a;需要移除的节点是 5 &#xff0c;2 和 3 。…...

【mars3d】FixedRoute的circle没有跟polyline贴着模型的解决方案

问题&#xff1a;【mars3d】官网的贴模型示例中&#xff0c;参考api文档增加了circle的配置&#xff0c;但是FixedRoute的circle没有跟polyline贴着模型 circle: { radius: 10, materialType: mars3d.MaterialType.CircleWave, materialOptions: { color: "#ffff00"…...

Day7 vitest 之 vitest配置第三版

项目目录 runner Type: VitestRunnerConstructor Default: node, 当运行test的时候 benchmark,当运行bench测试的时候 功能 自定义测试运行程序的路径。 要求 应与自定义库运行程序一起使用。 如果您只是运行测试&#xff0c;则可能不需要这个。它主要由library作者使用 …...

git补充上次提交

1.首先&#xff0c;确保你还没有执行 git push 操作。如果尚未推送到远程仓库&#xff0c;那么可以在本地进行修正。 2.添加遗漏的文件&#xff1a; git add <遗漏的文件路径>3.提交新修改或新增的文件&#xff0c;并将它与上一次提交合并&#xff08;如果希望保持提交历…...

计算机网络名词解释

1.ICMP 网际控制报文 允许主机或路由器报告差错情况和提供有关异常情况的报告 2.RIP路由信息协议 是一种分布式的&#xff0c;基于距离向量的路由选择协议 3.BGP 外部网关协议 是不同自治系统的路由器之间交换路由信息的协议 4.IGMP 网际管理协议 使用多播路由器知道多播…...

flink table view datastream互转

case class outer(f1:String,f2:Inner) case class outerV1(f1:String,f2:Inner,f3:Int) case class Inner(f3:String,f4:Int) 测试代码 package com.yy.table.convertimport org.apache.flink.streaming.api.scala.StreamExecutionEnvironment import org.apache.flink.tabl…...

redis重启后数据丢失问题解决(亲测好用)

redis修改密码重启后发现redis中的数据丢失了 解决办法&#xff1a; 首先在redis的安装目录下查找重启之前的dump.rdb文件&#xff0c;发现只有当天的一个dump.rdb文件&#xff0c;确认不是重启备份的文件 然后我就全盘找一下dump.rdb的备份文件&#xff0c;找到前一天的备份…...

敬请期待……

敬请期待…… 《Python百宝箱》 序号文章目录直达链接表白系列1无法拒绝的表白界面https://want595.blog.csdn.net/article/details/1347448942满屏飘字表白代码https://want595.blog.csdn.net/article/details/1350373883无限弹窗表白代码...

3.10 Android eBPF HelloWorld调试(四)

一,读取eBPF map的android应用程序示例 1.1 C++源码及源码解读 /system/memory/bpfmapparsed/hello_world_map_parser.cpp //基于aosp android12#define LOG_TAG "BPF_MAP_PARSER"#include <log/log.h> #include <stdlib.h> #include <unistd.h&g…...

PyTorch常用工具(1)数据处理

文章目录 前言1 数据处理1.1 Dataset1.2 DataLoader 前言 在训练神经网络的过程中需要用到很多的工具&#xff0c;最重要的是数据处理、可视化和GPU加速。本章主要介绍PyTorch在这些方面常用的工具模块&#xff0c;合理使用这些工具可以极大地提高编程效率。 由于内容较多&am…...

docker-简单说说cgroup

前面我们简单说了下namespace&#xff0c; 现在我们来接着简单说说cgroup。通过docker-简单说说namespace文章我们知道&#xff1a; namespace 是为了隔离进程组之间的资源&#xff0c;那cgroup就是为了对进程组的监控和限制资源。Cgroup 可以限制进程组使用的资源数量和分配&a…...

印象笔记04: 如何将印象笔记超级会员价值最大化利用?

印象笔记04&#xff1a; 如何将印象笔记超级会员价值最大化利用&#xff1f; 为什么有这个问题 我不知道有没有人一开始接触印象笔记觉得非常好。奈何只能两个设备同步&#xff0c;局限太多。而会员活动比较优惠——就开了会员。而且我开了十年……。只能开发一下看看怎么最大…...

我的JDK动态代理流程

我的JDK动态代理流程 我梳理的动态代理流程大约是&#xff1a; 如果每一个框架都有自己的BPP&#xff0c;且自己的BPP中都有自己的wrapIfNecessory&#xff0c;那样可能就是一个BPP一个代理类。但通常应该都是各自的框架以提供 Advisior&#xff08;切面&#xff09;的方式&am…...

uniapp Vue3 面包屑导航 带动态样式

上干货 <template><view class"bei"><view class"container"><view class"indicator"></view><!-- 遍历路由列表 --><view v-for"(item, index) in routes" :key"index" :class&quo…...

openGauss学习笔记-174 openGauss 数据库运维-备份与恢复-导入数据-管理并发写入操作

文章目录 openGauss学习笔记-174 openGauss 数据库运维-备份与恢复-导入数据-管理并发写入操作174.1 事务隔离说明174.2 写入和读写操作174.3 并发写入事务的潜在死锁情况 openGauss学习笔记-174 openGauss 数据库运维-备份与恢复-导入数据-管理并发写入操作 174.1 事务隔离说…...

数据分析可被划分为4个重要的类别

1、描述型&#xff1a;发生了什么&#xff1f; 全面、准确、实时的数据有效的可视化 2、诊断型&#xff1a;为什么会发生&#xff1f; 能够深入了解问题的根本原因隔离所有混淆信息的能力 3、预测型&#xff1a;可能发生什么&#xff1f; 通过历史数据来预测特定的结果通过…...

爆火小游戏敲木鱼流量主小程序源码系统+完整的代码包以及安装搭建教程

随着移动互联网的快速发展&#xff0c;小程序已成为一种新的应用形态&#xff0c;深入到人们生活的方方面面。其中&#xff0c;小游戏由于其简单、有趣的特点&#xff0c;吸引了大量用户&#xff0c;也成为了许多开发者的首选。敲木鱼小游戏&#xff0c;以其独特的玩法和轻松的…...

Invoke和BeginInvoke的区别

Invoke和BeginInvoke的区别 本文导读&#xff1a;BeginInvoke() 调用时&#xff0c;当前线程会启用线程池中的某个线程来执行此方法&#xff0c;当前线程不被阻塞&#xff0c;继续运行后面的代码&#xff0c; Invoke() 调用时&#xff0c;会阻塞当前线程&#xff0c;等到 Invo…...

3 分钟为英语学习神器 Anki 部署一个专属同步服务器

Anki 介绍 Anki 是一款基于间隔重复&#xff08;Spaced Repetition&#xff09;原理的学习软件&#xff0c;想象一下&#xff0c;你的大脑就像是一个需要定期维护的精密仪器。间隔重复就好比是一种精准的维护计划&#xff0c;它通过在最佳时刻复习信息&#xff0c;来确保知识在…...

<HarmonyOS第一课>应用程序框架

【习题】应用程序框架 目录 判断题 单选题 多选题 判断题 1. 一个应用只能有一个UIAbility。错误 正确(True)错误(False) 2. 创建的Empty Ability模板工程&#xff0c;初始会生成一个UIAbility文件。正确 正确(True)错误(False) 3. 每调用一次router.pushUrl()方法&…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...