285. Inorder Successor in BST

https://stackoverflow.com/questions/5471731/in-order-successor-in-binary-search-tree

Version #1 Iterative
看上去很fancy，实际上看成是 binary search就很好理解了
if (mid <= target) start = mid + 1
if (mid > target) end = mid

12.79 %
class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        /* target = 4
          7
         / \
        3   8
       / \
      2   5
     /   / \
    1   4   6
    Why 5 should replace 7? Since 5 is the seconde time I walk left to approach 4, it is smaller than 7 and can be guaranteed to be larger than 4
        */
        // if a node has a right subtree, its sucessor is the left most node of its right butbree
        // if a node doesn't have a right subtree, result is the 1st ancestor on its right
        TreeNode result = null;
        TreeNode curr = root;
        while (curr != null) {
            if (curr.val > p.val) { // p is in left subtree
                result = curr;
                curr = curr.left;
            } else if (curr.val <= p.val) {
                curr = curr.right;
            }
        }
        return result;
    }
}


一刷
100.00 %
class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode curr = root;
        TreeNode result = null;
        while (curr != null) {
            if (curr.val > p.val) {
                result = curr;
                curr = curr.left;
            } else {
                curr = curr.right;
            }
        }
        return result;
    }
}

二刷
Time O(n)
这个方法实际上是在找binary tree的next node，没有利用BST的性质
如果利用BST的性质recursiveily可以达到O(logn)
Version #2 Recursive
7.58 %
class Solution {
    TreeNode prev;
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        return dfs(root, p);
    }
    private TreeNode dfs(TreeNode node, TreeNode p) {
        if (node == null) return null;
        TreeNode left = dfs(node.left, p);
        if (left != null) return left;
        if (prev == p) {
            return node;
        }
        prev = node;
        TreeNode right = dfs(node.right, p);
        if (right != null) return right;
        return null;
    }
}

333. Largest BST Subtree

一刷

Each node is used exactly once, so Time O(n)
Space O(height)
99.86 %
class Solution {
    public int largestBSTSubtree(TreeNode root) {
        int[] max = new int[1];
        helper(root, max);
        return max[0];
    }
 
    // int[0] count -> -1, not valid bst
    // int[1] min
    // int[2] max
    private int[] helper(TreeNode node, int[] max) {
        int[] result = null;
        if (node == null) {
            result = new int[]{0};
            return result;
        }
        if (node.left == null && node.right == null) {
            result = new int[]{1, node.val, node.val};
        } else {
            int[] left = helper(node.left, max);
            int[] right = helper(node.right, max);
            if (left[0] == -1 || right[0] == -1
               || (left[0] != 0 && left[2] >= node.val)
               || (right[0] != 0 && right[1] <= node.val)) {
                    result = new int[]{-1};
             } else {
                result = new int[]{1, node.val, node.val};
                if (left[0] != 0) {
                    result[0] += left[0];
                    result[1] = left[1];
                }
                if (right[0] != 0) {
                    result[0] += right[0];
                    result[2] = right[2];
                }
            }
        }
        max[0] = Math.max(max[0], result[0]);
        return result;
    }
}

199. Binary Tree Right Side View

二刷 07/2022

Version #1 DFS

感觉没有一刷做的好

这里是先看左边然后如果右边遇到了新的就覆盖之前的

一刷是直接从右往左看，取代了覆盖的过程

Time O(N)

Space O(N)

Runtime: 1 ms, faster than 95.06% of Java online submissions for Binary Tree Right Side View.

Memory Usage: 40.8 MB, less than 93.77% of Java online submissions for Binary Tree Right Side View.

class Solution {

    public List<Integer> rightSideView(TreeNode root) {

        List<Integer> result = new ArrayList<>();

        dfs(root, result, 0);

        return result;

    }

    

    private void dfs(TreeNode node, List<Integer> result, int level) {

        if (node == null) {

            return;

        }

        if (level == result.size()) {

            result.add(node.val);

        } else {

            result.set(level, node.val);

        }

        dfs(node.left, result, level + 1);

        dfs(node.right, result, level + 1);

    }

}

一刷

100.00 %
一刷
//
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root != null) {
            helper(root, result, 0);
        }
        return result;
    }
    private void helper(TreeNode node, List<Integer> result, int level) {
        if (level >= result.size()) {
            result.add(node.val);
        }
        if (node.right != null) {
            helper(node.right, result, level + 1);
        }
        if (node.left != null) {
            helper(node.left, result, level + 1);
        }
    }
}

875. Koko Eating Bananas

二刷 05/2022

可以用Math.ceil()

Math.ceil((double) pile / middle)

Let n be the length of the input array piles and m be the maximum number of bananas in a single pile from piles.

Time complexity O(nlogm)

Space O(1)

Runtime: 26 ms, faster than 59.51% of Java online submissions for Koko Eating Bananas.

Memory Usage: 54.1 MB, less than 40.11% of Java online submissions for Koko Eating Bananas.

class Solution {

    public int minEatingSpeed(int[] piles, int h) {

        if (piles == null) {

            throw new IllegalArgumentException();

        }

        int start = 1, end = 1;

        for (int pile : piles) {

            end = Math.max(end, pile);

        }

        while (start + 1 < end) {

            int mid = start + (end - start) / 2;

            if (canFinish(piles, h, mid)) {

                end = mid;

            } else {

                start = mid + 1;

            }

        }

        if (canFinish(piles, h, start)) {

            return start;

        }

        return end;

    }

    private boolean canFinish(int[] piles, int h, int speed) {

        for (int pile : piles) {

            h -= (pile / speed + (pile % speed == 0 ? 0 : 1));

        }

        return h >= 0;

    }

}

一刷

69.22 %

class Solution {
    public int minEatingSpeed(int[] piles, int H) {
        int sum = 0;
        int max = Integer.MIN_VALUE;
        for (int pile : piles) {
            sum += pile;
            max = Math.max(max, pile);
        }
        int start = Math.max(1, sum / H);
        int end = max;
        // find the first speed that can finish
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (canFinish(mid, piles, H)) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }
    private boolean canFinish(int k, int[] piles, int H) {
        for (int pile : piles) {
            if (pile <= k) {
                H--;
            } else {
                H -= pile / k + (pile % k == 0 ? 0 : 1);
            }
            if (H < 0) break;
        }
        return H >= 0;
    }
}

87. Scramble String

[TODO] Optimization
二刷

9.60 %
class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1 == null && s2 == null) return true;
        if (s1 == null || s2 == null || s1.length() != s2.length()) return false;
        if (s1.equals(s2)) {
            return true;
        }
        int[] counter = new int[26];
        int len = s1.length();
        System.out.println(s1 + " " + s2);
        for (int i = 0; i < len; i++) {
            counter[s1.charAt(i) - 'a']++;
            counter[s2.charAt(i) - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (counter[i] != 0) return false;
        }
        for (int i = 1; i < len; i++) {
            if (isScramble(s1.substring(0, i), s2.substring(0, i))
                && isScramble(s1.substring(i), s2.substring(i))
                || isScramble(s1.substring(0, i), s2.substring(len - i))
                && isScramble(s1.substring(i), s2.substring(0, len - i))) {
                return true;
            }
        }
        return false;
    }
}

一刷
8.19 %
class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        if (s1.equals(s2)) {
            return true;
        }
        int length = s1.length();
        if (length == 1) {
            return false;
        }
        Map<Character, Integer> counter = new HashMap<>();
        for (int i = 0; i < s1.length(); i++) {
            counter.put(s1.charAt(i), counter.getOrDefault(s1.charAt(i), 0) + 1);
            counter.put(s2.charAt(i), counter.getOrDefault(s2.charAt(i), 0) - 1);
        }
        for(Integer count : counter.values()) {
            if (count != 0) {
                return false;
            }
        }
        //start mid    end = 4
        // 1     2  3
        // 1  2      3
        // [start, mid) [mid, end)
        // [start, start + end - mid) [start - mid + end, end)
        for (int mid = 1; mid < length; mid++) {
            boolean left1 = isScramble(s1.substring(0, mid), s2.substring(0, mid));
            boolean right1 = isScramble(s1.substring(mid, length), s2.substring(mid, length));
            boolean left2 = isScramble(s1.substring(0, mid), s2.substring(length - mid, length));
            boolean right2 = isScramble(s1.substring(mid, length), s2.substring(0, length - mid));
            if (left1 && right1 || left2 && right2) {
                return true;
            }
        }
        return false;
    }
}

329. Longest Increasing Path in a Matrix

看了答案，这个topological sort也可以做，但是感觉没这个必要？

二刷 07/2022

Version #1 DFS with Memorization

Time O(MN)

Space O(MN)

Runtime: 9 ms, faster than 95.05% of Java online submissions for Longest Increasing Path in a Matrix.

Memory Usage: 42.3 MB, less than 97.52% of Java online submissions for Longest Increasing Path in a Matrix.

class Solution {

    public int longestIncreasingPath(int[][] matrix) {

        int rows = matrix.length;

        int cols = matrix[0].length;

        Integer[][] dp = new Integer[rows][cols];

        int max = 0;

        for (int y = 0; y < rows; y++) {

            for (int x = 0; x < cols; x++) {

                max = Math.max(max, dfs(matrix, dp, y, x));

            }

        }

        return max;

    }

    

    private int[] dx = new int[]{1, 0, -1, 0};

    private int[] dy = new int[]{0, -1, 0, 1};

    

    private int dfs(int[][] matrix, Integer[][] dp, int y, int x) {

        if (dp[y][x] != null) {

            return dp[y][x];

        }

        int max = 0;

        for (int i = 0; i < 4; i++) {

            int nx = x + dx[i];

            int ny = y + dy[i];

            if (ny < 0 || nx < 0 || ny >= matrix.length || nx >= matrix[0].length) {

                continue;

            }

            if (matrix[ny][nx] > matrix[y][x]) {

                max = Math.max(max, dfs(matrix, dp, ny, nx));

            }

        }

        dp[y][x] = 1 + max;

        return dp[y][x];

    }

}

一刷

DFS + mem
Time O(mn)
Space O(mn)

82.62 %
class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        // dp[x][y] -> longest increasing path started from position x,y
        // If its neighbor is larger than curr, get its value and +1
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }
        int rows = matrix.length;
        int cols = matrix[0].length;
        Integer[][] mem = new Integer[rows][cols];
        int[] max = new int[1];
        for (int x = 0; x < rows; x++) {
            for (int y = 0; y < cols; y++) {
                helper(matrix, x, y, mem, max);
            }
        }
        return max[0];
    }
    private int[] dx = {1, 0, -1, 0};
    private int[] dy = {0, -1, 0, 1};
    private int helper(int[][] matrix, int x, int y, Integer[][] mem, int[] max) {
        if (mem[x][y] != null) {
            return mem[x][y];
        }
        int currMax = 1;
        for (int i = 0; i < 4; i++) {
            int currX = x + dx[i];
            int currY = y + dy[i];
            if (currX >= 0 && currX < matrix.length && currY >= 0 && currY < matrix[0].length
                && matrix[currX][currY] > matrix[x][y]) {
                currMax = Math.max(currMax, 1 + helper(matrix, currX, currY, mem, max));
            }
        }
        mem[x][y] = currMax;
        max[0] = Math.max(max[0], currMax);
        return currMax;
    }
}

78. Subsets

三刷 06/2022

Version #2 Bit Manipulation

Time O(N*2^N)

Space O(1)

Runtime: 1 ms, faster than 87.63% of Java online submissions for Subsets.

Memory Usage: 42.4 MB, less than 90.42% of Java online submissions for Subsets.

class Solution {

    public List<List<Integer>> subsets(int[] nums) {

        // Given N numbers, the combination of those numbers could be represented by number 0-2^N-1

        int N = nums.length;

        List<List<Integer>> result = new ArrayList<>();

        // e.g. [1] -> [] [1] -> N=1

        for (int mask = 0; mask < (1 << N); mask++) {

            // Given a mask, if the bit is 1, then we should add the number

            List<Integer> sub = new ArrayList<>();

            for (int i = 0; i < N; i++) {

                if (((mask >> i) & 1) == 1) {

                    sub.add(nums[i]);

                }

            }

            result.add(sub);

        }

        return result;

    }

}

二刷 05/2022

Version #1 DFS Recursion - iterate over each number on every layer

Time O(N * 2^N) -> We need O(N) time to copy the result to a new list * 2^N subsets

Space O(N)

Runtime: 2 ms, faster than 29.41% of Java online submissions for Subsets.

Memory Usage: 43.9 MB, less than 7.12% of Java online submissions for Subsets.

class Solution {

    public List<List<Integer>> subsets(int[] nums) {

        List<List<Integer>> result = new ArrayList<>();

        if (nums == null) {

            return result;

        }

        dfs(nums, 0, new ArrayList<>(), result);

        return result;

    }

    private void dfs(int[] nums, int startIndex, List<Integer> path, List<List<Integer>> result) {

        result.add(new ArrayList<>(path));

        for (int i = startIndex; i < nums.length; i++) {

            path.add(nums[i]);

            dfs(nums, i + 1, path, result);

            path.remove(path.size() - 1);

        }

    }

}

Version #2 DFS - choose adding or not adding each element on every layer

Runtime: 1 ms, faster than 80.34% of Java online submissions for Subsets.

Memory Usage: 43.2 MB, less than 53.28% of Java online submissions for Subsets.

class Solution {

    public List<List<Integer>> subsets(int[] nums) {

        List<List<Integer>> result = new ArrayList<>();

        if (nums == null) {

            return result;

        }

        dfs(nums, 0, new ArrayList<>(), result);

        return result;

    }

    

    private void dfs(int[] nums, int index, List<Integer> path, List<List<Integer>> result) {

        if (index == nums.length) {

            result.add(new ArrayList<>(path));

            return;

        }

        // Two possible solutions

        // 1 not choose current index

        dfs(nums, index + 1, path, result);

        // 2 choose current index

        path.add(nums[index]);

        dfs(nums, index + 1, path, result);

        path.remove(path.size() - 1);

    }

}

Version #3 Bit Manipulation

Runtime: 1 ms, faster than 80.34% of Java online submissions for Subsets.

Memory Usage: 43.4 MB, less than 38.72% of Java online submissions for Subsets.

class Solution {

    public List<List<Integer>> subsets(int[] nums) {

        // For each index of nums, we can choose either put it in the set or not

        // 0 -> 0 0 0 -> []

        // 1 -> 0 0 1 -> [1]

        // 2 -> 0 1 0 -> [2]

        // .    . . .     .

        // 2^nums.length - 1

        List<List<Integer>> result = new ArrayList<>();

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

            return result;

        }

        for (int i = 0; i < 1 << nums.length; i++) {

            List<Integer> subset = new ArrayList<>();

            int bit = 0;

            while (i >> bit > 0) {

                if (((i >> bit) & 1) == 1) {

                    subset.add(nums[bit]);

                }

                bit++;

            }

            result.add(subset);

        }

        return result;

    }

}           

一刷

Version #3 Bit Manipulation
For a given length of bits, we can use 0 to represent not shown and 1 to represent shown
So a binary number can represent 1 result
Iterate through all possible binary numbers, add the digit when we see 1

100.00 %
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
       
        for (int i = 0; i < (1 << nums.length); i++) {
            List<Integer> sub = new ArrayList<>();
            int bit = 0;
            while ((i >> bit) > 0) {
                if (((i >> bit) & 1) == 1) {
                    sub.add(nums[bit]);
                }
                bit++;
            }
            result.add(sub);
        }
        return result;
    }
}



Version #1 Iterate through next elements, choose which one to add
Always adding to result list at every level

100.00 %
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums == null || nums.length == 0) return result;
        helper(nums, 0, new ArrayList<>(), result);
        return result;
    }
    private void helper(int[] nums, int index, List<Integer> path, List<List<Integer>> result) {
        result.add(new ArrayList<>(path));
        for (int i = index; i < nums.length; i++) {
            path.add(nums[i]);
            helper(nums, i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
}

Version #2  Look at current index at each level, decide if we add current element or not
Results are added at the last level

310. Minimum Height Trees[TODO]

Version #2 DP[TODO]

三刷 07/2022

Version #1 BFS

Time O(N)

Space O(N)

Runtime: 20 ms, faster than 96.83% of Java online submissions for Minimum Height Trees.

Memory Usage: 69.1 MB, less than 81.98% of Java online submissions for Minimum Height Trees.

class Solution {

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {

        int[] count = new int[n];

        List<Integer>[] graph = new ArrayList[n];

        for (int i = 0; i < n; i++) {

            graph[i] = new ArrayList<>();

        }

        for (int[] edge : edges) {

            int a = edge[0];

            int b = edge[1];

            count[a]++;

            count[b]++;

            graph[a].add(b);

            graph[b].add(a);

        }

        int visited = 0;

        Queue<Integer> que = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {

            if (count[i] <= 1) {

                que.offer(i);

                visited++;

            }

        }

        // 3 [[0,1],[0,2]]

        //  1 - 0 - 2

        while (!que.isEmpty()) {

            int size = que.size();

            if (visited == n) {

                return new ArrayList<>(que);

            }

            while (size-- > 0) {

                int curr = que.poll();

                for (Integer next : graph[curr]) {

                    if (count[next] <= 1) {

                        continue;

                    }

                    count[next]--;

                    if (count[next] == 1) {

                        que.offer(next);

                        visited++;

                    }

                }

            }

        }

        return new ArrayList<>();

    }

}

Version #1 BFS

一刷
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<Integer> result = new ArrayList<>();
if (n < 0) {
return result;
}
if (n == 1) {
result.add(0);
return result;
}
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
Queue<Integer> que = new LinkedList<>();
for (int i = 0; i < n; i++) {
if (graph.get(i).size() == 1) {
que.offer(i);
}
}

while (n > 2) {
int size = que.size();
while (size-- > 0) {
Integer curr = que.poll();
for (Integer next : graph.get(curr)) {
graph.get(next).remove(curr);
if (graph.get(next).size() == 1) {
que.offer(next);
}
}
}
}
while (!que.isEmpty()) {
result.add(que.poll());
}
return result;
}




O(n)

For a tree we can do some thing similar. We start from every end, by end we mean vertex of degree 1 (aka leaves). We let the pointers move the same speed. When two pointers meet, we keep only one of them, until the last two pointers meet or one step away we then find the roots.

84.37 %

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return new ArrayList<Integer>(Arrays.asList(0));
        // build the graph represented by List<Set<Integer>> list of neighbors for each node
        List<Set<Integer>> neighborList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            neighborList.add(new HashSet<>());
        }
        // O(#edges)
        for (int[] edge : edges) {
            neighborList.get(edge[0]).add(edge[1]);
            neighborList.get(edge[1]).add(edge[0]);
        }
     
        Queue<Integer> que = new LinkedList<>();
        // Add leaves to que
        for(int i = 0; i < n; i++) {
            if (neighborList.get(i).size() == 1) {
                que.offer(i);
            }
        }
        while (n > 2) {
            int size = que.size();
            n -= size;
            while (size-- > 0) {
                int curr = que.poll();
                for (int neighbor : neighborList.get(curr)) {
                    Set<Integer> set = neighborList.get(neighbor);
                    set.remove(curr);
                    if (set.size() == 1) {
                        que.offer(neighbor);
                    }
                }
            }
        }
        return new ArrayList<Integer>(que);
    }
}

二刷BFS

“Basically, the idea is to eat up all the leaves at the same time, until one/two leaves are left.”

Runtime: 16 ms, faster than 68.64% of Java online submissions for Minimum Height Trees.

Memory Usage: 43.6 MB, less than 48.82% of Java online submissions for Minimum Height Trees.

class Solution {

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {

        if (n == 1) {

            return Collections.singletonList(0);

        }

        // leaf, there's only 1 edge connected to it

        // key-node, value-count of edges that touch the node

        List<Set<Integer>> graph = new ArrayList<>();

        for (int i = 0; i < n; i++) {

            graph.add(new HashSet<>());

        }

        for (int[] edge : edges) {

            graph.get(edge[0]).add(edge[1]);

            graph.get(edge[1]).add(edge[0]);

        }

        Queue<Integer> que = new LinkedList<>();

        List<Integer> leaves = new ArrayList<>();

        for (int i = 0; i < graph.size(); i++) {

            if (graph.get(i).size() == 1) {

                que.offer(i);

                leaves.add(i);

            }

        }

        while (n > 2) {

            int size = que.size();

            n -= size;

            List<Integer> newLeaves = new ArrayList<>();

            while (size-- > 0) {

                int curr = que.poll();

                for (Integer neighbor : graph.get(curr)) {

                    Set<Integer> nSet = graph.get(neighbor);

                    nSet.remove(curr);

                    if (nSet.size() == 1) {

                        que.offer(neighbor);

                        newLeaves.add(neighbor);

                    }

                }

            }

            leaves = newLeaves;

        }

        return leaves;

    }

}

317. Shortest Distance from All Buildings

三刷 05/2022

Version #1 Matrix BFS

写了两个bug

一个是landInfos 的hash是next position的hash不应该用current position的hash

另外一个是(0, 0) 的hash value是0，恰好等于matrix的default value，导致(0, 0)点没法被BFS，所以要初始化成-1

Time O(M^2N^2)

Space O(MN)

Runtime: 674 ms, faster than 26.68% of Java online submissions for Shortest Distance from All Buildings.

Memory Usage: 145 MB, less than 15.34% of Java online submissions for Shortest Distance from All Buildings.

class Solution {

    class LandInfo {

        int buildingCount = 0;

        int buildingDistance = 0;

        public LandInfo() {}

    }

    private static int LAND = 0;

    private static int BUILDING = 1;

    private static int OBSTACLE = 2;

    public int shortestDistance(int[][] grid) {

        // Calculate all the building's distance to all land

        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {

            return -1;

        }

        int rows = grid.length;

        int cols = grid[0].length;

        // key-y*cols+x, value-LandInfo

        Map<Integer, LandInfo> landInfos = new HashMap<>();

        int[][] visited = new int[rows][cols];

       for (int y = 0; y < rows; y++) {

            for (int x = 0; x < cols; x++) {

                visited[y][x] = -1;

            }

       }

        int buildingCnt = 0;

        for (int y = 0; y < rows; y++) {

            for (int x = 0; x < cols; x++) {

                if (grid[y][x] != BUILDING) {

                    continue;

                }

                buildingCnt++;

                bfs(grid, visited, x, y, landInfos);

            }

        }

        // System.out.println(buildingCnt);

        Integer res = Integer.MAX_VALUE;

        for (LandInfo info : landInfos.values()) {

            // System.out.printf("buildingCnt %d, buildingDist %d\n", info.buildingCount, info.buildingDistance);

            if (info.buildingCount == buildingCnt) {

                res = Math.min(res, info.buildingDistance);

            }

        }

        return res == Integer.MAX_VALUE ? -1 : res;

    }

    private int[] dx = new int[]{1, 0, -1, 0};

    private int[] dy = new int[]{0, -1, 0, 1};

    private void bfs(int[][] grid, int[][] visited, int x, int y, Map<Integer, LandInfo> landInfos) {

        int rows = grid.length, cols = grid[0].length;

        // System.out.printf("(%d, %d)\n", x, y);

        int hash = y * cols + x;

        Queue<int[]> que = new ArrayDeque<>();

        que.offer(new int[]{x, y});

        visited[y][x] = hash;

        int dist = 0;

        while (!que.isEmpty()) {

            int size = que.size();

            dist++;

            while (size-- > 0) {

                int[] curr = que.poll();

                for (int i = 0; i < 4; i++) {

                    int nx = curr[0] + dx[i];

                    int ny = curr[1] + dy[i];

                    if (nx < 0 || nx >= cols || ny < 0 || ny >= rows) {

                        continue;

                    }

                    if (visited[ny][nx] != hash && grid[ny][nx] == LAND) {

                        // System.out.printf("hash=%d\n", hash);

                        int nHash = ny * cols + nx;

                        LandInfo info = landInfos.getOrDefault(nHash, new LandInfo());

                        info.buildingCount++;

                        info.buildingDistance += dist;

                        landInfos.put(nHash, info);

                        visited[ny][nx] = hash;

                        que.offer(new int[]{nx, ny});

                    }

                }

            }

        }

    }

}

一刷
// Start from a building, try to find its shortest path to every empty land on the grid
        // Accumulate the shortest path of all buildings
        // If an empty land can be reached by all buildings and its accumulated shortest path is minimum, return the value

22.15 %

class Solution {
    private final int LAND = 0;
    private final int BUILDING = 1;
    private final int OBSTACLE = 2;
 
    public int shortestDistance(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
            return -1;
        }
        int minPath = Integer.MAX_VALUE;
        int rows = grid.length;
        int cols = grid[0].length;
        int[][] sp = new int[rows][cols];
        // Count how many times it is visited
        int[][] visitedCount = new int[rows][cols];
        // Iterate
        int buildingCount = 0;
        for(int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == BUILDING) {
                    shortestDistanceHelper(grid, sp, visitedCount, new int[]{i, j});
                    buildingCount++;
                }
            }
        }
     
        for(int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == LAND && visitedCount[i][j] == buildingCount) {
                    minPath = Math.min(minPath, sp[i][j]);
                }
            }
        }
     
        return minPath == Integer.MAX_VALUE ? -1 : minPath;
     
    }
    private int[] dx = new int[]{1, 0, -1, 0};
    private int[] dy = new int[]{0, -1, 0, 1};
 
    // x -> coordinate[0], y -> coordinate[1]
    private void shortestDistanceHelper(int[][] grid, int[][] sp, int[][] visitedCount, int[] coordinate) {
        int cols = grid[0].length;
        Set<Integer> visited = new HashSet<>();
        Queue<int[]> que = new LinkedList<>();
        // Mark start point as visited and add it into queue
        que.offer(coordinate);
        visited.add(coordinate[0] * cols + coordinate[1]);
        int level = 0;
        while (!que.isEmpty()) {
            int size = que.size();
            level++;
            while (size-- > 0) {
                int[] curr = que.poll();
                // Tries to go to 4 directions
                for (int i = 0; i < 4; i++) {
                    int x = curr[0] + dx[i];
                    int y = curr[1] + dy[i];
                    if(isValid(grid, visited, x, y)) {
                        que.offer(new int[]{x,  y});
                        visited.add(x * cols + y);
                        visitedCount[x][y]++;
                        sp[x][y] += level;
                    }
                }
            }
        }
    }
    private boolean isValid(int[][] grid, Set<Integer> visited, int x, int y) {
        return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length
            && grid[x][y] == LAND
            && !visited.contains(x * grid[0].length + y);
    }
}

二刷

果然hard题还是有陷阱的

譬如corner case

0 2 1

1 0 2

0 1 0

这里的右上角building被block住了，所以无解

所以需要用一个全局的visited count来保证所有的empty space都是可以被所有的building reach的

Runtime: 28 ms, faster than 70.18% of Java online submissions for Shortest Distance from All Buildings.

Memory Usage: 38.9 MB, less than 74.09% of Java online submissions for Shortest Distance from All Buildings.

class Solution {

    private int[] dx = new int[]{1, 0, -1, 0};

    private int[] dy = new int[]{0, 1, 0, -1};

    public int shortestDistance(int[][] grid) {

        int buildingCount = 0;

        int[][] visitedCount = new int[grid.length][grid[0].length];

        for (int x = 0; x < grid.length; x++) {

            for (int y = 0; y < grid[0].length; y++) {

                if (grid[x][y] == 1) {

                    buildingCount++;

                    bfs(grid, visitedCount, x, y);

                }

            }

        }

        int sp = Integer.MIN_VALUE;

        for (int x = 0; x < grid.length; x++) {

            for (int y = 0; y < grid[0].length; y++) {

                // System.out.printf("x: %d, y: %d, grid: %d\n", x, y, grid[x][y]);

                if (grid[x][y] < 0 && visitedCount[x][y] == buildingCount) {

                    sp = Math.max(sp, grid[x][y]);

                }

            }

        }

        if (sp != Integer.MIN_VALUE) {

            return Math.abs(sp);

        }

        return -1;

    }

    

    private void bfs(int[][] grid, int[][] visitedCount, int startX, int startY) {

        boolean[][] visited = new boolean[grid.length][grid[0].length];

        Queue<int[]> que = new LinkedList<>();

        visited[startX][startY] = true;

        que.offer(new int[]{startX, startY});

        int step = 0;

        while (!que.isEmpty()) {

            step++;

            int size = que.size();

            while (size-- > 0) {

                int[] curr = que.poll();

                for (int i = 0; i < 4; i++) {

                    int x = curr[0] + dx[i];

                    int y = curr[1] + dy[i];

                    if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] <= 0 && !visited[x][y]) {

                        visited[x][y] = true;

                        grid[x][y] = grid[x][y] - step;

                        que.offer(new int[]{x, y});

                        visitedCount[x][y]++;

                    }

                }

            }       

        } 

    }

}

430. Flatten a Multilevel Doubly Linked List

Version #1 DFS
96.57 %
class Solution {
    public Node flatten(Node head) {
        if (head != null) {
            flattenHelper(head);
        }
       
        return head;
    }
   
    // return last node after flatten
    private Node flattenHelper(Node node) {
        if (node.child == null && node.next == null) return node;
        Node childNode = node.child;
        node.child = null;
        Node nextNode = node.next;
        Node childTail = null;
        Node nextTail = null;
        if (childNode != null) {
            childTail = flattenHelper(childNode);
            node.next = childNode;
            childNode.prev = node;
        }
       
        if (nextNode != null) {
            nextTail = flattenHelper(nextNode);
            if (childTail != null) {
                childTail.next = nextNode;
                nextNode.prev = childTail;
            }
        }
        if (nextTail != null) return nextTail;
        else return childTail;
    }
}

Version #2 Stack

75.11 %
class Solution {
    public Node flatten(Node head) {
        Stack<Node> stack = new Stack<>();
        if (head != null) {
            stack.push(head);
        }
        Node curr = null;
        Node prev = null;
        while (!stack.isEmpty()) {
            curr = stack.pop();
            if (curr.next != null) {
                stack.push(curr.next);
            }
            if (curr.child != null) {
                stack.push(curr.child);
            }
            if (curr.prev != prev && prev != null) {
                prev.next = curr;
                curr.prev = prev;
            }
            prev = curr;
            curr.child = null;
        }
        return head;
    }
}