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:

[1] http://n00tc0d3r.blogspot.com/2013/01/add-two-binary-numbers.html?q=add

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

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

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