2014年9月11日星期四

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:

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:  }  

2014年9月3日星期三

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:  }  

2014年7月17日星期四

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:  }  

2014年7月14日星期一

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:  }  

2014年7月8日星期二

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:  }  

2014年4月21日星期一

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

2014年4月16日星期三

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:  }