[Swift]LeetCode358. 按距离为k隔离重排字符串 $ Rearrange String k Distance Apart

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

 1 //结果会有多种可能
 2 print(Solution().rearrangeString("aabbcc", 3))
 3 //Print cbacab
 4 
 5 print(Solution().rearrangeString("aaabc", 3))
 6 //Print ""
 7 
 8 //结果会有多种可能
 9 print(Solution().rearrangeString("aaadbbcc", 2))
10 //Print abcabacd