Bin's Tech Diary

Union Find Union Find Union Find 动态的计算联通块问题 结构 global variables constructor() find(int x) union(int a, int b) 模板 (Map) global variables private Map<Integer, Integer> f; constructor() UnionFind(int n) { this.f = new HashMap<Integer, Integer>(); for (int i = 0; i < n; i++) { f.put(i, i); } } find(int x) int find(int x) { int root = x; // 找到“根” while (f.get(root) != root) { root = f.get(root); } // 拆“整”为“零”，把每个元素直接接到“根”上 while (root != x) { int nx = f.get(x); f.put(x, root); x = nx; } return root; } union(int a, int b) void union(int a, int b) { int rA = find(a); int rB = find(b); if (rA != rB) { f.put(rB, rA); } } 例题 Friend Circles 根据模板添加额外的全局变量，比如此题需要count，在每次合并的时候 count-- ，在初始化的时候或者写一个 setter 和 getter 去给 count 赋值和取值 public class Solution { class UnionFind { private int count; private Map...

Tree的经典题 Tree的经典题 找第k小 Kth Smallest Element in a BST 在树上就不需要使用Heap了，因为inorder traversal本身就是一个从小到大的序列，这里我们有几种方法 1. Recursive traversal 创建全局变量，记录traverse到哪儿了，当走到k的时候把值赋给result即可 时间复杂度 O(n) public class Solution { //设置全局变量 private int count = 0; private int result = 0; public int kthSmallest(TreeNode root, int k) { traversal(root, k); return result; } private void traversal(TreeNode root, int k) { if (root == null) { return; } traversal(root.left, k); //如果count等于k的时候才把结果赋给result //注意count从0开始，所以count先++之后再判断 count++; if (count == k) { result = root.val; } traversal(root.right, k); } } 2. Quick Select on Tree 首先要traverse计算每个点到它的时候子树总共有多少个点，然后用quick select，如果大于k，直接去左边找，如果小于k，判断当左边的个数加1正好等于k，那么这个k就落在root上，如果加1之后还小于k那么就要去向右边找了，因为此时左边没有第k个点。 时间复杂度 O(n) 最好最坏都是 public class Solution { public int kthSmal...