Showing posts with label BFS. Show all posts
Showing posts with label BFS. Show all posts

Monday, March 13, 2017

Leetcode -- 103. Binary Tree Zigzag Level Order Traversal (BFS)

103. Binary Tree Zigzag Level Order Traversal (BFS)
medium
https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/#/description
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its zigzag level order traversal as:
[
  [3],
  [20,9],
  [15,7]
]
思路: just like level order traversal, but we travel the tree in Z shape.
          So any even row, the order of nodes in the row will be reversed when adding to the result arraylist: Collections.reverse(res.get(level))

Complexity: Time O(n) Space O(n)

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;
        Queue<TreeNode> q = new LinkedList();
        int level = 0;
        q.offer(root);
        while(!q.isEmpty()){
            int size = q.size();
            res.add(new ArrayList());
            for(int i = 0; i < size; i++){
                TreeNode cur = q.poll();
                res.get(level).add(cur.val);
                if(cur.left != null){
                    q.offer(cur.left);
                }
                if(cur.right != null){
                    q.offer(cur.right);
                }
            }
            if(level%2 == 1)
                Collections.reverse(res.get(level));
            level++;
        }
        return res;
    }



Wednesday, February 1, 2017

Leetcode/亚麻 -- 199. Binary Tree Right Side View (BFS + DFS)

199. Binary Tree Right Side View (BFS + DFS)
medium
https://leetcode.com/problems/binary-tree-right-side-view/
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
For example:
Given the following binary tree,
   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---
You should return [1, 3, 4].
思路1: BFS, use level order traverlsal. key is to track each level size, and add the 1ast one to list.

public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> qu = new LinkedList<>();
        if(root == null) return res;
        qu.offer(root);
        while(!qu.isEmpty()){
            int size = qu.size();
            for(int i = 0; i < size; i++){//traveling current level
                TreeNode curr = qu.remove();
                if(i == size - 1)res.add(curr.val);
                if(curr.left != null) qu.offer(curr.left);
                if(curr.right != null) qu.offer(curr.right);
            }
        }
        return res;
    }

思路2: DFS, preorder改一下顺序,从右走的左边. To ensure rightmost node of depth,
            Key is we ensure we only add the first node of the specific depth by check depth == list size.
for ex, if we add node at depth 1 from right subtree, we won't add it again when travel the left subtree

public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        traverse(root, result, 0);
        return result;
    }
    public void traverse(TreeNode root, List<Integer> result, int depth){
        if(root == null)return;
        if(depth == result.size()){
            result.add(root.val);
        }
        traverse(root.right, result, depth + 1);
        traverse(root.left, result, depth + 1);
    }

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)


Wednesday, January 18, 2017

Leetcode/各大家 -- 127. Word Ladder(BFS)

127. Word Ladder(BFS)
Medium
https://leetcode.com/problems/word-ladder/
Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
  1. Only one letter can be changed at a time.
  2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
For example,
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:
  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.


思路: Use BFS to traverse dictionary. The level is composed of the words that are 1 char diff from curWord. If find such newWord, first check if is end word so we return min length, else check if in dict & remove it to avoid repeat.
4 loops in total: 1st queue.isEmpty(); 2nd queue.size() -- current level
                          3rd curword.length() - chose every char; 4th 'a' to 'z' - replace each char

 Note: if use DFS, we need to travel all path to decide the shortest one. If using BFS, we stop once we found since we start from short to find the path.解释


public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if(beginWord.equals(endWord)) return 1;
        Set<String> set = new HashSet<>(wordList);
        Queue<String> q = new LinkedList<>();
        int len = 2;
        q.offer(beginWord);
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0; i < size; i++){
                String cur = q.poll();
                for(int j = 0; j < cur.length(); j++){
                    StringBuilder sb = new StringBuilder(cur);
                    for(char c = 'a'; c <= 'z'; c++){
                        sb.setCharAt(j, c);
                        String tmp = sb.toString();
                        if(set.contains(tmp)){
                            if(tmp.equals(endWord)) return len;//endword need to be in dict
                            q.offer(tmp);
                            set.remove(tmp);
                        }
                    }
                }
            }
            len++;
        }
        return 0;
    }
}

算法小结 -- BFS Graph的解法

BFS -- O(V+E) Time O(V)space
用queue, define graph 里面的level概念。    

» 133. Clone Graph(BFS) 各大家
level为current node's negihbors
http://rainykat.blogspot.com/2017/01/leetcode-133-clone-graphbfs.html

» 127. Word Ladder(BFS) 各大家
level focus on queue size.
http://rainykat.blogspot.com/2017/01/leetcode-127-word-ladderbfs.html

» 269. Alien Dictionary 各大家
level is defined before loop, add to queue when meeting requirements
http://rainykat.blogspot.com/2017/01/leetcode-269-alien-dictionarybfs.html

Leetcode/F家 -- 404. Sum of Left Leaves (BFS + DFS)

404. Sum of Left Leaves(BFS + DFS)
Easy
https://leetcode.com/problems/sum-of-left-leaves/
Find the sum of all left leaves in a given binary tree.
Example:
    3
   / \
  9  20
    /  \
   15   7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

思路1: BFS, just make sure left node is leaf(cur.left & cur.right == null) when adding to the sum
Complexity: O(N)time

public class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null){ return 0;}
        int sum = 0;
        LinkedList<TreeNode> qu = new LinkedList<TreeNode>();
        qu.add(root);
        while (!qu.isEmpty()){
            TreeNode cur = qu.remove();
            if(cur.left != null){
                qu.add(cur.left);
                if(cur.left.left == null && cur.left.right == null)//make sure leaf node
                    sum += cur.left.val;
            }
            if(cur.right != null){
                qu.add(cur.right);
            }
        }
        return sum;
    }
}

思路2: DFS, same as above need to check leaf property

public class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null){ return 0;}
        int sum = 0;
        if(root.left!=null){
             if(root.left.left == null && root.left.right == null){ sum += root.left.val;}//make sure left child leaf
        }
        sum += sumOfLeftLeaves(root.left);
        sum += sumOfLeftLeaves(root.right);
        
        return sum;
    }
   
} 

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;
    }
}