Unique Binary Search Trees

Problem:

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Analysis:

Refer http://blog.joysword.com/en/posts/2014/02/unique_binary_search_trees/.

Solution:

 public class Solution {  
   public int numTrees(int n) {  
     if(n==0)  
      return 1;  
     if(n==1)  
      return 1;  
     int num=0;  
       for(int j=1;j<=n;j++)  
       {  
         num+=numTrees(j-1)*numTrees(n-j);  
       }  
      return num;  
   }  
 }  

[LeetCode] Best Time to Buy and Sell Stock II

Problem:

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Analysis:

Greedy algorithm. Sum up all the positive differences between two values next to each other.

Solution:

1:  public class Solution {  
2:    public int maxProfit(int[] prices) {  
3:      if(prices.length==0)  
4:       return 0;  
5:      int maxProfit=0;  
6:      for(int i=1;i<prices.length;i++)  
7:      {  
8:        if(prices[i]>prices[i-1])  
9:         maxProfit+=prices[i]-prices[i-1];  
10:      }  
11:      return maxProfit;  
12:    }  
13:  }  

Best Time to Buy and Sell Stock

Problem:

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Analysis:

Compare the current value with the minimum of the previous values. Keep the maximum profit. The time is O(n).

Solution:

1:  public class Solution {  
2:    public int maxProfit(int[] prices) {  
3:      if(prices==null)  
4:       return 0;  
5:       else  
6:       {  
7:      int min=Integer.MAX_VALUE;  
8:      int profit=0;  
9:      int maxProfit=0;  
10:      for(int i=0;i<prices.length;i++)  
11:      {  
12:        if(prices[i]<=min)  
13:          min=prices[i];  
14:        profit=prices[i]-min;  
15:        if(profit>=maxProfit)  
16:         maxProfit=profit;  
17:      }  
18:      return maxProfit;  
19:       }  
20:    }  
21:  }  

Reverse Integer

Problem:

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

click to show spoilers.

Have you thought about this?

Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!

If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.

Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?

Throw an exception? Good, but what if throwing an exception is not an option? You would then have to re-design the function (ie, add an extra parameter).

Solution:

1:  public class Solution {  
2:    public int reverse(int x) {  
3:      int left=0;  
4:      int result=0;  
5:      while(x!=0)  
6:      {  
7:        left=x%10;  
8:        result=result*10+left;  
9:        x=x/10;  
10:      }  
11:      return result;  
12:    }  
13:  }  

Single Number

Problem:

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Solution:

1:  public class Solution {  
2:    public int singleNumber(int[] A) {  
3:      for(int i=1;i<A.length;i++)  
4:        A[i]^=A[i-1];  
5:      return A[A.length-1];  
6:    }  
7:  }  

Discussion:
Use bitwise OR operator ^. Definition is as follows.

A bitwise XOR takes two bit patterns of equal length and performs the logical exclusive OR operation on each pair of corresponding bits. The result in each position is 1 if only the first bit is 1 or only the second bit is 1, but will be 0 if both are 0 or both are 1. In this we perform the comparison of two bits, being 1 if the two bits are different, and 0 if they are the same. For example:

    0101 (decimal 5)
XOR 0011 (decimal 3)
  = 0110 (decimal 6)

The bitwise XOR may be used to invert selected bits in a register (also called toggle or flip). Any bit may be toggled by XORing it with 1. For example, given the bit pattern 0010 (decimal 2) the second and fourth bits may be toggled by a bitwise XOR with a bit pattern containing 1 in the second and fourth positions:

    0010 (decimal 2)
XOR 1010 (decimal 10)
  = 1000 (decimal 8)

Path Sum

Problem:

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

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 boolean hasPathSum(TreeNode root, int sum) {  
12:      if(root==null)  
13:       return false;  
14:      if(root.left==null && root.right==null&&root.val==sum)  
15:       return true;  
16:      return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val);  
17:    }  
18:  }  

Discussion:
Recursive solution. The path sum of the current node is the path sum of its child nodes plus its value.

Minimum Depth of Binary Tree

Problem:

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

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 int minDepth(TreeNode root) {  
12:      if(root==null)  
13:       return 0;  
14:      if(root.left==null&&root.right!=null)  
15:        return minDepth(root.right)+1;  
16:      else if(root.right==null && root.left!=null)  
17:        return minDepth(root.left)+1;  
18:      else if(root.left==null && root.right==null)  
19:        return 1;  
20:      else  
21:        return Math.min(minDepth(root.left),minDepth(root.right))+1;  
22:    }  
23:  }  

Discussion:
Similar to maximum depth of binary tree.

Balanced Binary Tree

Problem:

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.

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 boolean isBalanced(TreeNode root) {  
12:      if(root==null)  
13:       return true;  
14:      if(!isBalanced(root.left)||!isBalanced(root.right))  
15:       return false;  
16:       if(Math.abs(maxDepth(root.left)-maxDepth(root.right))<=1)  
17:        return true;  
18:       else  
19:        return false;   
20:    }  
21:    public int maxDepth(TreeNode root) {   
22:     if(root==null)   
23:      return 0;   
24:     if(root.left==null&&root.right==null)   
25:      return 1;   
26:     return Math.max(maxDepth(root.left),maxDepth(root.right))+1;   
27:    }   
28:  }  

Discussion:
The subtrees are all balanced doesn't mean the parent tree is balance. Then still need to check the heights of the subtrees make sure they are differs no more than one.

Maximum Depth of Binary Tree

Problem:

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

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 int maxDepth(TreeNode root) {  
12:      if(root==null)  
13:       return 0;  
14:      if(root.left==null&&root.right==null)  
15:       return 1;  
16:      return Math.max(maxDepth(root.left),maxDepth(root.right))+1;  
17:    }  
18:  }  

Discussion:
Use recursion is straight forward and simple. The depth of the current level is the maximum depth of its siblings plus 1.

Symmetric Tree

Problem:

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

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 boolean isSymmetric(TreeNode root) {  
12:      if(root==null)  
13:       return true;  
14:      else  
15:       return isSym(root.left,root.right);  
16:    }  
17:    public boolean isSym(TreeNode left, TreeNode right){  
18:      if(left==null) return right==null;  
19:      if(right==null) return left==null;  
20:      if(left.val!=right.val) return false;  
21:      if(!isSym(left.right,right.left))  
22:       return false;  
23:      if(!isSym(left.left,right.right))  
24:       return false;  
25:      return true;  
26:    }  
27:  }  

Discussion:

Recursive solution. If a tree is symmetric, it satisfies 3 conditions:
1. left node value equals to right node value or they are all null.
2. The left node's left child is symmetric to right node's right child.
3. The left node's right child is symmetric to right node's left child.

Same Tree

Problem:

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

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 boolean isSameTree(TreeNode p, TreeNode q) {  
12:      if(p==null&&q==null)  
13:       return true;  
14:      if(p!=null && q!=null)  
15:      {  
16:        if(p.val==q.val)  
17:         return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);  
18:        else  
19:        return false;  
20:      }  
21:      else  
22:       return false;  
23:    }  
24:  }  

Discussion:

Use pre-order to traverse the trees.

Remove Duplicates from Sorted List

Problem:

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Solution:

 /**  
  * Definition for singly-linked list.  
  * public class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) {  
  *     val = x;  
  *     next = null;  
  *   }  
  * }  
  */  
 public class Solution {  
   public ListNode deleteDuplicates(ListNode head) {  
     if(head==null)  
     return null;  
     ListNode temp=head;  
     while(temp.next!=null)  
     {  
       if(temp.val==temp.next.val)  
       {  
         if(temp.next.next!=null)  
         temp.next=temp.next.next;  
         else  
         {  
           temp.next=null;  
           break;  
         }  
       }  
       else  
       temp=temp.next;  
     }  
     return head;  
   }  
 }  

Discussion:

Do not forget to consider when head is null. Then the logic is simple. Don't need much to say.

Plus One

Problem:

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

Solution:

 public class Solution {  
   public int[] plusOne(int[] digits) {  
   boolean carry=true;  
   for(int i=digits.length-1;i>=0;i--)  
   {  
     if(digits[i]==9&&carry==true)  
     {  
       digits[i]=0;  
       if(i==0)//When all digits are 9, relocate a new array with length plus 1.  
       {  
       int[] newDigits=new int[digits.length+1];  
       for(int j=newDigits.length-1;j>0;j--)  
         newDigits[j]=digits[j-1];  
         newDigits[0]=1;  
         digits=newDigits;  
        break;  
       }  
     }  
     else if(carry==true)  
       {  
        digits[i]++;  
        carry=false;  
       }  
   }  
   return digits;  
   }  
 }  

Discussion:
Need to consider the extreme situation when the digits are all 9. Needs to relocate a new array with length plus 1. If the digit is 9, continues to carry 1 to the next digit. If not, stop carrying.

Length of Last Word

Problem:

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = "Hello World",
return 5.

Solution:

 public class Solution {  
   public int lengthOfLastWord(String s) {  
     int pos=0;   
     for(int i=s.length()-1;i>=0;i--)  
      {  
         if(s.charAt(i)!=' ')  
          pos++;  
         else if(pos>0 && s.charAt(i)==' ')  
          break;  
      }  
      return pos;  
   }  
 }  

Discussion:

I first attempt was from the beginning of the string, but failed to consider the situation when "a ". Then I tried iterate from tail of the string then succeeded.

Remove Element

Problem:

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Solution:

 public class Solution {  
   public int removeElement(int[] A, int elem) {  
     int pos=0;  
     for(int i=0;i<A.length;i++)  
     {  
       if(A[i]!=elem)  
       A[pos++]=A[i];  
     }  
     return pos;  
   }  
 } 

Discussion:

Similar to remove duplicate but position increments after being assigned so final return should be just position.

Remove Duplicates from Sorted Array

Problem:

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

Discussion:
Two pointers, one keeps moving forward the other keeps identical element.

Solution:

 public class Solution {  
   public int removeDuplicates(int[] A) {  
     if(A.length==0) return 0;  
     int pos=0;  
     for(int i=1;i<A.length;i++)  
     {  
       if(A[i]!=A[i-1])  
         A[++pos]=A[i];  
     }  
     return pos+1;  
   }  
 }