LeetCode 72. Edit Distance

Problem:

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Solution:

DP

public class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] d = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) d[i][0] = i;
        for (int i = 0; i <= n; i++) d[0][i] = i;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                int c1 = d[i-1][j];
                int c2 = d[i][j-1];
                int c = Math.min(c1, c2) + 1;
                if (word1.charAt(i-1) == word2.charAt(j-1)) d[i][j] = Math.min(d[i-1][j-1], c);
                else d[i][j] = Math.min(d[i-1][j-1] + 1, c);
            }
        }
        return d[m][n];
    }
}

LeetCode 152. Maximum Product Subarray

Problem:

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

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Solution:

DP

public class Solution {
    public int maxProduct(int[] nums) {
        int max = nums[0], min = nums[0], ans = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int m = max, n = min;
            max = Math.max(nums[i], Math.max(m * nums[i], n * nums[i]));
            min = Math.min(nums[i], Math.min(m * nums[i], n * nums[i]));
            ans = Math.max(ans, max);
        }
        return ans;
    }
}

LeetCode 53. Maximum Subarray

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.

Solution

DP

public class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0], maxEnd = nums[0];
        for (int i = 1; i < nums.length; i++) {
            maxEnd = Math.max(maxEnd + nums[i], nums[i]);
            max = Math.max(maxEnd, max);
        }
        return max;
    }
}

LeetCode 63. Unique Paths II

Problem:

Follow up for “Unique Paths”:

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3×3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

Solution:

DP

public class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] grid = new int[m][n];
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1) break;
            grid[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            if (obstacleGrid[0][i] == 1) break;
            grid[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] = obstacleGrid[i][j] == 1 ? 0 : grid[i-1][j] + grid[i][j-1];
            }
        }
        return grid[m-1][n-1];
    }
}

LeetCode 107. Binary Tree Level Order Traversal II

Problem:

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

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

Solution:

BFS

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (root == null) return result;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            List<Integer> row = new ArrayList<Integer>();
            while (size > 0) {
                TreeNode current = q.poll();
                row.add(current.val);
                if (current.left != null) q.offer(current.left);
                if (current.right != null) q.offer(current.right);
                size--;
            }
            result.add(0, row);
        }
        return result;
    }
}

LeetCode 297. Serialize and Deserialize Binary Tree

Problem:

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

Credits:
Special thanks to @Louis1992 for adding this problem and creating all test cases.

Solution:

BFS

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

	// Encodes a tree to a single string.
	public String serialize(TreeNode root) {
		if (root == null) return "[]";
		Queue<TreeNode> q = new LinkedList<TreeNode>();
		ArrayList<String> result = new ArrayList<String>();
		q.offer(root);
		TreeNode rightMost = root;
		int maxDepth = maxDepth(root, 0);
		int depth = 1;
		while (!q.isEmpty()) {
			TreeNode current = q.poll();
			if (current == null) {
				if (depth <= maxDepth) {
					result.add("null");
				}
				continue;
			}
			result.add(current.val + "");	
			q.offer(current.left);
			q.offer(current.right);

			if (current == rightMost) {
				depth++;
				rightMost = current.right == null ? current.left : current.right;
			}
		}
		return result.toString();
	}

	private int maxDepth(TreeNode root, int current) {
		if (root == null) return current;
		return Math.max(maxDepth(root.left, current + 1), maxDepth(root.right, current + 1));
	}

	// Decodes your encoded data to tree.
	public TreeNode deserialize(String data) {
		if (data.length() < 2) return null;
		data = data.substring(1, data.length() - 1);
		if (data.equals("")) return null;
		String[] elements = data.split(", ");
		TreeNode root = new TreeNode(Integer.parseInt(elements[0]));
		Queue<TreeNode> q = new LinkedList<TreeNode>();
		q.offer(root);

		int index = 1;

		while (!q.isEmpty()) {
			TreeNode current = q.poll();
			if (current == null || index >= elements.length) continue;
			String e = elements[index];
			String t = index + 1 >= elements.length ? "null" : elements[index + 1];
			current.left = e.equals("null") ? null : new TreeNode(Integer.parseInt(e));
			current.right = t.equals("null") ? null : new TreeNode(Integer.parseInt(t));
			index += 2;
			q.offer(current.left);
			q.offer(current.right);
		}

		return root;
	}
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

LeetCode 129. Sum Root to Leaf Numbers

Problem:

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

Solution:

caution: don’t count the path twice.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int sumNumbers(TreeNode root) {
        if (root == null) return 0;
        return getSum(root, 0);
    }
    
    private int getSum(TreeNode node, int current) {
        int next = current * 10 + node.val;
        if (node.left == null && node.right == null) return next;
        if (node.left == null) return getSum(node.right, next);
        if (node.right == null) return getSum(node.left, next);
        return getSum(node.left, next) + getSum(node.right, next);
    }
}

LeetCode 27. Remove Element

Problem:

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

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

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

Example:
Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

Hint:

  1. Try two pointers.
  2. Did you use the property of “the order of elements can be changed”?
  3. What happens when the elements to remove are rare?

Solution:

Use two pointers to replace val

public class Solution {
    public int removeElement(int[] nums, int val) {
        int front = 0, back = nums.length - 1;
        while (front <= back) {
            if (nums[front] == val) {
                nums[front] = nums[back--];
            }
            else front++;
        }
        return back + 1;
    }
}