Leetcode–Valid Parentheses

The Problem:

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Notes:

  1. This is a basic problem using stack.

Java Solution

public class Solution {
    public boolean isValid(String s) {
        if(s.length()==0 || s.length()%2==1) return false; 
        Stack<Character> st = new Stack<Character>();
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i)=='{' || s.charAt(i)=='[' || s.charAt(i)=='(')
                st.push(s.charAt(i));
            else if(st.empty())
                return false;
            else if(s.charAt(i)=='}'){
                if(st.peek()!= '{')
                    return false;
                else
                    st.pop();
            }
            else if(s.charAt(i)==']'){
                if(st.peek()!='[')
                    return false;
                else 
                    st.pop();
            }
            else if(s.charAt(i)==')'){
                if(st.peek()!='(')
                    return false;
                else 
                    st.pop();
            }
        }
        return st.empty();
    }
}

Leetcode–Climbing Stairs

The 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?

Notes:

  1. A basic DP problem, use the exact same approach as in Unique Path.

Java Solution

public class Solution {
    public int climbStairs(int n) {
        int[] ways = new int[n+1];
        ways[1] = 1;
        ways[0] = 1;
        for(int i = 2; i < n+1; i++){
            ways[i]=ways[i-1] + ways[i-2];
        }
        return ways[n];
    }
}

Leetcode–Unique Paths

The Problem:

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?

Notes:

  1. A basic DP problem, and also can be done by directly calculate choose m from (m+n).

Java Solution

  public class Solution {
    public int uniquePaths(int m, int n) {
        int[][] path= new int[m][n];
        for(int j = 0; j < n; j++){
            path[0][j] = 1;
        }
        for(int i = 0; i < m; i++){
            path[i][0] = 1;
        }
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                path[i][j] = path[i-1][j]+path[i][j-1];
            }
        }
        return path[m-1][n-1];
    }
} 

Leetcode–Maximum Subarray

The Problem:

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Notes:

  1. A basic DP problem

Java Solution

public class Solution {
    public int maxSubArray(int[] A) {
        if(A.length==0)return 0;
        int[] maxEndwith = new int[A.length];
        maxEndwith[0] = A[0];
        int max = maxEndwith[0];
        for(int i = 1; i < A.length; i++){
            if(maxEndwith[i-1] >0){
                maxEndwith[i] = maxEndwith[i-1] + A[i];
            }
            else{
                maxEndwith[i] = A[i];
            }
            max = Math.max(max, maxEndwith[i]);
        }
        return max;
    }
}
      

Leetcode–Best Time to Buy and Sell Stock II

The 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).

Notes:

  1. Observe a simple rule that each time detects a drop in price, should sell it before drop, and then buy at the drop. So use greedy. Remember to sell in the last day even no drop.

Java Solution

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length<=1) 
            return 0;
        int profit = 0;
        int buy = prices[0];
        for(int i = 1; i < prices.length; i++){
            // sell only prices go down
            if(prices[i] < prices[i-1]){
                profit += prices[i-1]-buy;
                buy = prices[i];
            }
            // sell in last day even not go down
            else if(i==prices.length-1){
                profit += prices[i]-buy;
            }
        }
        return profit;
    }
}

Leetcode–Same Tree

The 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.

Notes:

  1. Basic question.

Java Solution

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null && q== null)
            return true;
        else if(p!= null && q!= null &&
            p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right))
            return true;
        else 
            return false;
    }
}

Leetcode–Minimum Depth of Binary Tree

The 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.

Notes:

  1. Basic question, similar to Maximum Depth of Binary Tree.

Java Solution


/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int minDepth(TreeNode root) {
        if(root== null) return 0;
        return getMin(root, 1);
    }
    private int getMin(TreeNode root, int depth){
        if(root.left== null &&  root.right==null)
            return depth;
        int left=Integer.MAX_VALUE;
        int right = Integer.MAX_VALUE;
        if(root.left!= null)
            left = getMin(root.left, depth+1);
        if(root.right!= null)
            right = getMin(root.right, depth+1);
        
        return Math.min(left , right);
    }
}

Java Solution II

Actually it can be simpler than the above solution, since it does not pass in and out the depth, only one way will do. Be careful about cases that have left/right subtree empty.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int minDepth(TreeNode root) {
        if(root== null) return 0;
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        if(left==0 && right== 0) return 1;
        else if(left==0 || right ==0) return Math.max(left, right)+1;
        else return Math.min(left, right)+1;
    }
    
}