［LeetCode］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], ]


解题思路：
                1. 求n个数中的k个数的组合，如果此组合含有n,则就是求n-1的k-1个组合，不含有n，就是n-1的k。即 combine(n, k) = combine(n-1, k -1) + combine(n-1, k);
                2. 要注意的就是n-1,k-1可能返回nil, 那么这时就要初始化n。
       

public List> combine(int n, int k) {
         List> res = new ArrayList>();
         
         if( n < k || k == 0) return res;
         
         res = combine(n-1, k-1);
         
         for(int i = 0; i < res.size(); i++){
             List tmp = res.get(i);
             tmp.add(n);
         }
         
         if(res.size() == 0){
             List tmp = new ArrayList();
             tmp.add(n);
             res.add(tmp);
         }
         
         res.addAll(combine(n-1, k));
         
         return res;
    }

[LeetCode] Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.



解题思路：
1. recursion method, check the height of the left sub tree and right sub tree. 
2. Keep track the height of every node, then we iterate the whole tree only one time.

Java Code:
     

 public boolean isBalanced(TreeNode root) {
        
        return getHeight(root) != -1;
    }
    
    public int getHeight(TreeNode root){
        if(root == null) return 0;
        
        int leftheight = 0, rightheight = 0;
        
        if(root.left != null) leftheight = getHeight(root.left);
        if(root.right != null) rightheight = getHeight(root.right);
        if(leftheight == -1 || rightheight == -1 || Math.abs(leftheight - rightheight) > 1) return -1;
        
        int height = leftheight > rightheight? leftheight +1 : rightheight + 1;
        
        return height;
    }

[LeetCode] Binary Tree PostOrder

Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?

解题思路：
1. recursion 最直接的做法
2. non-recursion, 借助stack.
   2.1 find the leftmost node, for every step, push node.right, node into stack
  2.2  pop up one node if current node is null, if the popped one node has its right node at the top of the stack, then pop up its right child node, push itself into the stack. repeat the 2.1

和inorder类似，区别为在push node, node.right的顺序不一样。要确保node的right child 不会重复visit,就先push node.right, 再存入node. 这样每次就可以对比当前的node的right child是不是为stack top。

Java Code:

recursion solution:

 public List postorderTraversal(TreeNode root) {
         List res = new ArrayList();
        
         postorderT(res, root);
         return res;
    }
     public void postorderT(List res, TreeNode root) {
            if(root == null) return;
            if(root.left != null) postorderT(res, root.left);
            if(root.right != null) postorderT(res, root.right);
            res.add(root.val);
    }

non-recursion solution:

public List postorderTraversal(TreeNode root) {
         List res = new ArrayList();
         Stack tmp = new Stack();
         TreeNode p = root;
         
         while(!tmp.isEmpty() || p != null ){
             while(p != null){
                 if(p.right != null) tmp.add(p.right);
                  tmp.add(p);
                
                 p = p.left;
             }
             
            p = tmp.pop();
            
            if(p.right != null && !tmp.isEmpty() &&p.right == tmp.peek()){
               TreeNode tmp0 = tmp.pop();
               tmp.add(p);
               p = p.right;
            }else{
                res.add(p.val);
                p = null;
            }
         }
         
         return res;
    }

Binary Tree Zigzag Level Order Traversal

Question:

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,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
] 

Java Code:

  public static ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root)
    {
        ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>> ();
        ArrayList<TreeNode> tmpQ = new ArrayList<TreeNode> ();
        
        int i = 0;
        
        if(root != null)
            tmpQ.add(root);
    
        while ( !tmpQ.isEmpty() )
        {
            ArrayList<Integer> tmpresult = new ArrayList<Integer> ();
            int length = tmpQ.size();
            int count = 0;
            
            for (int z = 0; z < length; z++)
                tmpresult.add(tmpQ.get(z).val);
            
            while( count < length)
            {
                TreeNode tmp = tmpQ.get(length - 1 - count);
                tmpQ.remove(length-1-count);
                
                count++;
                
               if (i%2 == 0)
                {
                   if(tmp.right != null)
                       tmpQ.add(tmp.right);
                   if(tmp.left != null)
                       tmpQ.add(tmp.left);
                }
               else 
               {
                   if(tmp.left != null)
                       tmpQ.add(tmp.left);
                   if(tmp.right != null)
                       tmpQ.add(tmp.right);   
               }
             
            }
            
            results.add(tmpresult);
            i++;
        
        }
    
        return results;
    
    }

[LeetCode] Anagrams

Question:
Given an array of strings, return all groups of strings that are anagrams. 

解题思路：
        寻找回文构词，就是需要建立一个hash函数，使得为anagrams的词都映射到相同的hash key。
      1. 最直接的方法，就是对每个str进行排序，然后比较它们是否相等
      2. 这里我用的是countandsay的方法，就是统计出每个字母出现的次数，然后用字母的次数和字母组合成一个key。
     3. 这个题可以转化为，如何找出2个str为anagrams. 我们可以为每个字母分配一个不同的prime，最后把所有的prime相乘。如果最后的数相等，则为anangrams.

Notice : 这里hash函数的value存的为第一次出现此key的str在数组里的index. 如果出现了此词的anangrams，则将此index. 改为-1。

Java Code:

   

  public List anagrams(String[] strs) {
       List res = new ArrayList ();
       HashMap tmp = new HashMap();

       for(int i = 0; i < strs.length; i++){     
           String key = getKey(strs[i]);
           
           if(tmp.containsKey(key)){
                if(tmp.get(key) != -1){
                   res.add(strs[tmp.get(key)]);
                   tmp.put(key, -1);
               }
               res.add(strs[i]);
              
           }else{
               tmp.put(key, i);
           }
       }
       
       return res;
    }
    
    public String getKey(String str){
        int[] count = new int[26];
        String res = "";
        
        for(int i = 0; i < str.length(); i++){
            count[str.charAt(i) - 'a']++;
        }
        
        for(int i = 0; i < 26; i++){
            if(count[i] > 0){
                res += count[i] + String.valueOf(Character.toChars(i+'a')) ;
            }
        }
        
        return res;
    }

[LeetCode] Add Two Numbers

Question:

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

解题思路： 一道实现题

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
           ListNode p1 = l1;
           ListNode p2 = l2;
           ListNode head = new ListNode(0);
           ListNode p = head;
           
           int add = 0;
           
           while(p1 != null || p2 != null || add > 0){
               int add1 = 0, add2 = 0;
               
               if(p1 != null){
                  add1 = p1.val;
                  p1 = p1.next;
               } 
               
               if(p2 != null){
                   add2 = p2.val;
                   p2 = p2.next;
               } 
               
                int val = (add1 + add2 + add)%10;
                add = (add1 + add2 + add)/10;
                
                ListNode l = new ListNode(val);
                p.next = l;
                p = p.next;
           }
           
           return head.next;
    }

[LeetCode] Add Binary

Question:

Given two binary strings, return their sum (also a binary string). 
For example,
a = "11"
b = "1"
Return "100".  

Java Code:

 
 public String addBinary(String a, String b) {
     String res = "";
          int aLen = a.length();
          int bLen = b.length();
          int add = 0, add1 = 0, add2 = 0;
          
          int i = 1;
          
          while( i <= aLen || i <= bLen || add > 0){
              add1 = i <= aLen ? a.charAt(aLen - i) - '0' : 0;
              add2 = i <= bLen? b.charAt(bLen - i) - '0' : 0;
              
              res = (add1+add2+add)%2 + res;
              add = (add1 + add2 + add)/2;
              i++;
          }
          
          return res;
       }