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


Naive Way: Use a level-order traversal and always note down the last TreeNode value in the result.

 /**  
  * Definition for binary tree  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   public List<Integer> rightSideView(TreeNode root) {  
     List<Integer> list = new ArrayList<Integer>();  
     List<TreeNode> cur_layer = new ArrayList<TreeNode>();  
     // edge case  
     if(root==null) return list;  
     // initialize current layer  
     cur_layer.add(root);  
     // level-order traversal  
     while(!cur_layer.isEmpty()){  
       list.add(cur_layer.get(cur_layer.size()-1).val);  
       List<TreeNode> next_layer = new ArrayList<TreeNode>();  
       for(TreeNode node: cur_layer){  
         if(node.left!=null) next_layer.add(node.left);  
         if(node.right!=null) next_layer.add(node.right);  
       }  
       cur_layer = next_layer;  
     }  
     return list;  
   }  
 }  

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Naive Thinking: First thought was to use DP. The logic is as follows:
opt[i] // the maximum amount of money one rob without alerting the police.
// base case
opt[0] = 0
opt[1] = num[0]
// iteration
opt[i] = max(opt[i-1], opt[i-2]+num[i-1])

 public class Solution {  
   public int rob(int[] num) {  
     if(num == null || num.length == 0) return 0;  
     int opt[] = new int[num.length+1];  
     // base case  
     opt[0] = 0;  
     opt[1] = num[0];  
     // iteration  
     for(int i = 2;i <= num.length;i++)  
       opt[i] = Math.max(opt[i-1], opt[i-2] + num[i-1]);  
     return opt[num.length];  
   }  
 }  

From the structure of the code. It is easy to see the O(N) space could be constrained to O(1).

 public class Solution {  
   public int rob(int[] num) {  
     if(num == null || num.length == 0) return 0;  
     // base case  
     int pre = 0;  
     int cur = num[0];  
     // iteration  
     for(int i = 2;i <= num.length;i++){  
       int temp = cur;  
       cur = Math.max(cur, pre + num[i-1]);  
       pre = temp;  
     }  
     return cur;  
   }  
 }  

Word Search

Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.


Naive Way: First came up with a DFS method. Need a hashset for each path to store visited positions.

 public class Solution {  
   class Node{  
     int x,y;  
     Node(int x, int y){  
       this.x = x;  
       this.y = y;  
     }  
     @Override  
     public boolean equals(Object other){  
       if (!(other instanceof Node))  
         return false;  
       Node n = (Node)other;  
       return this.x==n.x && this.y==n.y;  
     }  
     @Override  
     public int hashCode(){  
       return x << 16 | y;  
     }  
   }  
   public boolean exist(char[][] board, String word) {  
     for(int i = 0;i < board.length;i++)  
       for(int j = 0;j < board[i].length;j++){  
           Node node = new Node(i,j);  
           Stack<Node> stack = new Stack<Node>();  
           Set<Node> set = new HashSet<Node>();  
           stack.add(node);  
           set.add(node);  
           if(dfs(board, node, word, 0, stack, set))  
             return true;  
         }  
     return false;  
   }  
   private boolean dfs(char[][] board, Node node, String word, int index, Stack<Node> stack, Set<Node> set){  
     /* ending cases */  
     // find a path  
     if(index == word.length()) return true;  
     // invalid node  
     if(node.x < 0 || node.x >= board.length || node.y < 0 || node.y >= board[0].length) return false;  
     // not match  
     if(board[node.x][node.y] != word.charAt(index)) return false;  
     // recusive case  
     Node up = new Node(node.x-1, node.y);  
     if(!set.contains(up)){  
       stack.push(up);  
       set.add(up);  
       if(dfs(board, up, word, index+1, stack, set)) return true;  
       stack.pop();  
       set.remove(up);  
     }  
     Node down = new Node(node.x+1, node.y);  
     if(!set.contains(down)){  
       stack.push(down);  
       set.add(down);  
       if(dfs(board, down, word, index+1, stack, set)) return true;  
       stack.pop();  
       set.remove(down);  
     }  
     Node left = new Node(node.x, node.y-1);  
     if(!set.contains(left)){  
       stack.push(left);  
       set.add(left);  
       if(dfs(board, left, word, index+1, stack, set)) return true;  
       stack.pop();  
       set.remove(left);  
     }  
     Node right = new Node(node.x, node.y+1);  
     if(!set.contains(right)){  
       stack.push(right);  
       set.add(right);  
       if(dfs(board, right, word, index+1, stack, set)) return true;  
       stack.pop();  
       set.remove(right);  
     }  
     return false;  
   }  
 }  

And then, I think I am bring too much extra stuff to a simple problem. Better use a 2D array to record used cell.

 public class Solution {  
   public boolean exist(char[][] board, String word) {  
     // edge case  
     if(board == null || board.length == 0) return false;  
     if(word.length() > board.length*board[0].length) return false;  
     boolean[][] used = new boolean[board.length][board[0].length];  
     for(int i = 0;i < board.length;i++){  
       for(int j = 0;j < board[0].length;j++){  
         used[i][j] = true;  
         if(dfs(board, i, j, word, 0, used)) return true;  
         used[i][j] = false;  
       }  
     }  
     return false;  
   }  
   private boolean dfs(char[][] board, int x, int y, String word, int index, boolean[][] used){  
     // ending case  
     if(index==word.length()) return true;  
     if(board[x][y]!=word.charAt(index)) return false;  
     // recursive call  
     if(x-1 >= 0 && !used[x-1][y]){  
       used[x-1][y] = true;  
       if(dfs(board,x-1,y,word,index+1,used)) return true;  
       used[x-1][y] = false;  
     }  
     if(x+1 < board.length && !used[x+1][y]){  
       used[x+1][y] = true;  
       if(dfs(board,x+1,y,word,index+1,used)) return true;  
       used[x+1][y] = false;  
     }  
     if(y-1 >= 0 && !used[x][y-1]){  
       used[x][y-1] = true;  
       if(dfs(board,x,y-1,word,index+1,used)) return true;  
       used[x][y-1] = false;  
     }  
     if(y+1 < board[0].length && !used[x][y+1]){  
       used[x][y+1] = true;  
       if(dfs(board,x,y+1,word,index+1,used)) return true;  
       used[x][y+1] = false;  
     }  
     return false;  
   }  
 }  

but this code get TLE for the longest "aaa.."" string case. And then I saw others' code and found a modified, much more elegant way.

 public class Solution {  
   public boolean exist(char[][] board, String word) {  
     // edge case  
     if(word == null || board == null || board.length == 0) return false;  
     if(word.length() > board.length*board[0].length) return false;  
     boolean[][] used = new boolean[board.length][board[0].length];  
     for(int i = 0;i < board.length;i++)  
       for(int j = 0;j < board[0].length;j++)  
         if(dfs(board, i, j, word, 0, used)) return true;  
     return false;  
   }  
   private boolean dfs(char[][] board, int x, int y, String word, int index, boolean[][] used){  
     // ending case  
     if(index==word.length()) return true;  
     if(x < 0 || x >= board.length || y < 0 || y >= board[0].length) return false;  
     if(used[x][y] || board[x][y]!=word.charAt(index)) return false;  
     // recursive call  
     used[x][y] = true;  
     if(dfs(board,x-1,y,word,index+1,used)) return true;  
     if(dfs(board,x+1,y,word,index+1,used)) return true;  
     if(dfs(board,x,y-1,word,index+1,used)) return true;  
     if(dfs(board,x,y+1,word,index+1,used)) return true;  
     used[x][y] = false;  
     return false;  
   }  
 }  

Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
] 

Naive Way: A recursive method is straightforward. Need to convey current index, n, current k as parameter to recursive function. It is a DFS idea.

 public class Solution {  
   public List<List<Integer>> combine(int n, int k) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     dfs(new Stack<Integer>(), 1, n, k, rslt);  
     return rslt;  
   }  
   private void dfs(Stack<Integer> path, int index, int n, int k, List<List<Integer>> rslt){  
     // ending case  
     if(k==0){  
       List<Integer> list = new ArrayList<Integer>(path);  
       rslt.add(list);  
       return;  
     }  
     // recursion case  
     for(int i = index;i <= n;i++){  
       path.push(i);  
       dfs(path, i+1, n, k-1, rslt);  
       path.pop();  
     }  
   }  
 }  

An iterative method correspondingly.

 public class Solution {  
   public List<List<Integer>> combine(int n, int k) {  
     List<List<Integer>> rslt = new ArrayList<List<Integer>>();  
     Deque<List<Integer>> gross = new ArrayDeque<List<Integer>>();  
     // edge case   
     if(k==0) return rslt;  
     // initialize the rslt  
     for(int i = 1;i <= n-k+1;i++){  
       List<Integer> list = new ArrayList<Integer>();  
       list.add(i);  
       gross.offerLast(list);  
     }  
     // iteration on k  
     int ind = 1;  
     while(ind++ < k){  
       int length = gross.size();  
       for(int i = 0;i < length;i++){  
         List<Integer> list = gross.pollFirst();  
         int num = list.get(list.size()-1);  
         for(int j = num+1;j <= n;j++){  
           List<Integer> new_list = new ArrayList<Integer>(list);  
           new_list.add(j);  
           gross.offerLast(new_list);  
         }  
       }  
     }  
     // add to result  
     while(!gross.isEmpty()) rslt.add(gross.pollFirst());  
     return rslt;  
   }  
 }