Merge Intervals - LeetCode

Merge Intervals

1. sort Intervals
2. compare last interval in result with current Interval.

Two Sum - LeetCode

Two Sum

Using HashMap to solve this problem would be much easier.

String to Integer (atoi) - LeetCode

String to Integer (atoi)

Watch out the corner cases. 

Climbing Stairs - LeetCode

Climbing Stairs

1. Recursive:
We can use recursive way to solve this problem: O(n) = O(n - 1) + O(n - 2).

2. DP:
This method also very straightforward. dp[i] means how many ways to reach level i. So it would take O(n) time and O(n) space to solve the problem.

3. Two pointers:
We also can use to pointers to store the info. It is like DP. But the space is reduced to O(1).

Validate Binary Search Tree - LeetCode

Validate Binary Search Tree

This problem is like the other tree questions, recursive method is the easiest read way.

Here is the code:

Pow(x, n) - LeetCode

Pow(x, n)

This question is very easy. But the corner case must be considered in.

1. negative n.
2. n equals to 0.

Then we can using recursive method to solve this problem.

Here is the code: 
Additional throughout: how about n is also double?

Word Ladder - LeetCode

Word Ladder

For this problem, BFS is better than DFS. 

DFS, it's like from the first char to the last char of the word, try to match the dictionary. However, if there is not match, then start from last matching char and do the same again. So it is not efficiency. 

Using BFS, it is like Level traverse a tree. So it would reduce the times for matching. 

Here is the code. Using two queue( the distance Queue is not required. it just used for store the distance every time generate.) to do the BFS. (when mention the BFS, the first thought must be Queue. LOL).

About BFS

Here is the problems solved by using BFS on LeetCode OJ.

package InterviewCode;

import java.util.ArrayList;

import java.util.Collections;

import java.util.LinkedList;

import java.util.List;

import java.util.Queue;

import java.util.Set;

import java.util.Stack;

import Util.TreeNode;

public class AboutBFS

{

    //Binary Tree Level Order Traversal 

    public List> levelOrder(TreeNode root)

    {

        ArrayList> result = new ArrayList>();

        if (root == null)

        {

            return result;

        }

        Queue queue = new LinkedList();

        queue.add(root);

        int curNodeNum = 1;

        int nextNodeNum = 0;

        ArrayList array = new ArrayList();

        while (!queue.isEmpty())

        {

            TreeNode node = queue.poll();

            array.add(node.val);

            if (node.left != null)

            {

                queue.add(node.left);

                nextNodeNum++;

            }

            if (node.right != null)

            {

                queue.add(node.right);

                nextNodeNum++;

            }

            curNodeNum--;

            if (curNodeNum == 0)

            {

                result.add(new ArrayList(array));

                array.clear();

                curNodeNum = nextNodeNum;

                nextNodeNum = 0;

            }

        }

        return result;

    }

    //Binary Tree Level Order Traversal II 

    public List> levelOrderII(TreeNode root)

    {

        ArrayList> result = new ArrayList>();

        if (root == null)

        {

            return result;

        }

        Queue queue = new LinkedList();

        Stack> stack = new Stack>();

        queue.add(root);

        int curNodeNum = 1;

        int nextNodeNum = 0;

        ArrayList array = new ArrayList();

        while (!queue.isEmpty())

        {

            TreeNode node = queue.poll();

            array.add(node.val);

            if (node.left != null)

            {

                queue.add(node.left);

                nextNodeNum++;

            }

            if (node.right != null)

            {

                queue.add(node.right);

                nextNodeNum++;

            }

            curNodeNum--;

            if (curNodeNum == 0)

            {

                stack.push(new ArrayList(array));

                array.clear();

                curNodeNum = nextNodeNum;

                nextNodeNum = 0;

            }

        }

        while (!stack.isEmpty())

        {

            result.add(stack.pop());

        }

        return result;

    }

    //Surrounded Regions

    public void solve(char[][] board)

    {

        if (board.length == 0 || board[0].length == 0)

        {

            return;

        }

        Queue rowQueue = new LinkedList();

        Queue colQueue = new LinkedList();

        for (int row = 0; row < board.length; row++)

        {

            if (board[row][0] == 'O')

            {

                rowQueue.offer(row);

                colQueue.offer(0);

            }

            if (board[row][board[0].length - 1] == 'O')

            {

                rowQueue.offer(row);

                colQueue.offer(board[0].length - 1);

            }

        }

        for (int col = 1; col <= board[0].length - 2; col++)

        {

            if (board[0][col] == 'O')

            {

                rowQueue.offer(0);

                colQueue.offer(col);

            }

            if (board[board.length - 1][col] == 'O')

            {

                rowQueue.offer(board.length - 1);

                colQueue.offer(col);

            }

        }

        while (!rowQueue.isEmpty())

        {

            int row = rowQueue.poll();

            int col = colQueue.poll();

            board[row][col] = 'Y';

            if (row >= 1 && board[row - 1][col] == 'O')

            {

                rowQueue.offer(row - 1);

                colQueue.offer(col);

            }

            if (row <= board.length - 2 && board[row + 1][col] == 'O')

            {

                rowQueue.offer(row + 1);

                colQueue.offer(col);

            }

            if (col >= 1 && board[row][col - 1] == 'O')

            {

                rowQueue.offer(row);

                colQueue.offer(col - 1);

            }

            if (col <= board[0].length - 2 && board[row][col + 1] == 'O')

            {

                rowQueue.offer(row);

                colQueue.offer(col + 1);

            }

        }

        for (int i = 0; i < board.length; i++)

        {

            for (int j = 0; j < board[0].length; j++)

            {

                if (board[i][j] == 'Y')

                {

                    board[i][j] = 'O';

                }

                else if (board[i][j] == 'O')

                {

                    board[i][j] = 'X';

                }

            }

        }

    }

    //Word Ladder

    public int ladderLength(String start, String end, Set dict)

    {

        if (start.length() != end.length() || dict.size() == 0)

        {

            return 0;

        }

        Queue wordQueue = new LinkedList();

        Queue disQueue = new LinkedList();

        wordQueue.offer(start);

        disQueue.offer(1);

        while (!wordQueue.isEmpty())

        {

            String s = wordQueue.poll();

            int dis = disQueue.poll();

            if (s.equals(end))

            {

                return dis;

            }

            for (int i = 0; i < s.length(); i++)

            {

                char[] chars = s.toCharArray();

                for (char j = 'a'; j <= 'z'; j++)

                {

                    chars[i] = j;

                    String newword = new String(chars);

                    if (dict.contains(newword))

                    {

                        wordQueue.offer(newword);

                        disQueue.offer(dis + 1);

                        dict.remove(newword);

                    }

                }

            }

        }

        return 0;

    }

    //Binary Tree Zigzag Level Order Traversal 

    public List> zigzagLevelOrder(TreeNode root)

    {

        ArrayList> result = new ArrayList>();

        if (root == null)

        {

            return result;

        }

        ArrayList arrayList = new ArrayList();

        Queue queue = new LinkedList();

        queue.add(root);

        int num = 0;

        boolean reversed = false;

        while (!queue.isEmpty())

        {

            num = queue.size();

            arrayList.clear();

            for (int i = 0; i < num; i++)

            {

                TreeNode node = queue.remove();

                arrayList.add(node.val);

                if (node.left != null)

                {

                    queue.add(node.left);

                }

                if (node.right != null)

                {

                    queue.add(node.right);

                }

            }

            if (reversed)

            {

                Collections.reverse(arrayList);

                reversed = false;

            }

            else

            {

                reversed = true;

            }

            result.add(new ArrayList(arrayList));

        }

        return result;

    }

}

About DFS

Here is all the problems using DFS solved on LeetCode OJ.

package InterviewCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

import Util.TreeNode;

public class AboutDFS
{
    //Letter Combinations of a Phone Number
    public List letterCombinations(String digits)
    {
        HashMap map = new HashMap();
        map.put('1', "");
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");
        ArrayList result = new ArrayList();
        char[] chars = new char[digits.length()];
        dfs(digits, 0, result, chars, map);
        return result;
    }

    private void dfs(String digits, int index, ArrayList result, char[] chars, HashMap map)
    {
        if (index == digits.length())
        {
            result.add(new String(chars));
        }
        String letters = map.get(digits.charAt(index));
        for (int i = 0; i < letters.length(); i++)
        {
            chars[index] = letters.charAt(i);
            dfs(digits, index + 1, result, chars, map);
        }
    }

    //Generate Parentheses
    public List generateParenthesis(int n)
    {
        ArrayList result = new ArrayList();
        if (n <= 0)
        {
            return result;
        }
        String s = new String();
        dfs(n, n, s, result);
        return result;
    }

    private void dfs(int l, int r, String s, ArrayList result)
    {
        if (r < l)
        {
            return;
        }
        if (l == 0 && r == 0)
        {
            result.add(s);
        }
        if (l >= 1)
        {
            dfs(l - 1, r, s + "(", result);
        }
        if (r >= 1)
        {
            dfs(l, r - 1, s + ")", result);
        }
    }

    //Sudoku Solver
    public void solveSudoku(char[][] board)
    {
        dfs(board, 0, 0);
    }

    private boolean dfs(char[][] board, int i, int j)
    {
        if (j >= 9)
        {
            return dfs(board, i + 1, 0);
        }
        if (i == 9)
        {
            return true;
        }
        if (board[i][j] == '.')
        {
            for (int k = 1; k <= 9; k++)
            {
                board[i][j] = (char) (k + '0');
                if (isValid(board, i, j))
                {
                    if (dfs(board, i, j + 1))
                    {
                        return true;
                    }
                }
                board[i][j] = '.';
            }
        }
        else
        {
            return dfs(board, i, j + 1);
        }
        return false;
    }

    private boolean isValid(char[][] board, int i, int j)
    {
        for (int k = 0; k < 9; k++)
        {
            if (k != j && board[i][k] == board[i][j])
                return false;
        }
        for (int k = 0; k < 9; k++)
        {
            if (k != i && board[k][j] == board[i][j])
                return false;
        }
        for (int row = i / 3 * 3; row < i / 3 * 3 + 3; row++)
        {
            for (int col = j / 3 * 3; col < j / 3 * 3 + 3; col++)
            {
                if ((row != i || col != j) && board[row][col] == board[i][j])
                    return false;
            }
        }
        return true;
    }

    //N-Queens
    public List solveNQueens(int n)
    {
        ArrayList result = new ArrayList();
        if (n <= 0)
        {
            return result;
        }
        String[] rows = new String[n];
        dfs(0, n, rows, result);
        return result;
    }

    private void dfs(int row, int n, String[] rows, ArrayList result)
    {
        if (row >= n)
        {
            result.add(rows.clone());
            return;
        }
        for (int col = 0; col < n; col++)
        {
            if (!isValid(col, row, rows))
            {
                continue;
            }

            char[] chars = new char[n];
            Arrays.fill(chars, '.');
            chars[col] = 'Q';

            rows[row] = String.valueOf(chars);
            dfs(row + 1, n, rows, result);
        }
    }

    private boolean isValid(int col, int row, String[] rows)
    {
        for (int i = 0; i < row; i++)
        {
            int indexQ = rows[i].indexOf('Q');
            if (indexQ == col)
            {
                return false;
            }

            int rowDis = Math.abs(row - i);
            int colDis = Math.abs(col - indexQ);
            if (rowDis == colDis)
            {
                return false;
            }
        }
        return true;
    }

    //N-Queens II
    public int totalNQueens(int n)
    {
        int[] result = new int[1];
        if (n <= 0)
        {
            return result[0];
        }
        String[] rows = new String[n];
        dfs(0, n, rows, result);
        return result[0];
    }

    private void dfs(int row, int n, String[] rows, int[] result)
    {
        if (row >= n)
        {
            result[0] += 1;
            return;
        }
        for (int col = 0; col < n; col++)
        {
            if (!isValid(col, row, rows))
            {
                continue;
            }

            char[] chars = new char[n];
            Arrays.fill(chars, '.');
            chars[col] = 'Q';

            rows[row] = String.valueOf(chars);
            dfs(row + 1, n, rows, result);
        }
    }

    //Word Search
    public boolean exist(char[][] board, String word)
    {
        for (int i = 0; i < board.length; i++)
        {
            for (int j = 0; j < board[0].length; j++)
            {
                if (dfs(board, word, 0, i, j))
                    return true;
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int index, int i, int j)
    {
        if (index == word.length() - 1 && word.charAt(word.length() - 1) == board[i][j])
        {
            return true;
        }
        if (word.charAt(index) != board[i][j])
        {
            return false;
        }
        char temp = board[i][j];
        board[i][j] = '.';
        boolean b1 = false, b2 = false, b3 = false, b4 = false;
        if (i - 1 >= 0 && board[i - 1][j] != '.')
        {
            b1 = dfs(board, word, index + 1, i - 1, j);
        }
        if (!b1 && j - 1 >= 0 && board[i][j - 1] != '.')
        {
            b2 = dfs(board, word, index + 1, i, j - 1);
        }
        if (!b1 && !b2 && i + 1 < board.length && board[i + 1][j] != '.')
        {
            b3 = dfs(board, word, index + 1, i + 1, j);
        }
        if (!b1 && !b2 && b3 && j + 1 < board[0].length && board[i][j + 1] != '.')
        {
            b4 = dfs(board, word, index + 1, i, j + 1);
        }
        board[i][j] = temp;
        return b1 || b2 || b3 || b4;
    }

    //Restore IP Addresses
    public List restoreIpAddresses(String s)
    {
        ArrayList result = new ArrayList();
        if (s.length() < 4 || s.length() > 12)
        {
            return result;
        }
        dfs(s, "", result, 0);
        return result;
    }

    private void dfs(String s, String tmp, ArrayList result, int count)
    {
        if (count == 3 && isValidIP(s))
        {
            result.add(tmp + s);
            return;
        }
        for (int i = 1; i < 4 && i < s.length(); i++)
        {
            String substr = s.substring(0, i);
            if (isValidIP(substr))
            {
                dfs(s.substring(i), tmp + substr + '.', result, count + 1);
            }
        }
    }

    private boolean isValidIP(String s)
    {
        if (s.charAt(0) == '0')
        {
            return s.equals("0");
        }
        int num = Integer.parseInt(s);
        return num <= 255 && num > 0;
    }

    //Validate Binary Search Tree
    public boolean isValidBST(TreeNode root)
    {
        return isValidate(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private boolean isValidate(TreeNode root, int min, int max)
    {
        if (root == null)
        {
            return true;
        }
        if (min >= root.val || max <= root.val)
        {
            return false;
        }
        return isValidate(root.left, min, root.val) && isValidate(root.right, root.val, max);
    }

    // Recover Binary Search Tree
    TreeNode pre;
    TreeNode first;
    TreeNode second;

    private void inorder(TreeNode root)
    {
        if (root == null)
            return;
        inorder(root.left);
        if (pre == null)
        {
            pre = root;
        }
        else
        {
            if (pre.val > root.val)
            {
                if (first == null)
                {
                    first = pre;
                }
                second = root;
            }
            pre = root;
        }
        inorder(root.right);
    }

    public void recoverTree(TreeNode root)
    {
        pre = null;
        first = null;
        second = null;
        inorder(root);
        if (first != null && second != null)
        {
            int tem = first.val;
            first.val = second.val;
            second.val = tem;
        }
    }

    //Same Tree
    public boolean isSameTree(TreeNode p, TreeNode q)
    {
        if (p == null)
        {
            return q == null;
        }
        if (q == null)
        {
            return p == null;
        }
        if (p.val != q.val)
        {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    //Symmetric Tree
    public boolean isSymmetric(TreeNode root)
    {
        if (root == null)
        {
            return true;
        }

        return isSymmetric(root.left, root.right);
    }

    private boolean isSymmetric(TreeNode left, TreeNode right)
    {
        if (left == null)
        {
            return right == null;
        }
        if (right == null)
        {
            return left == null;
        }
        if (left.val != right.val)
        {
            return false;
        }
        return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
    }

    //Construct Binary Tree from Preorder and Inorder Traversal
    public TreeNode buildTree(int[] preorder, int[] inorder)
    {
        int preLen = preorder.length;
        int inLen = inorder.length;
        return dfs(preorder, 0, preLen - 1, inorder, 0, inLen - 1);
    }

    private TreeNode dfs(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd)
    {
        if (preStart > preEnd)
        {
            return null;
        }

        int rootVal = preorder[preStart];
        int rootIndex = 0;

        for (int i = inStart; i <= inEnd; i++)
        {
            if (inorder[i] == rootVal)
            {
                rootIndex = i;
                break;
            }
        }

        int len = rootIndex - inStart;
        TreeNode root = new TreeNode(rootVal);
        root.left = dfs(preorder, preStart + 1, preStart + len, inorder, inStart, rootIndex - 1);
        root.right = dfs(preorder, preStart + len + 1, preEnd, inorder, rootIndex + 1, inEnd);

        return root;
    }

    //Convert Sorted Array to Binary Search Tree
    public TreeNode sortedArrayToBST(int[] num)
    {
        if (num == null || num.length == 0)
        {
            return null;
        }
        return dfs(num, 0, num.length - 1);
    }

    private TreeNode dfs(int[] num, int start, int end)
    {
        if (start > end)
        {
            return null;
        }
        int mid = (end - start) / 2 + start;
        TreeNode root = new TreeNode(num[mid]);
        root.left = dfs(num, start, mid - 1);
        root.right = dfs(num, mid + 1, end);
        return root;
    }

    //Balanced Binary Tree
    public boolean isBalanced(TreeNode root)
    {
        if (root == null)
        {
            return true;
        }
        if (Math.abs(getDepth(root.left) - getDepth(root.right)) > 1)
        {
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);
    }

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

    //Minimum Depth of Binary Tree
    public int minDepth(TreeNode root)
    {
        if (root == null)
        {
            return 0;
        }
        int a = minDepth(root.left);
        int b = minDepth(root.right);
        if (a * b != 0)
        {
            return Math.min(a, b) + 1;
        }
        else if (a == 0)
        {
            return b + 1;
        }
        else
        {
            return a + 1;
        }
    }

    //Path Sum
    public boolean hasPathSum(TreeNode root, int sum)
    {
        if (root == null)
        {
            return false;
        }
        if (root.left == null && root.right == null && root.val == sum)
        {
            return true;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }

    //Populating Next Right Pointers in Each Node
    public class TreeLinkNode
    {
        int val;
        TreeLinkNode left, right, next;

        TreeLinkNode(int x)
        {
            val = x;
        }
    }

    public void connect(TreeLinkNode root)
    {
        if (root == null)
        {
            return;
        }
        if (root.left != null)
        {
            root.left.next = root.right;
        }
        if (root.right != null && root.next != null)
        {
            root.right.next = root.next.left;
        }
        connect(root.left);
        connect(root.right);
    }

    //Populating Next Right Pointers in Each Node II
    public void connectII(TreeLinkNode root)
    {
        if (root == null)
        {
            return;
        }
        TreeLinkNode rootNext = root.next;
        TreeLinkNode next = null;
        while (rootNext != null)
        {
            if (rootNext.left != null)
            {
                next = rootNext.left;
                break;
            }
            else if (rootNext.right != null)
            {
                next = rootNext.right;
                break;
            }
            else
            {
                rootNext = rootNext.next;
            }
        }
        if (root.left != null)
        {
            if (root.right != null)
            {
                root.left.next = root.right;
            }
            else
            {
                root.left.next = next;
            }
        }
        if (root.right != null)
        {
            root.right.next = next;
        }
        //!!!! right first!!!
        connect(root.right);
        connect(root.left);
    }

    //Binary Tree Maximum Path Sum
    public int maxPathSum(TreeNode root)
    {
        int[] max = { Integer.MIN_VALUE };
        dfs(root, max);
        return max[0];
    }

    private int dfs(TreeNode root, int[] max)
    {
        if (root == null)
        {
            return 0;
        }
        int leftSubMaxSum = dfs(root.left, max);
        int rightSubMaxSum = dfs(root.right, max);
        int arch = leftSubMaxSum + root.val + rightSubMaxSum;

        int maxPathAcrossRootToParent = Math.max(root.val, Math.max(leftSubMaxSum, rightSubMaxSum) + root.val);
        max[0] = Math.max(max[0], Math.max(arch, maxPathAcrossRootToParent));
        return maxPathAcrossRootToParent;
    }

    //Sum Root to Leaf Numbers
    public int sumNumbers(TreeNode root)
    {
        int[] result = { 0 };
        int current = 0;
        dfs(root, current, result);
        return result[0];
    }

    private void dfs(TreeNode root, int current, int[] result)
    {
        if (root == null)
        {
            return;
        }
        current = current * 10 + root.val;
        if (root.left == null && root.right == null)
        {
            result[0] += current;
            return;
        }
        dfs(root.left, current, result);
        dfs(root.right, current, result);
    }

    //Palindrome Partitioning
    public List> partition(String s)
    {
        ArrayList> result = new ArrayList>();
        if (s == null || s.length() == 0)
        {
            return result;
        }
        ArrayList array = new ArrayList();
        HashMap map = new HashMap();
        dfs(s, 0, map, result, array);
        return result;
    }

    private void dfs(String s, int index, HashMap map, ArrayList> result, ArrayList array)
    {
        if (index == s.length())
        {
            result.add(new ArrayList(array));
            return;
        }
        for (int i = index; i < s.length(); i++)
        {
            boolean isPalindrome = false;
            String subString = s.substring(index, i + 1);
            if (map.get(subString) != null)
            {
                isPalindrome = map.get(subString);
            }
            else
            {
                isPalindrome = checkIsPalindrome(subString);
                map.put(subString, isPalindrome);
            }
            if (isPalindrome)
            {
                array.add(subString);
                dfs(s, i + 1, map, result, array);
                //TODO: why remove last???
                array.remove(array.size() - 1);
            }
        }
    }

    private boolean checkIsPalindrome(String s)
    {
        int i = 0;
        int j = s.length() - 1;
        while (i < j)
        {
            if (s.charAt(i) != s.charAt(j))
            {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

Jump Game II - LeetCode

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

-----
It is easy to thought using DP to solve this problem. However, there is some generous guy find a easy solution. (You should convince yourself that there always exits someone smarter than you, haha).

public class Solution {
    int jump(int A[], int n) {
        int numJump = 0;
        int lastLongestDisCanBeCover = 0;
        int currLongestDisCanBeCover = 0;
        for (int i = 0; i < n; ++i) {
            if (i > lastLongestDisCanBeCover) {
                lastLongestDisCanBeCover = currLongestDisCanBeCover;
                ++ numJump;
            }
            currLongestDisCanBeCover = max(currLongestDisCanBeCover, i+A[i]);
        }
        return numJump;
    }
};

The basic idea with this algorithm is scan the array and find every element the longest distances they can reach.