刷题记录

class UnionFind { int [] father; public UnionFind ( int n) { father = new int [n]; for ( int i = 0 ; i < n; i ++ ) { father[i] = i; } } public int find ( int n) { if (father[n] != n) father[n] = find(father[n]); return father[n]; } public void union ( int a, int b) { father[find(a)] = find(b); } public boolean query ( int a, int b){ return find(a) == find(b); } } 1. 融合不同的component Number of Islands 2. 判断环   Graph Valid Tree   Redundant Connection Number of Connected Components in an Undirected Graph 3. 判断是否在一个group里面 Sentence Similarity II Accounts Merge Union find实现的关键是找father

Problem: Given an integer array, find a subarray where the sum of numbers is  zero . Your code should return the index of the first number and the index of the last number.  Notice There is at least one subarray that it's sum equals to zero. 2/23/2018 update It has been explained pretty well below. But still need to note that, the prefix sum stores in hashtable instead of array. Initial the hashtable with (0, -1) is important. The case[1, -1] would not pass without (0, -1) pushed. Since it can not find the index before 0. Solution: public class Solution { /** * @param nums: A list of integers * @return : A list of integers includes the index of the first number * and the index of the last number */ public ArrayList< Integer > subarraySum ( int [] nums) { // write your code here ArrayList< Integer > res = new ArrayList<> (); HashMap< Integer , Integer > hm =