在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skylineformed by these buildings collectively (Figure B). The geometric information of each building is represented by a triplet of integers For instance, the dimensions of all buildings in Figure A are recorded as: The output is a list of "key points" (red dots in Figure B) in the format of For instance, the skyline in Figure B should be represented as: Notes:
城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。现在,假设您获得了城市风光照片(图A)上显示的所有建筑物的位置和高度,请编写一个程序以输出由这些建筑物形成的天际线(图B)。 每个建筑物的几何信息用三元组 例如,图A中所有建筑物的尺寸记录为: 输出是以 例如,图B中的天际线应该表示为: 说明:
264ms 1 class Solution { 2 func getSkyline(_ buildings: [[Int]]) -> [[Int]] { 3 var queue = [[Int]]() 4 for building in buildings { 5 let begin = [building[0],building[2]] 6 let end = [building[1], -building[2]] 7 queue.append(begin) 8 queue.append(end) 9 } 10 11 queue.sort { (nums1, nums2) -> Bool in 12 if nums1[0] == nums2[0] { 13 return nums1[1] > nums2[1] 14 } 15 16 return nums1[0] < nums2[0] 17 } 18 19 20 var res = [[Int]]() 21 var heights = Heap(array: [Int](), sort: >) 22 var removes = Heap(array: [Int](), sort: >) 23 var pHeight = 0 24 for line in queue { 25 let h = line[1] 26 27 if h > 0 { 28 if h > pHeight { 29 res.append([line[0],h]) 30 } 31 heights.insert(h) 32 pHeight = heights.peek()! 33 }else { 34 removes.insert(-h) 35 while !heights.isEmpty && !removes.isEmpty && heights.peek()! == removes.peek()! { 36 heights.remove() 37 removes.remove() 38 } 39 pHeight = heights.peek() ?? 0 40 if -h > pHeight { 41 res.append([line[0],pHeight]) 42 } 43 } 44 } 45 return res 46 } 47 48 public struct Heap<T> { 49 var nodes = [T]() 50 51 private var orderCriteria:(T,T) -> Bool 52 53 public init(sort:@escaping (T,T) -> Bool) { 54 self.orderCriteria = sort 55 } 56 57 public init(array:[T],sort:@escaping(T, T) -> Bool) { 58 self.orderCriteria = sort 59 configureHeap(from:array) 60 } 61 62 private mutating func configureHeap(from array:[T]) { 63 nodes = array 64 for i in stride(from: (nodes.count - 1) / 2, through: 0, by: -1) { 65 shiftDown(i) 66 } 67 } 68 69 public var isEmpty:Bool { 70 return nodes.isEmpty 71 } 72 73 public var count : Int { 74 return nodes.count 75 } 76 77 @inline(__always) internal func parentIndex(ofIndex i : Int) -> Int { 78 return (i - 1) / 2 79 } 80 81 @inline(__always) internal func leftChildIndex(ofIndex i : Int) -> Int { 82 return 2 * i + 1 83 } 84 85 @inline(__always) internal func rightChildIndex(ofIndex i : Int) -> Int { 86 return 2 * i + 2 87 } 88 89 public func peek() -> T? { 90 return nodes.first 91 } 92 93 public mutating func insert(_ value: T) { 94 nodes.append(value) 95 shiftUp(nodes.count - 1) 96 } 97 98 public mutating func insert<S:Sequence>(_ sequence: S) where S.Iterator.Element == T { 99 for value in sequence { 100 insert(value) 101 } 102 } 103 104 @discardableResult public mutating func remove() -> T? { 105 guard !isEmpty else {return nil} 106 if nodes.count == 1 { 107 return nodes.removeFirst() 108 }else { 109 let value = nodes[0] 110 nodes[0] = nodes.removeLast() 111 shiftDown(0) 112 return value 113 } 114 } 115 116 117 @discardableResult public mutating func remove(at index: Int) -> T? { 118 guard index < count else {return nil} 119 120 let size = nodes.count - 1 121 if index != count { 122 nodes.swapAt(index, size) 123 shiftDown(form: index, until: size) 124 shiftUp(index) 125 } 126 127 return nodes.removeLast() 128 129 } 130 131 internal mutating func shiftUp(_ index : Int) { 132 var childIndex = index 133 let child = nodes[childIndex] 134 var parentIndex = self.parentIndex(ofIndex: childIndex) 135 136 while childIndex > 0 && orderCriteria(child, nodes[parentIndex]) { 137 nodes[childIndex] = nodes[parentIndex] 138 childIndex = parentIndex 139 parentIndex = self.parentIndex(ofIndex: childIndex) 140 } 141 nodes[childIndex] = child 142 } 143 144 internal mutating func shiftDown(form index: Int, until endIndex: Int) { 145 let leftChildIndex = self.leftChildIndex(ofIndex: index) 146 let rightChildIndex = leftChildIndex + 1 147 var first = index 148 if leftChildIndex < endIndex && orderCriteria(nodes[leftChildIndex], nodes[first]) { 149 first = leftChildIndex 150 } 151 152 if rightChildIndex < endIndex && orderCriteria(nodes[rightChildIndex], nodes[first]) { 153 first = rightChildIndex 154 } 155 if first == index {return} 156 nodes.swapAt(index, first) 157 shiftDown(form: first, until: endIndex) 158 } 159 160 internal mutating func shiftDown(_ index:Int) { 161 162 shiftDown(form: index, until: nodes.count) 163 } 164 165 } 166 } 676ms 1 class Solution { 2 func getSkyline(_ buildings: [[Int]]) -> [[Int]] { 3 var points: [Int] = [] 4 for building in buildings { 5 points.append(building[0]) 6 points.append(building[1]) 7 } 8 points.sort() 9 10 var segs = [Int](repeating: 0, count: points.count) 11 12 var pos = 0 13 for building in buildings { 14 // find start point 15 while points[pos] < building[0] { pos += 1 } 16 // go to end 17 var i = pos 18 19 while points[i] < building[1] { 20 if segs[i] < building[2] { 21 segs[i] = building[2] 22 } 23 i += 1 24 } 25 } 26 27 var result: [[Int]] = [] 28 var currHeight = 0 29 for (index, h) in segs.enumerated() { 30 if currHeight != h { 31 result.append([points[index], h]) 32 currHeight = h 33 } 34 } 35 36 return result 37 } 38 } 1660ms 1 class Solution { 2 public struct PriorityQueue<T: Comparable> { 3 4 fileprivate var heap = [T]() 5 private let ordered: (T, T) -> Bool 6 7 public init(ascending: Bool = false, startingValues: [T] = []) { 8 self.init(order: ascending ? { $0 > $1 } : { $0 < $1 }, startingValues: startingValues) 9 } 10 11 /// Creates a new PriorityQueue with the given ordering. 12 /// 13 /// - parameter order: A function that specifies whether its first argument should 14 /// come after the second argument in the PriorityQueue. 15 /// - parameter startingValues: An array of elements to initialize the PriorityQueue with. 16 public init(order: @escaping (T, T) -> Bool, startingValues: [T] = []) { 17 ordered = order 18 19 // Based on "Heap construction" from Sedgewick p 323 20 heap = startingValues 21 var i = heap.count/2 - 1 22 while i >= 0 { 23 sink(i) 24 i -= 1 25 } 26 } 27 28 /// How many elements the Priority Queue stores 29 public var count: Int { return heap.count } 30 31 /// true if and only if the Priority Queue is empty 32 public var isEmpty: Bool { return heap.isEmpty } 33 34 /// Add a new element onto the Priority Queue. O(lg n) 35 /// 36 /// - parameter element: The element to be inserted into the Priority Queue. 37 public mutating func push(_ element: T) { 38 heap.append(element) 39 swim(heap.count - 1) 40 } 41 42 /// Remove and return the element with the highest priority (or lowest if ascending). O(lg n) 43 /// 44 /// - returns: The element with the highest priority in the Priority Queue, or nil if the PriorityQueue is empty. 45 public mutating func pop() -> T? { 46 47 if heap.isEmpty { return nil } 48 if heap.count == 1 { return heap.removeFirst() } // added for Swift 2 compatibility 49 // so as not to call swap() with two instances of the same location 50 heap.swapAt(0, heap.count - 1) 51 let temp = heap.removeLast() 52 sink(0) 53 54 return temp 55 } 56 57 58 /// Removes the first occurence of a particular item. Finds it by value comparison using ==. O(n) 59 /// Silently exits if no occurrence found. 60 /// 61 /// - parameter item: The item to remove the first occurrence of. 62 public mutating func remove(_ item: T) { 63 if let index = heap.index(of: item) { 64 heap.swapAt(index, heap.count - 1) 65 heap.removeLast() 66 if index < heap.count { // if we removed the last item, nothing to swim 67 swim(index) 68 sink(index) 69 } 70 } 71 } 72 73 /// Removes all occurences of a particular item. Finds it by value comparison using ==. O(n) 74 /// Silently exits if no occurrence found. 75 /// 76 /// - parameter item: The item to remove. 77 public mutating func removeAll(_ item: T) { 78 var lastCount = heap.count 79 remove(item) 80 while (heap.count < lastCount) { 81 lastCount = heap.count 82 remove(item) 83 } 84 } 85 86 /// Get a look at the current highest priority item, without removing it. O(1) 87 /// 88 /// - returns: The element with the highest priority in the PriorityQueue, or nil if the PriorityQueue is empty. 89 public func peek() -> T? { 90 return heap.first 91 } 92 93 /// Eliminate all of the elements from the Priority Queue. 94 public mutating func clear() { 95 heap.removeAll(keepingCapacity: false) 96 } 97 98 // Based on example from Sedgewick p 316 99 private mutating func sink(_ index: Int) { 100 var index = index 101 while 2 * index + 1 < heap.count { 102 103 var j = 2 * index + 1 104 105 if j < (heap.count - 1) && ordered(heap[j], heap[j + 1]) { j += 1 } 106 if !ordered(heap[index], heap[j]) { break } 107 108 heap.swapAt(index, j) 109 index = j 110 } 111 } 112 113 // Based on example from Sedgewick p 316 114 private mutating func swim(_ index: Int) { 115 var index = index 116 while index > 0 && ordered(heap[(index - 1) / 2], heap[index]) { 117 heap.swapAt((index - 1) / 2, index) 118 index = (index - 1) / 2 119 } 120 } 121 } 122 123 func getSkyline(_ buildings: [[Int]]) -> [[Int]] { 124 var heights: [(pos: Int, h: Int)] = [] 125 for building in buildings { 126 heights.append((building[0], -building[2])) 127 heights.append((building[1], building[2])) 128 } 129 heights.sort { (a, b) in 130 if (a.pos == b.pos) { 131 return a.h < b.h 132 } else { 133 return a.pos < b.pos 134 } 135 } 136 137 var heap = PriorityQueue<Int>() 138 var result: [[Int]] = [] 139 var prev = 0 140 141 heap.push(0) 142 for h in heights { 143 if (h.h < 0) { 144 heap.push(-h.h) 145 } else { 146 heap.remove(h.h) 147 } 148 if let curr = heap.peek(), prev != curr { 149 result.append([h.pos, curr]) 150 prev = curr 151 } 152 } 153 154 return result 155 } 156 } 1712ms 1 class PriorityQueue<T> { 2 private var heap: [T] = [T]() 3 private let ordered: (T, T) -> Bool 4 5 init(order: @escaping (T, T) -> Bool) { 6 self.ordered = order 7 } 8 9 var isEmpty: Bool { 10 return heap.isEmpty 11 } 12 var count: Int { 13 return heap.count 14 } 15 16 func push(_ element: T) { 17 heap.append(element) 18 swim(heap.count - 1) 19 } 20 21 func pop() -> T? { 22 if self.isEmpty { 23 return nil 24 } 25 26 if self.heap.count == 1 { 27 return heap.remove(at: 0 全部评论
专题导读
上一篇:[Swift]LeetCode671.二叉树中第二小的节点|SecondMinimumNodeInaBinaryTree发布时间:2022-07-13下一篇:《从零开始学Swift》学习笔记(Day 70)——Swift与Objective-C混合编程之Swift与Obje ...发布时间:2022-07-13热门推荐
热门话题
阅读排行榜
|
请发表评论