Valid Palindrome

Problem:

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

Analysis:
答案里面是从两端到中间,而且剔除字符和空格没有用多余的function，真简洁。我的想法是从中间到两端。明显复杂一些。Anyway, 能自己写出来通过是好事。对自己的预期不能再低了，呵呵。
Solution:

1:  public static boolean isPalindrome(String s)  
2:       {  
3:            int j=0;  
4:            int k=0;  
5:            s=trimString(s.toLowerCase());  
6:            int mod=s.length()%2;  
7:            if(mod==0)  
8:            {  
9:                 j=s.length()/2-1;  
10:                 k=j+1;  
11:            }  
12:            else  
13:            {  
14:                 j=s.length()/2;  
15:                 k=j;  
16:            }  
17:            for(;j>=0;j--,k++)  
18:            {  
19:                 if(s.charAt(j)!= s.charAt(k))  
20:                      return false;  
21:            }  
22:            return true;  
23:       }  
24:       public static String trimString(String s)  
25:       {  
26:      StringBuilder sb= new StringBuilder();  
27:            for(char c: s.toCharArray())  
28:            {  
29:                 if((c>='a'&&c<='z')||(c>='0'&&c<='9') )  
30:                 {  
31:                      sb.append(c);  
32:                 }  
33:            }  
34:            return sb.toString();  
35:       }  

Implement strStr()

Problem:

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Analysis:

这道题在leetcode String分类里算简单的。是因为暴力法很简单易懂。更高级的有Rabin-Karp algorithm, KMP algorithm 和 Boyer0 Moore algorigthm。以上都是出现在高级算法设计课的。暂时达不到那个高度。

Solution:

1:  public static int strStr(String haystack, String needle)  
2:       {  
3:            int hlen=haystack.length();  
4:            int nlen=needle.length();  
5:            if(haystack==null || needle==null || nlen<hlen)  
6:                 return -1;  
7:            boolean isSub=true;  
8:            for(int i=0;i<hlen-nlen;i++)  
9:            {  
10:          isSub=true;          
11:             for(int j=0;j<nlen;j++)  
12:             {  
13:                  if(haystack.charAt(i+j)!=needle.charAt(j))  
14:               {  
15:                   isSub=false;  
16:                   break;  
17:               }  
18:             }  
19:             if(isSub)  
20:                 return i;   
21:            }  
22:            return -1;  
23:       }  

Add Binary

Problem:

Given two binary strings, return their sum (also a binary string).

For example,

a = "11"

b = "1"

Return "100".

Analysis:

At the very beginning, I still didn't know where to start. Referenced [1], then I realized this is a simple problem. And decided to do it on my own. I implemented in Eclipse, debugged several rounds. Put the code to LeetCode online Jug, got accepted immediately.

The key of this problem is reverse the strings. Because we do math sum up from lower digit to higher digit right to left, but array index is from left to right.

Example:

 0 1 1 0 1
+     1 0 1 1 1
---------------------
=  1 0 0 1 0 0

The implementation of [1] seems a mass to me, so I did it in a more concise way. 

Solution:

1:  public static String addBinary(String a, String b)  
2:       {  
3:       StringBuilder asb=new StringBuilder(a);  
4:       StringBuilder bsb=new StringBuilder(b);  
5:       StringBuilder resB=new StringBuilder();  
6:       int length=Math.max(asb.length(), bsb.length());  
7:       int i=0;  
8:       int carry=0;  
9:       int digit1=0;  
10:       int digit2=0;  
11:       int digit3=0;  
12:       String resC = null;  
13:       asb.reverse();  
14:       bsb.reverse();  
15:       while(i<length)  
16:       {  
17:        digit1=i<asb.length()?asb.charAt(i)-'0':0;  
18:        digit2=i<bsb.length()?bsb.charAt(i)-'0':0;;  
19:        digit3=digit1+digit2+carry;  
20:       switch(digit3)  
21:       {  
22:        case 0:resC="0";  
23:           carry=0;  
24:           break;  
25:        case 1:resC="1";  
26:           carry=0;  
27:           break;  
28:        case 2:resC="0";  
29:           carry=1;  
30:           break;  
31:        case 3:resC="1";  
32:           carry=1;  
33:           break;  
34:       }  
35:       resB.append(resC);  
36:       i++;  
37:       }  
38:       if(carry>0)  
39:            resB.append("1");  
40:       resB.reverse();  
41:       return resB.toString();  
42:       }  

Reference:

[1] http://n00tc0d3r.blogspot.com/2013/01/add-two-binary-numbers.html?q=add

Anagrams

Problem:

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

Note: All inputs will be in lower-case.

Analysis:
基本没有会的题，从现在开始把参考人的链接发出来。也算是尊重别人的劳动成果。
Use hashmap to group the anagrams.
1. Pick up a string and sort it.
2. Compare the sorted string with existing keys.
3. If key is there, add the unsorted string to the keys values.
    If key is not there, create new hashmap item.
4. Return string groups have size greater than 1.

Solution:

1:            HashMap<String,ArrayList<String>> anagrams= new HashMap<String, ArrayList<String>>();  
2:            ArrayList<String> result=new ArrayList<String>();  
3:            for(String str: strs)  
4:            {  
5:                 char[] chars=str.toCharArray();  
6:                 Arrays.sort(chars);  
7:                 String key=new String(chars);  
8:                 if(anagrams.containsKey(key))  
9:                      anagrams.get(key).add(str);  
10:                 else  
11:                 {  
12:                      ArrayList<String> temp=new ArrayList<String>();  
13:                      temp.add(str);  
14:                      anagrams.put(key, temp);  
15:                 }  
16:            }  
17:            for(ArrayList<String> group:anagrams.values())  
18:            {  
19:                 if(group.size()>1)  
20:                      result.addAll(group);  
21:            }  
22:            return result;  

Reference:
https://github.com/ahmetalpbalkan/leetcode-solutions/blob/master/Anagrams.java

Multiply Strings

Problem:

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

Analysis:
Step 1: Convert string to integer arrays. Note that the int of the char is acquired by char-'0'.
Step 2: Multiply the integer arrays into a combined one. res[i+j+1]+=n1[i]+n2[j].
Step 3: Convert array back to string.

LeetCode说我test case "0","0"没通过，明明在Eclipse通过了的，答案就""。不管了。

Solution:

1:  public static String multiplyString(String num1, String num2)  
2:       {                      
3:            if(num1.isEmpty()||num2.isEmpty()||num1=="0"||num2=="0")  
4:                 return "0";  
5:            int l1=num1.length();  
6:            int l2=num2.length();  
7:            int[] n1=new int[l1];  
8:            int[] n2=new int[l2];  
9:            int[] res=new int[l1+l2];  
10:            //Convert string to integer arrays. Note that the int of the char is acquired by char-'0'.  
11:            for(int i = 0;i<l1;i++)  
12:            {  
13:                 n1[i]=num1.charAt(i)-'0';  
14:            }  
15:            for(int i=0;i<l2;i++)  
16:            {  
17:                 n2[i]=num2.charAt(i)-'0';  
18:            }  
19:            //Multiply the integer arrays into a combined one.  
20:            for(int i=0;i<l1;i++)  
21:                 for(int j=0;j<l2;j++)  
22:                 {  
23:                      res[i+j+1]+=n1[i]*n2[j];  
24:                 }  
25:            //Convert array back to string  
26:            StringBuilder sb= new StringBuilder();  
27:            for(int i=0;i<l1+l2;i++)  
28:            {  
29:                 if(res[i]!=0)  
30:                      sb.append(res[i]);  
31:            }  
32:            return sb.toString();  
33:        }  

Count and Say

Problem:

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

Analysis:

反应太慢,大概花了3天才看懂题目什么意思。觉得怎么会那么诡异。其实就是2个digit一个pattern，第一个digit代表counter，第二个代表实际的digit。有2个1那么就是21。wiki上面有公式，但是看不懂。下面用英文清理一下思路，能用这个思路写代码。
1.Check the previous strings' consecutive digit, keep the count.
2.If the current digit is different than the previous digit

•    Push the counter and digit to the result string. 
•    Reset counter.

Solution:
（抄得别人代码）

1:  private static String countandSay(int n)  
2:       {  
3:            if (n<=0) return null;   
4:              StringBuilder res = new StringBuilder("1");   
5:              while (n-- > 1) {   
6:               StringBuilder temp = new StringBuilder();   
7:               int count = 1;   
8:               for (int i=1; i<res.length(); ++i) {   
9:                if (res.charAt(i) == res.charAt(i-1)) {   
10:                 count++;   
11:                } else {   
12:                 temp.append(count);   
13:                 temp.append(res.charAt(i-1));   
14:                 count = 1; // reset   
15:                }   
16:               }   
17:               temp.append(count);   
18:               temp.append(res.charAt(res.length()-1));   
19:               res = temp;   
20:              }   
21:              return res.toString();   
22:       }  

Substring with Concatenation of All Words

Problem:

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

Analysis:

一开始觉得非常复杂，找了几个别人的博客看。看了几天，没看懂。最后找到一个牛人的地址http://n00tc0d3r.blogspot.com/2013/06/substring-with-concatenation-of-all.html?view=classic 慢慢的就懂了。不过有些细节还是不太清楚，只有慢慢积累。

现在开始把代码写到Eclipse里面了。1.可以节约在LeetCode编码的时间. 2. LeetCode如果报错可以Debug。之前一旦LeetCode没通过要找n久的bug，效率实在太低。

时间和空间复杂度就暂时不讨论了，不懂。

Solution:

1:  public class Solution {  
2:   public ArrayList<Integer> findSubstring(String S, String[] L){  
3:         ArrayList<Integer> res=new ArrayList<Integer>();  
4:         if(S==null||L==null)  
5:              return res;  
6:         HashMap<String,Integer> words=new HashMap<String,Integer>();  
7:         int wordLen=L[0].length(),total=L.length;  
8:         for(String s:L)//Store all words to hashmap  
9:         {  
10:              if(words.containsKey(s))  
11:                   words.put(s, words.get(s)+1);  
12:              else  
13:                   words.put(s, 1);  
14:         }  
15:         for(int i=0;i<=S.length()-wordLen*total;i++)  
16:         {  
17:              HashMap<String,Integer> curWords=new HashMap<String,Integer>(words);  
18:              for(int j=i;j<=S.length()-wordLen && !curWords.isEmpty();j+=wordLen)  
19:              {  
20:                   String word=S.substring(j,j+wordLen);  
21:                   if(!curWords.containsKey(word))  
22:                        break;  
23:                   else  
24:                   {  
25:                        if(curWords.get(word)>1)  
26:                             curWords.put(word, curWords.get(word)-1);  
27:                        else  
28:                             curWords.remove(word);  
29:                   }  
30:              }  
31:              if(curWords.isEmpty())  
32:                   res.add(i);  
33:         }  
34:       return res;  
35:    }  
36:  }  

Generate Parentheses

Problem:

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:

"((()))", "(()())", "(())()", "()(())", "()()()"

Analysis:
DFS

Solution:

1:  public class Solution {  
2:    public ArrayList<String> generateParenthesis(int n) {  
3:      ArrayList<String> result=new ArrayList<String>();  
4:      DoDSF("",n,n,result);  
5:      return result;  
6:    }  
7:    private void DoDSF(String prefix, int left, int right, ArrayList<String> result)  
8:    {  
9:      if(left==0&& right==0)  
10:      {  
11:        result.add(prefix);  
12:        return;  
13:      }  
14:      if(left!=0)  
15:       DoDSF(prefix+"(",left-1,right,result);  
16:      if(left<right)  
17:        DoDSF(prefix+")",left,right-1,result);  
18:       return;  
19:    }  
20:  }  

Valid Parentheses

Problem:

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Analysis:
Use stack and hashmap. Stack makes sure there is always "(" in front of ")", otherwise the string is not valid.

看了几天简单的算法看不懂。昨天找到一种笨方法，就是照着打，估计多打几遍就好了。

Solution:

1:  public class Solution {  
2:    public boolean isValid(String s) {  
3:      char[] chars=s.toCharArray();  
4:      HashMap<Character, Character> map=new HashMap<Character,Character>();  
5:      map.put('(', ')');  
6:          map.put('[', ']');  
7:         map.put('{', '}');  
8:         Stack<Character> stack = new Stack<Character>();  
9:         for(Character c: chars)  
10:         {  
11:           if(map.keySet().contains(c))  
12:            stack.push(c);  
13:           else if(map.values().contains(c))  
14:           {  
15:             if(!stack.isEmpty()&&map.get(stack.peek())==c)  
16:               stack.pop();  
17:             else   
18:             return false;  
19:           }  
20:         }  
21:         return stack.isEmpty();  
22:    }  
23:  }  

Longest Common Prefix

Problem:
Write a function to find the longest common prefix string amongst an array of strings.

Analysis:
Starting from the first char of the first string comparing with the rest. Leetocde 出问题了，strs.length()通不过。

Solution:

1:  public class Solution {  
2:    public String longestCommonPrefix(String[] strs) {  
3:      if(strs.length()==0)  
4:       return "";  
5:      if(strs==null)  
6:       return null;  
7:      String str0=strs[0];   
8:      for(int prefixLen=0;prefixLen<str0.length;prefixLen++)  
9:      {  
10:        char c=str0.charAt(prefixLen);  
11:        for(int j=1;j<strs.length();j++)  
12:        {  
13:          if(strs[j].length()<=prefixLen||strs[j].charAt(prefixLen)!=c)  
14:           return str0.substring(0,prefixLen);  
15:        }  
16:      }  
17:      return str0;  
18:    }  
19:  }  

Longest Palindromic Substring

Problem:

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Analysis:

Check: http://stevekrenzel.com/articles/longest-palnidrome

Solution:

1:  public class Solution {  
2:    public String longestPalindrome(String s) {  
3:      if(s==null)  
4:      return null;  
5:      if(s.length()==1)  
6:      return s;  
7:      String result="";  
8:      for(int i=0;i<s.length();i++)  
9:      {  
10:       String temp1=getPalindrome(s,i,i);  
11:       if(temp1.length()>=result.length())  
12:       {  
13:         result=temp1;  
14:       }  
15:       String temp2=getPalindrome(s,i,i+1);  
16:        if(temp2.length()>=result.length())  
17:       {  
18:         result=temp2;  
19:       }  
20:      }  
21:      return result;  
22:    }  
23:    private String getPalindrome(String s, int begin, int end)  
24:    {  
25:      while(begin>=0&&end<s.length()&&s.charAt(begin)==s.charAt(end))  
26:      {  
27:        begin--;  
28:        end++;  
29:      }  
30:      return s.substring(begin+1,end);  
31:    }  
32:  }  

ZigZag Conversion

Problem:

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

Analysis:
For the first and the last rows, the period between tow items is 2nRow-2(Step). For other rows, the period changes after every step. The first period is 2(nRows-1-rowIndex)(Step1), the second period is Step-Step1. 

Solution:

1:  public class Solution {  
2:    public String convert(String s, int nRows) {  
3:      if(nRows==1)  
4:       return s;  
5:      StringBuilder sb=new StringBuilder();   
6:      int step=2*nRows-2;//the period on the first and the last rows  
7:      for(int i=0;i<nRows;i++)  
8:      {  
9:        if(i==0 || i==nRows-1)//first row or last row  
10:        {  
11:         for(int j=i;j<s.length();j+=step)  
12:         {  
13:           sb.append(s.charAt(j));  
14:         }  
15:        }  
16:        else  
17:        {  
18:          int j=i;  
19:          int substep=2*(nRows-1-i);  
20:          while(j<s.length())  
21:          {  
22:            sb.append(s.charAt(j));  
23:            j+=substep;  
24:            substep=step-substep;    
25:          }  
26:        }  
27:      }  
28:      return sb.toString();  
29:    }  
30:  }  

Add Two Numbers

Problem:

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

Analysis:
Need to create a new ListNode other than the returned one. Because each iteration would cause the new ListNode point to its next node, keep the head is necessary.

Solution:

1:  /**  
2:   * Definition for singly-linked list.  
3:   * public class ListNode {  
4:   *   int val;  
5:   *   ListNode next;  
6:   *   ListNode(int x) {  
7:   *     val = x;  
8:   *     next = null;  
9:   *   }  
10:   * }  
11:   */  
12:  public class Solution {  
13:    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {  
14:      int carry=0;  
15:      ListNode result=new ListNode(0);  
16:      ListNode l3=result;  
17:      while(l1!=null || l2!=null)  
18:      {  
19:        if(l1!=null)  
20:        {  
21:          carry+=l1.val;  
22:          l1=l1.next;  
23:        }  
24:        if(l2!=null)  
25:        {  
26:          carry+=l2.val;  
27:          l2=l2.next;  
28:        }  
29:        l3.next=new ListNode(carry%10);  
30:        carry/=10;  
31:        l3=l3.next;  
32:      }  
33:      if(carry==1)  
34:      {  
35:       l3.next=new ListNode(1);    
36:      }  
37:      return result.next;  
38:    }  
39:  }  

Two Sum

Problem:

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Solution:

1:  public class Solution {  
2:    public int[] twoSum(int[] numbers, int target) {  
3:      HashMap<Integer,Integer> map= new HashMap<Integer,Integer>();  
4:      int[] result=new int[2];  
5:      for(int i=0;i<numbers.length;i++)  
6:        {  
7:          if(map.containsKey(numbers[i]))  
8:         {  
9:           int index=map.get(numbers[i]);  
10:           result[0]=index+1;  
11:           result[1]=i+1;  
12:           break;  
13:         }   
14:         else  
15:          map.put(target-numbers[i],i);  
16:        }  
17:       return result;  
18:    }  
19:  }  

String to Integer (atoi)

Problem:

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Requirements for atoi:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

Analysis:

1. The initial plus or minus sign is optional.. 

2. When encounter a non digit character, ignore the rest of the string.

3. When converts char to int, use str.charAt(i)-'0'. The difference of the unicodes. 

4. Need to check integer overflow before add up to the next digit. 

Solution:

1:  public class Solution {  
2:    public int atoi(String str) {  
3:      int i=0;//the counter  
4:      boolean isNeg=false;  
5:      int result=0;  
6:      if(str==null || str.length()<1)  
7:       return 0;  
8:      str=str.trim(); //Elimilate spaces   
9:      if(str.charAt(i)=='-')  
10:      {  
11:        isNeg=true;  
12:        i++;  
13:      }  
14:      else if(str.charAt(i)=='+')  
15:      {  
16:        i++;  
17:      }  
18:      while(i<str.length()&& str.charAt(i) >= '0' && str.charAt(i) <= '9') {  
19:        //Check overflow  
20:      if(Integer.MAX_VALUE/10<result||Integer.MAX_VALUE/10==result&&Integer.MAX_VALUE%10<(str.charAt(i) - '0'))  
21:       return isNeg==false?Integer.MAX_VALUE:Integer.MIN_VALUE;  
22:            result = result * 10 + (str.charAt(i) - '0');  
23:            i++;  
24:      }  
25:     return isNeg==false?result:-result;  
26:    }  
27:  }  

Roman to Integer

Problem:

Given a roman numeral, convert it to an integer.

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

Analysis:

The tricky in this problem is that Symbols are placed from left to right in order of value, starting with the largest. However, in a few specific cases, to avoid four characters being repeated in succession (such as IIII or XXXX) these can be reduced using subtractive notation as follows:

• the numeral I can be placed before V and X to make 4 units (IV) and 9 units (IX respectively)
• X can be placed before L and C to make 40 (XL) and 90 (XC respectively)
• C can be placed before D and M to make 400 (CD) and 900 (CM) according to the same pattern

An example using the above rules would be 1904: this is composed of 1 (one thousand), 9 (nine hundreds), 0 (zero tens), and 4 (four units). To write the Roman numeral, each of the non-zero digits should be treated separately. Thus 1,000 = M, 900 = CM, and 4 =IV. Therefore, 1904 is MCMIV.

The solution is that add up every character, if the previous character is smaller than the  current character then subtract the previous character twice. 

Solution:

1:  public class Solution {  

2:    public int romanToInt(String s) {  

3:      if(s==null) return 0;  

4:      if(s.length()==1) return getInt(s.charAt(0));  

5:      int pre=s.charAt(0);  

6:      int cur=0;  

7:      int total=s.charAt(0);  

8:      for(int i=1;i<s.length();i++)  

9:      {  

10:        cur=getInt(s.charAt(i));  

11:        total+=cur;  

12:        if(pre<cur)  

13:          total=total-pre*2;  

14:        pre=cur;  

15:      }  

16:      return total;  

17:    }  

18:    public int getInt(char digit)  

19:    {  

20:      int result=0;  

21:      switch (digit)  

22:      {  

23:        case 'I': result=1; break;  

24:        case 'V': result=5; break;  

25:        case 'X': result=10;break;  

26:        case 'L': result=50;break;  

27:        case 'C': result=100;break;  

28:        case 'D': result=500;break;  

29:        case 'M': result=1000;break;  

30:      }  

31:      return result;  

32:    }  

33:  }  

Reference:
http://en.wikipedia.org/wiki/Roman_numerals

Climbing Stairs

Problem:

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Analysis:

Recursive solution is slow and could not pass online judge because time limit exceeded. But I don't familiar with dynamic programming right now.

Solution:

1:  public class Solution {  
2:    public int climbStairs(int n) {  
3:      if(n==1) return 1;  
4:      if(n==2) return 2;  
5:      return climbStairs(n-1)+climbStairs(n-2);  
6:    }  
7:  }  

Search Insert Position

Problem:

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

Analysis:

A typical binary search problem. 

Solution:

1:  public class Solution {  
2:    public int searchInsert(int[] A, int target) {  
3:      int high=A.length-1;  
4:      int low=0;  
5:      int mid=(high+low)/2;  
6:      while(low <=high)  
7:      {  
8:        mid=(high+low)/2;  
9:        if(target==A[mid])  
10:          return mid;  
11:        if(target>A[mid])  
12:          low=mid+1;  
13:        else  
14:          high=mid-1;  
15:      }  
16:      return low;  
17:    }  
18:  }  

Populating Next Right Pointers in Each Node

Problem:

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

Analysis:
The first thought occurs to me is the level order traversal, but this problem requires constant space. Level order traversal requires a queue. The recursive method is fast and easy to under stand. Let's assume that the current node is connected with its next node. Its left child's next node is its right child. Its right child's next node is its next node's left child. The space is O(N).

Solution:

1:  /**  
2:   * Definition for binary tree with next pointer.  
3:   * public class TreeLinkNode {  
4:   *   int val;  
5:   *   TreeLinkNode left, right, next;  
6:   *   TreeLinkNode(int x) { val = x; }  
7:   * }  
8:   */  
9:  public class Solution {  
10:    public void connect(TreeLinkNode root) {  
11:      if(root==null)  
12:       return;  
13:      if(root.left!=null)  
14:       root.left.next=root.right;  
15:      if(root.right!=null)  
16:       root.right.next=root.next==null?null:root.next.left;  
17:      connect(root.left);  
18:      connect(root.right);  
19:    }  
20:  }  

Binary Tree Level Order Traversal

Problem:

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

Analysis:
Method 1:
Use two queues. One to record the current level, the other keeps record of the next level. Iterate the current level add the children of each nodes in current level to the next level queue. After the current level queue becomes empty, assign the next level to current level.

Method 2:
Use one queue. Use two counters, one counts the current level number of nodes the other counts the next level number of nodes. Each time remove from the linked list, current level number of nodes decrease and add next level number of nodes accordingly.  When current level counter reaches 0, add current level to the final ArrayList. Then next level counter becomes current level counter. Have to note that the ArrayList is the reference type in Java, if clear the ArraryList<Integer> after adding it to the ArraryList<ArraryList<Integer>> then reuse it, it would clear what's inside the ArraryList<ArraryList<Integer>>. So I created another instance every time current level nodes reaches 0.

Solution:
1. Two Queues

1:  /**  
2:   * Definition for binary tree  
3:   * public class TreeNode {  
4:   *   int val;  
5:   *   TreeNode left;  
6:   *   TreeNode right;  
7:   *   TreeNode(int x) { val = x; }  
8:   * }  
9:   */  
10:  public class Solution {  
11:    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {  
12:      ArrayList<ArrayList<Integer>> alResult=new ArrayList<ArrayList<Integer>>();  
13:      if(root==null)  
14:        return alResult;  
15:      LinkedList<TreeNode> currLevel=new LinkedList<TreeNode>();  
16:      currLevel.add(root);  
17:      while(!currLevel.isEmpty())  
18:      {  
19:        ArrayList<Integer> alLevel=new ArrayList<Integer>();  
20:        LinkedList<TreeNode> nextLevel=new LinkedList<TreeNode>();  
21:        while(!currLevel.isEmpty())  
22:        {  
23:          TreeNode currNode=currLevel.remove();  
24:          alLevel.add(currNode.val);  
25:          if(currNode.left!=null) nextLevel.add(currNode.left);  
26:          if(currNode.right!=null) nextLevel.add(currNode.right);  
27:        }  
28:        currLevel=nextLevel;  
29:        alResult.add(alLevel);  
30:      }  
31:      return alResult;  
32:    }  
33:  }  

2. One queue

1:  /**  
2:   * Definition for binary tree  
3:   * public class TreeNode {  
4:   *   int val;  
5:   *   TreeNode left;  
6:   *   TreeNode right;  
7:   *   TreeNode(int x) { val = x; }  
8:   * }  
9:   */  
10:  public class Solution {  
11:    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {  
12:      ArrayList<ArrayList<Integer>> alResult=new ArrayList<ArrayList<Integer>>();  
13:      ArrayList<Integer> alLevel=new ArrayList<Integer>();  
14:      LinkedList<TreeNode> currLevel=new LinkedList<TreeNode>();  
15:      if(root==null)  
16:        return alResult;  
17:      int curr=1;  
18:      int next=0;  
19:      currLevel.add(root);  
20:      while(!currLevel.isEmpty())  
21:      {  
22:        TreeNode currNode=currLevel.remove();  
23:        curr--;  
24:        alLevel.add(currNode.val);  
25:        if(currNode.left!=null)   
26:        {  
27:          currLevel.add(currNode.left);  
28:          next++;  
29:        }  
30:        if(currNode.right!=null)   
31:        {  
32:          currLevel.add(currNode.right);  
33:          next++;  
34:        }  
35:        if(curr==0)  
36:        {  
37:          curr=next;  
38:          next=0;  
39:          alResult.add(alLevel);  
40:          ArrayList<Integer> alLevelTemp=new ArrayList<Integer>();  
41:          alLevel=alLevelTemp;  
42:        }  
43:      }  
44:      return alResult;  
45:    }  
46:  }  

Binary Tree Postorder Traversal

Problem:

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

Analysis:
The most difficult one among preorder, inorder and postorder traversals. The difficulty lays in that after going down to left it will go right, storing the parent node is a problem. Use one more stack to assist push nodes in reserve order of postorder to the final stack.
Steps:
1.Push the root node to the temp stack.
2.Pop node c from temp stack.
3.If c has left child push it to final stack.If c has right child push it to final stack.
4.Push c to final stack.
5.Repeat 2-4 until temp stack is empty.
6.Print final stack.

Solution:

1:  /**  
2:   * Definition for binary tree  
3:   * public class TreeNode {  
4:   *   int val;  
5:   *   TreeNode left;  
6:   *   TreeNode right;  
7:   *   TreeNode(int x) { val = x; }  
8:   * }  
9:   */  
10:  public class Solution {  
11:    public ArrayList<Integer> postorderTraversal(TreeNode root) {  
12:      ArrayList<Integer> result=new ArrayList<Integer>();  
13:      if(root==null)  
14:       return result;  
15:      Stack<TreeNode> t=new Stack<TreeNode>();//temp stack   
16:      Stack<TreeNode> r=new Stack<TreeNode>();//result stack  
17:      t.push(root);  
18:      while(!t.isEmpty())  
19:      {  
20:       TreeNode current=t.pop();  
21:        if(current.left!=null) t.push(current.left);  
22:        if(current.right!=null) t.push(current.right);  
23:        r.push(current);  
24:      }  
25:      while(!r.isEmpty())  
26:      {  
27:       TreeNode current=r.pop();  
28:        result.add(current.val);  
29:      }  
30:      return result;  
31:    }  
32:  }  

Binary Tree Inorder Traversal

Problem:

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

Analysis:

The definition of inorder traversal is visit the left node first, the parent node second and the right node last. Iterative implementation of inorder traversal is more difficult than preorder traversal. We need to consider how to visit the left most node and keep track of the trace.

1. Push the root node to the stack.

2. Set the left child of the current node to the current node.

3. Continue 1,2 until current node is null.

4. If current node is not null.

   1). Pop current node from the stack and write it.

   2). Set the right child of the current node to the current node. go to 2.

5. If the stack is empty return. 

Solution:

1:  /**  
2:   * Definition for binary tree  
3:   * public class TreeNode {  
4:   *   int val;  
5:   *   TreeNode left;  
6:   *   TreeNode right;  
7:   *   TreeNode(int x) { val = x; }  
8:   * }  
9:   */  
10:  public class Solution {  
11:    public ArrayList<Integer> inorderTraversal(TreeNode root) {  
12:      ArrayList<Integer> result=new ArrayList<Integer>();  
13:      if(root==null)  
14:       return result;  
15:      Stack<TreeNode> stack=new Stack<TreeNode>();  
16:      TreeNode current=root;  
17:      while(true)  
18:      {  
19:        if(current!=null)//iterate left until there is no left node at all       
20:        {  
21:         stack.push(current);  
22:         current=current.left;  
23:        }  
24:        else  
25:        {  
26:          if(!stack.isEmpty())  
27:          {  
28:            current=stack.pop();  
29:            result.add(current.val);  
30:            current=current.right;//have visited the left and the parent node, time to visit the right one.  
31:          }  
32:          else  
33:           break;  
34:        }  
35:      }  
36:      return result;  
37:    }  
38:  }