[Swift]LeetCode358. 按距离为k隔离重排字符串 $ Rearrange String k Distance Apart
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10742310.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
Given a non-empty string str and an integer k, rearrange the string such that the same characters are at least distance k from each other.
All input strings are given in lowercase letters. If it is not possible to rearrange the string, return an empty string "".
Example 1:
str = "aabbcc", k = 3 Result: "abcabc" The same letters are at least distance 3 from each other.
Example 2:
str = "aaabc", k = 3 Answer: "" It is not possible to rearrange the string.
Example 3:
str = "aaadbbcc", k = 2 Answer: "abacabcd" Another possible answer is: "abcabcda" The same letters are at least distance 2 from each other.
Credits:
Special thanks to @elmirap for adding this problem and creating all test cases.
给定一个非空字符串str和一个整数k，重新排列该字符串，使相同的字符至少彼此相距k。
所有输入字符串都用小写字母表示。如果无法重新排列字符串，请返回空字符串“”。
例1：
str = "aabbcc", k = 3 Result: "abcabc"
相同的字母彼此之间至少有3个距离。
例2：
str = "aaabc", k = 3 Answer: ""
无法重新排列字符串。
例3：
str = "aaadbbcc", k = 2 Answer: "abacabcd"
另一个可能的答案是：“abcabcda”
相同的字母彼此之间至少有2个距离。
信用：
特别感谢@elmirap添加此问题并创建所有测试用例。
Solution:
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 }点击：Playground测试
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