248. Strobogrammatic Number III

21.52 %
class Solution {
    public int strobogrammaticInRange(String low, String high) {
        // 1 1
        // 6 9
        // 8 8
        // 9 6
        // 0 0
        int start = low.length(), end = high.length();
        List<String> rawResult = new ArrayList<>();
        for (int i = start; i <= end; i++) {
            rawResult.addAll(helper(i));
            List<String> curr = helper(i);
        }
        int count = 0;
        for (String str : rawResult) {
            if ((str.length() > 1 && str.charAt(0) == '0')
               || (str.length() == low.length() && str.compareTo(low) < 0)
               || (str.length() == high.length() && str.compareTo(high) > 0)) continue;
            count++;
        }
        return count;
    }
   
    private List<String> helper(int len) {
        if (len == 0) return Arrays.asList(new String[]{""});
        if (len == 1) return Arrays.asList(new String[]{"0", "1", "8"});
       
        List<String> result = new ArrayList<>();
        List<String> center = helper(len - 2);
        for (String cen : center) {
            result.add("1" + cen + "1");
            result.add("6" + cen + "9");
            result.add("8" + cen + "8");
            result.add("9" + cen + "6");
            result.add("0" + cen + "0");
        }
        return result;
    }
}

150. Evaluate Reverse Polish Notation

Version #1 Stack

15.27 %
class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            String curr = tokens[i];
            if (curr.equals("+") || curr.equals("-") || curr.equals("*") || curr.equals("/")) {
                int operand2 = stack.pop();
                int operand1 = stack.pop();
                int res = 0;
                switch (curr) {
                    case "+":
                        res = operand1 + operand2;
                        break;
                    case "-":
                        res = operand1 - operand2;
                        break;
                    case "*":
                        res = operand1 * operand2;
                        break;
                    case "/":
                        res = operand1 / operand2;
                }
                stack.push(res);
            } else {
                stack.push(Integer.valueOf(curr));
            }
        }
        return stack.pop();
    }
}

115. Distinct Subsequences

Version #1 DP
1st row must be 1s because we are using s to match empty string
and an empty string is the subsequence of any string

10.00 %
class Solution {
    public int numDistinct(String s, String t) {
        // dp[i][j] -> number of ways to match s.substring[0, i) with t.substring[0, j)
        // if (s.charAt(i - 1) == t.charAt(j - 1))
        // dp[i][j] += for all k, s.charAt(k - 1) == t.charAt(j - 2)
        // if j == 1, dp[i][j] = 1
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        for (int i = 0; i <= s.length(); i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= t.length(); j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    // use or not use
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j]; // cannot use
                }
            }
        }
        return dp[s.length()][t.length()];
    }
}

918. Maximum Sum Circular Subarray

Bug
One** corner case** to pay attention:
If all number are negative,
return the maximum one,
(which equals to the max subarray sum)

If the maximum sum is negative, means all numbers are negative
In this case, total sum is the minimum one -> total sum - min sum = 0, which is not a valid subarray
So when maxSum < 0, return maxSum

21.88 %
class Solution {
    public int maxSubarraySumCircular(int[] A) {
        // max subarray sum, min suarray sum
        // result = Math.max(max, totalSum - min)
        if (A == null || A.length == 0) return 0;
        int prevMin = A[0], prevMax = A[0]; // min/max subarray sum end with i-1
        int sum = A[0], max = A[0], min = A[0];
        for (int i = 1; i < A.length; i++) {
            sum += A[i];
            int currMin = Math.min(prevMin, 0) + A[i];
            int currMax = Math.max(prevMax, 0) + A[i];
            max = Math.max(max, currMax);
            min = Math.min(min, currMin);
            prevMin = currMin;
            prevMax = currMax;
        }
        return max > 0 ? Math.max(max, sum - min) : max;
    }
}

152. Maximum Product Subarray

Version #1 Optimized DP
是一个dp题，对于乘法来说情况比较特殊，因为有负数
如果一个绝对值非常大的负数再乘一个负数，负负得正，有产生最大值的可能
所以要同时keep track of dpMin 以及dpMax
更新dp的时候要考虑也可是nums[i] 单独成为最大或者最小


70.82 %
class Solution {
    public int maxProduct(int[] nums) {
        // pos[i] -> maxProduct ends with current nums[i]
        // neg[i] -> minProduct ends with current nums[i]
        // pos[i] = Math.max(nums[i], Math.max(post[i - 1] * nums[i], neg[i - 1] * nums[i]));
        // neg[i] = Math.min(nums[i], Math.min(post[i - 1] * nums[i], neg[i - 1] * nums[i]));
        int result = Integer.MIN_VALUE;
        int pos = 1, neg = 1;
        for (int i = 0; i < nums.length; i++) {
            int currPos = Math.max(nums[i], Math.max(pos * nums[i], neg * nums[i]));
            int currNeg = Math.min(nums[i], Math.min(pos * nums[i], neg * nums[i]));
            pos = currPos;
            neg = currNeg;
            result = Math.max(pos, result);
        }
        return result;
    }
}

780. Reaching Points

Follow up:
What if any x, y can be negative
对source的正负号进行分类讨论， 如果同号，则可以转化成原题
因为如果source的xy value同负，那么target也只能是负的

所以最后只需要讨论xy异号的情况， 易知由于xy异号所以abs(x + y) will always become closer to zero
所以我们尝试枚举出所有这样的情况直到xy同号，然后问题退化成原问题

95.45 %
class Solution {
    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        // all sx,sy,tx,ty are larger than zero
        // if (tx > ty) -> it can only be generated from (tx - ty, ty)
        // we can keep subtract ty from tx until tx < ty
        // new tx = tx - kty = tx % ty
        while (tx > sx && ty > sy) {
            if (tx > ty) {
                tx = tx % ty;
            } else {
                ty = ty % tx;
            }
        }
        return tx == sx && (ty - sy) % tx == 0 ||
            ty == sy && (tx - sx) % ty == 0;
    }
}

337. House Robber III

三刷 07/2022

Version #2 Bottom up DFS

Time O(N)

Space O(H) - height of the tree, worst O(N)

Runtime: 1 ms, faster than 92.27% of Java online submissions for House Robber III.

Memory Usage: 44.8 MB, less than 29.44% of Java online submissions for House Robber III.

class Solution {

    public int rob(TreeNode root) {

        int[] result = robHelper(root);

        return Math.max(result[0], result[1]);

    }

    

    private int[] robHelper(TreeNode node) {

        int[] result = new int[2];

        if (node == null) {

            return result;

        }

        int[] left = robHelper(node.left);

        int[] right = robHelper(node.right);

        result[0] = node.val + left[1] + right[1];

        result[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

        return result;

    }

}

二刷  06/2022

Version #2 Bottom up DFS

我们return一个int[]表示rob current node/ not rob current node两个结果

每个node保证只visited一次

Time O(N)

Space - depth of the stack, O(N) worst, O(logN) best

Runtime: 0 ms, faster than 100.00% of Java online submissions for House Robber III.

Memory Usage: 41.5 MB, less than 98.09% of Java online submissions for House Robber III.

class Solution {

    public int rob(TreeNode root) {

        // For each node, return two values - int[0] max if rob the house, int[1] max of the children no matter rob or not rob

        int[] res = robHelper(root);

        return Math.max(res[0], res[1]);

    }

    

    private int[] robHelper(TreeNode node) {

        if (node == null) {

            return new int[]{0, 0};

        }

        // leaf

        if (node.left == null && node.right == null) {

            return new int[]{node.val, 0};

        }

        int[] left = robHelper(node.left);

        int[] right = robHelper(node.right);

        // if we rob the house, then we cannot rob it's children

        int curr = node.val + left[1] + right[1];

        // if not rob, we are free to choose rob the children or not

        int children = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

        return new int[]{curr, children};

    }

} 

一刷
Version #1 DFS


67.32 %
class Solution {
    public int rob(TreeNode root) {
        Map<TreeNode, Integer> map = new HashMap<>();
        return dfs(root, map);
    }
   
    private int dfs(TreeNode node, Map<TreeNode, Integer> map) {
        // max amount of money we can get if we enter through this node
        if (node == null) {
            return 0;
        }
        if (map.containsKey(node)) return map.get(node);
       
        // if we rob this node, then we can't rob any of its child node
        int curr = node.val;
        if (node.left != null) {
            curr += dfs(node.left.left, map) + dfs(node.left.right, map);
        }
        if (node.right != null) {
            curr += dfs(node.right.left, map) + dfs(node.right.right, map);
        }
       
        curr = Math.max(curr, dfs(node.left, map) + dfs(node.right, map));
        map.put(node, curr);
        return curr;
    }
}