​LeetCode解法汇总1171. 从链表中删去总和值为零的连续节点

news/2024/2/21 4:02:33

目录链接:

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目:

https://github.com/September26/java-algorithms

原题链接:力扣


描述:

给你一个链表的头节点 head,请你编写代码,反复删去链表中由 总和 值为 0 的连续节点组成的序列,直到不存在这样的序列为止。

删除完毕后,请你返回最终结果链表的头节点。

你可以返回任何满足题目要求的答案。

(注意,下面示例中的所有序列,都是对 ListNode 对象序列化的表示。)

示例 1:

输入:head = [1,2,-3,3,1]
输出:[3,1]
提示:答案 [1,2,1] 也是正确的。

示例 2:

输入:head = [1,2,3,-3,4]
输出:[1,2,4]

示例 3:

输入:head = [1,2,3,-3,-2]
输出:[1]

提示:

  • 给你的链表中可能有 1 到 1000 个节点。
  • 对于链表中的每个节点,节点的值:-1000 <= node.val <= 1000.

解题思路:

* 解题思路:

* 构建前缀和,相同前缀和的位置,其连续累加值必定为0,相同前缀和之间的节点都是可以被删掉的。

* 另外,如果有多个前缀和都相同的节点,我们只需要取第一个和最后一个即可。

* 所以构建一个map,key为前缀和,value则为对应的节点。

* 首先遍历第一遍,找到最后一个前缀和的节点加入到map中。

* 然后第二遍循环,找到等于当前前缀和值的节点,这时候是一定存在的,是不过有可能是当前的节点。

* 如果是当前节点的话,使用node->next = seen[prefix]->next;也满足要求。

代码:

class Solution1171
{
public:ListNode *removeZeroSumSublists(ListNode *head){ListNode *newHead = new ListNode(0);newHead->next = head;int prefix = 0;map<int, ListNode *> seen;for (ListNode *node = newHead; node; node = node->next){prefix += node->val;seen[prefix] = node;}prefix = 0;for (ListNode *node = newHead; node; node = node->next){prefix += node->val;node->next = seen[prefix]->next;}return newHead->next;}
};


http://www.ppmy.cn/news/421319.html

相关文章

电脑重装系统后需要更新哪些驱动

在电脑重装系统后&#xff0c;由于系统的重置&#xff0c;您需要重新安装和更新一些关键的驱动程序&#xff0c;以确保硬件设备正常工作和性能最佳化。以下是在电脑重装系统后需要更新的一些常见驱动程序。 工具/原料&#xff1a; 系统版本&#xff1a;win10系统 品牌型号&…

iOS App 上架流程图文教学

在上架App 之前必须先准备好开发者帐号&#xff0c;但申请开发者帐号因法兰克早在之前已经申请好了&#xff0c;故就跳过此步骤&#xff0c;直接从产生凭证到上传App开始讲起。首先&#xff0c;要将自己辛苦写好的App 送审的话&#xff0c;则要依序做完下列几件事情即可。 在开…

云计算——云计算与虚拟化的关系

作者简介&#xff1a;一名云计算网络运维人员、每天分享网络与运维的技术与干货。 座右铭&#xff1a;低头赶路&#xff0c;敬事如仪 个人主页&#xff1a;网络豆的主页​​​​​ 目录 前言 一.虚拟化 1.什么是虚拟化 2.虚拟化技术作用 二.云计算与虚拟化的关系 三.虚…

PHP设计模式21-工厂模式的讲解及应用

文章目录 前言基础知识简单工厂模式工厂方法模式抽象工厂模式 详解工厂模式普通的实现更加优雅的实现 总结 前言 本文已收录于PHP全栈系列专栏&#xff1a;PHP快速入门与实战 学会好设计模式&#xff0c;能够对我们的技术水平得到非常大的提升。同时也会让我们的代码写的非常…

虚拟机全屏太小,如何放大

干货&#xff01;&#xff01;&#xff01; 点击虚拟机右上角的电源图表、&#xff0c;找到螺丝刀扳手图标、搜索Display更改分辨率、确认更改问题解决&#xff01;&#xff01;&#xff01;

有效减小虚拟机占的内存

我这个电脑内存少&#xff0c;D盘才350g,结果kali占了300g,主要的原因还是我的快照拍了比较多&#xff0c;平常拍快照可以避免我们操作失误导致系统崩溃&#xff0c;就算崩溃了还可以还原&#xff0c;这样确实挺好&#xff0c;但快照很占内存&#xff0c;如果是分散的快照还行&…

玩游戏计算机虚拟内存怎么设置,玩游戏时提示虚拟内存太小怎么办

小编这里要跟大家分享的是关于玩游戏时提示虚拟内存太小的解决方法&#xff0c;游戏是如今很多人在业余时间用来消遣和放松的方式&#xff0c;电脑运行顺畅是玩游戏必备的条件之一&#xff0c;否则就会很扫兴&#xff0c;但是一些用户反映&#xff0c;好不容易想要玩一把游戏的…

服务器虚拟内存最佳设置范围,虚拟内存有什么用?虚拟内存设置多少合适?

在硬盘上划分一块区域用于保存内存中暂时不用的数据&#xff0c;这块区域称为虚拟内存。相对于硬盘空间来说&#xff0c;内存容量往往小得多&#xff0c;尤其是2005 年以前(128MB、256MB)&#xff0c;现在内存容量增加不少&#xff0c;最小的都有4GB&#xff0c;大的有64GB、12…

最终幻想15计算机内存不足,虚拟内存不足

虚拟内存不足 08/12/2011 本文内容 当 Visual Studio 崩溃并且虚拟内存不足时&#xff0c;会显示此消息。 但是&#xff0c;这并不意味着系统中的虚拟内存不足&#xff0c;而是 Visual Studio 将用尽地址空间。 此错误通常出现在具有 32 位操作系统的计算机上&#xff0c;这些操…

什么是虚拟内存?虚拟内存的原理

虚拟内存 最近看Binder原理的时候&#xff0c;讲到一个概念MMap&#xff0c;Memory Map&#xff0c;内存映射&#xff0c;一言蔽之就是物理内存和虚拟内存的映射&#xff08;这个不是重点&#xff09;。然而突然产生个疑问——什么是虚拟内存&#xff1f;我大概是傻了&#xf…

认识---虚拟内存

内存 物理内存 真正的内存 真实插在板子的内存多大 虚拟内存 为满足内存容量不足需求 -> 在外存(硬盘)开辟空间 一个程序想要运行&#xff0c;必须运行在真实的物理内存之上。 所以必须在虚拟内存地址和物理内存地址之间建立一种映射关系。 虚拟内存的意义&#xff1a…

虚拟内存?

虚拟内存&#xff1f; 虚拟内存是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续的可用的内存&#xff08;一个连续完整的地址空间&#xff09;&#xff0c;而实际上&#xff0c;它通常是被分隔成多个物理内存碎片&#xff0c;还有部分暂时存储在外部磁盘存储器…

你知道虚拟内存吗?

虚拟内存 一、虚拟内存概述二、内存分段分段虚拟地址结构分段映射过程分段的不足之处内存碎片内存交换效率低内存交换效率低 三、内存分页内存分页映射过程分页是如何解决分段产生的物理碎片、内存交换效率低&#xff1f;简单分页存在的问题多级页表 四、TLB五、段页式内存管理…

聊聊虚拟内存

目录 前提的内存知识分段和分页页表 理解虚拟内存简述一下如何实现后备存储缺页中断处理过程共享 前提的内存知识 内存是什么&#xff1f;说白了就是一长串字节数组。编程的时候难免申请一段内存空间&#xff0c;有了内存空间才能存放数据、存放指令代码。 早期不存在操作系统…

什么是虚拟内存?服务器虚拟内存怎么设置最好?

什么是虚拟内存&#xff1f;服务器虚拟内存怎么设置最好&#xff1f; 一、什么是虚拟内存&#xff1f;虚拟内存有什么用处&#xff1f;二、怎么设置服务器虚拟内存&#xff1f;虚拟内存设置多少合适&#xff1f; 一、什么是虚拟内存&#xff1f;虚拟内存有什么用处&#xff1f;…

什么是虚拟内存

原文地址 深入剖析虚拟内存工作原理 (qq.com) 原作者&#xff1a;allanpan "计算机科学领域的任何问题都可以通过增加一个间接的中间层来解决" 我们电脑里的物理内存指的是RAM 主存&#xff08;随机访问存储器&#xff09;&#xff0c;它是与 CPU 直接交换数据的内部…

如何合理使用虚拟内存

这些天电脑老是出现虚拟内存不足现象&#xff0c;就在网上找了相关的信息来琢磨。。这篇文章共赏下。。 网上有很多广泛流传的关于虚拟内存优化的技巧&#xff0c;其实很多都是经不起推敲的。大家一起来看看吧。 观点一&#xff1a; 对于拥有大容量物理内存的用户&#xff0c;…

计算机更改虚拟内存有用吗,电脑内存不足怎么办,虚拟内存能起到多大作用

电脑内存不足怎么办,虚拟内存能起到多大作用?我们可以看到下图网友反映"电脑内存有12GB内存,但是玩大型游戏的时候,经常弹出内存不足的窗口,导致游戏经常崩溃"。怎么回事呢?其实跟我们今天聊的话题很契合,物理内存和虚拟内存有什么区别?那么虚拟内存有什么作…

计算机的体积大小和什么有关,虚拟内存的大小和什么有关?

满意答案 osaeiwqo 2013.06.27 采纳率&#xff1a;53% 等级&#xff1a;13 已帮助&#xff1a;13714人 内存在计算机中的作用很大&#xff0c;电脑中所有运行的程序都需要经过内存来执行&#xff0c;如果执行的程序很大或很多&#xff0c;就会导致内存消耗殆尽。为了解决这个…

kvm虚拟机调节内存

这个才是正确的做法&#xff0c;老夫实战&#xff0c;果然&#xff0c;大佬教给我们知识的时候都留了一手&#xff0c;哼 升级后 virsh setmem server1 8388608 查看正在运行的虚拟机&#xff1a; rootweb:~# virsh list --allId Name State ---…
最新文章