Leetcode: Unique Paths

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Version 1. Initialize first row and first column separately

    public int uniquePaths(int m, int n) {
    	if (m <= 0 || n <= 0) {
    		return 0;
    	}
    	int[][] f = new int[m][n];
    	//initialize the first column
    	for (int i = 0; i < m; i++) {
    		f[i][0] = 1;
    	}
    	//initialize the first row
    	for (int j = 0; j < n; j++) {
    		f[0][j] = 1;
    	}
    	for (int i = 1; i < m; i++) {
    		for (int j = 1; j < n; j++) {
    			f[i][j] = f[i - 1][j] + f[i][j - 1];
    		}
    	}
    	return f[m - 1][n - 1];
    }

Version 2. Put initialization in the 2 for loop.

public class Solution {
   public int uniquePaths(int m, int n) {
        if (m <= 0 || n <= 0) {
            return 0;
        }
        int[][] pathMap = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    pathMap[i][j] = 1;
                } else if (pathMap[i][j] == 0) {
                    pathMap[i][j] = pathMap[i - 1][j] + pathMap[i][j - 1];
                }
            }
        }
        return pathMap[m - 1][n - 1];
    }
}
FacebookTwitterGoogle+Share

Leetcode: Pascal’s Triangle

Given numRows, generate the first numRows of Pascal’s triangle.

For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]
public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> pascalTriangle = new ArrayList<List<Integer>>();
        List<Integer> currLevel = new ArrayList<Integer>();
        currLevel.add(1);
        while(numRows>0){
            pascalTriangle.add(new ArrayList<Integer>(currLevel));
            currLevel = generateNextLevel(currLevel);
            numRows--;
        }
        return pascalTriangle;
    }
    
    public List<Integer> generateNextLevel(List<Integer> currLevel){
        List<Integer> nextLevel = new ArrayList<Integer>();
        if(currLevel.size()!=0){
            currLevel.add(0);
            currLevel.add(0,0);
            for(int runner=0; runner<currLevel.size()-1; runner++){
                nextLevel.add(currLevel.get(runner)+currLevel.get(runner+1));
            }
        }
        return nextLevel;
    }
}

Note: for each row, pretend there is always one 0 at each side of the row. So the triangle would look like following, so when calculating next level, just need to sum each adjacent integers in the current level.

[
     0[1]0,
    0[1,1]0,
   0[1,2,1]0,
  0[1,3,3,1]0,
 0[1,4,6,4,1]0
]

Leetcode: Plus One

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.

public class Solution {
    public int[] plusOne(int[] digits) {
        if(digits==null||digits.length==0){
            return digits;
        }
        int index = digits.length-1;
        int carry = 1;
        int sum;
        while(index>=0 && carry==1){
            sum = digits[index]+carry;
            digits[index] = sum%10;
            carry = sum/10;
            index--;
        }
        if(carry==1){
            int[] newDigits = new int[digits.length+1];
            newDigits[0]=carry;
            for(int i=0;i<digits.length;i++){
                newDigits[i+1] = digits[i];
            }
            return newDigits;
        }
        return digits;
        
    }
}

Note: use a while loop here so that we don’t need to go through the entire array if it’s not necessary. It starts from the last index of the array and go backwards. If carry==1, then it will keep going, otherwise it will stop. After the traversing is done, it checks if the first digit==0 and handle that case.

Leetcode: Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library’s sort function for this problem.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.

Could you come up with an one-pass algorithm using only constant space?

One pass version:

public class Solution {
    public void sortColors(int[] A) {
        int red = 0;
        int blue = A.length-1;
        int runner = 0;
        while(runner<=blue){
            switch(A[runner]){
                case 0:
                    swap(A, red, runner);
                    red++;
                    runner++;
                    break;
                case 1:
                    runner++;   
                    break;
                case 2:
                    swap(A, blue, runner);
                    blue--;
                    break;
            }
        }
    }
     
    public void swap(int[] A, int a, int b){
        int temp = A[a];
        A[a] = A[b];
        A[b] = temp;
    }
}

 

 

Leetcode: 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 (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and respectively.

public class Solution {
 public void merge(int A[], int m, int B[], int n) {
   int index = m+n-1;
   while(index>=0 && m>0 && n>0){
     if(A[m-1]>=B[n-1]){
       A[index]=A[m-1];
       m--;
     }else{
       A[index]=B[n-1];
       n--;
     }
     index--;
   }
   if(n>0){
     for(int i=0;i<n;i++){
       A[i]=B[i];
     }
   }
 }
}

 

 

Leetcode: Symmetric Tree

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

Note:
Bonus points if you could solve it both recursively and iteratively.

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

Recursive:

public class Solution {
 public boolean isSymmetric(TreeNode root) {
   if(root==null){
     return true;
   }
   return isSymmetric(root.left, root.right);
 }
 
 public boolean isSymmetric(TreeNode left, TreeNode right){
   if(left==null&&right==null){
     return true;
   }
   if((left==null&&right!=null)||(left!=null&right==null)){
     return false;
   }
   return left.val==right.val && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
 }
}

 

Non-Recursive/Iteratively:


 

Leetcode: Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

public class Solution {
 public TreeNode sortedArrayToBST(int[] num) {
   return sortedArrayToBST(num, 0, num.length-1);
 }
 
 public TreeNode sortedArrayToBST(int[] num, int start, int end){
   if(start>end){
     return null;
   }
   int pivot = (start+end)/2;
   TreeNode root = new TreeNode(num[pivot]);
   root.left = sortedArrayToBST(num, start, pivot-1);
   root.right = sortedArrayToBST(num, pivot+1, end);
   return root;
 }
}

 

Leetcode: 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.

public class Solution {
 public boolean isBalanced(TreeNode root) {
   return getRebalancedHeight(root)==-1?false:true;
 }
 //getHeight for each node, -1 if it is already not balanced.
 public int getRebalancedHeight(TreeNode root){
 if(root==null){
   return 0;
 }
 int leftHeight = getRebalancedHeight(root.left);
 int rightHeight = getRebalancedHeight(root.right);
 if(leftHeight==-1||rightHeight==-1||Math.abs(leftHeight-rightHeight)>1){
   return -1;
 }
   return Math.max(leftHeight, rightHeight)+1;
 }
}