Google

683. K Empty Slots

Given an array flowers consists of number from 1 to N. Each number in the array represents the place where the flower will open in that day. Given an integer k, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them is k and these flowers are not blooming.

1 O(nlogn)

• Use the TreeSet to record the already open place

• TreeSet add, delete, search O(logn)

• return the first one match requirement

public int kEmptySlots(int[] flowers, int k) {
    TreeSet<Integer> active = new TreeSet();
    int day = 0;
    for (int flower: flowers) {
        day++;
        active.add(flower);
        Integer lower = active.lower(flower)
        Integer higher = active.higher(flower);
        if (lower != null && flower - lower - 1 == k ||
                higher != null && higher - flower - 1 == k)
            return day;
    }
    return -1;
}

2 O(n)

• A position array, pos[x] = i means the flower x blooms at i day

• fix left and right pointer, check if we can find an array [left, 1, 2,..., k, right] is valids

public int kEmptySlots(int[] flowers, int k) {
    int len = flowers.length;
    int[] pos = new int[len];
    for(int i=0; i<len; i++){
        // pos[x] = i means the flower x blooms at i day
        pos[flowers[i]-1] = i+1; 
    }

    int left = 0, right = k + 1;
    for(int i=0; Math.max(i, right) < len; i++){
        System.out.println(i);
        if(pos[left] > pos[i] || pos[right] > pos[i]){
            left = i;
            right = left + k + 1;
        }else if( i == right){
            return Math.max(left, right);
        }
    }
    return -1;
}

889. Construct Binary Tree from Preorder and Postorder Traversal

Return any binary tree that matches the given preorder and postorder traversals.

Example

Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1] Output: [1,2,3,4,5,6,7]

• find the length of left tree and use it split the left tree and right tree

• Preorder and postorder left tree length are the same, and pre[1] the head of left tree, use is to find the last position in postorder

public TreeNode constructFromPrePost(int[] pre, int[] post) {
    // pre  [1][2,4,5][3,6,7]
    // post [4,5,2][6,7,3][1]

    int len = pre.length;
    if(len == 0) return null;
    TreeNode node = new TreeNode(pre[0]);
    if(len == 1) return node;

    // find out the length of left tree
    int left_len = 0;
    for(int i=0; i<len; i++){
        if(post[i] == pre[1]) left_len = i+1;
    }

    node.left = constructFromPrePost(Arrays.copyOfRange(pre, 1, 1+left_len), 
                                        Arrays.copyOfRange(post, 0, left_len));
    node.right = constructFromPrePost(Arrays.copyOfRange(pre, 1+left_len, len),
                                         Arrays.copyOfRange(post, left_len, len-1));
    return node;
}

280 Wiggle Sort

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....

public void wiggleSort(int[] nums) {
    if (nums.length == 0) return;

    for(int i=0; i<nums.length-1; i++){
        if(i%2 == 0){
            if(nums[i] > nums[i+1]) swap(nums, i, i+1);   
        }else{
            if(nums[i] < nums[i+1]) swap(nums, i, i+1);
        }
    }
}
private void swap(int[] nums, int i, int j){
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

324 Wiggle Sort II

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....

• Copy the array and sort it, the number smaller than mid should put in odd slots; others should put in even slots.

public void wiggleSort(int[] nums) {
    if (nums.length == 0) return;

    int n = nums.length;
    int mid = (n+1)/2;
    int[] copy = Arrays.copyOf(nums, n);
    Arrays.sort(copy);

    // corner case [4,5,5,6]  medium must be at head and tail
    // put smaller than nums[mid] elements to odd slot, start from mid-1
    for(int i=mid-1, j=0; i>=0; i--, j+=2) nums[j] = copy[i];
    // put greater than nums[mid] elements to even slot, start from n-1
    for(int i=n-1, j=1; i>=mid; i--, j+=2) nums[j] = copy[i];

}

475 Heaters

you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters.

Example: Input: [1,2,3,4],[1,4] Output: 1

public int findRadius(int[] houses, int[] heaters) {
    Arrays.sort(houses);
    Arrays.sort(heaters);
    int i=0, ans=0;

    for(int house: houses){
        while(i<heaters.length-1 && Math.abs(house-heaters[i]) >= Math.abs(house-heaters[i+1])){
            i++;
        }
        ans = Math.max(ans, Math.abs(house-heaters[i]));
    }
    return ans;
}

656 Coin Path

Given an array(index start from 1), B is the step you can jump from index i. Return the path indexes starting from 1 to last index in array.

• A next[] array to record the indexes

• Statement: dp[i] is the min jumping cost starting from index i to end of array.

• Func: dp[i] = min(A[i]+dp[i+B]) B <- 1:B

• Ans: Loop the next[], if index == -1, then return empty list

public List<Integer> cheapestJump(int[] A, int B) {
    int[] dp = new int[A.length];
    int[] next = new int[A.length-1];
    Arrays.fill(next, -1);

    for(int i=A.length-2; i>=0; i--){
        int cost = Integer.MAX_VALUE;
        for(int j=i+1; j<=i+B && j<A.length; j++){
            if(A[j] != -1){
                if(A[i] + dp[j] < cost){
                    cost = A[i] + dp[j];
                    next[i] = j;
                }
            }
        }
        dp[i] = cost;
    }

    List<Integer> ans = new ArrayList<>();
    int i=0;

       // if i is not init means it cannot proceed    
    while(i<A.length-1 && i != -1){
        System.out.println(i);
        ans.add(i+1);
        i=next[i];
    }
    ans.add(i+1);

    if(i == -1) return new ArrayList<>();
    return ans;
}

399. Evaluate Division

Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.

• Time: O(q+ q*E), q is the number of queries, E is the connecting edges. The best case of E is 1, worst is length of equations

  • Space: O(q)

Map<String, ArrayList<String>> pair = new HashMap<>();
Map<String, ArrayList<Double>> pairValue = new HashMap<>();
public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
    for(int i=0; i<equations.length; i++){
        String x = equations[i][0];
        String y = equations[i][1];

        // update nodes connected with x
        if(!pair.containsKey(x)){
            pair.put(x, new ArrayList<String>());
            pairValue.put(x, new ArrayList<Double>());
        }
        pair.get(x).add(y);
        pairValue.get(x).add(values[i]);

        // update nodes connected with y
        if(!pair.containsKey(y)){
            pair.put(y, new ArrayList<String>());
            pairValue.put(y, new ArrayList<Double>());
        }
        pair.get(y).add(x);
        pairValue.get(y).add(1/values[i]);
    }

    double[] ans = new double[queries.length];
    for(int i=0; i<queries.length; i++){
        String[] query = queries[i];
        ans[i] = dfs(query[0], query[1], new HashSet<String>(), 1.0);
        if(ans[i] == 0.0) ans[i] = -1.0;
    }
    return ans;
}

private double dfs(String start, String end, Set<String> visited, double value){
    // 有環
    if(visited.contains(start)) return 0.0;
    if(!pair.containsKey(start)) return 0.0;
    if(start.equals(end)) return value;
    visited.add(start);

    for(int i=0; i<pair.get(start).size(); i++){
        String s = pair.get(start).get(i);
        // visited.add(s);
        double tmp = dfs(s, end, visited, value*pairValue.get(start).get(i));
        if(tmp != 0.0) return tmp;
        // visited.remove(s);
    }
    visited.remove(start);
    return 0.0;
}

524. Longest Word in Dictionary through Deleting

Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

• Implement a isSubsequence method

public String findLongestWord(String s, List<String> d) {
    String ans = "";
    for(String target: d){
        if(isValid(s, target)){
            if(target.length() > ans.length() || 
               (target.length() == ans.length() && target.compareTo(ans) < 0))
                ans = target;
        }
    }
    return ans;
}

private boolean isValid(String s, String target){
    int count=0;
    for(int i=0; i<s.length() && count<target.length(); i++){
        if(s.charAt(i) == target.charAt(count)) count++;
    }
    return count == target.length();
}

792. Number of Matching Subsequences

Given string S and a dictionary of words words, find the number of words[i] that is a subsequence of S.

1 Brute Force

• Time: O(words.len*S.len)

• Space: O(1)

public int numMatchingSubseq(String S, String[] words) {
    int count=0;
    for(String w: words){
        if(isValid(S, w)) count++;
    }
    return count;
}

private boolean isValid(String s, String w){
    int j=0;
    for(int i=0; i<s.length() && j<w.length(); i++){
        if(s.charAt(i) == w.charAt(j)) j++;
    }
    return j == w.length();
}

2 Variant Trie

• Class node to record the word and current index

• Time: O(S.len)

• Space: O(words.len)

• Explaination

• loop list 注意 concurrency, new ArraList

class Node{
    String word;
    int index;
    public Node(String word, int index){
        this.word = word;
        this.index = index;
    }
}

public int numMatchingSubseq(String S, String[] words) {
    int count=0;
    Map<Character, List<Node>> map = new HashMap<>();
    // build the heads
    for(int i=0; i<26; i++){
        map.put((char)('a'+ i), new ArrayList<Node>());
    }

    // init
    for(String w: words){
        char c = w.charAt(0);
        map.get(c).add(new Node(w, 0));
    }

    // loop the String s
    // if index == word len means it got throght the whole word
    for(char c: S.toCharArray()){
        // list在loop過程中不能更動，不然會拋出ConcurrentModificationException
        List<Node> list = map.get(c);
        map.put(c, new ArrayList<>());
        for(Node node: list){
            node.index++;
            if(node.index == node.word.length()) count++;
            else map.get(node.word.charAt(node.index)).add(node);
        }
        list.clear();
    }
    return count;
}

835. Image Overlap

Two images A and B are given, represented as binary, square matrices of the same size. (A binary matrix has only 0s and 1s as values.)

We translate one image however we choose (sliding it left, right, up, or down any number of units), and place it on top of the other image. After, the overlap of this translation is the number of positions that have a 1 in both images.

What is the largest possible overlap?

• Count the moving vector from image A to image B

• Time O(n^4)

public int largestOverlap(int[][] A, int[][] B) {
    // count the moving vector from A to B
    int n = A.length;

    int[][] vector = new int[2*n][2*n];

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(A[i][j] == 1){
                for(int k=0; k<n; k++){
                    for(int l=0; l<n; l++){
                        if(B[k][l] == 1) vector[k-i+n][l-j+n]+=1;
                    }
                }
            }
        }
    }

    // count the max
    int max=0;
    for(int[] row: vector){
        for(int num: row){
            max = Math.max(max, num);
        }
    }

    return max;
}

328. Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

public ListNode oddEvenList(ListNode head) {
    if(head == null) return head;
    ListNode odd = head;
    ListNode even = head.next;
    ListNode evenHead = even;

    while(even != null && even.next != null){
        odd.next = even.next;
        odd = odd.next;
        even.next = odd.next;
        even = even.next;
    }
    odd.next = evenHead;
    return head;

844. Backspace String Compare

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

public boolean backspaceCompare(String S, String T) {
    return helper(S).equals(helper(T));
}

private String helper(String s){
    Stack<Character> stack = new Stack<>();
    for(char c: s.toCharArray()){
        if(c != '#') stack.push(c);
        else if(! stack.empty()) stack.pop();
    }

    return String.valueOf(stack);
}

857. Minimum Cost to Hire K Workers

There are N workers. The i-th worker has a quality[i] and a minimum wage expectation wage[i].

Now we want to hire exactly K workers to form a paid group. When hiring a group of K workers, we must pay them according to the following rules:

1. Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group.

2. Every worker in the paid group must be paid at least their minimum wage expectation.

Return the least amount of money needed to form a paid group satisfying the above conditions.

public double mincostToHireWorkers(int[] quality, int[] wage, int K) {
    double[][] workers = new double[quality.length][2];
    for(int i=0; i<quality.length; i++){
        workers[i] = new double[]{(double)wage[i]/quality[i], (double)quality[i]};
    }

    Arrays.sort(workers, (a,b) -> Double.compare(a[0], b[0]));
    double ans = Double.MAX_VALUE;
    double qualitySum = 0;
    Queue<Double> maxHeap = new PriorityQueue<>();
    for(double[] w: workers){
        qualitySum += w[1];
        maxHeap.add(-w[1]);
        if(maxHeap.size() > K) qualitySum += maxHeap.poll();
        if(maxHeap.size() == K) ans = Math.min(ans, qualitySum*w[0]);
    }
    return ans;
}

843. Guess the Word

We are given a word list of unique words, each word is 6 letters long, and one word in this list is chosen as secret.

You may call master.guess(word) to guess a word. You can not guess the word more than 10 times. The test case has 100 words in wordlist

• Strategy: find a word 有最大的可猜測族群, 利用guess API縮減wordlist

public void findSecretWord(String[] wordlist, Master master) {
    for(int i=0; i<10; i++){
        Map<String, Integer> map = new HashMap<>();
        for(String w1: wordlist){
            for(String w2: wordlist){
                // find a word with the least frequent varietion to others.
                // The group of similar words is bigger
                if(match(w1, w2) == 0) map.put(w1, map.getOrDefault(w1, 0)+1);
            }
        }

        int min = 100;
        String candidate = "";
        for(Map.Entry<String, Integer> entry: map.entrySet()){
            if(entry.getValue() < min){
                min = entry.getValue();
                candidate = entry.getKey();
            }
        }

        if(candidate.equals("")) candidate = wordlist[0];

        int diff = master.guess(candidate);
        List<String> tmp = new ArrayList<>();
        for(String w: wordlist){
            if(match(w, candidate) == diff) tmp.add(w);
        }
        wordlist = tmp.toArray(new String[0]);   
    }
}

private int match(String s1, String s2){
    int match=0;
    for(int i=0; i<s1.length(); i++)
        if(s1.charAt(i) == s2.charAt(i)) match++;
    return match;
}

863. All Nodes Distance K in Binary Tree

We are given a binary tree (with root node root), a target node, and an integer value K.

Return a list of the values of all nodes that have a distance K from the target node.

• Node分兩種，從target往上跟往下

• findTarget(), 返回target跟node之間的距離

  1. node is null

  2. target is node

  3. dfs計算node.left, node.right

  4. 分別根據距離addNode(), 返回距離

private List<Integer> ans;
private int K;
private TreeNode target;

public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
    this.K= K;
    this.target = target;
    ans = new ArrayList<>();
    findTarget(root);
    return ans;
}

private int findTarget(TreeNode node){
    if(node == null){
        return -1;
    }else if(node.val == target.val){
        addNode(node, 0);
        return 1;
    }else{
        int L = findTarget(node.left);
        int R = findTarget(node.right);
        // 必定在某一邊，選擇在一邊return
        if(L != -1){
            if(L == K) ans.add(node.val);
            addNode(node.right, L+1);
            return L+1;
        }else if( R != -1){
            if(R == K) ans.add(node.val);
            addNode(node.left, R+1);
            return R+1;
        }else{
            return -1;
        }
    }
}

private void addNode(TreeNode node, int dist){
    if(node == null) return;
    if(dist == K) ans.add(node.val);
    addNode(node.left, dist+1);
    addNode(node.right, dist+1);
}

858. Mirror Reflection

There is a special square room with mirrors on each of the four walls. Except for the southwest corner, there are receptors on each of the remaining corners, numbered 0, 1, and 2.

The square room has walls of length p, and a laser ray from the southwest corner first meets the east wall at a distance q from the 0th receptor.

Return the number of the receptor that the ray meets first.

• 想像box向上延伸m次，laser反射n次

Explain

public int mirrorReflection(int p, int q) {
    int m=1, n=1;
    while( m*p != n*q){
        n++;
        m = n*q/p;
    }
    // if light reflection is even(n is odd), on the rhs; otherwise lhs
    // if box extension is even(m is odd), on 1; otherwise on 0
    if(m%2==0 && n%2==1) return 0;
    if(m%2==1 && n%2==1) return 1;
    if(m%2==1 && n%2==0) return 2;
    return -1;
}

855. Exam Room

In an exam room, there are N seats in a single row, numbered 0, 1, 2, ..., N-1.

When a student enters the room, they must sit in the seat that maximizes the distance to the closest person

• Need a dynamic sorted array, use TreeSet

• 比較dist分三部分

  1. array head to first seat

  2. seat betweens

  3. last seat to array tail

class ExamRoom {
    TreeSet<Integer> students;
    int N;

    public ExamRoom(int N) {
        this.N = N;
        students = new TreeSet<>();;
    }

    public int seat() {
        int pos = 0;

        if(students.size() > 0){
            // first dist is the dist from beginning to first student
            int dist = students.first();
            Integer prev = null;

            for(int s: students){
                if(prev != null){
                    int tmp = (s-prev)/2;
                    if(tmp > dist){
                        dist = tmp;
                        pos = prev + tmp;
                    }
                }
                prev = s;
            } 

            // test the dist from last student to end of array
            if( (N-1) - students.last() > dist) pos = N-1;
        }

        // add pos to treeSet
        students.add(pos);
        return pos;
    }

    public void leave(int p) {
        students.remove(p);
    }
}

853. Car Fleet

N cars is array. Each car i has a constant speed speed[i] and initial position position[i]

A car can never pass another car ahead of it, if car A catch up car B, they are assumed to have the same position.

Return how many car fleets arrive target

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        if(position.length == 0 || speed.length == 0) return 0;

        int n = position.length;
        Car[] cars = new Car[n];
        for(int i=0; i<n; i++){
            cars[i] = new Car(position[i], (double)(target-position[i])/speed[i]);
        }

        Arrays.sort(cars, (a,b) -> a.pos-b.pos);

        int ans = 0;
        for(int i=n-1; i>0; i--){
            // i較i-1早到, 自成fleet
            if(cars[i].time < cars[i-1].time) ans++;
            // i-1 跟i 結合成fleet, 將i的時間更新至i-1
            else cars[i-1] = cars[i];
        }
        //有無fleet皆+1
        return ans+1;
    }
}

class Car{
    int pos;
    double time;
    public Car(int pos, double time){
        this.pos = pos;
        this.time = time;
    }
}

850. Rectangle Area II

We are given a list of (axis-aligned) rectangles. Each rectangle[i] = [x1, y1, x2, y2] , where (x1, y1) are the coordinates of the bottom-left corner, and (x2, y2) are the coordinates of the top-right corner of the ith rectangle.

Find the total area covered by all rectangles in the plane. Since the answer may be too large, return it modulo 10^9 + 7.

• 記錄每一個rectangle 在y軸上in & out的event, 並且sort by y dimention

• Use sweep line to count x distance, multiple y diff

• Put 'in' event in active lit, move 'out' event

// int[0]: y1/y2, int[1]: in/out, int[2]: x1, int[3]: x2 
public int rectangleArea(int[][] rectangles) {
    int n = rectangles.length;
    List<int[]> line = new ArrayList<>();

    for(int[] rec: rectangles){
        line.add(new int[]{rec[1], 0, rec[0], rec[2]});
        line.add(new int[]{rec[3], 1, rec[0], rec[2]});
    }

    // sort by y dimention
    Collections.sort(line, (a,b) -> a[0] - b[0]);

    int y = line.get(0)[0];
    long ans = 0;
    List<int[]> intervals = new ArrayList<>();

    for(int i=0; i<line.size(); i++){
        int[] cur = line.get(i);
        long dis = getXDistance(intervals);
        ans += dis*(cur[0] - y);   
        if(cur[1] == 0){
            intervals.add(new int[]{cur[2], cur[3]});
            Collections.sort(intervals, (a,b) -> a[0] - b[0]);
        }else{
            for(int[] tmp: intervals){
                if(tmp[0] == cur[2] && tmp[1] == cur[3]){
                    intervals.remove(tmp);
                    break;
                } 
            }
        }
        y = cur[0];
    }

    ans %= 1e9 + 7;
    // if(ans < 0) ans += 1e9+7;
    return (int)ans;
}

private long getXDistance(List<int[]> intervals){
    long ans = 0;
    int prev = -1;
    for(int[] cur: intervals){
        // prev 為上一個x2
        prev = Math.max(prev, cur[0]);
        ans += Math.max(cur[1]-prev, 0);
        prev = Math.max(prev, cur[1]);
    }
    return ans;
}

846. Hand of Straights

Alice has a hand of cards, given as an array of integers.

Now she wants to rearrange the cards into groups so that each group is size W, and consists of W consecutive cards.

Return true if and only if she can.

• Use a TreeMap to record the frequency and continuous of number

public boolean isNStraightHand(int[] hand, int W) {
    if (hand.length%W != 0) return false;

    TreeMap<Integer, Integer> map = new TreeMap<>();
    for(int c: hand) map.put(c, map.getOrDefault(c, 0)+1);

    for(int n: map.keySet()){
        int iter=W;
        // == 0 代表之前已經扣完
        if(map.get(n) > 0){
            while(--iter >=0){
                int cur_val = map.get(n);
                int iter_val = map.getOrDefault(n+iter, 0);
                // 1. n+iter 的數量要大於 n 才對
                // 2. 0 的話沒找到, return false
                if(iter_val < cur_val) return false;
                map.put(n+iter, iter_val - cur_val);
            }
        }
    }
    return true;
}

845. Longest Mountain in Array

Let's call any (contiguous) subarray B (of A) a mountain if the following properties hold:

B.length >= 3 There exists some 0 < i < B.length - 1 such that B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]

return the longest len of mountain

public int longestMountain(int[] A) {
    int max = 0;
    int iter = 1;
    Boolean checked1 = false;
    Boolean checked2 = false;

    while(iter < A.length){
        // 若相等，跟山峰沒關係
        if(A[iter] == A[iter-1]){
            iter++;
            continue;
        }
        int start = iter-1;
        while(iter < A.length && A[iter] > A[iter-1]){
            checked1 = true;
            iter++;
        } 
        while(iter < A.length && A[iter] < A[iter-1]){
            checked2 = true;
            iter++;
        }
        if(checked1 && checked2){
            max = Math.max(max, iter-start);
        }
        checked1 = false;
        checked2 = false;
    }
    return max;
}

833. Find And Replace in String

• The indexes is not sorted order, use a map to store the string index and array index

• StringBuilder starts to update from rear, it doesn't affect the subString

public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
    int n = indexes.length;
    StringBuilder sb = new StringBuilder(S);
    Map<Integer, Integer> map = new HashMap<>();
    for(int i=0; i<n; i++) map.put(indexes[i], i);

    // 從sb後面開始更改，對前面不會影響
    for(int i=sb.length()-1; i>=0; i--){
        if(map.containsKey(i)){
            int index = map.get(i);
            if(S.substring(i).startsWith(sources[index])){
                sb.replace(i, i+sources[index].length(), targets[index]);
            }
        } 
    }
    return sb.toString();
}

818. Race Car

Your car starts at position 0 and speed +1 on an infinite number line. (Your car can go into negative positions.)

Your car drives automatically according to a sequence of instructions A (accelerate) and R (reverse).

When you get an instruction "A", your car does the following: position += speed, speed *= 2.

When you get an instruction "R", your car does the following: if your speed is positive then speed = -1 , otherwise speed = 1. Return the shortest sequence of instructions

• Recursion + memorization

• DP(t): the shortest sequence to achieve target

• 3 condition

  1. t is exact nA: n

  2. t is over 2^n-1 (nA1R): n+1+helper(left)

  3. t is reverse twice (n-1)ARmAR: (n+m+1) + helper( t - (2^(n-1)-1+2^(m)-1))

Explain

class Solution {
    private int[] dp;
    public int racecar(int target) {
        dp = new int[target+1];
        return helper(target);
    }

    private int helper(int t){
        if(dp[t] > 0) return dp[t];
        int n = (int)Math.ceil(Math.log(t+1)/Math.log(2));

        // best case nA: n
        if(1 << n == t+1){
            dp[t] = n;
            return dp[t];
        }
        // nA1R:  n+1+helper(left) 超過回來
        dp[t] = n+1 + helper((1 << n) - 1 - t);
        // (n-1)ARmAR: (n+m+1) + helper( t - (2^(n-1)-1+2^(m)-1))
        // m 最多只會到2^(n-2) 長度, 需要n-1 steps
        for(int m=0; m<n-1; m++){
            int diff = (1 << (n-1)) - (1 << m);
            dp[t] = Math.min(dp[t], n+m+1 + helper(t - diff));
        }
        return dp[t];
    }
}

815. Bus Routes

We have a list of bus routes. Each routes[i] is a bus route that the i-th bus repeats forever. For example if routes[0] = [1, 5, 7], this means that the first bus (0-th indexed) travels in the sequence 1->5->7->1->5->7->1->... forever.

We start at bus stop S (initially not on a bus), and we want to go to bus stop T. Travelling by buses only, what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.

• BFS from bust stop 2 each routes it connected

• Prune if stop is visited

public int numBusesToDestination(int[][] routes, int S, int T) {
    Map<Integer, Set<Integer>> stop2route = new HashMap<>();
    Set<Integer> visited = new HashSet<>();
    Queue<int[]> q = new LinkedList<>();

    // init the map
    for(int i=0; i<routes.length; i++){
        for(int j: routes[i]){
            if(!stop2route.containsKey(j)) stop2route.put(j, new HashSet<>());
            stop2route.get(j).add(i);
        }
    }

    // int[0]: stop, int[1]: count of rount
    q.add(new int[]{S, 0});

    while(!q.isEmpty()){
        int[] cur = q.poll();
        if(cur[0] == T) return cur[1];

        for(Integer route: stop2route.get(cur[0])){
            for(int stop: routes[route]){
                if(visited.contains(stop)) continue;
                visited.add(stop);
                q.add(new int[]{stop, cur[1]+1});
            }
        }
    }
    return -1;
}

805. Split Array With Same Average

In a given integer array A, we must move every element of A to either list B or list C. (B and C initially start empty.)

Return true if and only if after such a move, it is possible that the average value of B is equal to the average value of C, and B and C are both non-empty.

• The avg of A and avg of B and C are the same.

• totalSum/n = Asum/k => Asum = totalSum*k/n整除

• 利用combinationSum, 遞回到 k=0 && remain == 0

public boolean splitArraySameAverage(int[] A) {
    int sum=0;
    int n = A.length;
    for(int num:A) sum+=num;
    Arrays.sort(A);

    for(int i=1; i<=n/2;i++){
        if(sum*i%n == 0 && combinationSum(A, 0, i, sum*i/n)) return true;
    }
    return false;
}

private boolean combinationSum(int[] A, int start, int num, int remain){
    if(remain==0) return num == 0;
    if(remain<0 || num<1) return false;
    for(int i=start; i<A.length-num+1; i++){
        if(combinationSum(A, i+1, num-1, remain-A[i])) return true;
    }
    return false;
}

684. Redundant Connection

Undirected Graph

• Use union find to find cycle

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length + 1;

        UF uf = new UF(n);

        for(int[] edge: edges){
            if(uf.union(edge[0], edge[1])) return edge;
        }
        return new int[]{};
    }   
}

class UF{
    int[] father;
    int[] size;

    public UF(int n){
        father = new int[n];
        size = new int[n];

        for(int i=0; i<n; i++){
            father[i] = i;
            size[i] = 1;
        }
    }

    public int find(int a){
        if(father[a] != a) father[a] = find(father[a]);
        return father[a];
    }

    public boolean union(int a, int b){
        int f_a = find(a);
        int f_b = find(b);

        if(f_a == f_b) return true;
        if(size[f_a] > size[f_b]){
            father[f_b] = f_a;
            size[f_a] += f_b;
        }else{
            father[f_a] = f_b;
            size[f_b] += f_a;
        }
        return false;
    }
}

685. Redundant Connection II

Directed Graph

• 3 circumstances

  1. Only multiple parents

  2. Only cycle

  3. Both

Example:[[2,1],[3,1],[4,2],[1,4]]

class Solution {
    class UF{
        int[] father;

        public UF(int n){
            father = new int[n];
            for(int i=0; i<n; i++){
                father[i] = i;
            }
        }

        public int find(int a){
            if(father[a] != a) father[a] = find(father[a]);
            return father[a];
        }

        public void union(int a, int b){
            int f_a = find(a);
            int f_b = find(b);

            father[f_b] = f_a;
        }
    }

    public int[] findRedundantDirectedConnection(int[][] edges) {
        int n = edges.length+1;
        UF uf = new UF(n);

        int[] candidate1 = null, candidate2 = null;

        for(int[] e: edges){
            int f_a = uf.find(e[0]), f_b = uf.find(e[1]);
            if(f_a != f_b){
                // multiple parents, means e[1] has been seen before and its parents is not itself
                if(f_b != e[1]) candidate1 = e;
                else uf.union(e[0], e[1]);
            }else{
                // cycle
                candidate2 = e;
            } 
        }

        // if only either multiple parents or cycle happens
        if(candidate2 == null) return candidate1;
        if(candidate1 == null) return candidate2;

        // if both happen, we don't consider the 2nd multiple edge since beginning
        // The first edge caused multiple father must be removed

        for(int[] e: edges){
            if(e[1] == candidate1[1]) return e;
        }
        return new int[2];

    }
}

312. Burst Balloons

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] nums[i] nums[right] coins. Here left and right are adjacent indices of i. nums[-1] = nums[n] = 1

• dp[i][j]: 第i個到第j個nums的array中, ballon burst的最大值

• Trans: dp[i][j] = dp[i][k-1] + nums[i]nums[k]nums[j] + dp[k+1][j], i <= k <= j

• Ans: dp[1][n]

• Explain

public int maxCoins(int[] nums) {
    int n = nums.length;
    int[][] dp = new int[n+2][n+2];

    // create arr with arr[-1] & arr[n]
    int[] arr = new int[n+2];
    for(int i=1; i<arr.length-1; i++){
        arr[i] = nums[i-1];
    }
    arr[0] = arr[arr.length-1] = 1;

    // 第一個 loop 間距
    for(int l=1; l<=n; l++){
        for(int i=1; i<=n-l+1; i++){
            int j = i+l-1;
            for(int k=i; k<=j; k++){
                dp[i][j] = Math.max(dp[i][j],
                    dp[i][k-1] + arr[i-1]*arr[k]*arr[j+1] + dp[k+1][j]);
            }
        }
    }
    return dp[1][n];
}

Back 1017t. Similar RGB Color

Given the color "#ABCDEF", return a 7 character color that is most similar to #ABCDEF, and has a shorthand (that is, it can be represented as some "#XYZ")

// 要求的形式為AA, 必定為轉換後的數字為17的倍數
public String similarRGB(String color) {
    return "#" + helper(color.substring(1, 3))
    + helper(color.substring(3, 5)) + helper(color.substring(5));
}

private String helper(String s){
    int num = Integer.parseInt(s, 16);
    num = num / 17 + (num % 17 > 8 ? 1 : 0);
    return String.format("%02x", num * 17);
}