LeetCode 226. Invert Binary Tree

Problem:

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Trivia:
This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

Solution:

The famous Google interview question for Max Howell ROFL.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

LeetCode 213. House Robber II

Problem:

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

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

Solution:

public class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        return Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1));
    }
    
    private int rob(int[] nums, int low, int high) {
        int include = 0, exclude = 0;
        for (int i = low; i <= high; i++) {
            int tmp = include;
            include = exclude + nums[i];
            exclude = Math.max(exclude, tmp);
        }
        return Math.max(include, exclude);
    }
}

 

LeetCode 337. House Robber III

Problem:

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

     3
    / \
   2   3
    \   \ 
     3   1

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

     3
    / \
   4   5
  / \   \ 
 1   3   1

Maximum amount of money the thief can rob = 4 + 5 = 9.

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

Solution:

DP, at first I just did it recursively and it was AWFUL.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    HashMap<TreeNode, Integer> map = new HashMap<>();
    
    public int rob(TreeNode root) {
        if (root == null) return 0;
        if (map.containsKey(root)) return map.get(root);
        int rob0 = robNot(root);
        int rob1 = robYes(root);
        int max = Math.max(rob0, rob1);
        map.put(root, max);
        return max;
    }
    
    private int robYes(TreeNode root) {
        if (root == null) return 0;
        return root.val + robNot(root.left) + robNot(root.right);
    }
    
    private int robNot(TreeNode root) {
        if (root == null) return 0;
        return rob(root.left) + rob(root.right);
    }
}

LeetCode 238. Product of Array Except Self

Problem:

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements ofnums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

Solution:

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] output = new int[nums.length];
        output[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            output[i] = output[i-1] * nums[i-1];
        }
        int right = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            output[i] *= right;
            right *= nums[i];
        }
        return output;
    }
}

LeetCode 279. Perfect Squares

Problem:

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

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

Solution:

DP

public class Solution {
    
    public int numSquares(int n) {
        int[] least = new int[n+1];
        int root = 0;
        for (int i = 0; i <= n; i++) {
            if (i == root * root) {
                least[i] = 1;
                root++;
                continue;
            }
            int min = Integer.MAX_VALUE;
            for (int j = 1; j * j < i; j++)
                min = Math.min(least[j*j] + least[i-j*j], min);
            least[i] = min;
        }
        return least[n];
    }
}

LeetCode 382. Linked List Random Node

Problem:

Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen.

Follow up:
What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

Example:

// Init a singly linked list [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();

Solution:

Not using Reservoir Sampling, but I found this post that describes the process.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {

    int count;
    ListNode head;
    
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    public Solution(ListNode head) {
        count = 0;
        this.head = head;
        ListNode current = head;
        while (current != null) {
            current = current.next;
            count++;
        }
    }
    
    /** Returns a random node's value. */
    public int getRandom() {
        Random random = new Random();
        int rnd = random.nextInt(count);
        ListNode current = head;
        for (int i = 0; i < rnd; i++)
            current = current.next;
        return current.val;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.getRandom();
 */

LeetCode 59. Spiral Matrix II

Problem:

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

Solution:

Just like Spiral Matrix problem.

public class Solution {
    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];
        if (n == 0) return result;
        int x = n, y = n;
        int row = 0, col = -1;
        int num = 0;
        while (true) {
            for (int i = 0; i < x; i++)
                result[row][++col] = ++num;
            if (--y == 0) break;
            for (int i = 0; i < y; i++)
                result[++row][col] = ++num;
            if (--x == 0) break;
            for (int i = 0; i < x; i++)
                result[row][--col] = ++num;
            if (--y == 0) break;
            for (int i = 0; i < y; i++)
                result[--row][col] = ++num;
            if (--x == 0) break;
        }
        return result;
    }
}

LeetCode 172. Factorial Trailing Zeroes

Problem:

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

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

Solution:

public class Solution {
    public int trailingZeroes(int n) {
        int deg = 5;
        int div = n/deg;
        int result = div;
        while(div > 1) {
            deg *= 5;
            div  = n/deg;
            result += div;
        }
        return result;
    }
}

LeetCode 39. Combination Sum

Problem:

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

[
  [7],
  [2, 2, 3]
]

Solution:

Should’ve used DP but whatever I passed.

public class Solution {
    List<List<Integer>> result;
    int[] candidates;
    int target;
    
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        result = new ArrayList<List<Integer>>();
        this.candidates = candidates;
        this.target = target;
        List<Integer> option = new ArrayList<Integer>();
        tryOption(option, 0);
        return result;
    }
    
    private void tryOption(List<Integer> option, int sum) {
        if (sum > target) return;
        if (sum == target) {
            List<Integer> copy = new ArrayList<Integer>(option);
            result.add(copy);
            return;
        }
        for (int candy: candidates) {
            if (option.size() > 0 && candy < option.get(option.size() - 1)) continue;
            option.add(candy);
            tryOption(option, sum + candy);
            option.remove((Integer)candy);
        }
    }
}