• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode1171.从链表中删去总和值为零的连续节点|RemoveZeroSumConsecutiveNod ...

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(www.zengqiang.org
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences.

After doing so, return the head of the final linked list.  You may return any such answer.

 

(Note that in the examples below, all sequences are serializations of ListNode objects.)

Example 1:

Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.

Example 2:

Input: head = [1,2,3,-3,4]
Output: [1,2,4]

Example 3:

Input: head = [1,2,3,-3,-2]
Output: [1]

 

Constraints:

  • The given linked list will contain between 1 and 1000 nodes.
  • Each node in the linked list has -1000 <= node.val <= 1000.

给你一个链表的头节点 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.

Runtime: 28 ms
Memory Usage: 21.5 MB
 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 class Solution {
13     func removeZeroSumSublists(_ head: ListNode?) -> ListNode? {
14         var head = head
15         if head == nil {return head}
16         var sums:[Int:ListNode] = [Int:ListNode]()
17         var sum:Int = 0
18         var curr:ListNode? = head
19         while(curr != nil)
20         {
21             sum += curr!.val
22             if sum == 0
23             {
24                 head = curr?.next
25             }
26             if sums[sum] != nil
27             {
28                 sums[sum]!.next = curr?.next
29             }
30             else
31             {
32                 sums[sum] = curr
33             }
34             curr = curr?.next
35         }
36         return head        
37     }
38 }

36ms

 

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 class Solution {
13     func removeZeroSumSublists(_ head: ListNode?) -> ListNode? {
14                
15         var arr = [Int]()
16         var sumArr = [Int]()
17         var dic = [0: -1]
18         var head = head
19         var invaildRange = [(Int, Int)]()
20         var i = 0
21         while head != nil {
22             if head!.val == 0 {
23                 head = head!.next
24                 continue
25             }
26             arr.append(head!.val)
27             if sumArr.count == 0 {
28                 sumArr.append(head!.val)
29             } else {
30                 sumArr.append(sumArr[sumArr.count-1]+head!.val)
31             }
32             if dic[sumArr[sumArr.count-1]] != nil {
33                 let lasti = dic[sumArr[sumArr.count-1]]!
34                 invaildRange.append((lasti+1, i))
35                 for j in lasti..<i {
36                     dic[sumArr[j+1]] = nil
37                 } 
38                 dic[sumArr[sumArr.count-1]] = lasti
39             } else {
40                 dic[sumArr[sumArr.count-1]] = i
41             }
42             head = head!.next
43             i += 1
44         }
45         if sumArr.count == 0 || sumArr[sumArr.count-1] == 0 {
46             return nil
47         }
48 
49         // print(invaildRange)
50         
51         var hd: ListNode? = nil
52         var res: ListNode? = nil
53 
54         invaildRange.append((Int.max, Int.max))
55         invaildRange.sort {
56             if $0.0 < $1.0 || ($0.0 == $1.0 && $0.1 > $1.1 ) {
57                 return true
58             }
59             return false
60         }
61         var last = invaildRange.removeFirst()
62         for i in arr.indices {
63             while i > last.1 && invaildRange.count > 0 {
64                 last = invaildRange.removeFirst()
65             }
66             // print(i, last)
67             if i < last.0 {
68                 if hd == nil {
69                     hd = ListNode(arr[i])
70                     res = hd
71                 } else {
72                     hd!.next = ListNode(arr[i])
73                     hd = hd!.next
74                 }
75             }
76         }
77         return res 
78     }
79 }

44ms

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public var val: Int
 5  *     public var next: ListNode?
 6  *     public init(_ val: Int) {
 7  *         self.val = val
 8  *         self.next = nil
 9  *     }
10  * }
11  */
12 class Solution {
13     func removeZeroSumSublists(_ head: ListNode?) -> ListNode? { 
14         var arr = [Int](), sumArr = [Int]()
15         var dic = [0: -1]
16         var head = head
17         var invaildRange = [(Int, Int)]()
18         var i = 0
19         while head != nil {
20             //ignor zero element
21             if head!.val == 0 { head = head!.next; continue }
22             
23             arr.append(head!.val)
24             if sumArr.count == 0 { sumArr.append(head!.val) } 
25             else { sumArr.append(sumArr.last! + head!.val) }
26             
27             let lasti = dic[sumArr.last!] ?? i
28             if lasti != i {
29                 invaildRange.append((lasti+1, i))
30                 for j in lasti..<i {
31                     dic[sumArr[j+1]] = nil
32                 } 
33             } 
34             dic[sumArr.last!] = lasti
35             head = head!.next
36             i += 1
37         }
38         if sumArr.count == 0 || sumArr[sumArr.count-1] == 0 { return nil }
39         var hd: ListNode? = nil
40         var res: ListNode? = nil
41 
42         invaildRange.append((Int.max, Int.max))
43         invaildRange.sort { $0.0 < $1.0  }
44         var last = invaildRange.removeFirst()
45         for i in arr.indices {
46             while i > last.1 { last = invaildRange.removeFirst() }
47             if i < last.0 {
48                 if hd == nil {
49                     hd = ListNode(arr[i])
50                     res = hd
51                 } else {
52                     hd!.next = ListNode(arr[i])
53                     hd = hd!.next
54                 }
55             }
56         }
57         return res 
58     }
59 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
swift 语法 →运算符发布时间:2022-07-13
下一篇:
Swift-6-函数发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap