463. Island Perimeter

86.10 %
class Solution {
    public int islandPerimeter(int[][] grid) {
        // try to add 4 edges to each node
        // if there are to node connect to each other, then 2 edges should be subtracted
        int result = 0;
        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) return 0;
        for (int y = 0; y < grid.length; y++) {
            for (int x = 0; x < grid[0].length; x++) {
                if (grid[y][x] == 1) {
                    result += 4;
                    if (y + 1 < grid.length && grid[y + 1][x] == 1) {
                        result -= 2;
                    }
                    if (x + 1 < grid[0].length && grid[y][x + 1] == 1) {
                        result -= 2;
                    }
                }
            }
        }
        return result;
    }
}

657. Robot Return to Origin

91.43 %
class Solution {
    public boolean judgeCircle(String moves) {
        int y = 0;
        int x = 0;
        for (int i = 0; i < moves.length(); i++) {
            char c = moves.charAt(i);
            if (c == 'U') {
                y--;
            } else if (c == 'D') {
                y++;
            } else if (c == 'L') {
                x--;
            } else {
                x++;
            }
        }
        return x == 0 && y == 0;
    }
}

972. Equal Rational Numbers

68.52 %
class Solution {
    public boolean isRationalEqual(String S, String T) {
        return Double.valueOf(normalize(S)).compareTo(
            Double.valueOf(normalize(T))) == 0;
    }
   
    private String normalize(String s) {
        int index = s.indexOf("(");
        String result = s;
        if (index > 0) {
            result = s.substring(0, index);
            for (int i = 0; i < 20; i++) {
               result += s.substring(index + 1, s.length() - 1);
            }
        }
        return result;
    }
}

958. Check Completeness of a Binary Tree

Version #2 BFS[TODO]


Version #1 DFS

98.36 
class Solution {
    int count;
    public boolean isCompleteTree(TreeNode root) {
        count = getCount(root);
        return validate(root, 1);
    }
   
    private boolean validate(TreeNode node, int id) {
        if (node == null) return true;
        if (id > count) return false;
        return validate(node.left, id * 2) && validate(node.right, id * 2 + 1);
    }
   
   
    private int getCount(TreeNode node) {
        if (node == null) return 0;
        return 1 + getCount(node.left) + getCount(node.right);
    }
}

943. Find the Shortest Superstring

Version #1 DP

非常难的一道题
bug出在了当A[i] 为第一个word的时候，如果不设parent[1 << i][i] = i 而default为0的话就会陷入死循环
其余的思路其实和knapsack有点类似
关键在于状态压缩
把两个word之间的连接状态，压缩成一个已知的set，append一个word的状态

95.59 %
class Solution {
    public String shortestSuperstring(String[] A) {
        // int state -> which words index have been visited
        // dp[state][i] -> minimum superstring length to cover state, and i is the last word
        // having dp[state][j] -> try to expand to word that have not been visited before
        // dp[state][i] = Math.min(dp[state][i], dp[state][j] + cost[j][i])
        // store the last index j for dp[state][i] -> parent[state][i] = j
        // cost[i][j] -> the length increased to append A[j] after A[i], not including length of A[i]
        int len = A.length;
        int[][] cost = new int[len][len];
        int endState = 0; // if state reached this state, we know that all words have been used
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < i; j++) {
                cost[i][j] = getCost(A[i], A[j]);
                cost[j][i] = getCost(A[j], A[i]);
            }
            endState += 1 << i;
        }
        int totalCost = Integer.MAX_VALUE;
        int lastIndex = 0;
        int[][] dp = new int[endState + 1][len];
        int[][] parent = new int[endState + 1][len]; // parent index for min cost
        for (int i = 0; i < len; i++) {
            dp[1 << i][i] = A[i].length(); // A[i] is the first word, cost is it self
            parent[1 << i][i] = i;
        }
        for (int s = 0; s <= endState; s++) {
            for (int i = 0; i < len; i++) {
                // check if this state has visited A[i] or not
                if ((s & (1 << i)) == 0 || s == (1 << i)) continue;
                dp[s][i] = Integer.MAX_VALUE;
                int prevState = s & (~(1 << i)); // reset bit i
                for (int j = 0; j < len; j++) {
                    if ((prevState & (1 << j)) == 0) continue;
                    // All possible prev states
                    if (dp[prevState][j] + cost[j][i] < dp[s][i]) {
                        dp[s][i] = dp[prevState][j] + cost[j][i];
                        parent[s][i] = j;
                    }
                }
                if (s == endState && dp[s][i] < totalCost) {
                    totalCost = dp[s][i];
                    lastIndex = i;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        while (endState != 0) {
            int curr = lastIndex;
            lastIndex = parent[endState][curr];
            endState = endState & (~(1 << curr)); // reset lastIndex
            String temp = A[curr].substring(A[curr].length() - cost[lastIndex][curr]);
            sb.insert(0, temp);
        }
        sb.insert(0, A[lastIndex]);
        return sb.toString();
    }
   
    private int getCost(String first, String second) {
        // abcd     cdef
        int overlap = 0;
        for (int i = 0; i < first.length(); i++) {
            if (second.startsWith(first.substring(i))) {
                overlap = first.length() - i;
                break;
            }
        }
        return second.length() - overlap;
    }
}

347. Top K Frequent Elements

二刷 06/2022

Version #3 Quick Select

和973用了不同的partition方法

这里没有把pivot swap到它正确的位置

返回的index是left - 1, 表示从(0-index) >= partition, (index+1, len-1) <= partition

如果index<k-1表示从0到index不足k个数，这时候要start=index+1，如果不+1会infinite loop

表示从0到index有大于等于k个数，这时候要end=index

Time O(N)

Space O(#distinct number)

Runtime: 16 ms, faster than 58.05% of Java online submissions for Top K Frequent Elements.

Memory Usage: 50.2 MB, less than 59.80% of Java online submissions for Top K Frequent Elements.

class Solution {

    public int[] topKFrequent(int[] nums, int k) {

        if (nums == null || nums.length == 0) {

            return new int[0];

        }

        Map<Integer, Integer> count = new HashMap<>();

        for (int num : nums) {

            count.put(num, count.getOrDefault(num, 0) + 1);

        }

        int[] unique = new int[count.size()];

        int i = 0;

        for (int num : count.keySet()) {

            unique[i++] = num;

        }

        int index = unique.length;

        int start = 0, end = unique.length - 1;

        while (index != k - 1) {

            index = partition(unique, start, end, count);

            // System.out.printf("start=%d,end=%d,index=%d\n", start, end, index);

            if (index < k - 1) {

                start = index + 1;

            } else {

                end = index;

            }

        }

        int[] result = new int[k];

        for (int j = 0; j < k; j++) {

            result[j] = unique[j];

        }

        return result;

    }

    

    private int partition(int[] nums, int start, int end, Map<Integer, Integer> count) {

        int pivot = nums[start + (end - start) / 2];

        int pivotCnt = count.get(pivot);

        int left = start, right = end;

        while (left <= right) {

            while (left <= right && count.get(nums[left]) > pivotCnt) {

                left++;

            }

            while (left <= right && count.get(nums[right]) < pivotCnt) {

                right--;

            }

            if (left <= right) {

                swap(nums, left, right);

                left++;

                right--;

            }

        }

        return left - 1;

    }

    

    private void swap(int[] nums, int a, int b) {

        int temp = nums[a];

        nums[a] = nums[b];

        nums[b] = temp;

    }

}

Version #2 Bucket Sort
有一个bug
因为count 是从1开始，所以生成的bucket size 需要 是length + 1

Time O(n)
95.43 %
class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        // key-num, value-count
        for (int num : nums) {
            map.put(num, 1 + map.getOrDefault(num, 0));
        }
        // the frequency can't exceed total number of nums
        List<Integer>[] bucket = new List[nums.length + 1];
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int count = entry.getValue();
            if (bucket[count] == null) {
                bucket[count] = new ArrayList<>();
            }
            bucket[count].add(entry.getKey());
        }
        List<Integer> result = new ArrayList<>();
        int i = nums.length;
        while (i >= 0 && result.size() < k) {
            if (bucket[i] != null) {
                result.addAll(bucket[i]);
            }
            i--;
        }
        return result;
    }
}

Version #1 HashMap + minHeap
Time O(nlogk)
Space O(count of unique values)

51.98 %
class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        // Count frequency -> Map<num, count> -> O(n) for all nums
        // get most k count
        // retrieve from map
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            int count = 1 + map.getOrDefault(num, 0);
            map.put(num, count);
        }
        // O(nlogk)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int count : map.values()) {
            if (minHeap.size() < k) {
                minHeap.offer(count);
            } else if (count > minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(count);
            }
        }
        Set<Integer> countK = new HashSet<>(minHeap);
        List<Integer> result = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (countK.contains(entry.getValue())) {
                result.add(entry.getKey());
            }
        }
        return result;
    }
}

760. Find Anagram Mappings

92.70 %
class Solution {
    public int[] anagramMappings(int[] A, int[] B) {
// key-num, value-index
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < B.length; i++) {
            map.putIfAbsent(B[i], i);
        }
        int[] result = new int[A.length];
        for (int i = 0; i < A.length; i++) {
            result[i] = map.get(A[i]);
        }
        return result;
    }
}