23-05-23 刷题

练习刷题思路

722. 删除注释 - 力扣（LeetCode） 【Mid】

思路：

• 不难，但是细节比较多。要理清楚有点麻烦。【题目不好】

class Solution {
    public List<String> removeComments(String[] source) {
        List<String> ans = new ArrayList<>();
        boolean inBlock = false;
        StringBuilder sb = null;
        for(String line : source) {
            char[] A = line.toCharArray();
            if (!inBlock) {
                sb = new StringBuilder();
            }
            for(int i = 0, n = A.length; i < n; i++) {
                if (!inBlock && A[i] == '/' && i + 1 < n && A[i + 1] == '*') {
                    inBlock = true;
                    i++;
                } else if (inBlock && A[i] == '*' && i + 1 < n && A[i + 1] == '/') {
                    inBlock = false;
                    i++;
                } else if (!inBlock && A[i] == '/' && i + 1 < n && A[i + 1] == '/') {
                    break;
                } else if (!inBlock) {
                    sb.append(A[i]);
                }
            }
            if (!inBlock && !sb.isEmpty()) {
                ans.add(sb.toString());
            }
        }
        return ans;
    }
}

1786. 从第一个节点出发到最后一个节点的受限路径数 - 力扣（LeetCode） 【Mid】

思路：

• build graph (use adjList) + dijstrala (with priority queue optimize) + DP(BFS)
• 跑一遍堆优化Dijkstra，求出所有点到n的最短距离
  动态规划，定义dp[i] 表示从 1 -> i 受限制的路径数，由于动态规划要求无后效性，如果dist[i] > dist[j],则dp[j] 一定可以从dp[i] 转移过来，dp[i]一定不能从dp[j]转移过来，因此需要对所有节点按dist从大到小(或者从小到大)排序
  对于某个结点 i，则和它相连的点 j，如果dist[j] < dist[i], 则i->j可行，因此，dp[j] += dp[i]

class Solution {
    public int countRestrictedPaths(int n, int[][] edges) {
        // 1. construct graph, use adjList
        List<Edge>[] graph = new List[n];
        for(int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for(int[] edge: edges) {
            int from = edge[0] - 1, to = edge[1] - 1, weight = edge[2];
            graph[from].add(new Edge(from, to, weight));
            graph[to].add(new Edge(to, from, weight));
        }

        // 2. dijstrala
        int[] dist = new int[n];
        dijstrala(graph, dist, n - 1);

        // 3. BFS+DP to find all the path        
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> Integer.compare(dist[b], dist[a]));
        queue.offer(0);
        boolean[] visited = new boolean[n];
        int[] dp = new int[n];
        dp[0] = 1;
        visited[0] = true; // 这个题目，只能进队列时，标记访问过
        
        final int MODE_MAX = 1000000007;
        while (!queue.isEmpty()) {            
            int cur = queue.poll();
            for (Edge edge : graph[cur]) {
                int to = edge.to;
                if (dist[to] < dist[cur]) {
                    dp[to] = (dp[to] + dp[cur]) % MODE_MAX;
                    if (!visited[to]) {
                        queue.offer(to);
                        visited[to] = true;
                    }
                }
            }
        }
        return dp[n - 1];
    } 

    // time: O(VlogE)
    void dijstrala(List<Edge>[] graph, int[] dist, int v) {
        int n = dist.length;
        boolean[] visited = new boolean[dist.length];
        final int INF = Integer.MAX_VALUE;
        Arrays.fill(dist, INF);
        dist[v] = 0;
        // store the pair: (vertext, dist)
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));

        for(Edge edge : graph[v]) {
            dist[edge.to] = edge.weight;
            minHeap.offer(new int[] {edge.to, edge.weight});
        }
        visited[v] = true;

        while (!minHeap.isEmpty()) {
            // find one from nearest dist
            int u = minHeap.poll()[0];
            if (visited[u]) continue;
            
            visited[u] = true;
            // relax the shortest path after adding vertex: minIdx
            for(Edge edge : graph[u]) {
                int to = edge.to;
                if (!visited[to] && dist[to] > dist[u] + edge.weight) {
                    dist[to] = dist[u] + edge.weight;
                    minHeap.offer(new int[] {to, dist[to]});
                }
            }
        }
    }

    class Edge {
        int from, to, weight;
        public Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }
}

863. 二叉树中所有距离为 K 的结点 - 力扣（LeetCode） 【Mid】

思路：

• 很好的题，用两次DFS来做，不容易出错，思路也很清楚。第一遍DFS找每个节点的parent，保存到hash表里。
• 第二遍DFS是从target节点开始，从三个方向去遍历，left, right, parent. 需要注意避免走回头路，所以在dfs的参数中要标记遍历到当前节点时，是从哪一个方向过来的，然后不走那个方向即可。
• 复杂度分析：
  • 时间：两边DFS，O(n)。 空间：hash表保存parent，O(n).

class Solution {
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        ans = new ArrayList<>();
        preOrder(root);
        dfsFindDistanceK(target, k, 0, null);
        return ans;
    }

    void dfsFindDistanceK(TreeNode node, int k, int depth, TreeNode from) {
        if (node == null) return;
        if (depth == k) {
            ans.add(node.val);
            return;
        }
        if (node.left != from) {
            dfsFindDistanceK(node.left, k, depth + 1, node);
        }
        if (node.right != from) {
            dfsFindDistanceK(node.right, k, depth + 1, node);
        }
        TreeNode parent = parentMap.get(node);
        if (parent != null && parent != from) {
            dfsFindDistanceK(parent, k, depth + 1, node);
        }
    }

    void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            parentMap.put(root.left, root);            
        }
        if (root.right != null) {
            parentMap.put(root.right, root);
        }
        preOrder(root.left);
        preOrder(root.right);
    }


    Map<TreeNode, TreeNode> parentMap = new HashMap<>();    
    List<Integer> ans;
}

2163. 删除元素后和的最小差值 - 力扣（LeetCode） 【Hard】

分析：

• 也挺好的一个题目，hard，看不懂。思考了几分钟后，直接看了中文官方题解的思路分析，然后自己写代码实现
• 优先队列（maxHeap, minHeap）可以用来求n个最大的元素，n个最小的元素。然后，枚举分割点，统计答案。
• 复杂度分析：
  • 时间：优先队列，最多总共操作n/3 * 2次，每次log n，遍历是 O(n). 总的时间是O(n)。
  • 空间：优先队列，以及数组，O(n)

class Solution {
    public long minimumDifference(int[] A) {
        int n = A.length;
        int m = n / 3;
        long[] leftMinSum = new long[n];
        long[] rightMaxSum = new long[n];
        // 1. calculate leftSum (n elements), rightMaxSum(n elem)
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
        long curSum = 0;
        for(int i = 0; i < 2 * m; i++) {
            curSum += A[i];
            maxHeap.offer(A[i]);
            if (i >= m) {
                curSum -= maxHeap.poll();
            }
            if (i >= m - 1) {
                leftMinSum[i] = curSum;
            }
        }
        curSum = 0;
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for(int i = n - 1; i >= m; i--) {
            curSum += A[i];
            minHeap.offer(A[i]);
            if (i <= n - m - 1) {
                curSum -= minHeap.poll();
            }
            if (i <= n - m) {
                rightMaxSum[i] = curSum;
            }
        }

        // 2. iterate and calc ans
        long ans = Long.MAX_VALUE;
        for (int i = m - 1; i < n - m; i++) {
            ans = Math.min(ans, leftMinSum[i] - rightMaxSum[i + 1]);
        }

        return ans;
    }
}

https://leetcode.cn/problems/minimum-difference-in-sums-after-removal-of-elements/solution/qian-zhui-zui-xiao-he-hou-zhui-zui-da-he-yz3d/ 【这个写法挺好的，有空学习一下】