【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 ""
