Three Sum

Problem:

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

Analysis:

1. Sort the array

2. Set lower boundary left

3. Set upper boundary right

4. check sum of num[left],num[i] and num[right]

5. if greater than 0, move 

Remove Element

Problem:
Given an array and a value, remove all instances of that value in place and return the new length. The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Analysis:
It's simple, just replace the give value with the last item in the array. 

Search in Rotated Sorted Array

好无聊啊，只有刷题玩玩，让大脑充实一些。有时候刷题不要死脑经去搞懂最基本的东西，能用就行。其实这道题的核心就是找target， 如果target不在搜索区间内就换。

 public class SearchinRotatedSortedArray {  
   public static int search(int A[], int n, int target)  
   {  
     int first=0;  
     int last=n;  
     int mid=0;  
     while(first!=last)  
     {  
       mid=(first+last)/2;  
       if(A[mid]==target)  
         return mid;  
       if(A[first]<=A[mid])  
       {  
         if(A[first]<=target && target<A[mid])  
           last=mid;  
         else  
           first=mid+1;  
       }  
       else  
         if(A[mid]<target && target<=A[last-1])  
           first=mid+1;  
         else  
           last=mid;  
     }  
     return -1;  
   }  
 }  

Compare Version Numbers

Problem:

Compare two version numbers version1 and version2.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:

0.1 < 1.1 < 1.2 < 13.37

Analysis:

Use string.split method. Split the string into two arrays by '.'.

Solution:

1:  public static int CompareVersion(string version1, string version2)  
2:      {  
3:        string[] v1 = version1.Split('.');  
4:        string[] v2 = version2.Split('.');  
5:        int longest = v1.Length > v2.Length ? v1.Length : v2.Length;  
6:        for(int i=0;i<longest;i++)  
7:        {  
8:          int ver1 = i < v1.Length ? int.Parse(v1[i]) : 0;  
9:          int ver2 = i < v2.Length ? int.Parse(v2[i]) : 0;  
10:          if (ver1 > ver2) return 1;  
11:          if (ver1 < ver2) return -1;  
12:        }  
13:        return 0;  
14:      }  

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