General

Longest Absolute File Path

Suppose we abstract our file system by a string in the following manner:

The string "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" represents:

dir subdir1 subdir2 file.ext

• Leetcode 388

• '\t', '\n' 長度為1

• Sting.split(), String.lastIndexOf()

• sum[]紀錄目前長度

public int lengthLongestPath(String input) {
    if(input.equals("")) return 0;

    int[] sum = new int[input.length()+1];
    int ans = 0;

    for(String dir: input.split("\n")){
        int level = dir.lastIndexOf('\t') + 2;
        int len = dir.length() - level + 1;
        if(dir.contains(".")){
            ans = Math.max(ans, sum[level-1] + len);
        }else{
            sum[level] = sum[level-1] + len + 1;
        }
    }
    return ans;
}

Find Celebrity

• Leetcode 277

public int findCelebrity(int n) {
    int cele = 0;  

    // select candidate
    for(int i=1; i<n; i++){
        if(knows(cele, i)){
            cele = i;
        }
    }

    // test if candidate knows others
    for(int i=0; i<cele; i++){
        if(knows(cele, i)) return -1;
    }

    // test if everyone knows
    for(int i=0; i<n; i++){
        if(i != cele && !knows(i, cele)) return -1;
    }
    return cele;
}

390. Elimination Game

There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.

Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers.

Find the last number that remains starting with a list of length n.

Explain

def lastRemaining(self, n: int) -> int:
    head = 1
    step = 1
    goLeft = True
    while n > 1:
        if goLeft or n % 2 == 1:
            head += step
        step *= 2
        n //= 2
        goLeft = not goLeft
    return head

621 Task Scheduler

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle. You need to return the least number of intervals the CPU will take to finish all the given tasks.

1. Heap

   • Take the most frequent character first as possible

   • Time O(n), Space O(1)

public int leastInterval(char[] tasks, int n) {
    int[] arr = new int[26];
    for(char c: tasks){
        arr[c-'A']++;
    }
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(26, Collections.reverseOrder());
    for(int num: arr){
        if(num != 0) maxHeap.add(num);
    }

    int time=0;
    while(!maxHeap.isEmpty()){
        List<Integer> tmp = new ArrayList<>();
        int i = 0;
        while(i<=n){
            if(!maxHeap.isEmpty()){
                int num = maxHeap.poll();
                if(num != 1){
                    tmp.add(num-1);
                }
            }
            time++;
            if(maxHeap.isEmpty() && tmp.isEmpty()) break;
            i++;
        }
        maxHeap.addAll(tmp);
    }
    return time;
}

1. Count extra slot

   • Time O(n), Space O(1)

   • sort O(26log26) is O(1)

def leastInterval(self, tasks: List[str], n: int) -> int:
    counter = collections.Counter(tasks)
    max_count = max(counter.values())
    
    total_slot = (max_count - 1) * (n + 1)
    for k, v in counter.items():
        if v == max_count:
            total_slot -= v - 1
        else:
            total_slot -= v
        
    return len(tasks) + (total_slot if total_slot > 0 else 0)