[Swift]LeetCode1046.最后一块石头的重量|LastStoneWeight

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

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

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

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

We have a collection of rocks, each rock has a positive integer weight.

Each turn, we choose the two heaviest rocks and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

If x == y, both stones are totally destroyed;
If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.)

Note:

1 <= stones.length <= 30
1 <= stones[i] <= 1000

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块最重的石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

提示：

1 <= stones.length <= 30
1 <= stones[i] <= 1000

8ms

  1 class Solution {
  2     let heap = Heap<Int>(type: .max)
  3     
  4     func lastStoneWeight(_ stones: [Int]) -> Int {
  5         for stone in stones {
  6             heap.insert(stone)
  7         }
  8         
  9         return helper()
 10     }
 11     
 12     private func helper() -> Int {
 13         guard let a = heap.pop() else { return 0 }
 14         guard let b = heap.pop() else { return a }
 15         
 16         if a != b {
 17             heap.insert(a - b)
 18         }
 19         
 20         return helper()
 21     }
 22 }
 23 
 24 enum HeapType {
 25     case min
 26     case max
 27     
 28     func compare<T: Comparable>(_ a: T, _ b: T) -> Bool {
 29         switch self {
 30         case .min:
 31             return a < b
 32         case .max:
 33             return a > b
 34         }
 35     }
 36 }
 37 
 38 class Heap<T: Comparable> {
 39     // MARK: - Properties & Init
 40     var array: [T]
 41     var type: HeapType
 42     var nodeIndexUpdateHandler: ((Int) -> Void)? = nil
 43     
 44     init(type: HeapType, array: [T] = []) {
 45         self.type = type
 46         self.array = array
 47         
 48         guard !array.isEmpty else { return }
 49         
 50         var i = (array.count - 1) / 2
 51         while i >= 0 {
 52             heapify(i)
 53             i -= 1
 54         }
 55     }
 56     
 57     // MARK: - APIs
 58     
 59     var count: Int {
 60         return array.count
 61     }
 62     
 63     // O[1]
 64     func pop() -> T? {
 65         guard let first = array.first else {
 66             return nil
 67         }
 68         
 69         if let last = array.last {
 70             array[0] = last
 71             heapify(0)
 72         }
 73         
 74         array.removeLast()
 75         
 76         return first
 77     }
 78     
 79     // O[1]
 80     func peek() -> T? {
 81         return array.first
 82     }
 83     
 84     // O[log(n)]
 85     func insert(_ val: T) {
 86         array.append(val)
 87         nodeIndexUpdateHandler?(array.count - 1)
 88         siftUp(array.count - 1)
 89     }
 90     
 91     // MARK: - Utilty Methods
 92     func heapify(_ i: Int) {
 93         var top = i
 94         
 95         if let left = left(i), type.compare(array[left], array[top]) {
 96             top = left
 97         }
 98         
 99         if let right = right(i), type.compare(array[right], array[top]) {
100             top = right
101         }
102         
103         if top != i {
104             swapAt(i, top)
105             heapify(top)
106         } else {
107             nodeIndexUpdateHandler?(i)
108         }
109     }
110     
111     func siftUp(_ i: Int) {
112         var parent = parentIndex(i)
113         var this = i
114         
115         while let p = parent, type.compare(array[this], array[p]) {
116             swapAt(p, this)
117             parent = parentIndex(p)
118             this = p
119         }
120     }
121     
122     func swapAt(_ i: Int, _ j: Int) {
123         array.swapAt(i, j)
124         nodeIndexUpdateHandler?(i)
125         nodeIndexUpdateHandler?(j)
126     }
127     
128     func parentIndex(_ i: Int) -> Int? {
129         guard i > 0 else { return nil }
130         return (i - 1) / 2
131     }
132     
133     func left(_ i: Int) -> Int? {
134         let left = i * 2 + 1
135         return left < array.count ? left : nil
136     }
137     
138     func right(_ i: Int) -> Int? {
139         let right = i * 2 + 2
140         return right < array.count ? right : nil
141     }
142 }

Runtime: 12 ms

Memory Usage: 21.1 MB

 1 class Solution {
 2     func lastStoneWeight(_ stones: [Int]) -> Int {
 3         var stones = stones
 4         while (stones.count > 1)
 5         {
 6             stones = stones.sorted()
 7             stones.append(abs(stones.popLast()! - stones.popLast()!))
 8         }
 9         return stones[0]        
10     }
11 }