23-05-31 刷题，两道Mid题目

Mid - 1020. 飞地的数量 - 力扣（LeetCode） - BFS - grid

分析：

• 飞地，就是被敌人（水）包围的陆地。本题中是指不与任何border相联的1组成，只考虑四个方向。
• 思路：换种角度，从border的1出发，总共有4个border，利用BFS遍历，初始队列中包含四个border中1的位置，然后将他们标记成其他值（例如 2），这样省掉了一个visit数组，但是会修改输入数组，如果不允许，那么clone一遍即可。
• 有了思路之后，代码很简单，就是写起来有点长而已。
• 复杂度分析：时间上，每个点最多进入queue一次，出队列一次，因此时间复杂度是O(nm); 空间是 O(nm) 队列中最大的长度是nxm

class Solution {
    public int numEnclaves(int[][] A) {
        int n = A.length, m = A[0].length;
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (A[i][0] == 1) {
                queue.offer(new int[] {i, 0});
                A[i][0] = 2;
            }
            if (A[i][m - 1] == 1) {
                queue.offer(new int[] {i, m - 1});
                A[i][m - 1] = 2;
            }
        }
        for (int j = 0; j < m; j++) {
            if (A[0][j] == 1) {
                queue.offer(new int[] {0, j});
                A[0][j] = 2;
            }
            if (A[n - 1][j] == 1) {
                queue.offer(new int[] {n - 1, j});
                A[n - 1][j] = 2;
            }
        }

        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        // do BFS from each border islands
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0], y = cur[1];
            // check each dir
            for (int[] dir : dirs) {
                int nx = dir[0] + x, ny = dir[1] + y;
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && A[nx][ny] == 1) {
                    A[nx][ny] = 2;
                    queue.offer(new int[] {nx, ny});
                }
            }
        }

        // count remaining 1's
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (A[i][j] == 1) {
                    ans++;
                }
            }
        }
        return ans;
    }
}

Mid - 669. 修剪二叉搜索树 - 力扣（LeetCode） 好题-DFS有返回值

分析：

• 题目的意思，画个图就好理解了
• 思路：想象成递归函数，子问题解决了，怎么拼接成父问题。如果当前root.val 在[low, high]范围内，那么我们只需要trim左右两个子树即可，返回trim之后的root。然后分析仪下，如果root.val在范围之外怎么办，自然是一边不需要了，返回另外一边可能有节点的子树即可。
• 复杂度分析：时间O(n), 空间O(n) 当二叉树蜕化成单支的链表时，栈的最大调用深度是n.

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) { // time: O(n), space: O(n)
        if (root == null) return null;
        if (root.val < low) {
            return trimBST(root.right, low, high);
        }
        if (root.val > high) {
            return trimBST(root.left, low, high);
        }
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}