博文

目前显示的是 七月, 2017的博文

Connecting Graph III

Connecting Graph II

Union find template and notes

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

Connecting Graph

Subarray Sum

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...