2018年7月11日星期三

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 

2015年9月8日星期二

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. 

2015年7月9日星期四

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

2015年5月7日星期四

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

2014年11月11日星期二

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

2014年10月29日星期三

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:


2014年10月27日星期一

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

2014年10月23日星期四

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

2014年10月2日星期四

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

2014年9月26日星期五

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

2014年9月19日星期五

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

2014年9月17日星期三

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

2014年9月15日星期一

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

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