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