Showing posts with label Graph. Show all posts
Showing posts with label Graph. Show all posts

Tuesday, January 24, 2017

Leetcode/各大家 -- 269. Alien Dictionary(BFS)

269. Alien Dictionary(BFS)
Hard
https://leetcode.com/problems/alien-dictionary/
There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.
For example,
Given the following words in dictionary,
[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]
The correct order is: "wertf".
Note:
  1. You may assume all letters are in lowercase.
  2. If the order is invalid, return an empty string.
  3. There may be multiple valid order of letters, return any one of them is fine.

思路: use map1: map to store <c, set of char after c>
           use map2: degree to store <c, # of char before c> //based on loop not the final one
           Iterate each two adjacent string, to fill map and update degree 
           use a queue to do BFS. add c to queue when its degree is 0. When remove a c, minus degree
           ! watch edge case,  loop case
Complexity: time: O(n) space: O(n

public class Solution {
    public String alienOrder(String[] words) {
        HashMap<Character, Set<Character>> map = new HashMap<Character, Set<Character>>();//<c, char after c>
        HashMap<Character, Integer> degree = new HashMap<Character, Integer>();//<c, # of char before c>
        StringBuilder res = new StringBuilder();
        //initialize degree map
        for(int i = 0; i < words.length; i++){
            char[] word = words[i].toCharArray();
            for(int j = 0; j < word.length; j++){
                degree.put(word[j], 0);
            }
        }
        //compare adjacent string & fill map
        for(int i = 0; i < words.length - 1; i++){
            String cur = words[i];
            String next = words[i + 1];
            int len = Math.min(cur.length(), next.length());
            for(int j = 0; j < len; j++){
                char c1 = cur.charAt(j);
                char c2 = next.charAt(j);
                if(c1 != c2){
                    Set<Character> set = new HashSet<Character>();//watch 'Set' declaration
                    if(map.containsKey(c1))set = map.get(c1);
                    if(!set.contains(c2)){
                        set.add(c2);
                        map.put(c1, set);
                        degree.put(c2, degree.get(c2) + 1);
                    }
                    break;//rest comparision is meaningless & not record it!
                }else{
                    //edge case - no order: ["wrtkj","wrt"] 1:next stop at end 2: cur still have lefts
                    if(j + 1 == next.length() && j + 1 < cur.length())
                        return "";
                }
            }
        }
        //BFS - use Queue to pop char in order
        Queue<Character> queue = new LinkedList<Character>();
        for(char c: degree.keySet()){
            if(degree.get(c)==0){
                queue.add(c);//eg:[zx,zy], c: z,x
            } 
        }
        while(!queue.isEmpty()){
            char cur = queue.remove();
            res.append(cur);
            if(map.containsKey(cur)){
                for(char c: map.get(cur)){
                    degree.put(c, degree.get(c) - 1);
                    if(degree.get(c) == 0)queue.add(c);//add next char
                }
            }
        }
        //avoid loops. only < possible -- eg: ["qd","ab"] res = qa
        if(res.length() != degree.size())return "";
        return res.toString();
    }
}

ex:   ["wrt","wrf","er","ett","rftt","a","t"] answer: weratf
                                   ?"f"why working
w0(degree) letter before
f1(t)
e1(w)
t1(r)2(a)
r1(e)
a1(r)


Tuesday, January 17, 2017

Leetcode/各大家 -- 133. Clone Graph(BFS)

133. Clone Graph(BFS)
medium
https://leetcode.com/problems/clone-graph/
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:
Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.
  1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
  2. Second node is labeled as 1. Connect node 1 to node 2.
  3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:
       1
      / \
     /   \
    0 --- 2
         / \
         \_/

 Pocket Gems Google Uber Facebook

思路: Create HashMap to match each node from old graph to new graph.
           Use BFS to travel each node in old graph. Create corresponding node (copy) in hashmap for new graph on the fly.
           Then add each neighbor of current node to the matching node in new graph (here need to get(key) for a copy) 
Complexity: O(N) visit each node only once.  Space O(N)


public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node == null)return node;
        Queue<UndirectedGraphNode> qu = new LinkedList<UndirectedGraphNode>();//travel node in old graph
        HashMap<UndirectedGraphNode,UndirectedGraphNode> map = new HashMap<>();//<node in old graph,node in new graph>
        UndirectedGraphNode root = new UndirectedGraphNode (node.label);
        map.put(node,root);
        qu.add(node);
        while(!qu.isEmpty()){
            UndirectedGraphNode cur = qu.remove();
            for (UndirectedGraphNode oldn: cur.neighbors){
                if(!map.containsKey(oldn)){
                    map.put(oldn, new UndirectedGraphNode(oldn.label));
                    qu.add(oldn);
                }
                map.get(cur).neighbors.add(map.get(oldn));//need to add nodes in new graph
            }
        }
        return root;
    }
}

Monday, January 9, 2017

Leetcode/G家twitter -- 323. Number of Connected Components in an Undirected Graph (Union Find)

323. Number of Connected Components in an Undirected Graph(Union Find)
  • Difficulty: Medium
https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/
iven n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.
Example 1:
     0          3
     |          |
     1 --- 2    4
Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.
Example 2:
     0           4
     |           |
     1 --- 2 --- 3
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 1.
Note:
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

参考:https://discuss.leetcode.com/topic/32752/easiest-2ms-java-solution
This is 1D version of Number of Islands II. For more explanations, check out this 2D Solution.
  1. n points = n islands = n trees = n roots.
  2. With each edge added, check which island is e[0] or e[1] belonging to.
  3. If e[0] and e[1] are in same islands, do nothing.
  4. Otherwise, union two islands, and reduce islands count by 1.
  5. Bonus: path compression can reduce time by 50%.
Hope it helps!
Complexity: The complexity for M quick union + path compression on N objects should be N + MlgN, I think in this problem, M = 2E, N = V, so O(V + 2ElgV)

public class Solution {
    public int countComponents(int n, int[][] edges) {
         // initialize n isolated islands
        int[] roots = new int[n];
        for(int i = 0; i < n; i++) roots[i] = i; 
        int count =n;
        // perform union find
        for (int i = 0; i < edges.length; i++) {
            int root1 = findSet(roots,edges[i][0]);//when union, always update the top parent(recur)
            int root2 = findSet(roots,edges[i][1]);
            //if in one set means already reduce count by adding edge before, new edge not impact
            if(root1!=root2){
                roots[root1] = root2;//in 2 sets,union(add a edge)
                count--;
            }
        }
        return count;
    }
    public int findSet(int[] roots,int i){
        if(roots[i]==i)return i;//is top parent
        roots[i] = findSet(roots,roots[i]);//path compression(optional)
        return roots[i];
    }
}

Optional path compression: (Iteration has little difference from recursion)
public int findSet(int[] roots,int i){
        while(roots[i] != i) {
            roots[i] = roots[roots[i]];  // optional: path compression
            i = roots[i];
        }
        return i;
    }


算法小结 -- Union Find的套路

Union Find
Good for graph problem, like finding cycles in edge, largest components, etc

O(M) for union find, M operations

M quick union + path compression on N objects should be N + MlgN

-make set
-union
-find set
思路:-- for n nodes from 0 to n-1, create roots[n] to track each root's parents. 
         -- initialize parent with -1(point to null), roots = [-1,-1,-1,...-1],
 eg: n nodes from 0 to n-1, edges[0,1] [0,2] [2,3] will be [1,2,3,-1...]
         -- recursively find root1 and root2 (edge[root1,root2])check if they are in the same set
 if found in two sets, then union: roots[root1] = root2;
         -- middle roots can be dirty, keep updating&maintain top parents or boundaries.
         -- use path compression(point child root directly to top parent) to save time 
               
应用: Undirected Graph 

EX: 
» 323. Number of Connected Components in an Undirected Graph(Union Find) G家Twitter
http://rainykat.blogspot.com/2017/01/leetcodegtwitter-323-number-of.html
» 261. Graph Valid Tree(Union Find)
G家F家
http://rainykat.blogspot.com/2017/01/leetcodegf-261-graph-valid-treeunion.html
» 128. Longest Consecutive Sequence G家F家 

http://rainykat.blogspot.com/2017/01/leetcodefg-128-longest-consecutive.html

Leetcode/G家F家 -- 261. Graph Valid Tree(Union Find)


261. Graph Valid Tree(Union Find)
  • Difficulty: Medium
https://leetcode.com/problems/graph-valid-tree/
Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.
For example:
Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.


Tree: Any connected graph w/o cycle
思路: 1. Union find: for each interval, start's set and end's set should be in different set.
               If in same set, there is cycle. Start and end find its set recursively tot the top parents where nums[i] is -1. Once in 2 sets(top parent not equal), union 2 set by setting start's top parent be end.
(nums[start's top parent] = end's top parent)
               Exit loop with no loop, judge if (nodes number -1 = edge number) to ensure connected graph

 Complexity: say the graph has V vertices and E edges, the find( ) function takes O(V) time because in the worst case it has to go through all the vertices, and from outside we loop through all the edges, so the time complexity should be O(V*E).


public class Solution {
    public boolean validTree(int n, int[][] edges) {
        // initialize n isolated islands
        int[] roots = new int[n];
        Arrays.fill(roots, -1);
        
        // perform union find,if start & end in same set, means cycle
        for (int i = 0; i < edges.length; i++) {
            int root1 = findSet(roots,edges[i][0]);//when union, always update the top parent(recur)
            int root2 = findSet(roots,edges[i][1]);
            if(root1 == root2)//in same set=find cycle
                return false;
            roots[root1] = root2;//union, must be root1, don't forget mid nodes traveled when find top parents
        }
        
        return edges.length == n - 1;//no cycle but still need check if # of nodes equals # of edges
    }
    public int findSet(int[] roots,int i){
        if(roots[i]==-1)return i;//is top parent
        return findSet(roots,roots[i]);
    }
}