推 sustainer123: 大師 03/12 23:29
→ RinNoKareshi: 大師 03/12 23:30
→ YukihanaLami: 大師 03/12 23:30
推 NCKUEECS: 大師 我直接擺爛N^2硬嚕過去 03/12 23:43
又到了騙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