K 距离间隔重排字符串
难度:
标签:
题目描述
代码结果
运行时间: 58 ms, 内存: 0.0 MB
/*
* LeetCode 358: Rearrange String k Distance Apart using Java Streams
* This solution uses Java Streams to handle the rearrangement logic.
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public String rearrangeString(String s, int k) {
if (k == 0) return s;
Map<Character, Long> freqMap = s.chars()
.mapToObj(c -> (char) c)
.collect(Collectors.groupingBy(c -> c, Collectors.counting()));
PriorityQueue<Map.Entry<Character, Long>> maxHeap = new PriorityQueue<>((a, b) -> Long.compare(b.getValue(), a.getValue()));
maxHeap.addAll(freqMap.entrySet());
Queue<Map.Entry<Character, Long>> waitQueue = new LinkedList<>();
StringBuilder result = new StringBuilder();
while (!maxHeap.isEmpty()) {
Map.Entry<Character, Long> current = maxHeap.poll();
result.append(current.getKey());
current.setValue(current.getValue() - 1);
waitQueue.offer(current);
if (waitQueue.size() < k) continue;
Map.Entry<Character, Long> front = waitQueue.poll();
if (front.getValue() > 0) {
maxHeap.offer(front);
}
}
return result.length() == s.length() ? result.toString() : "";
}
}解释
方法:
这个题解的思路是先统计每个字符出现的频率，然后将字符按频率从大到小排序。接下来检查出现频率最高的字符是否会导致无法构造有效的重排后字符串，如果无法构造则直接返回空字符串。如果可以构造，则创建一个长度为n的数组ans，初始化为'_'。然后从频率最高的字符开始，每次将字符放到ans中当前位置，并将当前位置向后移动k个位置。如果到达末尾，则回到开头继续。每放置一个字符，就将该字符的剩余数量减1，直到所有字符都放置完毕。最后将ans数组转换为字符串返回。
时间复杂度:
O(n^2)
空间复杂度:
O(n)
代码细节讲解
🦆
在进行字符频率统计和排序后，你是如何确保在字符放置时遵循了距离间隔k的规则？
▷🦆
如果在重排过程中，当前索引位置已被占用，你是如何处理这种情况以确保字符间的距离维持在k？
▷🦆
你提及在重排时可能需要回到数组的开头继续放置字符，这种环状处理是否可能导致无限循环？如果是，你是如何避免这种情况的？
▷🦆
在题解中，你检查了出现频率最高的字符是否会导致无法构造有效的重排后字符串，能否解释为什么使用表达式 `(temp[0][1] - 1) * k + 1 + count - 1 > n` 来进行这一检查？
▷相关问题
任务调度器
给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表，用字母 A 到 Z 表示，以及一个冷却时间 n。每个周期或时间间隔允许完成一项任务。任务可以按任何顺序完成，但有一个限制：两个 相同种类 的任务之间必须有长度为 n 的冷却时间。
返回完成所有任务所需要的 最短时间间隔 。
示例 1：
输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B
在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。
示例 2：
输入：tasks = ["A","A","A","B","B","B"], n = 0 输出：6 解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0 ["A","A","A","B","B","B"] ["A","B","A","B","A","B"] ["B","B","B","A","A","A"] ... 诸如此类
示例 3：
输入：tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
输出：16
解释：一种可能的解决方案是：
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A
提示：
1 <= tasks.length <= 104tasks[i]是大写英文字母0 <= n <= 100