Re: [閒聊] 每日leetcode
又到了騙p幣的時間
思路
prefix sum記錄到目前的總和
hash map紀錄每個prefix sum對應到node
當同個值出現兩次，就把兩個node中間的hash map刪掉
並且把第一個node的next接到第二個node的next
記得一開始要在hash map裡面放一個0
golang code:
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeZeroSumSublists(head *ListNode) *ListNode {
ans := &ListNode{0, head}
prefixSumToNode := make(map[int]*ListNode)
prefixSum := 0
temp := ans
for temp != nil {
prefixSum += temp.Val
if prev, found := prefixSumToNode[prefixSum]; found {
toRemove := prev.Next
p := prefixSum
for toRemove!=temp {
p+=toRemove.Val
delete(prefixSumToNode, p)
toRemove = toRemove.Next
}
prev.Next = temp.Next
} else {
prefixSumToNode[prefixSum] = temp
}
temp = temp.Next
}
return ans.Next
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.69.200 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1710257320.A.EFC.html
推
03/12 23:29,
1年前
, 1F
03/12 23:29, 1F
→
03/12 23:30,
1年前
, 2F
03/12 23:30, 2F
→
03/12 23:30,
1年前
, 3F
03/12 23:30, 3F
推
03/12 23:43,
1年前
, 4F
03/12 23:43, 4F
討論串 (同標題文章)
完整討論串 (本文為第 41 之 1548 篇)：