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