Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

Solution: using a stack to match the '(' and ')' pairs, and use a hashtable to store these pairs. later, given a left parentheses, with the help of the hash table, you can find the furthest match ')' parentheses.

Java语言: LongestValidParentheses

01 public int longestValidParentheses(String s) {
02     //store the left parentheses
03     Stack<Integer> st=new Stack<Integer>();
04     //store the left, right pairs of parentheses
05     Hashtable<Integer, Integer> matches=new Hashtable<Integer,Integer>();
06     int length=0;
07     int max=0;
08     for(int i=0;i<s.length();i++)
09     {
10         if(s.charAt(i)=='(' )
11         {
12             st.push(i);
13         }
14         if(s.charAt(i)==')')
15         {
16             if(st.size()==0)
17             {
18                 continue;
19             }
20             else
21             {
22                 int left=st.pop();
23                 matches.put(left,i);
24             }
25         }
26     }
27   
28     for(int i=0;i<s.length();i++)
29     {
30         if(matches.containsKey(i))
31         {
32             int value=matches.get(i);
33             while(matches.containsKey(value+1))
34             {
35                 value=matches.get(value+1);
36             }
37             length=value-i+1;
38             if(length>max)
39             {
40                 max=length;
41             }
42         }
43     }
44   
45     return max;
46 }

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Solution: use two hash tables to map a number to its longest sequence starting and ending at this number. Update the entries when you find numbers which are one more or one less than the current number in the table. Update the length of the interval as max.

Java语言: Longest Consecutive Sequence

01 public int longestConsecutive(int[] num) {
02     if(num.length<=1)
03         return num.length;
04     int max=1;
05     //Maps this number to the sequence start by this value;
06     Hashtable<Integer,Integer> start=new Hashtable<Integer,Integer>();
07     //Maps this number to the sequence end by this value;
08     Hashtable<Integer,Integer> end=new Hashtable<Integer,Integer>();
09     for(int i=0;i<num.length;i++)
10     {
11         //skip the number that has already seen
12         if(start.containsKey(num[i]))
13             continue;  
14       
15         start.put(num[i],1);
16         end.put(num[i],1);
17 
18         int lowerBound=num[i];          
19         int upperBound=num[i];
20       
21         //check the interval ending by its prev number
22         //get the lower bound that can be reached from the current  number
23         if(end.containsKey(num[i]-1))
24         {
25             lowerBound=num[i]-1-end.get(num[i]-1)+1;
26           
27         }
28         //check the interval starting from its next number
29         //get the upper bound that can be reached from the current number
30         if(start.containsKey(num[i]+1))
31         {
32             upperBound=num[i]+1+start.get(num[i]+1)-1;
33           
34         }
35         //update the interval
36         int range=upperBound-lowerBound+1;          
37         start.put(lowerBound, range);
38         end.put(upperBound, range);
39       
40         if(range>max)
41             max=range;          
42     }
43     return max;
44 }

Letter Combination of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Hint: the first question is, how do we store and find the letters that can be represented by a digit? Using hashtable!

The second question, how can we enumerate all combinations? For example, the imput String is "23". Look at digit 2, we could have this position be a or b or c. 

a
b
c

Then we come to digit 3, we can have it as d, e, f. What we should do? We should append the letter after the previous position which we have already solved. Right?

ad
ae
af
bd
be
bf
...

Therefore, we should enumerate the letters at the current digit repeatedly, put one to the current position, then we call the same function recursively at the next position.

01 public ArrayList<String> letterCombinations(String digits) {
02     char [] input=digits.toCharArray();
03     ArrayList<String> results=new ArrayList<String>();
04     char [] output=new char[input.length];
05 
06   //use a hashtable to map the keyboard to the letters
07     Hashtable<Character,String> ht=new Hashtable<Character,String>();
08     ht.put('2',"abc");
09     ht.put('3',"def");
10     ht.put('4',"ghi");
11     ht.put('5',"jkl");
12     ht.put('6',"mno");
13     ht.put('7',"pqrs");
14     ht.put('8',"tuv");
15     ht.put('9',"wxyz");
16     doCombine(ht, 0, input, output, results);
17     return results;
18 }
19 
20 public void doCombine(Hashtable<Character,String>ht, int pos, char [] input, char[] output, ArrayList<String> results)
21 {
22   //reach the last index, then output
23     if(pos==input.length)
24     {
25         String outStr=new String(output);
26         results.add(outStr);
27         return;
28     }
29   
30     char c=input[pos];
31     if(!ht.containsKey(c))
32     {
33         return;
34     }
35     String str=ht.get(c);
36     char [] c_str=str.toCharArray();
37   //repeatedly assign all letters that can be represented by the current digit
38     for(int i=0;i<c_str.length;i++)
39     {
40         output[pos]=c_str[i];
41     
42       //call the function recursively to the next digit
43         doCombine(ht,pos+1,input,output,results);
44     }
45 }

Two Sum

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

01 public int[] twoSum(int[] numbers, int target) {
02     int[] results=new int[2];
03     HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
04     for(int i=0; i<numbers.length;i++)
05     {
06         hm.put(numbers[i],i);
07     }
08   
09     for (int i=0;i<numbers.length;i++)
10     {
11         int key= target - numbers [i];
12         if(hm.containsKey(key))
13         {
14             int indx2=hm.get(key);
15             if(i<indx2)
16             {
17                 results[0]=i+1;
18                 results[1]=indx2+1;
19             }
20         }
21     }
22     return results;
23 }

Anagrams

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

Note: All inputs will be in lower-case.

01 public ArrayList<String> anagrams(String[] strs) {
02     Hashtable <ArrayList<Integer>,String> ht=new Hashtable<ArrayList<Integer>,String>();
03     ArrayList<String> result=new ArrayList<String>();
04     for(int i=0;i<strs.length;i++)
05     {
06         ArrayList<Integer> al=new ArrayList<Integer> ();
07         int[] str_array=new int[26];
08         for(int k=0;k<26;k++)
09             str_array[k]=0;
10         char[] str_char_array=strs[i].toCharArray();
11         for(int j=0;j<str_char_array.length;j++)
12         {
13             int index=(int) (str_char_array[j]-'a');
14             str_array[index]++;
15         }
16         for(int k=0;k<26;k++)
17         {
18             al.add(str_array[k]);              
19         }                      
20         if(!ht.containsKey(al))
21         {
22             ht.put(al,strs[i]);              
23         }
24 
25         else
26         {              
27             String s=ht.get(al);              
28             if(!result.contains(s))
29             {
30                 result.add(s);
31             }              
32             result.add(strs[i]);              
33         }
34     }
35     return result;
36 }

Substring with Concatenation of All Words

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




Java: Substring with Concatenation of All Words

public ArrayList<Integer> findSubstring(String S, String[] L) {
   ArrayList<Integer> result=new ArrayList<Integer>();
   Hashtable<String,Integer>ht=new Hashtable<String,Integer>();
   for(int i=0;i<L.length;i++)
   {
       if(!ht.containsKey(L[i]))
       {
           ht.put(L[i],1);
       }
   }
   int len=L[0].length();              
   int totalLen=L.length*len;
   int start=0;
   while(start+totalLen<=S.length())
   {
       String tempStr=S.substring(start,start+totalLen);
       String starter=tempStr.substring(0,len);
       if(!ht.containsKey(starter))
       {
           start++;
           continue;
       }
                 
       String[] strs=new String[L.length];  
       ArrayList<String>show=new ArrayList<String>();
       for(int i=0;i+len<=totalLen;i=i+len)
       {
           strs[i/len]=tempStr.substring(i,i+len);
           show.add(strs[i/len]);
       }
       for(int j=0;j<L.length;j++)
       {
           if(show.contains(L[j]))
               show.remove(L[j]);
           else
               break;
       }
       if(show.isEmpty())
       {
           result.add(start);
           start=start+len;
       }
       else
       {              
           start++;            
       }                  
   }
 
   return result;
}

Roman to Integer

This problem, in contrast to the previous one, convert a roman number back to an integer, and is not that straightforward. The main idea is to group the roman characters together which can be convert to a valid integer.

The main idea is to group the roman characters properly. This requires a careful manipulation of strings. Also, a hash table is needed for look-up.

Java: Roman to Integer

001 public int romanToInt(String s) {
002     String[]digits={"I","II","III","IV","V","VI","VII","VIII","IX"};
003     String[]tens={"X","XX","XXX","XL","L","LX","LXX","LXXX","XC"};
004     String[]hundreds={"C","CC","CCC","CD","D","DC","DCC","DCCC","CM"};
005     String[]thousands={"M","MM","MMM"};
006   
007     Hashtable<String,Integer> ht=new Hashtable<String,Integer>();
008 
009     for(int i=0;i<3;i++)
010     {
011         ht.put(thousands[i],(i+1)*1000);
012     }
013   
014     for(int i=0;i<9;i++)
015     {
016         ht.put(hundreds[i],(i+1)*100);
017     }
018   
019     for(int i=0;i<9;i++)
020     {
021         ht.put(tens[i],(i+1)*10);
022     }
023   
024     for(int i=0;i<9;i++)
025     {
026         ht.put(digits[i],i+1);
027     }
028   
029     int result=0;
030   
031     char[] str=s.toCharArray();
032     int i=0;
033     int start=0;
034   
035     if(str[i]=='M')
036     {
037         while(str[i]=='M' )
038         {
039             i++;
040             if(i==str.length)
041             {
042                 break;
043             }                                  
044         }
045       
046         if(i>start)
047         {
048             int thousand=ht.get(s.substring(start,i));
049             result+=thousand;
050             start=i;
051         }          
052     }
053   
054     if(i<str.length && (str[i]=='C'||str[i]=='D'))
055     {
056         while(str[i]=='C'||str[i]=='D'||str[i]=='M')
057         {
058             i++;
059             if (i==str.length)
060             {
061                 break;
062             }              
063         }
064       
065         if(i>start)
066         {
067             int hundred=ht.get(s.substring(start,i));
068             result+=hundred;
069             start=i;
070         }          
071     }
072   
073     if(i<str.length && (str[i]=='X'||str[i]=='L'))
074     {
075         while(str[i]=='X'||str[i]=='L'||str[i]=='C')
076         {
077             i++;
078             if (i==str.length)
079             {
080                 break;
081             }              
082         }
083       
084         if(i>start)
085         {
086             int ten=ht.get(s.substring(start,i));
087             result+=ten;
088             start=i;
089         }
090       
091     }
092   
093     while(i<str.length)
094     {
095         i++;
096     }
097     if(i>start)
098     {
099         int digit=ht.get(s.substring(start,i));
100         result+=digit;
101     }
102                 
103     return result;
104 }