[LeetCode] Same Tree

Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Java Code:

 public boolean isSameTree(TreeNode p, TreeNode q) {
        if( p == null && q == null) return true;
        
        if( p != null && q != null && p.val == q.val){
            return isSameTree(p.left, q.left)&&isSameTree(p.right, q.right);
        }
        
        return false;
    }

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

[LeetCode] Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. 

解题思路：recursion

Java Code:

public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List> res = new ArrayList>();
        List solution = new ArrayList();
        
        combination(candidates, 0, target, res, solution);
        
        return res;
    }
    
    public void combination(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]);
                combination(candidates, i, target - candidates[i], res, solution);
                solution.remove(solution.size() - 1);
            }else break;
        }
    }

[LeetCode] Generate Parenthese

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"

解题思路：
 i 位置为（ 或者 ) 取决于 目前左括号的数目和右括号的数目.
leftN < n 时，此位置可以为左括号
rightN < leftN && rightN < n时，此位置可以为右括号.


 

 public List generateParenthesis(int n) {
           List res = new ArrayList();
           
           getAllSolution(0,0,n,"",res);
           
           return res;
    }
    
    public void getAllSolution(int leftN, int rightN, int n,String s, List solution){
           if(leftN == n && rightN == n){
               solution.add(s);
               return;
           }
           
           if(leftN < n){
               getAllSolution(leftN+1, rightN, n, s + "(", solution);
           }
           
           if(rightN < n && rightN < leftN){
               getAllSolution(leftN, rightN + 1, n, s + ")", solution);
           }
    }

[LeetCode] Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0 
01 - 1 
11 - 3
10 - 2

解题思路：
F（n） = F(n-1) + (F(n-1) in reverse order) + 1<<(n-1)

n个数的greycode等于 n-1的greycode再加上把greycode反序各自在第1位加个1

 public List grayCode(int n) {
          List res = new ArrayList();
         res.add(0);
         
         for(int i = 1; i <= n; i++){
             int j = res.size();
             int k = 1<<(i-1);
             
             while(j > 0){
                 res.add(res.get(j-1) + k);
                 j--;
             }
         }
         
       return res;
    }