[LeetCode] Binary Tree Inorder Traversal

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

   1
    \
     2
    /
   3

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

confused what "{1,#,2,3}" means?

解题思路：
DSF,  先把所有的左结点存放到stack, pop的时候，print 当前位置的值，然后再遍历右子树

Java Code:

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

[LeetCode] Binary Tree Level Order traversal II

Question:

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

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

Java Code:

public List> levelOrderBottom(TreeNode root) {
        List> res = new ArrayList>();
        Queue tmp = new LinkedList();
        Stack> res0 = new Stack>();
        
        if(root == null) return res;
        
        tmp.add(root);
        
        while(!tmp.isEmpty()){
            int size = tmp.size();
            List level = new ArrayList();
            
            for(int i = 0; i < size; i++){
                TreeNode node = tmp.poll();
                level.add(node.val);
                
                if(node.left != null) tmp.add(node.left);
                if(node.right != null) tmp.add(node.right);
            }
            
            res0.add(level);
        }
        
        while(!res0.isEmpty()){
            res.add(res0.pop());
        }
        
        return res;
    }

[LeetCode] Binary Tree Level order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

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

confused what "{1,#,2,3}" means? 

解题思路： BSF，一层一层的打印

Java Code

public List> levelOrder(TreeNode root) {
        List> res = new ArrayList>();
        Queue tmp = new LinkedList();
        
        if(root == null) return res;
        
        tmp.add(root);
        while(!tmp.isEmpty()){
            int size = tmp.size();
            List level = new ArrayList();
            
            for(int i = 0; i < size; i++){
                TreeNode node = tmp.poll();
                level.add(node.val);
                if(node.left != null) tmp.add(node.left);
                if(node.right != null) tmp.add(node.right);
            }
            
            res.add(level);
        }
        
        return res;
    }

[LeetCode] Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

 解题思路：
用两个指针，一个指针遍历整个list，一个指针来指向当前小于x的最后一个node
这样每次找到一个新的node小于x，则把此node移到当前最后一个小于x的后面.
考虑到初始没有小于x的node,则增加一个dummy node 在开头，作为最开始的最后一个小于x的node

Java Code:

public ListNode partition(ListNode head, int x) {
        ListNode safeHead = new ListNode(0);
        safeHead.next = head;
        ListNode prev = safeHead;
        ListNode p = prev;
        
        while(p.next != null && p.next.val < x){
                p = p.next;
                prev = p;
        }
        
        while(p.next != null){
            if(p.next.val < x){          
                ListNode tmp = p.next;
                p.next = p.next.next;
                tmp.next = prev.next;
                prev.next = tmp;
                prev = prev.next;
                
              }else{
                p = p.next;
             }
        }
        
        return safeHead.next;
    }

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

解题思路：
DP解法，可以用recursion. 每次从一个state 转换到另外一个state的时候，我们需要知道，当前的位置(x, y), 以及匹配word的位置 pos, 还有就是为了避免重复visit一个元素，我们得有一个visited数组来记录走过的路径。 



Java Code:

public boolean exist(char[][] board, String word) {
         int row = board.length;
         int col = board[0].length;
          
         boolean[] visited = new boolean[row*col];
         
         for(int i = 0; i < row; i++){
             for(int j = 0; j < col; j++){
                 if(board[i][j] == word.charAt(0) && search(board, i, j, visited, word, 0)){
                     return true;
                 }
             }
         }
        return false;
    }
    
    public boolean search(char[][] board, int x, int y, boolean[] visited, String word, int pos){    
          if(pos == word.length() - 1){
              return true;
          }
       
          int row = board.length;
          int col = board[0].length;
          
          if(x > 0 && !visited[(x-1)*col + y] && word.charAt(pos+1) == board[x-1][y]){
              visited[x*col+y] = true;
              
              if(search(board, x-1, y, visited, word, pos+1)){
                  return true;
              }
              visited[x*col+y] = false;
          }
          
           if(x+1 < row  && !visited[(x+1)*col + y] && word.charAt(pos+1) == board[x+1][y]){
              visited[x*col+y] = true;
              
              if(search(board, x+1, y, visited, word, pos+1)){
                  return true;
              }
              visited[x*col+y] = false;
           }
           
           if(y > 0  && !visited[x*col + y - 1] && word.charAt(pos+1) == board[x][y-1]){
              visited[x*col+y] = true;
              
              if(search(board, x, y-1, visited, word, pos+1)){
                  return true;
              }
              visited[x*col+y] = false;
           }
           
           if(y+1 < col  && !visited[x*col + y + 1] && word.charAt(pos+1) == board[x][y+1]){
              visited[x*col+y] = true;
              
              if(search(board, x, y+1, visited, word, pos+1)){
                  return true;
              }
              visited[x*col+y] = false;
           }
          
        return false;
    }

[LeetCode] N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
] 

解题思路：

1.与N-Queens 2的思路一致，不过此题需要额外多的变量来记录所有的解。 

Java Code:

 public List solveNQueens(int n) {
        List res = new ArrayList();
        int[] solution = new int[n];
    
        String[] curr = new String[n];
        Nqueen1(1, solution, curr, res);
        return res;
    }
    
    public void Nqueen1(int level, int[] solution, String[] curr, List res){
        
        if(level == solution.length + 1){
            res.add(Arrays.copyOf(curr, level-1));
            return;
        }
        
        for(int i = 1; i <= solution.length; i++){
            int slop0 = Math.abs(i - level);
            
                int j = 0; 
                while(j < level && solution[j] != i && Math.abs(j + 1- level) != Math.abs(solution[j] - i)){
                    j++;
                }
                
                if(j == level){
                    String tmp = "";
                    
                    for(int t = 1; t <= solution.length; t++){
                        if(t==i) tmp += "Q";
                        else tmp += ".";
                    }
                    
                   
                    solution[level-1] = i;
                    curr[level-1] = tmp;
                    Nqueen1(level + 1, solution, curr, res);
                    solution[level - 1] = 0;
                    curr[level - 1] = ""; 
                }
         }
    }

[LeetCode] N-Queens

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.





解题思路：问题，每步的solution都与前面的solution相关。要满足，当前的位置i没有被前面使用过并且 |x-y| != |x0 -y0|

Java Code:

 public int totalNQueens(int n) {
          
         ArrayList solution = new ArrayList ();
           
         return totalNq(solution, 0, n);     
    }
    
    public int totalNq(ArrayList orders, int level, int n){
           int total = 0;
           
           if(level == n) {
               return 1;
           }else{
               for(int col = 0; col < n; col++){  
                   
                   if(!orders.contains(col)){
                       int j = 0;
                       while(j < level && Math.abs(j - level) != Math.abs(orders.get(j) - col) ){              
                           j++;
                       }
                       
                       if( j == level){
                           orders.add(level, col);
                           total +=totalNq(orders, level + 1,n); 
                           orders.remove(level);
                       }
                   }
               }
           } 
           
           return total;
    }

[LeetCode] Letters Combinations of a phone Number

Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Java code

 public List letterCombinations(String digits) {
      String[] letters = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        List prevList = new ArrayList();
        prevList.add("");
        
        for(int i = 0; i < digits.length(); i++){
            int digit = digits.charAt(i) - '0';
            List currList = new ArrayList();
            
            for(int j = 0; j < prevList.size(); j++){
                for(int t = 0; t < letters[digit].length(); t++){
                    currList.add(prevList.get(j)+letters[digit].substring(t, t+1));
                }
            }

            prevList.clear();
            prevList.addAll(currList);
        }
        
        return prevList;
     }

[LeetCode] Pascal's Triangle 2

Java Code:

public List getRow(int rowIndex) {
       List res = new ArrayList();
       
       for(int i = 0; i <= rowIndex; i++){       
           int temp = 0;
           
           for(int j = 0; j < res.size(); j++){
               int temp1 = res.get(j);
               res.set(j, temp1 + temp);
               temp = temp1;
           }
           
           if(temp == 0){
               res.add(1);
           }else{
               res.add(temp);
           }
       }
       
       return res; 
    }

[LeetCode] Pascal' Triangle

Given numRows, generate the first numRows of Pascal's triangle.
For example, given numRows = 5,
Return

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

Java Code

public List> generate(int numRows) {
        List> res = new ArrayList>();       
        List first = new ArrayList();
        if(numRows < 1) return res;
        
        first.add(1);
        res.add(first);
        
        for(int i = 1; i < numRows; i++){
            List prev = new ArrayList();
            prev = res.get(i - 1);
            
            List curr = new ArrayList();
            
            for(int j = 0; j <= prev.size(); j++){
                int num = 0;
                
                if(j < prev.size()) num += prev.get(j);
                if(j > 0) num += prev.get(j-1);
                
                curr.add(num);
            }
            
            res.add(curr);
        }
        
        return res;
    }

[LeetCode] Populating Next Right Pointer Each node

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

        1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

Java Code:

 public void connect(TreeLinkNode root) {
         if(root == null) return;
        
        Queue tmp = new LinkedList();
        tmp.add(root);
        
        while(!tmp.isEmpty()){
            int size = tmp.size();
            TreeLinkNode prev = null;
            
            for(int i = 0; i < size; i++){
                TreeLinkNode node = tmp.poll();
                
                if(node.left != null) tmp.add(node.left);
                if(node.right != null) tmp.add(node.right);
                
                if(i == 0){
                    prev = node;
                }else{
                    prev.next = node;
                    prev = prev.next;
                }
            }
        }
            
    }

[LeetCode] Maximum depth of Binary Tree

Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Java code:

 public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        
        int max = 0;
        Queue tmp = new LinkedList();
        tmp.add(root);
        
        while(!tmp.isEmpty()){
            max++;
            int size = tmp.size();
            for(int i = 0; i < size; i++){
                TreeNode node = tmp.poll();
                if(node.left != null) tmp.add(node.left);
                if(node.right != null) tmp.add(node.right);
            }
        }
        
        return max;
    }

[LeetCode] Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

解题思路：
merge sort, 从后往前

Java Code

 public void merge(int A[], int m, int B[], int n) {
        int t = 1;
        int i = m-1;
        int j = n-1;
        
        while(i >= 0 && j>=0){
            if(A[i] > B[j]){
                A[m+n-t] = A[i];
                i--;
            }else{
                A[m+n-t] = B[j];
                j--;
            }
            
            t++;
        }
        
        while(j>=0){
            A[m+n-t] = B[j];
            t++;
            j--;
        }
    }

[LeetCode] LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

解题思路：
1. 要求每次查询元素要constant-time，则我们想到要用hashmap
2. 要每次能返回least recently used cache, 则我们想到要用queue或者linkedlist
则合起来则用linkedhahsmap

注意：每次get, 或者set都要把已经存在的此元素挪到后面去，因为这些操作为调用了cache

Java Code:

 public class LRUCache {
    
   private int totalCapacity;
    LinkedHashMap linkedHashMap = new LinkedHashMap();
    private int num;
    
    public LRUCache(int capacity){
           this.totalCapacity = capacity;
           this.num = 0;
    }
    
    public int get(int key){
        int value = -1;
        if (linkedHashMap.containsKey(key)){
            value = linkedHashMap.get(key);
            linkedHashMap.remove(key);
            linkedHashMap.put(key, value);
         }
         
         return value;
    }
    public void set(int key, int value){
        if (linkedHashMap.containsKey(key)){
            linkedHashMap.remove(key);
            linkedHashMap.put(key, value);
            return;
        }
        
        if(this.num == this.totalCapacity){  
           Iterator keys= linkedHashMap.keySet().iterator();           
           linkedHashMap.remove(keys.next()); 
           this.num--;
        }
        
        this.num++;
        
        linkedHashMap.put(key, value);
    }
    
}

[LeetCode] Longest Substring without repeat characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

Java Code

public int lengthOfLongestSubstring(String s) {
         int startIndex = 0;
           boolean[] visited = new boolean[256];
           int maxLen = 0;
           
           for(int i = 0; startIndex <= i && i < s.length(); i++){
               char a = s.charAt(i);
               if(!visited[a]) {
                   visited[a] = true;
               }else{
                   maxLen = maxLen > (i+1-startIndex)? maxLen : i + 1 - startIndex;
                   while(s.charAt(startIndex) != a ) {
                        visited[s.charAt(startIndex)] = false;
                       startIndex++;
                   }
                   
                   startIndex++;
               }
                   
           }
           
           maxLen = maxLen > s.length() - startIndex? maxLen : s.length() - startIndex;
           
           return maxLen;
    }

[LeetCode] Linked List Cycle 2

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

解题思路：
1. 延续linked list cycle1的题目，先用两个指针p, pn分别走一步和2步，则它们相遇的时候，等于
    n = m*Y  (Y为圈的长度，n为移动一位走的步数)
   如果假设它们相遇的位置离圈开始的那个地方为k，则有，x + k ＝ n (x 为非圈的点数)。
   也就是说 x + k = m*Y. 也就是p再往后走x步就到达了圈开始的结点。

如果此时我们再从头开始一个指针一起往后走，则走x步，它们会在圈开始的结点处相遇

Java Code

 ListNode p = head;
        ListNode pn = head;
        
        while(p != null && pn != null && pn.next != null){
            p = p.next;
            pn = pn.next.next;
            
            if(p != null && p == pn){
                ListNode pre = head;//set another pointer to the beginning
                
                while(p != pre){
                    p = p.next;
                    pre = pre.next;
                }
                return pre;
            }
        }
        
        return null;

[LeetCode] Linked List Cycle

Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?

解题思路：
给两个指针，一个每次走一步，另外一个每次走2步。如果两者相遇，则有圈，否则没有圈

Java code

public boolean hasCycle(ListNode head) {
        ListNode p = head;
        ListNode pn = head;
        
        while(p != null && pn != null && pn.next != null){
             p = p.next;
             pn = pn.next.next;
             
             if(p != null && p == pn) return true;
        }
        
        return false;
    }

[LeetCode] Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4. 
Your algorithm should run in O(n) complexity.

解题思路：
1. 先sort array，时间复杂度为logn， 然后再遍历数组找出连续的sequence。
2. 先scan一遍数组，然后放到hashmap里，然后再以每个数为中心，向两边找到最大的连续sequence. 每次扫完一个element后，将其标为false, 以避免以后重复扫描。

Java code

 public int longestConsecutive(int[] num) {
        Arrays.sort(num);
        int max = 0;
        int len = 1;
        
        for(int i = 0; i < num.length - 1; i++){
            if(num[i] == num[i+1] - 1){
                len++;
            }else if(num[i] < num[i+1] - 1){
                max = len > max? len : max;
                len = 1;
            }
        }
        
        max = max > len ? max : len;
        return max;
    } 

 public int longestConsecutive2(int[] num) {
       HashMap tmp = new HashMap();
       int maxLen = 0;
       
       for(int i = 0; i < num.length; i++){
           tmp.put(num[i], true);
       }
       
       for(int i = 0; i < num.length; i++){
           int len = 0;
           int num0 = num[i];
           
           while(tmp.containsKey(num0) && tmp.get(num0)){
               len++;
               tmp.put(num0, false);
               num0++;
           }
           
           num0 = num[i]-1;
     
            while(tmp.containsKey(num0) && tmp.get(num0)){
               len++;
               tmp.put(num0, false);
               num0--;
           }
           
           maxLen = Math.max(len, maxLen);
       }
       
       return maxLen;
    }

[LeetCode] Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = "Hello World",
return 5.

 public int lengthOfLastWord(String s) {
        int length = s.length();
        int len = 0;
        
        int i = length - 1;
        while( i >= 0 && s.charAt(i) == ' '){
            i--;
        }
        
        while(i >= 0 && s.charAt(i) != ' '){
             i--;
             len++;
         }
            
        
        return len;
    }

[LeetCode] Roman To Integer

Given a roman numeral, convert it to an integer.


Input is guaranteed to be within the range from 1 to 3999.

public int RomanToInt(String s) {
        HashMap romanIntMap = new HashMap();
        romanIntMap.put('M', 1000);
        romanIntMap.put('D', 500); 
        romanIntMap.put('C', 100);
        romanIntMap.put('L', 50);
        romanIntMap.put('X', 10);     
        romanIntMap.put('V', 5);
        romanIntMap.put('I', 1);
      
        int num = 0;
        
        for(int i = 0; i < s.length(); i++){
            int value = romanIntMap.get(s.charAt(i));
            
            if( (i != s.length() - 1) && value < romanIntMap.get(s.charAt(i+1))){
                num -= value;
                continue;
            }
            
            num +=value;
        }
        
        return num;
    }

[LeetCode] Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

解题思路：

DP， 和edit distance有点类似

    public boolean isInterleave(String s1, String s2, String s3) {
           int len1 = s1.length();
           int len2 = s2.length();
           
           if(s3.length() != len1 + len2) return false;
           
           boolean[][] match = new boolean[len1+1][len2+1];
           
           for(int i = 0; i <= len1; i++){
               for(int j = 0; j <= len2; j++){
                   if(i == 0 && j == 0){
                       match[i][j] = true;
                   }else{
                       if(j > 0 && s3.charAt(i+j-1) == s2.charAt(j-1)) match[i][j] = match[i][j] || match[i][j-1];
                       if(i > 0 && s3.charAt(i+j-1) == s1.charAt(i-1)) match[i][j] = match[i][j] || match[i-1][j];
                   }
               }
           }
           
           return match[len1][len2];
    }

[LeetCode] Insertion Sort List

Sort a linked list using insertion sort.

解题思路：
1. 需要2个指针，一个是遍历List，指向将要插入的节点，另外一个是遍历已经sorted的部分，找到要插入的位置
2. 在List的头，加入一个dummy node, 因为新插入的节点可能会在头部

public ListNode insertionSortList(ListNode head) {
        ListNode res = new ListNode(0);        
        ListNode pNode = head;
   
        while(pNode != null){
              ListNode tNode = res;
              
              while( tNode.next != null  && pNode.val > tNode.next.val){
                  tNode = tNode.next;
              }
              
              ListNode tNextNode = tNode.next;
              tNode.next = pNode;
              pNode = pNode.next;
              tNode.next.next = tNextNode;
        }
        
        return res.next;
    }

[LeetCode] Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.

解题思路：
 隐含的一个条件为： 如果 i 不能到达j, 则 i+1..j-1也不能到达j.

 public int canCompleteCircuit(int[] gas, int[] cost) {
        int gasleft = 0;
        int beginIndex = 0;
        int n = gas.length;
        
        while (beginIndex < n){
            int i = 0;
             while( i < n ){
                   int curr = (i + beginIndex)%n; 
                   gasleft +=gas[curr] -cost[curr]; 
                   
                   if(gasleft < 0){
                         beginIndex += i + 1;
                         gasleft = 0;
                         break;
                     }
                   
                   i++;
              }
             
             if(i == n) return beginIndex;
        } 
              
        return -1;
              
   }

[LeetCode] Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

解题思路： 用一个stack即可

 public int evalRPN(String[] tokens) {
       Stack tmp = new Stack ();
       
       for(int i = 0; i < tokens.length; i++){
           if(tokens[i].matches("[+-]?\\d+")){
               tmp.add(Integer.valueOf(tokens[i]));
           }else{
            if(tmp.isEmpty()) return 0;
            
            int b = tmp.pop();
            int a = tmp.pop();
            
            switch(tokens[i]){
               case "+": a += b;
                         break;
               case "-": a -= b;
                         break;
               case "*": a *= b;
                         break;
               case "/": a /= b;
                         break;
               default: break;
            }
            
            tmp.add(a);
           }
       }
        
        return tmp.peek();
    }

[LeetCode] Distinct Subsequence

Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.

解题思路：
      DP思想 ：1.  S(i) -> T(j) = S(i-1)->T(j)  if s.charAt(i) !=  t.charAt(j)
                        2. S(i) -> T(j) = S(i-1) -> T(j-1) + S(i-1)->T(j) if s.charAt(i) ==  t.charAt(j)

public int numDistinct(String S, String T) {
       int row = S.length();
       int col = T.length();
       int[][] num = new int[row+1][col+1];
       
       for(int i = 0; i <= row; i++){
           for(int j = 0; j <= col; j++){
               if(i==0){
                   if(j == 0) num[i][j] = 1;
                   else num[i][j] = 0;
               }else if(j == 0){
                   num[i][j] = 1;
               }else{
                   num[i][j] = num[i-1][j];
                   
                   if(S.charAt(i-1) == T.charAt(j-1)){
                       num[i][j] +=num[i-1][j-1];
                   }
               } 
           }
       }
       
       return num[row][col];
       
    }

[LeetCode] Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.


解题思路：
            1. 与climbstairs非常相似，只是这里多加了一些限制条件
            f(n) = f(n-2) 当n为0时。
            f(n) = f(n-1) 当大于26
 容易出错点： 当遇到0的时候，需要判断。

 public int numDecodings(String s) {
        int n = s.length();

        if (n == 0 || s.charAt(0) == '0') {
            return 0;
        }

        int num0 = 1, num1 = 1, num = 1;

        for (int i = 1; i < n; i++) {
                if(s.charAt(i) != '0'){
                    num = num1;
                }else{
                    num = 0;
                }
                
                if(s.charAt(i-1) != '0' && Integer.valueOf(s.substring(i-1, i+1)) <= 26){
                    num += num0;
                }
                
                if(num == 0) return 0;
            
                num0 = num1;
                num1 = num;
            
        }

        return num;
    }

[LeetCode] Candy

There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

解题思路：
        1. 对于ratings[i], ratings[i]的数目的大小，取决于ratings[i-1], ratings[i+1]和ratings[i]的大小对比。我们可以简化为，ratings[i-1] vs ratings[i] 或者ratings[i+1] vs ratings[i].
        从左到右扫描数组，candies[i] = candies[i-1] + 1 if ratisngs[i] > ratings[i-1]
          然后第二遍，从右到左，candies[i-1] = candies[i] + 1 if ratings[i-1] > ratisngs[i]
          第二遍，要注意在ratings[i-1] > ratings[i] and candies[i-1] > candies[i], 就不需要更改了candies了。

 
public int candy(int[] ratings) {
        int n = ratings.length;
        if(n == 0) return 0;
        
       int[] candies = new int[n];
       int total = 0;
       candies[0] = 1;
       
       
       for(int i = 1; i < ratings.length; i++){
           if(ratings[i] > ratings[i-1]){
               candies[i] = candies[i-1] + 1;
           }else{
               candies[i] = 1;
           }
       }
       
       total = candies[n - 1];
       
       for(int i = ratings.length - 1; i > 0 ; i--){
           if(ratings[i] < ratings[i-1] && candies[i] >= candies[i-1]){
               candies[i-1] = candies[i] + 1;
           }
               total += candies[i-1];
       }
       
       return total;
           
    }

[LeetCode] Combination Sum2

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

解题思路：
      1. 与combination sum基本一致，区别为每次都要移动到下一个不相同的数。

 public List> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List> res = new ArrayList>();
        List solution = new ArrayList();
        
        combination2(candidates, 0, target, res, solution);
        
        return res;
    }
    
    public void combination2(int[] candidates, int startIndex, int target, List> res, List solution){
        if(target == 0){
            List tmp = new ArrayList(solution);
            res.add(tmp);
            return;
        }
        
        for(int i = startIndex; i < candidates.length; i++){
            if(candidates[i] <= target){
                solution.add(candidates[i]);
                combination2(candidates, i+1, target - candidates[i], res, solution);
                solution.remove(solution.size() - 1);
                
                while(i < candidates.length - 1 && candidates[i] == candidates[i+1]) i++; //move to next diff candidate
            }else break;
        }
    }