LeetCode - Circular Array Loop

16 Mar 2018 • LeetCode(Second)

Question Definition

You are given an array of positive and negative integers. If a number n at an index is positive, then move forward n steps. Conversely, if it’s negative (-n), move backward n steps. Assume the first element of the array is forward next to the last element, and the last element is backward next to the first element. Determine if there is a loop in this array. A loop starts and ends at a particular index with more than 1 element along the loop. The loop must be “forward” or “backward’.

More …

LeetCode - Binary Tree Preorder Traversal

16 Mar 2018 • LeetCode(Second)

Question Definition

Given a binary tree, return the preorder traversal of its nodes’ values.

For example: Given binary tree [1,null,2,3],

   1
    \
     2
    /
   3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

Java Solution

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new LinkedList<>();
    if(root == null) return result;

    Deque<TreeNode> deque = new ArrayDeque<>();
    deque.push(root);

    while(!deque.isEmpty()){
        TreeNode temp = deque.pop();
        result.add(temp.val);
        if(temp.right != null) deque.push(temp.right);
        if(temp.left != null) deque.push(temp.left);
    }
    return result;
}

LeetCode - Binary Search Tree Iterator

16 Mar 2018 • LeetCode(Second)

Question Definition

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

Java Solution

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

public class BSTIterator {
    private Deque<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        stack = new ArrayDeque<>();
        while(root != null) {
            stack.push(root);
            root = root.left;
        }
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    /** @return the next smallest number */
    public int next() {
        TreeNode temp = stack.pop();
        int result = temp.val;
        temp = temp.right;
        while(temp != null){
            stack.push(temp);
            temp = temp.left;
        }
        return result;
    }
}

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = new BSTIterator(root);
 * while (i.hasNext()) v[f()] = i.next();
 */

LeetCode - Palindrome Partitioning

15 Mar 2018 • LeetCode(Second)

Question Definition

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = “aab”, Return

[
  ["aa","b"],
  ["a","a","b"]
]

Java Solution

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new LinkedList<>();
        List<String> cur = new LinkedList<>();
        helper(s, 0, cur, result);
        return result;
    }

    private void helper(String s, int start, List<String> cur, List<List<String>> result){
        if(start == s.length()){
            result.add(new LinkedList<>(cur));
            return;
        }
        for(int i = start + 1; i <= s.length(); i++){
            if(isPalindrome(s, start, i - 1)){
                cur.add(s.substring(start, i));
                helper(s, i, cur, result);
                cur.remove(cur.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s, int start, int end){
        if(start == end) return true;
        while(start < end){
            if(s.charAt(start) != s.charAt(end)) return false;
            start++;
            end--;
        }
        return true;
    }
}