(FB) Rearrange String k Distance Apart

(高频) Rearrange String k Distance Apart

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();
    }
}

思路来自 https://discuss.leetcode.com/topic/48125/java_solution_in_12_ms-o-n-time-and-space

注意，下面的代码和画图有 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) 变种：任务调度，生成“最优”的任务序列，可以用空格占位；

• 问题一：返回最优长度

• 问题二：返回带空格的最优序列

• follow up：https://instant.1point3acres.com/thread/167190 在这个基础上，已知cooldown会很小，可以视作constant，task的type会很多，让我减少空间复杂度 (这个是 task 顺序已经给好不需要动的情况)