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

注意,下面的代码和画图有 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 顺序已经给好不需要动的情况)

Last updated