专栏首页灰子学技术算法篇:链表之删除和为0的元素

算法篇:链表之删除和为0的元素

算法简介

利用前缀和的方法,例如前缀和[3,5,6,3,7],那么第一个3和最后一个3之间的节点之和就是0,不然的这两个数字不可能相等

// 1.基于上面的原理,我们采用 两次hash的办法,第一次hash找到相同前缀和的最后一个位置的节点
// 2. 第二次hash找到第一次出现和相同的节点位置,那么将这两个节点之间的所有检点都删除,即可

笔者觉得这类题目可以扩展成,多数之和为固定值的场景,不过有个小技巧需要注意,在求和的时候,记得减去这个固定值,如此一来便退化成了多数之和为0的情况。

题目1: 链表中删除综合值为0的连续节点

https://leetcode-cn.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/

代码实现:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeZeroSumSublists(head *ListNode) *ListNode {
    m1 := make(map[int]*ListNode)
    pre := new(ListNode)
    pre.Next = head
    sum := 0
    for n:=pre; n!=nil; n=n.Next {
        sum += n.Val
        m1[sum] = n // 保存最后一个位置的相同节点的内容
    }
    
    s := 0 
    for m:=pre; m != nil; m=m.Next {
        s += m.Val
        m.Next = m1[s].Next // 删除相同sum第一次出现和最后一次出现之间的节点内容
    }
    return pre.Next
}

执行结果:

本文分享自微信公众号 - 灰子学技术(huizixueguoxue),作者:灰子学技术

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法篇:链表之删除链表中重复节点

    核心点在于如何找到重复节点,有序链表的话,只要下一个节点与当前节点数值一样就是重复节点,直接将当前节点指向下一个节点的下一个节点即可。

    灰子学技术
  • 算法篇:链表之反转链表

    https://leetcode-cn.com/problems/reverse-linked-list/

    灰子学技术
  • 算法:链表之环形链表

    该类题目的核心点在于如何判断是环形链表,核心思想是:两个人在环上跑步,跑的快的早晚会追上跑的慢的。

    灰子学技术
  • 图解精选 TOP 面试题 005 | 反转链表之迭代求解

    链表反转在面试中非常常见,我也在面试中遇到过这道题。在本篇文章中我们先说说如何用迭代法求解该题。

    江不知
  • 每天一道剑指offer-反转链表

    今天的题目 每天的题目见github(看最新的日期): https://github.com/gzc426 具体的题目可以去牛客网对应专题去找。

    乔戈里
  • 最短路问题与标号算法(label correcting algorithm)研究(6) - 扩展阅读

    这是全文第四章拓展阅读,也是全篇的最后一个章节。在前三章的内容里,我们详细介绍了最短路问题及其数学模型、最短路径求解算法以及单源、多源Label Correct...

    用户1621951
  • 【程序猿硬核科普】Java获取指定时间年月日 | 时间戳转换bug你的项目中招了吗 | yyyy和YYYY的区别

    最近在知乎看到有篇回答说:跨年导致日期格式YYYY和yyyy导致日期显示Bug的帖子,微信公众号、一些论坛好多中招了,快来看看你的项目里面有没有这个bug吧,哈...

    浩Coding
  • SAP最佳业务实践:FI–应收帐款(157)-5 FB75贷项凭证

    4.6 根据发票过帐贷项凭证 如果销售与分销模块在实施范围内,请执行步骤 根据销售与分销模块发票过帐贷项凭证。这样就确保了销售与分销模块和财务/控制会计之间的整...

    SAP最佳业务实践
  • 关于 RTL8723BS 同时开启 STA/AP 模式

    最近接到一个调试 wifi 驱动的任务,使用的是 rtl8723bs 芯片组。要求是让无线设备工作在 station 模式的时候同时开启一个 ap 热点。简单来...

    RainMark
  • Java--为什么需要主动关闭文件?

    在Java编程中,对于一些文件的使用往往需要主动释放,比如InputStream,OutputStream,SocketChannel等等,那么有没有想过为什么...

    屈定

扫码关注云+社区

领取腾讯云代金券