【LeetCode】358.K 距離間隔重排字符串
358.K 距離間隔重排字符串
知識點：哈希表；貪心；堆；隊列
題目描述
給你一個非空的字符串 s 和一個整數 k，你要將這個字符串中的字母進行重新排列，使得重排後的字符串中相同字母的位置間隔距離至少為 k。
所有輸入的字符串都由小寫字母組成，如果找不到距離至少為 k 的重排結果，請返回一個空字符串 「」
說明：你不能傾斜容器。
示例
示例 1：
輸入: s = "aabbcc", k = 3
輸出: "abcabc"
解釋: 相同的字母在新的字符串中間隔至少 3 個單位距離。
示例 2:
輸入: s = "aaabc", k = 3
輸出: ""
解釋: 沒有辦法找到可能的重排結果。
示例 3
輸入: s = "aaadbbcc", k = 2
輸出: "abacabcd"
解釋: 相同的字母在新的字符串中間隔至少 2 個單位距離。
解法一：貪心+隊列
這道題應該先對每個字符統計數字，然後應該先插入的是數字最多的字符，這時候需要把這個字符的數量-1，而且應該先把這個字符移出去，因為下一次不能插入它了，必須等長度到達k後才能插入它。
對於插入數字最多的字符，應該排序，所以可以用一個大根堆，堆頂就是數量最多的。
而對於把插入的移出去，可以用隊列。
判斷隊列中的元素個數是否為k，if是的話，那說明對於插入的字符c，它已經間隔夠k個字符了，所以c可以再出去一次了，那麼久可以把c這個隊列頭拿出來，放到大根堆里去了。
當大根堆沒有元素後，可以判斷res的長度，if等於原來的長度，那證明重構完成了，if不等於，那說明有字符還在queue里，重構失敗；
class Solution {
public String rearrangeString(String s, int k) {
if (k <= 1) {
return s;
}
HashMap<Character, Integer> map = new HashMap<>();
// 大頂堆
PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
for (Character c : s.toCharArray()) {
// 遍歷字符，統計字符的出現次數
map.put(c, map.getOrDefault(c, 0) + 1);
}
maxHeap.addAll(map.entrySet()); // 裝入大頂堆，按照字符重複次數作為比較
StringBuilder sb = new StringBuilder(s.length());
Queue<Map.Entry<Character, Integer>> queue = new LinkedList<>();
while (!maxHeap.isEmpty()) {
Map.Entry<Character, Integer> currentEntry = maxHeap.poll(); // 從大頂堆取出重複次數最多的字符
sb.append(currentEntry.getKey());
currentEntry.setValue(currentEntry.getValue() - 1); // 用掉一個字符，次數減一
queue.offer(currentEntry); // 放入到queue中，因為k距離後還要用。
if (queue.size() == k) {
// queue的大小到達了k，也就是說我們已經越過了k個單位，在結果中應該要出現相同的字母了
Map.Entry<Character, Integer> entry = queue.poll();
if (entry.getValue() > 0) {
// 該字符的重複次數大於 0，則添加入大頂堆中，要是0那還加它幹嘛
maxHeap.add(entry);
}
}
}
// 退出 while 循環就是大頂堆已經沒有元素了，如果此時 sb 的長度沒有還原，說明還有元素掛在 queue 中
// 即 queue.size() == k 這個條件沒有完全滿足，即存在一些字符無法間隔 k 個距離
return sb.length() == s.length() ? sb.toString() : "";
}
}
- python
import heapq
from collections import Counter, deque
class Solution:
def combine_chars(self, input: str, interval: int) -> str:
if interval <= 1:
return input
count = Counter(input) #生成一個字典
heap = [(-v, k) for k, v in count.items()] #按照元祖的第一個即-v來生成小根堆，也就是v的大根堆
heapq.heapify(heap) #生成大根堆
queue = deque() # 隊列用來記錄已經被記錄的字符
res = []
while heap:
count, ch = heapq.heappop(heap)
res.append(ch)
queue.append((count+1, ch))
if len(queue) == interval:
element = queue.popleft()
if element[0] < 0:
heapq.heappush(heap, element)
return "".join(res) if len(res) == len(input) else ""
