leetcode #537: Complex Number Multiplication

public class Solution {
    public String complexNumberMultiply(String a, String b) {
        int aP = a.indexOf('+'), bP = b.indexOf('+');
        int a1 = Integer.parseInt(a.substring(0, aP)), a2 = Integer.parseInt(a.substring(aP + 1, a.length() - 1));
        int b1 = Integer.parseInt(b.substring(0, bP)), b2 = Integer.parseInt(b.substring(bP + 1, b.length() - 1));
        return (a1 * b1 - a2 * b2) + "+" + (a1 * b2 + b1 * a2) + "i";
    }
}

leetcode #507: Perfect Number

public class Solution {
    public boolean checkPerfectNumber(int num) {
        int end = (int) Math.sqrt((double) num), result = num;
        for (int i = 2; i <= end; i++) {
            if (num % i == 0) {
                result -= i + num / i;
            }
        }
        return result == 1 && num != 1;
    }
}

[Algorithm 101] 0-1 Knapsack Problem

We start this problem with leetcode #494: Target Sum:

You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Assume positive subset P and negative subset N are of one possible way, hence P and N meet the requirement:

sum\left ( P \right ) - sum\left ( N \right ) = S

As the problem implies, the union of subset P and subset N is nums, and the intersection of subset P and subset N is empty(for each element of nums is either positive or negative), so:

sum\left ( P \right ) + sum\left ( N \right ) = sum\left ( nums \right )

So the problem is equivalent to: find subset P from set nums that sum(P) = (S + sum(nums)) / 2, which is a variation of 0-1 knapsack problem.

0-1 Knapsack Problem

Given two integer arrays value[0, …, i – 1] and weight[0, …, i – 1] which represent values and weights associated with i items respectively, and a knapsack of capacity W, find the most valuable subset of the items that fit into the knapsack. We assume here that all the weights and the knapsack’s capacity are positive integers; the items values do not have to be integers.

To design a dynamic programming algorithm, we need to derive a recurrence relation that express a solution to a instance of the knapsack problem in terms of solutions to its smaller subinstances. Let f[i][w] to be the value of an optimal solution to this instance, i.e., the most valuable subset of the first ith items that fit into the knapsack of capacity w.

First, we need to consider some corner cases:

  • f[0][w] = 0(0 <= w <= W ), for i = 0 means when we don’t choose any item, the max value must be 0.
  • f[i][0] = 0(i >= 0), for w = 0 means no capacity is available, the max value must be 0.

For f[i][w](i >= 1), we have two choices:

  • among the subsets that do not include the ith item, the value of an optimal subset is f[i – 1][w];
  • among the subsets that do include the ith item, an optimal subset is made up of this item and an optimal subset of the first i – 1 items that fit into the knapsack of capacity w – weight[i], the value of such an optimal subset is f[i – 1][w – weight[i]] + value[i](w >= weight[i]).

Thus f[i][w] = max{f[i – 1][w] , f[i – 1][w – weight[i]] + value[i] }, the overall formulation is:

f\left [ i \right ]\left [ w \right ] = \left\{\begin{matrix}\\0 & if\ i = 0\ or\ w = 0\\f\left [ i - 1 \right ]\left [ w \right ] & weight\left [ i \right ] > w\\max \left \{ f\left [ i - 1 \right ]\left [ w \right ], f\left [ i - 1 \right ]\left [ w - weight\left [ i \right ] \right ] + value\left [ i \right ] \right \} & weight\left [ i \right ] \leq w\\\end{matrix}\right.

And here is our algorithm:

public class Knapsack {
    static int knapsack(int W, int weight[], int value[]) {
        int f[][] = new int[weight.length + 1][W + 1];

        for (int i = 1; i <= weight.length; i++) {
            for (int w = 1; w <= W; w++) {
                if (weight[i - 1] <= w) {
                    f[i][w] = Math.max(f[i - 1][w], f[i - 1][w - weight[i - 1]] + value[i - 1]);
                } else {
                    f[i][w] = f[i - 1][w];
                }
            }
        }

        return f[weight.length][W];
    }

    public static void main(String[] args) {
        System.out.println(knapsack(5, new int[]{2, 3, 4, 5}, new int[]{3, 4, 5, 6}));
    }
}

Reduce Space Complexity

The method’s space complexity and time complexity are both O(W * weight.length), is there any further optimization?

State f[i][w] is associated with two previous state only: f[i – 1][w] and f[i – 1][w – weight[i]], if f[i – 1][w] and f[i – 1][w – weight[i]] can be kept while calculating f[i][w], space complexity should be reduced to O(W), and this can be achieved by reversing the inner loop:

public class Knapsack {
    static int knapsack(int W, int weight[], int value[]) {
        int f[] = new int[W + 1];

        for (int i = 1; i <= weight.length; i++) {
            for (int w = W; w >= 1; w--) {
                if (weight[i - 1] <= w) {
                    f[w] = Math.max(f[w], f[w - weight[i - 1]] + value[i - 1]);
                }
            }
        }

        return f[W];
    }

    public static void main(String[] args) {
        System.out.println(knapsack(5, new int[]{2, 3, 4, 5}, new int[]{3, 4, 5, 6}));
    }
}

And of course, the if statement can be removed by updating the inner loop condition:

public class Knapsack {
    static int knapsack(int W, int weight[], int value[]) {
        int f[] = new int[W + 1];
        for (int i = 1; i <= weight.length; i++) {
            for (int w = W; w >= weight[i - 1]; w--) {
                f[w] = Math.max(f[w], f[w - weight[i - 1]] + value[i - 1]);
            }
        }
        return f[W];
    }

    public static void main(String[] args) {
        System.out.println(knapsack(5, new int[]{2, 3, 4, 5}, new int[]{3, 4, 5, 6}));
    }
}

A Minor Improvement On Time Complexity

f[W] is what we care, which is affected by state f[W – weight[i – 1]], and f[W – weight[i – 1]] is affected by state f[W – weight[i – 1] – weight[i – 2]], etc. For the kth item, the inner loop end condition can be subjected to max{W – sum{weight[ki]}, weight[i]}:

public class Knapsack {
    static int knapsack(int W, int weight[], int value[]) {
        int f[] = new int[W + 1], sum = 0;
        for (int w : weight) sum += w;

        for (int i = 1; i <= weight.length; i++) {
            int bound = Math.max(W - sum, weight[i - 1]);
            for (int w = W; w >= bound; w--) {
                f[w] = Math.max(f[w], f[w - weight[i - 1]] + value[i - 1]);
            }
            sum -= weight[i - 1];
        }

        return f[W];
    }

    public static void main(String[] args) {
        System.out.println(knapsack(5, new int[]{2, 3, 4, 5}, new int[]{3, 4, 5, 6}));
    }
}

Back To Problem Target Sum

Let dp[n] to be count of the possible ways to add up to n, here is the DP solution for the original problem:

public class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int num : nums) sum += num;
        if (sum < S || -sum > S || (sum + S) % 2 == 1) return 0;

        int target = (sum + S) >>> 1, dp[] = new int[target + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int i = target; i >= num; i--) {
                dp[i] += dp[i - num];
            }
        }
        return dp[target];
    }
}

leetcode #494: Target Sum

  • BFS
import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        if (nums.length == 0) return 0;

        HashMap<Integer, Integer> cache = new HashMap<>();
        cache.put(nums[0], 1);
        cache.put(-nums[0], cache.getOrDefault(-nums[0], 0) + 1);
        for (int i = 1; i < nums.length; i++) {
            HashMap<Integer, Integer> tmp = new HashMap<>();
            for (Map.Entry<Integer, Integer>entry : cache.entrySet()) {
                tmp.put(entry.getKey() + nums[i], tmp.getOrDefault(entry.getKey() + nums[i], 0) + entry.getValue());
                tmp.put(entry.getKey() - nums[i], tmp.getOrDefault(entry.getKey() - nums[i], 0) + entry.getValue());
            }
            cache = tmp;
        }
        return cache.getOrDefault(S, 0);
    }
}
  • DFS
public class Solution {
    private int result = 0;

    public int findTargetSumWays(int[] nums, int S) {
        travel(nums, 0, 0, S);
        return result;
    }

    private void travel(int[] nums, int tmp, int index, int target) {
        if (index == nums.length - 1) {
            if (tmp + nums[index] == target) result++;
            if (tmp - nums[index] == target) result++;
        } else if(index < nums.length - 1) {
            travel(nums, tmp + nums[index], index + 1, target);
            travel(nums, tmp - nums[index], index + 1, target);
        }
    }
}
  • DP
public class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int num : nums) sum += num;
        if (S < -sum || S > sum) return 0;

        int[] dp = new int[sum * 2 + 1];
        dp[sum] = 1;
        for (int num : nums) {
            int[] tmp = new int[dp.length];
            for (int j = 0; j < dp.length; j++) {
                if (dp[j] != 0) {
                    tmp[j + num] += dp[j];
                    tmp[j - num] += dp[j];
                }
            }
            dp = tmp;
        }
        return dp[S + sum];
    }
}

The DP Solution can be explained by this picture below:

  1. calculate sum of the given array nums[], return 0 if S > sum or S < -sum. When S is larger than sum of all numbers positive in nums[] or S is smaller than sum of all numbers negetive in nums[], further caculation is not necessary.
  2. init dp[] with length sum * 2 + 1. dp[n] represents the number of ways to sum up to number n - sum, and dp[sum] should be 1, which means given an empty array, we can get one way to sum up to zero.
  3. loop the given array nums[], and update dp[] each round by the formulation: dp[j +/- num] += dp[j]. each element in nums[] contributes either +num or -num, so we update dp[j + num] and dp[j - num] by adding dp[j].
  4. the number of ways to sum up to S is dp[sum + S].

leetcode #538: Convert BST to Greater Tree

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

    public TreeNode convertBST(TreeNode root) {
        if (root == null) return null;
        convertBST(root.right);
        root.val += tmp;
        tmp = root.val;
        convertBST(root.left);
        return root;
    }
}

leetcode #543: Diameter of Binary Tree

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

    public int diameterOfBinaryTree(TreeNode root) {
        travel(root);
        return result;
    }

    private int travel(TreeNode treeNode) {
        if (treeNode == null) return -1;
        int left = travel(treeNode.left) + 1, right = travel(treeNode.right) + 1;
        result = Math.max(result, left + right);
        return Math.max(right, left);
    }
}

leetcode #113: Path Sum II

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private List<List<Integer>> result = new ArrayList<>();
    private Stack<Integer> stack = new Stack<>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root == null) return result;
        stack.add(root.val);
        if (root.left == null && root.right == null && sum == root.val) result.add(new ArrayList<>(stack));
        pathSum(root.left, sum - root.val);
        pathSum(root.right, sum - root.val);
        stack.pop();
        return result;
    }
}

leetcode #539: Minimum Time Difference

import java.util.Collections;
import java.util.List;

public class Solution {
    public int findMinDifference(List<String> timePoints) {
        Collections.sort(timePoints);
        int result = 720;
        for (int i = 0; i < timePoints.size(); i++) {
            String m = timePoints.get(i), n = timePoints.get((i + 1) % timePoints.size());
            int a = ((m.charAt(0) - 48) * 10 + m.charAt(1) - 48) * 60 + (m.charAt(3) - 48) * 10 + m.charAt(4) - 48;
            int b = ((n.charAt(0) - 48) * 10 + n.charAt(1) - 48) * 60 + (n.charAt(3) - 48) * 10 + n.charAt(4) - 48;
            result = Math.min(result, Math.min(((a - b) + 1440) % 1440, ((b - a) + 1440) % 1440));
        }
        return result;
    }
}

leetcode #536: Construct Binary Tree from String

/**
 * 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 str2tree(String s) {
        if (s.length() == 0) return null;

        int firstLeftP = s.indexOf('(');
        if (firstLeftP == -1) return new TreeNode(Integer.valueOf(s));
        TreeNode result = new TreeNode(Integer.valueOf(s.substring(0, firstLeftP)));

        int counter = 1, secondLeftP = firstLeftP + 1;
        while (counter != 0) {
            if (s.charAt(secondLeftP) == ')') {
                counter--;
            } else if (s.charAt(secondLeftP) == '('){
                counter++;
            }
            secondLeftP++;
        }

        result.left = str2tree(s.substring(firstLeftP + 1, secondLeftP - 1));
        result.right = secondLeftP == s.length() ? null : str2tree(s.substring(secondLeftP + 1, s.length() - 1));
        return result;
    }
}

leetcode #541: Reverse String II

public class Solution {
    public String reverseStr(String s, int k) {
        char[] tmp = s.toCharArray();
        for (int i = 0; i < s.length(); i += 2 * k) {
            int start = i, end = Math.min(i + k - 1, s.length() - 1);
            while (start < end) {
                char c = tmp[start];
                tmp[start++] = tmp[end];
                tmp[end--] = c;
            }
        }
        return new String(tmp);
    }
}