明年本科毕业刷题贴

目前题量81. 今天9题 two pointer. 之前刷Graph刷到有点没动力，先刷点轻松的。

可以很强

DSU（unionFind）class implementation:
    private class DSU{
        private int [] parent;
        public DSU(int n){
            parent = new int[n];
            for(int i = 0; i < n ; i++ ){
                parent[i] = i;
            }
        }
        
        public void union(int x, int y){
            int rootX = find(x);
            int rootY = find(y);
            if(rootX == rootY) return;
            parent[rootX] = rootY;
        }
        
        public int find(int x){
            if(parent[x] == x) return x;
            parent[x] = find(parent[x]);
            return parent[x];
        }
    }
根据问题可以加入 weight 和 size 进行优化使用。

微信用户_b99d1cc 发表于 2022-12-18 05:58
332. Reconstruct Itinerary
HierHolzer
条件： 必须存在解

1192. Critical Connections in a Network
DFS解法。
Critical Connections定义: 去掉当前边使图形成为两个不同的图形。
思路：
对于当前节点用DFS，记录当前步数和最低可访问的步数
初始化当前最低步数为当前步数
1.如果已经访问过当前nei节点，low[cur] = min(low[cur],disc[nei])
2.如果nei没被访问，dfs(nei)   low[cur] = min(low[nei],low[cur])
2-1 判断 low[nei] > disc[cur] if true， add to result
原理: 把low[nei]的值传递low[parent], 如果这个值小于当前步数，说明存在环，这种情况下去掉当前的边不会分割图形。 如果当前的low[nei] > disc[cur] 则说明当前边是critical。
Time:  O(V + E)
Space: O(V + E)

10/13   LC:15,16, 977.  2 Medium 1 Easy

补充内容 (2022-10-14 10:11 +8:00):
992  Hard+1

补充内容 (2022-10-14 10:42 +8:00):
DP 70 Easy +1

复习Tree Traversal 94:
基本套路
public void helper(TreeNode root){
   if(root == null) return;
  //ans.add(root.val)(preorder)
  helper(root.left);
  //ans.add(root.val); (Inorder)
  helper(root.right);
  //ans.add(root.val)(prosorder)
}

开始新topic   Search (BFS 17 Medium
复习94 144 145 (pre post inorder) tree traversal Easy  // 429 N-Array inorder Medium.

BackTracking 39 40 77 Medium. DFS
类似于树的做法，用target or length size 作为返回标准，每层update深度或者target。同层需要push back last element of list。
注意：需考虑题目duplicate的要求，求sum对当前层target值和加入的值进行对比，如果大于所需求，直接结束当前循环。

补充内容 (2022-10-15 10:58 +8:00):
78. Subsets Midum

补充内容 (2022-10-15 11:28 +8:00):
90 Subsets II
216 Combination Sum III

46 47 784 permutations. 注意duplicate判断条件。
复习 deepest sum tree traversal。  4 medium

补充内容 (2022-10-16 04:36 +8:00):
100 ez same tree
943 Hard(hold for DP) BackTracking超时

补充内容 (2022-10-16 04:42 +8:00):
复习 tree symmetric 101 ez

996 permutations Hard (须复习。swap解法没弄懂
14. Longest Common Prefix Easy
993. Cousins in Binary Tree Easy
终于到100了。

Permutaion和Combination问题主要注重于duplicate的判断和要求。模板都差不多。用Set储存Visited index不能用于数字set，否则会出现问题。

今天补课休息一天