Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

This is an implementation of Fibonacci numbers.
The recursion method is easy. The iterative one is challenging.

01 public int climbStairs(int n) {
02     if(n==0 || n==1)
03         return 1;
04     int x=1;
05     int y=1;
06     while(--n>0)
07     {
08         int temp=x+y;
09         x=y;
10         y=temp;
11     }      
12     return y;
13 }

Pow(x, n)

Implement pow(x, n).
Tips:
1. Use divide and conquer.
2. Powers can be negative. Always remember this.
3. Try to reduce the times of multiplication as many as possible.

01 public double pow(double x, int n) {
02     if(n==0)
03         return 1;
04     if(n==1)
05         return x;
06   
07     boolean isNegative=false;
08     if(n<0)
09     {
10         n=-n;
11         isNegative=true;
12     }
13   
14     double result=pow(x,n/2);
15     result=result*result;
16     if(n%2==1)
17         result*=x;
18     if(isNegative)
19         result=1/result;
20     return result;
21 }

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 }

Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

01 public void merge(int A[], int m, int B[], int n) {
02     int lastA=m-1;
03     int lastB=n-1;
04     int last=m+n-1;
05   
06     while(lastA>=0 && lastB>=0)
07     {
08         if(A[lastA]>=B[lastB])
09         {
10             A[last]=A[lastA];
11             lastA--;
12             last--;
13         }
14         else
15         {
16             A[last]=B[lastB];
17             lastB--;
18             last--;
19         }
20       
21     }
22 
23     while(lastB>=0)
24     {
25         A[last]=B[lastB];
26         lastB--;
27         last--;
28     }
29 }

Remove Nth Node from End of List

Given a linked list, remove the n^th node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

The key idea is to find the Nth node to the end of the list. Then the remaining things are easy. If we want to solve it in one pass, we should not use only one pointer. Therefore, we use two pointers, one moves earlier, which can reach the end of the list first, after n steps. Then the other starts to move.

01 public ListNode removeNthFromEnd(ListNode head, int n) {
02         if(n==0 || head==null)
03             return head;
04         ListNode fast=head;
05         while(n>0 && fast!=null)
06         {
07             fast=fast.next;
08             n--;
09         }
10         if(fast==null)
11         {
12             return head.next;
13         }
14         ListNode slow=head;
15         ListNode curr=slow;
16         while(fast!=null && fast.next!=null)
17         {
18             fast=fast.next;
19             curr=curr.next;
20         }
21         curr.next=curr.next.next;
22         return slow;
23     }

Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

The idea is to find the start node of the notation, the new head. This is done by counting the nodes until k. Note: Don't forget that k might be larger than the number of nodes in the linked list. If so, we need to use  the remainder of the mod of the length of the linked list, instead of k itself.

01 public ListNode rotateRight(ListNode head, int n) {
02     int len=0;
03     ListNode node=head;
04     //calculate length
05     while(node!=null)
06     {
07         len++;
08         node=node.next;
09     }
10     if(len<=1)
11         return head;
12     n=n%len;
13     if(n==0)
14         return head;
15   
16     ListNode first=head;
17     while(n-->0)
18     {
19         first=first.next;
20     }
21   
22     ListNode second=head;
23   
24     while(first!=null && first.next!=null)
25     {
26         first=first.next;
27         second=second.next;
28     }
29   
30     ListNode newHead=second.next;
31     second.next=null;
32     first.next=head;  
33     return newHead;      
34 }

Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

01 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
02     if(l1==null)
03         return l2;
04     if(l2==null)
05         return l1;
06     ListNode head=null;
07     ListNode curr=null;
08     while(l1!=null && l2!=null)
09     {
10         ListNode small=(l1.val<l2.val)?l1:l2;
11         if(head==null)
12         {
13             head=small;
14             curr=head;
15         }
16         else
17         {
18             curr.next=small;
19             curr=curr.next;
20         }
21       
22         if(small==l1)
23         {
24             l1=l1.next;
25         }
26         else
27         {
28             l2=l2.next;
29         }
30     }
31     if(l1!=null)
32     {
33         curr.next=l1;
34     }
35     if(l2!=null)
36     {
37         curr.next=l2;
38     }
39   
40     return head;
41 }

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 }

Add Binary

Given two binary strings, return their sum (also a binary string).

For example,

a = "11"

b = "1"

Return "100".

Remember the carry all the time!

01 public String addBinary(String a, String b) {
02     char []charA=a.toCharArray();
03     int lastA=charA.length-1;
04     char [] charB=b.toCharArray();
05     int lastB=charB.length-1;
06   
07     int len=lastA+1;
08     if(lastA<lastB)
09     {
10         len=lastB+1;
11     }
12     char[] results=new char[len+1];
13     int last=len;
14     int temp=0;
15     int sum=0;
16     int carrier=0;
17   
18     while(lastA>=0 && lastB >=0)
19     {
20         int digitA=charA[lastA]-'0';
21         int digitB=charB[lastB]-'0';
22         sum=digitA+digitB+carrier;
23         temp=sum%2;
24         carrier=sum/2;
25         results[last]=(char)(temp+'0');
26         lastA--;
27         lastB--;
28         last--;
29     }
30     while(lastA>=0)
31     {
32         int digitA=charA[lastA]-'0';
33         sum=digitA+carrier;
34         temp=sum%2;
35         carrier=sum/2;
36         results[last]=(char)(temp+'0');
37         lastA--;
38         last--;      
39     }
40   
41     while(lastB>=0)
42     {
43         int digitB=charB[lastB]-'0';
44         sum=digitB+carrier;
45         temp=sum%2;
46         carrier=sum/2;
47         results[last]=(char)(temp+'0');
48         lastB--;
49         last--;      
50     }
51     results[last]=(char)(carrier+'0');
52     String resultStr=new String(results);
53     if((results[0]-'0')==0)
54     {
55         resultStr=resultStr.substring(1,resultStr.length());
56     }
57     return resultStr;
58   
59 }

Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

To check whether a tree is balanced, we will check from the root, the height of the left child and the height of the right child and perform the process recursively. The height of a node can be calculated recursively in a separate function. However, we do not want so many recursions. What should we do? We can check the balance with the height at the same time. If the difference of the height from the left sub-tree to the right sub-tree is greater than 1, then we just return an error code -1, and do not need to do a further check.

01 public boolean isBalanced(TreeNode root) {
02     if(checkHeight(root)==-1)
03         return false;
04     return true;
05 }
06 
07 public int checkHeight(TreeNode root)
08 {
09     if(root==null)
10         return 0;
11     int leftHeight=checkHeight(root.left);
12     if(leftHeight==-1)
13         return -1;
14     int rightHeight=checkHeight(root.right);
15     if(rightHeight==-1)
16         return -1;
17     if(rightHeight-leftHeight>1 || rightHeight-leftHeight <-1)
18         return -1;
19     else
20     {
21         return findMax(leftHeight,rightHeight)+1;
22     }
23   
24 }
25 public int findMax(int a,int b)
26 {
27     return a>b?a:b;
28 }