(高频) Rearrange String k Distance Apart
第一次写的时候，用的是自定义 tuple(char, count, timestamp) + heap 的贪心法，每次取 count 最大的元素，count 一样取 timestamp 最小的。
但是挂在了 "aaabc" k = 2，上，正解是 "abaca"。
换句话说，条件允许的时候我们要从堆顶拿元素，但是堆顶元素非法的时候，不一定代表此时无解。
因此我们需要在此基础上加一个 queue，来维护这次循环寻找元素时候的解；如果在任何时刻 maxHeap 里没东西了，但是 queue 里还有，都可以说明此时真的没有合法元素了，返回 "".
速度尚可，超过 48%
public class Solution {
private class Tuple{
char chr;
int count;
int timestamp;
public Tuple(char chr, int count){
this.chr = chr;
this.count = count;
}
}
private class TupleComparator implements Comparator<Tuple>{
public int compare(Tuple a, Tuple b){
if(a.count != b.count) return b.count - a.count;
else return a.timestamp - b.timestamp;
}
}
public String rearrangeString(String str, int k) {
int[] hash = new int[26];
PriorityQueue<Tuple> maxHeap = new PriorityQueue<Tuple>(new TupleComparator());
for(int i = 0; i < str.length(); i++){
hash[str.charAt(i) - 'a']++;
}
for(int i = 0; i < 26; i++){
if(hash[i] > 0) maxHeap.offer(new Tuple((char)(i + 'a'),hash[i]));
}
StringBuilder sb = new StringBuilder();
Queue<Tuple> queue = new LinkedList<>();
int time = 0;
while(!maxHeap.isEmpty()){
Tuple tuple = maxHeap.poll();
time ++;
if(tuple.timestamp != 0 && time - tuple.timestamp < k){
queue.offer(tuple);
continue;
}
sb.append(tuple.chr);
tuple.count --;
tuple.timestamp = time;
if(tuple.count != 0) maxHeap.offer(tuple);
while(!queue.isEmpty()) maxHeap.offer(queue.poll());
}
return !queue.isEmpty() ? "": sb.toString();
}
}
注意，下面的代码和画图有 bug.
"aabbccd"
k = 3
返回了 abcacdb, c 冲突了，正解是 abcabcd
改良版的写法建立在下图的逻辑上：
我们在一个 size = str.length 的 char[] 上维护 size = k 的 bin 若干个
对于每个 bin ，里面都放置着最多 k 个 distinct character;
每个 bin 里面元素的顺序存在一种 consistent ordering，即一定会严格按照我们定义的 Tuple 顺序由大到小填充。因此 bin 与 bin 之间一定不会违反 distance constraint;
同时我们的遍历顺序是顺序依次遍历每个 bin，避免类似 AAAABBBBCCCCDDDD ，k = 3 的时候，实际 bin size 应该是 4 ，无脑从头填充会出 bug 的问题。
这种写法适合不适合写自己填空格的 follow-up，有待研究。。至少 AAABBBCCCDDD 这种填充时候需要额外判断一下 “这个 space 到底是不是必要的” 这类问题。
12ms，超过 90.16%
private class Tuple implements Comparable<Tuple>{
char chr;
int freq;
public Tuple(char chr, int freq){
this.chr = chr;
this.freq = freq;
}
public int compareTo(Tuple b){
if(this.freq != b.freq) return b.freq - this.freq;
else return this.chr - b.chr;
}
}
public String rearrangeString(String str, int k) {
if(k < 2) return str;
Tuple[] count = new Tuple[26];
for(int i = 0; i < str.length(); i++){
char chr = str.charAt(i);
int index = (int) chr - 'a';
if(count[index] == null) count[index] = new Tuple(chr, 0);
count[index].freq++;
}
ArrayList<Tuple> list = new ArrayList<>();
for(int i = 0; i < 26; i++){
if(count[i] != null) list.add(count[i]);
}
Collections.sort(list);
char[] rst = new char[str.length()];
int binIndex = 0;
int ptr = 0;
for(int index = 0; index < list.size(); index++){
Tuple tuple = list.get(index);
for(int i = 0; i < tuple.freq; i++){
rst[ptr] = tuple.chr;
if(ptr > 0 && rst[ptr] == rst[ptr - 1]) return "";
ptr += k;
if(ptr >= rst.length) ptr = ++ binIndex;
}
}
return new String(rst);
}
(FB) 不改顺序的 cooldown 输出
第二轮，老外面试官，给一个String, 如AABACCDCD, 插入''使同一个字母间隔为k: 如果k=3: A - - - A B - - A C - - - C D - - C D, 一开始理解有误，认为是要先shuffle字母顺序然后插入''，花了不少时间，然后面试官提示字母顺序不变。
刚刚面完，欧洲小哥，发上来攒人品 Tasks: 1, 1, 2, 1
cooldown: 2
Output: 7 (order is 1 - - 1 2 - 1)
Tasks: 1, 2, 3, 1, 2, 3
(cooldown): 3
Output: 7 (order is 1 2 3 - 1 2 3)
Tasks: 1, 2, 3 ,4, 5, 6, 2, 4, 6, 1, 2, 4
(cooldown): 6
Output: 18 (1 2 3 4 5 6 - - 2 - 4 - 6 1 - 2 - 4)
public static String schedule(int[] tasks, int k){
// Key : task number
// Value : index of last appearance
HashMap<Integer, Integer> map = new HashMap<>();
StringBuilder sb = new StringBuilder();
int timestamp = 0;
for(int i = 0; i < tasks.length; i++){
int task = tasks[i];
if(!map.containsKey(task)){
sb.append("" + task);
} else {
while(timestamp - map.get(task) <= k){
sb.append("_");
timestamp ++;
}
sb.append("" + task);
}
map.put(task, timestamp++);
}
return sb.toString();
}
public static void main(String[] args){
int[] tasks1 = new int[]{1,2,3,1,2,3};
int cooldown1 = 3;
int[] tasks2 = new int[]{1, 2, 3 ,4, 5, 6, 2, 4, 6, 1, 2, 4};
int cooldown2 = 6;
int[] tasks3 = new int[]{1,2,3,1,2,3};
int cooldown4 = 3;
System.out.println(schedule(tasks2, cooldown2));
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=137479&extra=page%3D1%26filter%3Dsortid%26sortid%3D311&page=1
给定任务AABCB, 冷却时间k（相同任务之间的最短距离时间），任务顺序不能变，问完成任务的总时间。
例子：AABCB, k = 3, A _ _ A B C _ B, 时间为8.
解法：用hashtable保存上次的时间。
Followup1：如果k很小，怎么优化？ 解法：之前的hashtable的大小是unique task的大小，如果k很小，可以只维护k那么大的hashtable
Followup2: 如果可以改变任务的顺序，最短的任务时间是多少？ 例子：AABBC, K=2, AB*ABC, 时间为6.
解法：根据每个任务出现的频率排序，优先处理频率高的。但是具体细节没有时间讨论。
(FB) 变种：任务调度，生成“最优”的任务序列，可以用空格占位；