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