[Swift]LeetCode767.重构字符串|ReorganizeString

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

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

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

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

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

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

Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.

If possible, output any possible result. If not possible, return the empty string.

Example 1:

Input: S = "aab"
Output: "aba"

Example 2:

Input: S = "aaab"
Output: ""

Note:

S will consist of lowercase letters and have length in range [1, 500].

给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。

若可行，输出任意可行的结果。若不可行，返回空字符串。

示例 1:

输入: S = "aab"
输出: "aba"

示例 2:

输入: S = "aaab"
输出: ""

注意:

S 只包含小写字母并且长度在[1, 500]区间内。

Runtime: 12 ms

Memory Usage: 20.2 MB

 1 class Solution {
 2     func reorganizeString(_ S: String) -> String {
 3         var n:Int = S.count
 4         var idx:Int = 1
 5         var cnt:[Int] = [Int](repeating:0,count:26)
 6         var arrChar:[Character] = Array(S)
 7         for char in S.characters
 8         {
 9             cnt[char.ascii - 97] += 100
10         }
11         for i in 0..<26
12         {
13             cnt[i] += i
14         }
15         cnt.sort()
16         for num in cnt
17         {
18             var t:Int = num / 100
19             var ch:Character = (97 + (num % 100)).ASCII
20             if t > (n + 1) / 2 {return String()}
21             for i in 0..<t
22             {
23                 if idx >= n {idx = 0}
24                 arrChar[idx] = ch
25                 idx += 2
26             }            
27         }
28         return String(arrChar)
29     }
30 }
31 
32 //Character扩展 
33 extension Character  
34 {  
35   //Character转ASCII整数值(定义小写为整数值)
36    var ascii: Int {
37        get {
38            return Int(self.unicodeScalars.first?.value ?? 0)
39        }       
40     }    
41 }
42 
43 //Int扩展
44 extension Int
45 {
46     //Int转Character,ASCII值(定义大写为字符值)
47     var ASCII:Character 
48     {
49         get {return Character(UnicodeScalar(self)!)}
50     }
51 }

12ms

 1 class Solution {
 2     func reorganizeString(_ s: String) -> String {
 3       let n = s.count
 4       var counts = [Int](repeating: 0, count: 26)
 5       for character in s {
 6         let index: Int = Int(character.unicodeScalars.first!.value - "a".unicodeScalars.first!.value)
 7         counts[index] += 100
 8       }
 9       for i in 0..<counts.count {
10         counts[i] += i
11       }
12       counts = counts.sorted(by: >)
13 
14       var output = [Character](repeating: " ", count:n)
15       var j = 0
16       for code in counts {
17         let count = code / 100
18         let charValue = Int("a".unicodeScalars.first!.value) + (code % 100)
19         let unicode = UnicodeScalar(charValue)!
20         let char = Character(unicode)
21         guard count <= (n + 1) / 2 else {
22           return ""
23         }
24 
25         for i in 0..<count {
26           if (j >= n) {
27             j = 1
28           }
29           output[j] = char
30           j += 2
31         }
32       }
33 
34       return String(output)
35     }
36 }

16ms

 1 class Solution {
 2     func reorganizeString(_ S: String) -> String {
 3         var s = Array(S.utf8)
 4         var counts = [Int](repeating: 0, count: 26)
 5         for u in s {
 6             counts[Int(u) - 97] += 1
 7         }
 8         var res = [Character]()
 9         var lastIndex = -1
10         while res.count != s.count {
11             guard let index = maxIndex(counts, lastIndex) else { 
12                 return "" 
13             }
14             counts[index] -= 1
15             lastIndex = index
16             res.append(Character(UnicodeScalar(index + 97)!))
17         }
18         return String(res)
19     }
20     
21     private func maxIndex(_ counts: [Int], _ notIndex: Int) -> Int? {
22         var maxC = 0
23         var retVal = -1
24         for i in 0..<26 {
25             if i != notIndex && counts[i] > maxC {
26                 retVal = i
27                 maxC = counts[i]
28             }   
29         }
30         return retVal == -1 ? nil : retVal
31     }
32 }

24ms

  1 class Solution {
  2     func reorganizeString(_ string: String) -> String {
  3         
  4         // we only care about the character counts, and not how the string is constructed
  5         let characterToCount = string.reduce(into: [:], { $0[$1, default: 0] += 1 })
  6         
  7         var maxHeap = Heap<(character: Character, count: Int)>(
  8             array: characterToCount.map { $0 },
  9             sort: { $0.count > $1.count })
 10         
 11         var newString = ""
 12         
 13         while let maxPair = maxHeap.remove() {
 14             
 15             // we can use the maxPair `character`
 16             if newString.last != maxPair.character {
 17                 
 18                 newString.append(maxPair.character)
 19                 
 20                 if maxPair.count > 1 {
 21                     maxHeap.insert((maxPair.character, maxPair.count-1))
 22                 }
 23             } else if let nextMaxPair = maxHeap.remove() {
 24                 
 25                 newString.append(nextMaxPair.character)
 26                 
 27                 if nextMaxPair.count > 1 {
 28                     maxHeap.insert((nextMaxPair.character, nextMaxPair.count-1))
 29                 }
 30                 maxHeap.insert(maxPair)
 31             } else {
 32                 return "" // we can't find any character to place in next
 33             }
 34         }
 35         
 36         return newString
 37     }
 38 }
 39 
 40 public struct Heap<T> {
 41     var elements = [T]()
 42     fileprivate var isOrderedBefore: (T, T) -> Bool
 43     public init(sort: @escaping (T, T) -> Bool) {
 44         self.isOrderedBefore = sort
 45     }
 46     public init(array: [T], sort: @escaping (T, T) -> Bool) {
 47         self.isOrderedBefore = sort
 48         buildHeap(fromArray: array)
 49     }
 50     fileprivate mutating func buildHeap(fromArray array: [T]) {
 51         elements = array
 52         for i in stride(from: (elements.count/2 - 1), through: 0, by: -1) {
 53             shiftDown(i, heapSize: elements.count)
 54         }
 55     }
 56     public var isEmpty: Bool {
 57         return elements.isEmpty
 58     }
 59 
 60     public var count: Int {
 61         return elements.count
 62     }
 63     @inline(__always) func parentIndex(ofIndex i: Int) -> Int {
 64         return (i - 1) / 2
 65     }
 66     @inline(__always) func leftChildIndex(ofIndex i: Int) -> Int {
 67         return 2*i + 1
 68     }
 69     @inline(__always) func rightChildIndex(ofIndex i: Int) -> Int {
 70         return 2*i + 2
 71     }
 72     public func peek() -> T? {
 73         return elements.first
 74     }
 75     public mutating func insert(_ value: T) {
 76         elements.append(value)
 77         shiftUp(elements.count - 1)
 78     }
 79     public mutating func insert<S: Sequence>(_ sequence: S) where S.Iterator.Element == T {
 80         for value in sequence {
 81             insert(value)
 82         }
 83     }
 84     public mutating func replace(index i: Int, value: T) {
 85         guard i < elements.count else { return }
 86 
 87         assert(isOrderedBefore(value, elements[i]))
 88         elements[i] = value
 89         shiftUp(i)
 90     }
 91     @discardableResult public mutating func remove() -> T? {
 92         if elements.isEmpty {
 93             return nil
 94         } else if elements.count == 1 {
 95             return elements.removeLast()
 96         } else {
 97             // Use the last node to replace the first one, then fix the heap by
 98             // shifting this new first node into its proper position.
 99             let value = elements[0]
100             elements[0] = elements.removeLast()
101             shiftDown()
102             return value
103         }
104     }
105     public mutating func removeAt(_ index: Int) -> T? {
106         guard index < elements.count else { return nil }
107 
108         let size = elements.count - 1
109         if index != size {
110             elements.swapAt(index, size)
111             // swap(&elements[index], &elements[size])
112             shiftDown(index, heapSize: size)
113             shiftUp(index)
114         }
115         return elements.removeLast()
116     }
117     mutating func shiftUp(_ index: Int) {
118         var childIndex = index
119         let child = elements[childIndex]
120         var parentIndex = self.parentIndex(ofIndex: childIndex)
121 
122         while childIndex > 0 && isOrderedBefore(child, elements[parentIndex]) {
123             elements[childIndex] = elements[parentIndex]
124             childIndex = parentIndex
125             parentIndex = self.parentIndex(ofIndex: childIndex)
126         }
127 
128         elements[childIndex] = child
129     }
130     mutating func shiftDown() {
131         shiftDown(0, heapSize: elements.count)
132     }
133     mutating func shiftDown(_ index: Int, heapSize: Int) {
134         var parentIndex = index
135 
136         while true {
137             let leftChildIndex = self.leftChildIndex(ofIndex: parentIndex)
138             let rightChildIndex = leftChildIndex + 1
139             var first = parentIndex
140             if leftChildIndex < heapSize && isOrderedBefore(elements[leftChildIndex], elements[first]) {
141                 first = leftChildIndex
142             }
143             if rightChildIndex < heapSize && isOrderedBefore(elements[rightChildIndex], elements[first]) {
144                 first = rightChildIndex
145             }
146             if first == parentIndex { return }
147 
148             elements.swapAt(parentIndex, first)
149             // swap(&elements[parentIndex], &elements[first])
150             parentIndex = first
151         }
152     }
153 }
154 extension Heap where T: Equatable {
155     public func index(of element: T) -> Int? {
156         return index(of: element, 0)
157     }
158     fileprivate func index(of element: T, _ i: Int) -> Int? {
159         if i >= count { return nil }
160         if isOrderedBefore(element, elements[i]) { return nil }
161         if element == elements[i] { return i }
162         if let j = index(of: element, self.leftChildIndex(ofIndex: i)) { return j }
163         if let j = index(of: element, self.rightChildIndex(ofIndex: i)) { return j }
164         return nil
165     }
166 }

36ms

  1 class Solution {
  2     func reorganizeString(_ S: String) -> String {
  3         var mapy = [Character: Int]()
  4         for c in S {
  5             mapy[c, default: 0] += 1
  6         }
  7         let heap = Heap<(Character, Int)>(elements: mapy.map { ($0.0,$0.1) }, priority: {
  8             return $0.1 > $1.1  
  9         })
 10         var arr = [Character]()
 11         while heap.isEmpty == false {
 12             var top = heap.dequeue()!
 13             if arr.last == top.0 {
 14                 if var second = heap.dequeue() {
 15                     arr.append(second.0)
 16                     second.1 -= 1
 17                     if top.1 > 0 {
 18                         heap.enqueue(top)
 19                     }
 20                     if second.1 > 0 {
 21                         heap.enqueue(second)
 22                     }
 23                 } else {
 24                     return ""
 25                 }
 26             } else {
 27                 arr.append(top.0)
 28                 top.1 -= 1
 29                 if top.1 > 0 {
 30                     heap.enqueue(top)
 31                 }
 32             }
 33         }
 34         return String(arr)
 35     }
 36 }
 37 
 38 final class Heap<T> {
 39 
 40     typealias Comparator = (T,T) -> Bool
 41 
 42     var elements: [T]
 43     let priority: Comparator
 44 
 45     init(elements: [T], priority: @escaping Comparator) {
 46         self.priority = priority
 47         self.elements = elements
 48         if elements.isEmpty == false {
 49             for i in stride(from: (count / 2) - 1, to: -1, by: -1) {
 50                 siftDown(i)
 51             }
 52         }
 53     }
 54 
 55     var isEmpty: Bool {
 56         return elements.isEmpty
 57     }
 58 
 59     var count: Int {
 60         return elements.count
 61     }
 62 
 63     var first: T? {
 64         return elements.first
 65     }
 66 
 67     func leftChildIndex(of index: Int) -> Int {
 68         return (2 * index) + 1
 69     }
 70 
 71     func rightChild(of index: Int) -> Int {
 72         return (2 * index) + 2
 73     }
 74 
 75     func parentIndex(of index: Int) -> Int {
 76         return (index - 1) / 2
 77     }
 78 
 79     func isHigherPriority(_ a: Int, _ b: Int) -> Bool {
 80         return priority(elements[a], elements[b])
 81     }
 82 
 83     func highestPriorityIndex(of index: Int) -> Int {
 84         let left = highestPriorityIndex(of: index, and: leftChildIndex(of: index))
 85         let right = highestPriorityIndex(of: index, and: rightChild(of: index))
 86         return highestPriorityIndex(of: left, and: right)
 87     }
 88 
 89     func highestPriorityIndex(of parent: Int, and child: Int) -> Int {
 90         guard child < count else {
 91             return parent
 92         }
 93         guard isHigherPriority(child, parent) else {
 94             return parent
 95         }
 96         return child
 97     }
 98 
 99     func enqueue(_ element: T) {
100         elements.append(element)
101         siftUp(count - 1)
102     }
103 
104     func siftUp(_ i: Int) {
105         let parent = parentIndex(of: i)
106         guard parent >= 0 else {
107             return
108         }
109         guard isHigherPriority(i, parent) else {
110             return
111         }
112         swap(i, parent)
113         siftUp(parent)