(高频) Rearrange String k Distance Apart
Rearrange String k Distance Apart
这道题考法非常多变，很好的题。普通写法
public class Solution {
public String rearrangeString(String str, int k) {
if(str==null || str.length()==0 || k<0) return "";
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
HashMap<Character, Integer> lastUsed = new HashMap<Character, Integer>();
for(int i=0;i<str.length();i++){
map.put(str.charAt(i), map.getOrDefault(str.charAt(i), 0) +1);
lastUsed.put(str.charAt(i), -k);
}
StringBuilder sb = new StringBuilder();
int time = 0;
while(true){
char selected = findAvailable(map, lastUsed, time, k);
if(selected ==' ') return "";
sb.append(selected);
map.put(selected, map.get(selected)-1);
lastUsed.put(selected, time);
time++;
if(sb.length()==str.length()){
break;
}
}
return sb.toString();
}
public char findAvailable(HashMap<Character, Integer> map, HashMap<Character, Integer> lastUsed, int time, int k){
int max = Integer.MIN_VALUE; char selected = ' ';
for(Character key : map.keySet()){
if(map.get(key)!=0 && map.get(key)>max && time-lastUsed.get(key)>=k){
selected = key;
max = map.get(key);
}
}
return selected;
}
}
以下的代码虽然慢，实际上在空间上保证了最优，当task有成千上万的时候，我们实际上不用位每个task maintain 一个table，用LinkedHashMap记录大小为K的就可以。
public class Solution {
public String rearrangeString(String s, int k) {
HashMap<Character, Integer> freq = new HashMap<Character, Integer>();
LinkedHashMap<Character, Integer> time = new LinkedHashMap<Character, Integer>(k, 0.75f, true){
protected boolean removeEldestEntry(Map.Entry eldest){
return size()>k-1; //key point: k-1
}
};
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
freq.put(c, freq.getOrDefault(c,0)+1);
}
PriorityQueue<Character> pq = new PriorityQueue<Character>(new Comparator<Character>(){
public int compare(Character c1, Character c2){
if(freq.get(c1)==freq.get(c2))
return c1-c2;
else
return freq.get(c2)-freq.get(c1); //key point: reverse order
}
});
for(char key : freq.keySet()){
pq.offer(key);
}
StringBuilder sb = new StringBuilder(); int count = 0;
while(!pq.isEmpty()){
char selected = getNext(pq, time, count);
if(selected==' ') return "";
sb.append(selected);
freq.put(selected, freq.get(selected)-1);
if(freq.get(selected)==0) freq.remove(selected);
else
pq.add(selected);
count++;
}
System.out.println(sb.toString());
return sb.length()==s.length()? sb.toString():"";
}
public char getNext(PriorityQueue<Character> pq, LinkedHashMap<Character, Integer> time, int count){
ArrayList<Character> invalid = new ArrayList<Character>();
char selected = ' ';
while(!pq.isEmpty()){
char tmp = pq.poll();
if(!time.containsKey(tmp)){
selected = tmp;
time.put(tmp, count);
break;
}
invalid.add(tmp);
}
pq.addAll(invalid);
return selected;
}
}
换句话说，条件允许的时候我们要从堆顶拿元素，但是堆顶元素非法的时候，不一定代表此时无解。
因此我们需要在此基础上加一个 queue，来维护这次循环寻找元素时候的解；如果在任何时刻 maxHeap 里没东西了，但是 queue 里还有，都可以说明此时真的没有合法元素了，返回 "".
改良版的写法建立在下图的逻辑上：
我们在一个 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 到底是不是必要的” 这类问题。
public class Solution {
public String rearrangeString(String str, int k) {
if(k==0) return str;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for(int i=0;i<str.length();i++){
if(!map.containsKey(str.charAt(i))) map.put(str.charAt(i), 1);
else map.put(str.charAt(i),map.get(str.charAt(i))+1);
}
PriorityQueue<Character> pq = new PriorityQueue<Character>(new Comparator<Character>(){
public int compare(Character c1, Character c2){
return map.get(c1).intValue()==map.get(c2).intValue()? c1.compareTo(c2) : map.get(c2)-map.get(c1); // >0 is ascending order
}
});
for(char c : map.keySet())
pq.offer(c);
StringBuilder sb = new StringBuilder();
int len = str.length();
while(!pq.isEmpty()){
int cnt = Math.min(k,len);
ArrayList<Character> tmp = new ArrayList<Character>();
for(int i=0;i<cnt;i++){
if(pq.isEmpty()) return ""; //example 3
Character ch = pq.poll();
sb.append(ch);
len--;
map.put(ch, map.get(ch)-1);
if(map.get(ch)>0)
tmp.add(ch);
}
for(char c : tmp)
pq.offer(c);
}
return sb.toString();
}
}
Task Scheduler
这个允许有idle。撸了最简单的写法，41/64 后TLE。
public class Solution {
public int leastInterval(char[] tasks, int n) {
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for(char c : tasks){
map.put(c, map.getOrDefault(c,0)+1);
}
PriorityQueue<Character> pq = new PriorityQueue<Character>(new Comparator<Character>(){
public int compare(Character c1, Character c2){
return map.get(c2)-map.get(c1);
}
});
for(Character t :map.keySet()){
pq.offer(t);
}
HashMap<Character, Integer> time = new HashMap<Character, Integer>(); int ans = 0;
while(!pq.isEmpty()){
ArrayList<Character> tmp = new ArrayList<Character>();
Character nextTask = null;
while(!pq.isEmpty()){
Character t = pq.poll();
if(!time.containsKey(t)||ans-time.get(t)>n){
nextTask = t; break;
}
else{
tmp.add(t);
}
}
pq.addAll(tmp);
if(nextTask!=null){
time.put(nextTask, ans);
if(map.get(nextTask)==1) map.remove(nextTask);
else{
map.put(nextTask, map.get(nextTask)-1);
pq.offer(nextTask);
}
}
ans++;
}
return ans;
}
}
惊世骇俗简单却没想到的解法，来看例子 AAAABBBEEFFGG 3
Frame: "AXXXAXXXAXXXA"
insert 'B': "ABXXABXXABXXA" <--- 'B' has higher frequency than the other characters, insert it first.
insert 'E': "ABEXABEXABXXA"
insert 'F': "ABEFABEXABFXA" <--- each time try to fill the k-1 gaps as full or evenly as possible.
insert 'G': "ABEFABEGABFGA"
实际这个range是由最频繁的字符控制的，一旦设置了最频繁的字符，这个frame就定下了最基本的框架，有多少个frequent的letter，就有多少个大小为k的bin。最后一个bin比较特殊，有多少个并列的frequent letter，最后就有多少。注意最后要和取原始字符串取max，一种情况“abcd”。
前面在思考这个问题的时候，更多的是站在局部考虑这个问题，下一步取什么；而这种approach站在一个大局在考虑问题，先设计好框架，再填数，甚至不填数字直接计算。
public class Solution {
public int leastInterval(char[] tasks, int n) {
int[] c = new int[26];
for(char t : tasks){
c[t - 'A']++;
}
Arrays.sort(c);
int i = 25;
while(i >= 0 && c[i] == c[25]) i--;
return Math.max(tasks.length, (c[25] - 1) * (n + 1) + 25 - i);
}
}
(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));
给定任务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) 变种：任务调度，生成“最优”的任务序列，可以用空格占位；
问题一：返回最优长度
问题二：返回带空格的最优序列
follow up：https://instant.1point3acres.com/thread/167190在这个基础上，已知cooldown会很小，可以视作constant，task的type会很多，让我减少空间复杂度 (这个是 task 顺序已经给好不需要动的情况)