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

[Swift]LeetCode1167.连接棒材的最低费用|MinimumCosttoConnectSticks

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

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

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

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

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

You have some sticks with positive integer lengths.

You can connect any two sticks of lengths X and Y into one stick by paying a cost of X + Y.  You perform this action until there is one stick remaining.

Return the minimum cost of connecting all the given sticks into one stick in this way.

 

Example 1:

Input: sticks = [2,4,3]
Output: 14

Example 2:

Input: sticks = [1,8,3,5]
Output: 30

 

Constraints:

  • 1 <= sticks.length <= 10^4
  • 1 <= sticks[i] <= 10^4

为了装修新房,你需要加工一些长度为正整数的棒材 sticks

如果要将长度分别为 X 和 Y 的两根棒材连接在一起,你需要支付 X + Y 的费用。 由于施工需要,你必须将所有棒材连接成一根。

返回你把所有棒材 sticks 连成一根所需要的最低费用。注意你可以任意选择棒材连接的顺序。

 

示例 1:

输入:sticks = [2,4,3]
输出:14
解释:先将 2 和 3 连接成 5,花费 5;再将 5 和 4 连接成 9;总花费为 14。

示例 2:

输入:sticks = [1,8,3,5]
输出:30

 

提示:

  • 1 <= sticks.length <= 10^4
  • 1 <= sticks[i] <= 10^4

1884 ms

  1 class Solution {
  2     func connectSticks(_ sticks: [Int]) -> Int {
  3         var pq:PriorityQueue<Int> = PriorityQueue<Int> { $0 < $1 }
  4         for v in sticks
  5         {
  6             pq.push(v)
  7         }
  8         var ans:Int = 0
  9         while(pq.count > 1)
 10         {
 11             let x:Int = pq.pop()!
 12             let y:Int = pq.pop()!
 13             let sum:Int = x + y
 14             ans += sum
 15             pq.push(sum)            
 16         }
 17         return ans
 18     }
 19 }
 20 
 21 public struct PriorityQueue<T> {
 22   fileprivate var heap: Heap<T>
 23   public init(sort: @escaping (T, T) -> Bool) {
 24     heap = Heap(sort: sort)
 25   }
 26 
 27   public var isEmpty: Bool {
 28     return heap.isEmpty
 29   }
 30 
 31   public var count: Int {
 32     return heap.count
 33   }
 34 
 35   public func peek() -> T? {
 36     return heap.peek()
 37   }
 38 
 39   public mutating func push(_ element: T) {
 40     heap.insert(element)
 41   }
 42 
 43   public mutating func pop() -> T? {
 44     return heap.remove()
 45   }
 46 
 47   public mutating func changePriority(index i: Int, value: T) {
 48     return heap.replace(index: i, value: value)
 49   }
 50 }
 51 
 52 extension PriorityQueue where T: Equatable {
 53   public func index(of element: T) -> Int? {
 54     return heap.index(of: element)
 55   }
 56 }
 57 
 58 public struct Heap<T> {
 59   var nodes = [T]()
 60 
 61   private var orderCriteria: (T, T) -> Bool
 62 
 63   public init(sort: @escaping (T, T) -> Bool) {
 64     self.orderCriteria = sort
 65   }
 66   
 67   public init(array: [T], sort: @escaping (T, T) -> Bool) {
 68     self.orderCriteria = sort
 69     configureHeap(from: array)
 70   }
 71 
 72   private mutating func configureHeap(from array: [T]) {
 73     nodes = array
 74     for i in stride(from: (nodes.count/2-1), through: 0, by: -1) {
 75       shiftDown(i)
 76     }
 77   }
 78   
 79   public var isEmpty: Bool {
 80     return nodes.isEmpty
 81   }
 82   
 83   public var count: Int {
 84     return nodes.count
 85   }
 86 
 87   @inline(__always) internal func parentIndex(ofIndex i: Int) -> Int {
 88     return (i - 1) / 2
 89   }
 90 
 91   @inline(__always) internal func leftChildIndex(ofIndex i: Int) -> Int {
 92     return 2*i + 1
 93   }
 94 
 95   @inline(__always) internal func rightChildIndex(ofIndex i: Int) -> Int {
 96     return 2*i + 2
 97   }
 98   
 99   public func peek() -> T? {
100     return nodes.first
101   }
102   
103   public mutating func insert(_ value: T) {
104     nodes.append(value)
105     shiftUp(nodes.count - 1)
106   }
107   
108   public mutating func insert<S: Sequence>(_ sequence: S) where S.Iterator.Element == T {
109     for value in sequence {
110       insert(value)
111     }
112   }
113   
114   public mutating func replace(index i: Int, value: T) {
115     guard i < nodes.count else { return }
116     
117     remove(at: i)
118     insert(value)
119   }
120 
121   @discardableResult public mutating func remove() -> T? {
122     guard !nodes.isEmpty else { return nil }
123     
124     if nodes.count == 1 {
125       return nodes.removeLast()
126     } else {
127       let value = nodes[0]
128       nodes[0] = nodes.removeLast()
129       shiftDown(0)
130       return value
131     }
132   }
133   
134   @discardableResult public mutating func remove(at index: Int) -> T? {
135     guard index < nodes.count else { return nil }
136     
137     let size = nodes.count - 1
138     if index != size {
139       nodes.swapAt(index, size)
140       shiftDown(from: index, until: size)
141       shiftUp(index)
142     }
143     return nodes.removeLast()
144   }
145 
146   internal mutating func shiftUp(_ index: Int) {
147     var childIndex = index
148     let child = nodes[childIndex]
149     var parentIndex = self.parentIndex(ofIndex: childIndex)
150     
151     while childIndex > 0 && orderCriteria(child, nodes[parentIndex]) {
152       nodes[childIndex] = nodes[parentIndex]
153       childIndex = parentIndex
154       parentIndex = self.parentIndex(ofIndex: childIndex)
155     }
156     
157     nodes[childIndex] = child
158   }
159 
160   internal mutating func shiftDown(from index: Int, until endIndex: Int) {
161     let leftChildIndex = self.leftChildIndex(ofIndex: index)
162     let rightChildIndex = leftChildIndex + 1
163 
164     var first = index
165     if leftChildIndex < endIndex && orderCriteria(nodes[leftChildIndex], nodes[first]) {
166       first = leftChildIndex
167     }
168     if rightChildIndex < endIndex && orderCriteria(nodes[rightChildIndex], nodes[first]) {
169       first = rightChildIndex
170     }
171     if first == index { return }
172     
173     nodes.swapAt(index, first)
174     shiftDown(from: first, until: endIndex)
175   }
176   
177   internal mutating func shiftDown(_ index: Int) {
178     shiftDown(from: index, until: nodes.count)
179   }
180   
181 }
182 
183 extension Heap where T: Equatable {
184     
185     public func index(of node: T) -> Int? {
186         return nodes.firstIndex(where: { $0 == node })
187     }
188     
189     @discardableResult public mutating func remove(node: T) -> T? {
190         if let index = index(of: node) {
191             return remove(at: index)
192         }
193         return nil
194     }
195 }

 


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
上一篇:
iOS 上的相机捕捉 swift发布时间:2022-07-13
下一篇:
Swift中添加标记(MARK)和警告(TODOFIXME)发布时间: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