Roman to Integer

Problem:

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

Analysis:

The tricky in this problem is that Symbols are placed from left to right in order of value, starting with the largest. However, in a few specific cases, to avoid four characters being repeated in succession (such as IIII or XXXX) these can be reduced using subtractive notation as follows:

• the numeral I can be placed before V and X to make 4 units (IV) and 9 units (IX respectively)
• X can be placed before L and C to make 40 (XL) and 90 (XC respectively)
• C can be placed before D and M to make 400 (CD) and 900 (CM) according to the same pattern

An example using the above rules would be 1904: this is composed of 1 (one thousand), 9 (nine hundreds), 0 (zero tens), and 4 (four units). To write the Roman numeral, each of the non-zero digits should be treated separately. Thus 1,000 = M, 900 = CM, and 4 =IV. Therefore, 1904 is MCMIV.

The solution is that add up every character, if the previous character is smaller than the  current character then subtract the previous character twice. 

Solution:

1:  public class Solution {  

2:    public int romanToInt(String s) {  

3:      if(s==null) return 0;  

4:      if(s.length()==1) return getInt(s.charAt(0));  

5:      int pre=s.charAt(0);  

6:      int cur=0;  

7:      int total=s.charAt(0);  

8:      for(int i=1;i<s.length();i++)  

9:      {  

10:        cur=getInt(s.charAt(i));  

11:        total+=cur;  

12:        if(pre<cur)  

13:          total=total-pre*2;  

14:        pre=cur;  

15:      }  

16:      return total;  

17:    }  

18:    public int getInt(char digit)  

19:    {  

20:      int result=0;  

21:      switch (digit)  

22:      {  

23:        case 'I': result=1; break;  

24:        case 'V': result=5; break;  

25:        case 'X': result=10;break;  

26:        case 'L': result=50;break;  

27:        case 'C': result=100;break;  

28:        case 'D': result=500;break;  

29:        case 'M': result=1000;break;  

30:      }  

31:      return result;  

32:    }  

33:  }  

Reference:
http://en.wikipedia.org/wiki/Roman_numerals

Climbing Stairs

Problem:

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?

Analysis:

Recursive solution is slow and could not pass online judge because time limit exceeded. But I don't familiar with dynamic programming right now.

Solution:

1:  public class Solution {  
2:    public int climbStairs(int n) {  
3:      if(n==1) return 1;  
4:      if(n==2) return 2;  
5:      return climbStairs(n-1)+climbStairs(n-2);  
6:    }  
7:  }  

Search Insert Position

Problem:

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

Analysis:

A typical binary search problem. 

Solution:

1:  public class Solution {  
2:    public int searchInsert(int[] A, int target) {  
3:      int high=A.length-1;  
4:      int low=0;  
5:      int mid=(high+low)/2;  
6:      while(low <=high)  
7:      {  
8:        mid=(high+low)/2;  
9:        if(target==A[mid])  
10:          return mid;  
11:        if(target>A[mid])  
12:          low=mid+1;  
13:        else  
14:          high=mid-1;  
15:      }  
16:      return low;  
17:    }  
18:  }  

Populating Next Right Pointers in Each Node

Problem:

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

Analysis:
The first thought occurs to me is the level order traversal, but this problem requires constant space. Level order traversal requires a queue. The recursive method is fast and easy to under stand. Let's assume that the current node is connected with its next node. Its left child's next node is its right child. Its right child's next node is its next node's left child. The space is O(N).

Solution:

1:  /**  
2:   * Definition for binary tree with next pointer.  
3:   * public class TreeLinkNode {  
4:   *   int val;  
5:   *   TreeLinkNode left, right, next;  
6:   *   TreeLinkNode(int x) { val = x; }  
7:   * }  
8:   */  
9:  public class Solution {  
10:    public void connect(TreeLinkNode root) {  
11:      if(root==null)  
12:       return;  
13:      if(root.left!=null)  
14:       root.left.next=root.right;  
15:      if(root.right!=null)  
16:       root.right.next=root.next==null?null:root.next.left;  
17:      connect(root.left);  
18:      connect(root.right);  
19:    }  
20:  }  

Binary Tree Level Order Traversal

Problem:

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

Analysis:
Method 1:
Use two queues. One to record the current level, the other keeps record of the next level. Iterate the current level add the children of each nodes in current level to the next level queue. After the current level queue becomes empty, assign the next level to current level.

Method 2:
Use one queue. Use two counters, one counts the current level number of nodes the other counts the next level number of nodes. Each time remove from the linked list, current level number of nodes decrease and add next level number of nodes accordingly.  When current level counter reaches 0, add current level to the final ArrayList. Then next level counter becomes current level counter. Have to note that the ArrayList is the reference type in Java, if clear the ArraryList<Integer> after adding it to the ArraryList<ArraryList<Integer>> then reuse it, it would clear what's inside the ArraryList<ArraryList<Integer>>. So I created another instance every time current level nodes reaches 0.

Solution:
1. Two Queues

1:  /**  
2:   * Definition for binary tree  
3:   * public class TreeNode {  
4:   *   int val;  
5:   *   TreeNode left;  
6:   *   TreeNode right;  
7:   *   TreeNode(int x) { val = x; }  
8:   * }  
9:   */  
10:  public class Solution {  
11:    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {  
12:      ArrayList<ArrayList<Integer>> alResult=new ArrayList<ArrayList<Integer>>();  
13:      if(root==null)  
14:        return alResult;  
15:      LinkedList<TreeNode> currLevel=new LinkedList<TreeNode>();  
16:      currLevel.add(root);  
17:      while(!currLevel.isEmpty())  
18:      {  
19:        ArrayList<Integer> alLevel=new ArrayList<Integer>();  
20:        LinkedList<TreeNode> nextLevel=new LinkedList<TreeNode>();  
21:        while(!currLevel.isEmpty())  
22:        {  
23:          TreeNode currNode=currLevel.remove();  
24:          alLevel.add(currNode.val);  
25:          if(currNode.left!=null) nextLevel.add(currNode.left);  
26:          if(currNode.right!=null) nextLevel.add(currNode.right);  
27:        }  
28:        currLevel=nextLevel;  
29:        alResult.add(alLevel);  
30:      }  
31:      return alResult;  
32:    }  
33:  }  

2. One queue

1:  /**  
2:   * Definition for binary tree  
3:   * public class TreeNode {  
4:   *   int val;  
5:   *   TreeNode left;  
6:   *   TreeNode right;  
7:   *   TreeNode(int x) { val = x; }  
8:   * }  
9:   */  
10:  public class Solution {  
11:    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {  
12:      ArrayList<ArrayList<Integer>> alResult=new ArrayList<ArrayList<Integer>>();  
13:      ArrayList<Integer> alLevel=new ArrayList<Integer>();  
14:      LinkedList<TreeNode> currLevel=new LinkedList<TreeNode>();  
15:      if(root==null)  
16:        return alResult;  
17:      int curr=1;  
18:      int next=0;  
19:      currLevel.add(root);  
20:      while(!currLevel.isEmpty())  
21:      {  
22:        TreeNode currNode=currLevel.remove();  
23:        curr--;  
24:        alLevel.add(currNode.val);  
25:        if(currNode.left!=null)   
26:        {  
27:          currLevel.add(currNode.left);  
28:          next++;  
29:        }  
30:        if(currNode.right!=null)   
31:        {  
32:          currLevel.add(currNode.right);  
33:          next++;  
34:        }  
35:        if(curr==0)  
36:        {  
37:          curr=next;  
38:          next=0;  
39:          alResult.add(alLevel);  
40:          ArrayList<Integer> alLevelTemp=new ArrayList<Integer>();  
41:          alLevel=alLevelTemp;  
42:        }  
43:      }  
44:      return alResult;  
45:    }  
46:  }  

Binary Tree Postorder Traversal

Problem:

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Analysis:
The most difficult one among preorder, inorder and postorder traversals. The difficulty lays in that after going down to left it will go right, storing the parent node is a problem. Use one more stack to assist push nodes in reserve order of postorder to the final stack.
Steps:
1.Push the root node to the temp stack.
2.Pop node c from temp stack.
3.If c has left child push it to final stack.If c has right child push it to final stack.
4.Push c to final stack.
5.Repeat 2-4 until temp stack is empty.
6.Print final stack.

Solution:

1:  /**  
2:   * Definition for binary tree  
3:   * public class TreeNode {  
4:   *   int val;  
5:   *   TreeNode left;  
6:   *   TreeNode right;  
7:   *   TreeNode(int x) { val = x; }  
8:   * }  
9:   */  
10:  public class Solution {  
11:    public ArrayList<Integer> postorderTraversal(TreeNode root) {  
12:      ArrayList<Integer> result=new ArrayList<Integer>();  
13:      if(root==null)  
14:       return result;  
15:      Stack<TreeNode> t=new Stack<TreeNode>();//temp stack   
16:      Stack<TreeNode> r=new Stack<TreeNode>();//result stack  
17:      t.push(root);  
18:      while(!t.isEmpty())  
19:      {  
20:       TreeNode current=t.pop();  
21:        if(current.left!=null) t.push(current.left);  
22:        if(current.right!=null) t.push(current.right);  
23:        r.push(current);  
24:      }  
25:      while(!r.isEmpty())  
26:      {  
27:       TreeNode current=r.pop();  
28:        result.add(current.val);  
29:      }  
30:      return result;  
31:    }  
32:  }  

Binary Tree Inorder Traversal

Problem:

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

Analysis:

The definition of inorder traversal is visit the left node first, the parent node second and the right node last. Iterative implementation of inorder traversal is more difficult than preorder traversal. We need to consider how to visit the left most node and keep track of the trace.

1. Push the root node to the stack.

2. Set the left child of the current node to the current node.

3. Continue 1,2 until current node is null.

4. If current node is not null.

   1). Pop current node from the stack and write it.

   2). Set the right child of the current node to the current node. go to 2.

5. If the stack is empty return. 

Solution:

1:  /**  
2:   * Definition for binary tree  
3:   * public class TreeNode {  
4:   *   int val;  
5:   *   TreeNode left;  
6:   *   TreeNode right;  
7:   *   TreeNode(int x) { val = x; }  
8:   * }  
9:   */  
10:  public class Solution {  
11:    public ArrayList<Integer> inorderTraversal(TreeNode root) {  
12:      ArrayList<Integer> result=new ArrayList<Integer>();  
13:      if(root==null)  
14:       return result;  
15:      Stack<TreeNode> stack=new Stack<TreeNode>();  
16:      TreeNode current=root;  
17:      while(true)  
18:      {  
19:        if(current!=null)//iterate left until there is no left node at all       
20:        {  
21:         stack.push(current);  
22:         current=current.left;  
23:        }  
24:        else  
25:        {  
26:          if(!stack.isEmpty())  
27:          {  
28:            current=stack.pop();  
29:            result.add(current.val);  
30:            current=current.right;//have visited the left and the parent node, time to visit the right one.  
31:          }  
32:          else  
33:           break;  
34:        }  
35:      }  
36:      return result;  
37:    }  
38:  }  

Binary Tree Preorder Traversal

Problem:

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].

Analysis:

Use stack to temporarily store the nodes. Because stack is FILO, push order is from right to left. I spent about half an hour thinking the idea. It was my first time implement the preorder traversal. 

Solution:

1:  /**  
2:   * Definition for binary tree  
3:   * public class TreeNode {  
4:   *   int val;  
5:   *   TreeNode left;  
6:   *   TreeNode right;  
7:   *   TreeNode(int x) { val = x; }  
8:   * }  
9:   */  
10:  public class Solution {  
11:    public ArrayList preorderTraversal(TreeNode root) {  
12:         ArrayList result = new ArrayList();  
13:      if(root==null)  
14:       return result;  
15:      Stack<TreeNode> nodeStack=new Stack<TreeNode>();  
16:      nodeStack.push(root);  
17:      while(!nodeStack.isEmpty())  
18:      {  
19:        TreeNode current=nodeStack.pop();  
20:        if(current.right!=null) nodeStack.push(current.right);  
21:        if(current.left!=null) nodeStack.push(current.left);  
22:        result.add(current.val);  
23:      }  
24:      return result;  
25:    }  
26:  }  

Linked List Cycle

Problem:

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

Analysis:

Usess Floyd’s cycle finding algorithm. Two pointer, one is the slow pointer travels a node at once the other is the fast pointer travels two nodes at once. These pointers will eventually meet at a point if the linked list has a cycle in it. The time is O(N) and space is O(1).

When coding, have to make sure the fast.next is not null otherwise a nullpointerexception will rise during execution. 

Solution:

 /**  
  * Definition for singly-linked list.  
  * class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) {  
  *     val = x;  
  *     next = null;  
  *   }  
  * }  
  */  
 public class Solution {  
   public boolean hasCycle(ListNode head) {  
     ListNode slow=head;  
     ListNode fast=head;  
     while(fast!=null&&slow!=null&&fast.next!=null)  
     {  
       slow=slow.next;  
       fast=fast.next.next;//fast is twice as fast as slow  
       if(fast==slow)//when fast meets slow  
        return true;  
     }  
     return false;  
   }  
 }