65. Valid Number

Version #1 Go library

10.61 % 

import (
    "strconv"
    "strings"
)
func isNumber(s string) bool {
    _, err := strconv.ParseFloat(strings.TrimSpace(s), 64)
    return err == nil || strings.Contains(err.Error(), "value out of range")
}

[Go]Notes

Defer

A defer statement defers the execution of a function until the surrounding function returns.

The deferred call's arguments are evaluated immediately, but the function call is not executed until the surrounding function returns.

Closures

https://www.calhoun.io/5-useful-ways-to-use-closures-in-go/

[Go]Exercise: Loops and Functions

package main

import (
"fmt"
"math"
)

const Delta = 1e-10
func Sqrt(x float64) float64 {
i := 0
z := float64(1)
prev := z
for i < 10 {
z -= (z * z - x) / (2 * z)
fmt.Println(z)
if math.Abs(z - prev) < Delta {
break;
}
prev = z
i++
}
return z
}

func main() {
fmt.Println(Sqrt(2))
}

[Go]Methods are functions

Methods
A method is a function with a special receiver argument.

package main

import (
"fmt"
"math"
)

type Vertex struct {
X, Y float64
}

func (v Vertex) Abs() float64 {
return math.Sqrt(v.X*v.X + v.Y*v.Y)
}

func main() {
v := Vertex{3, 4}
fmt.Println(v.Abs())
}

------------------------------------------------------------------
Regular Function
package main

import (
"fmt"
"math"
)

type Vertex struct {
X, Y float64
}

func Abs(v Vertex) float64 {
return math.Sqrt(v.X*v.X + v.Y*v.Y)
}

func main() {
v := Vertex{3, 4}
fmt.Println(Abs(v))
}

[Go]Fibonacci closure

Version #2 "Go" Version

package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an int.
func fibonacci() func() int {
prev := -1
curr := 1
return func() int {
prev, curr = curr, prev + curr
return curr
}
}

func main() {
f := fibonacci()
for i := 0; i < 10; i++ {
fmt.Println(f())
}
}

Version #1 "Java" Version
package main

import "fmt"

// fibonacci is a function that returns
// a function that returns an int.
func fibonacci() func() int {
prev := 0
curr := 1
return func() int {
next := prev + curr
prev = curr
curr = next
return prev
}
}

func main() {
f := fibonacci()
for i := 0; i < 10; i++ {
fmt.Println(f())
}
}

659. Split Array into Consecutive Subsequences

Greedily append the element to previous sequences
Always try to append
Only create a single sequence if we are not able to append

class Solution {
    public boolean isPossible(int[] nums) {
        // For every distinct number, we keep track of then consective sequence end with num
        // whose length are 1 2 3
        int prev = Integer.MIN_VALUE, p1 = 0, p2 = 0, p3 = 0;
        for (int i = 0; i < nums.length; i++) {
            int curr = nums[i];
            int c1 = 0, c2 = 0, c3 = 0;
            int count = 1;
            // accumulate numbers with same value as curr
            while (i < nums.length - 1 && nums[i + 1] == curr) {
                count++;
                i++;
            }
           
            // cannot append to previous number
            if (curr != prev + 1) {
                if (p1 != 0 || p2 != 0) return false;
                c1 = count;
            } else { // append to p1 first
                if (count < p1 + p2) return false;
                c2 = p1;
                c3 = p2 + Math.min(p3, count - (p1 + p2));
                c1 = Math.max(0, count - (p1 + p2 + p3));
            }
            prev = curr;
            p1 = c1;
            p2 = c2;
            p3 = c3;
        }
        return p1 == 0 && p2 == 0;
    }
}

499. The Maze III

Version #1 Dijastra

几个需要注意的点
首先visited是必须要有的，否则impossible就是infinite loop
但是不应该是个boolean而应该是一个int，因为一个点可以通过不同的path被到达，只要后来的dist <= visited[ny][nx]都可以
因为hole不一定是球可以停住的状态，所以第一次经过不一定是最佳答案
需要存起来然后每次经过的话都去更新

 73.91 %
class Solution {
    class Point implements Comparable<Point> {
        int x, y, dist;
        String path;
        public Point(int y, int x, int dist, String path) {
            this.x = x;
            this.y = y;
            this.dist = dist;
            this.path = path;
        }
        @Override
        public int compareTo(Point p) {
            if (this.dist != p.dist) {
                return this.dist - p.dist;
            } else {
                return this.path.compareTo(p.path);
            }
        }
    }
    private int rows, cols;
    private int[] dx = new int[]{1, 0, -1, 0};
    private int[] dy = new int[]{0, -1, 0, 1};
    private char[] direction = new char[]{'r', 'u', 'l', 'd'};
    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        // priorityQueue of int[] poisition + int dist so far
        // when we pop one element out, we have four choices
        // 1.minHeap ordered by dist
        // 2.original point into minHeap
        // polling from minHeap, try 4 directions and walk
        // if we can walk to that direction (move more than 0 step, destination not visited)
        // if we see hole while rolling, return the final steps directly
        // offer into minHeap with destination position and new distance
       
        if (maze == null || maze.length == 0 || maze[0] == null || maze[0].length == 0) {
            return "impossible";
        }
        PriorityQueue<Point> minHeap = new PriorityQueue<>();
        rows = maze.length;
        cols = maze[0].length;
        int[][] visited = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            Arrays.fill(visited[i], Integer.MAX_VALUE);
        }
        minHeap.offer(new Point(ball[0], ball[1], 0, ""));
        visited[ball[0]][ball[1]] = 0;
        Point minResult = null;
        while (!minHeap.isEmpty()) {
            Point curr = minHeap.poll();
            int x = curr.x;
            int y = curr.y;
            int dist = curr.dist;
            if (minResult != null && dist > minResult.dist) break;
            String path = curr.path;
            for (int i = 0; i < 4; i++) {
                // try to roll to direction
                int step = 0;
                int nx = x, ny = y;
                while (isValid(ny + dy[i], nx + dx[i]) && maze[ny + dy[i]][nx + dx[i]] == 0) {
                    ny += dy[i];
                    nx += dx[i];
                    step++;
                    if (ny == hole[0] && nx == hole[1]) {
                        Point temp = new Point(ny, nx, dist + step, path + direction[i]);
                        if (minResult == null || temp.compareTo(minResult) < 0) {
                            minResult = temp;
                        }
                    }
                }
                if (step > 0 && dist + step <= visited[ny][nx]) {
                    visited[ny][nx] = dist + step;
                    minHeap.offer(new Point(ny, nx, dist + step, path + direction[i]));
                }
               
            }
        }
        return minResult == null ? "impossible" : minResult.path;
    }
   
    private boolean isValid(int y, int x) {
        return x >= 0 && x < cols && y >= 0 && y < rows;
    }
}

494. Target Sum

二刷 06/2022

Version #1 1D DP

不知道为啥intuitively就是觉得特别简单，完全没有想到recursion上面去

思路就是until index i我们有一个map维护之前全部的sum可能性

然后当前有可能+nums[i]/-nums[i],再更新map

Time O(N * t) -> t is the sum of numbers

Space O(t)

Runtime: 64 ms, faster than 55.34% of Java online submissions for Target Sum.

Memory Usage: 42.1 MB, less than 60.80% of Java online submissions for Target Sum.

class Solution {

    public int findTargetSumWays(int[] nums, int target) {

        if (nums == null || nums.length == 0) {

            return 0;

        }

        // key-value of expression until current number

        // value-count of that value

        Map<Integer, Integer> map = new HashMap<>();

        map.put(0, 1);

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

            Map<Integer, Integer> tempMap = new HashMap<>();

            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {

                int val = entry.getKey() + nums[i];

                tempMap.put(val, tempMap.getOrDefault(val, 0) + entry.getValue());

                val = entry.getKey() - nums[i];

                tempMap.put(val, tempMap.getOrDefault(val, 0) + entry.getValue());

            }

            map = tempMap;

        }

        return map.getOrDefault(target, 0);

    }

}

一刷
0/1 Knapsack Problem

83.05 %
class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        // 2 dimension of states
        // dp[i][j] -> nums[0, i], with sum of j
        // since sum can be negative, we need to add offset to all sums
        int len = nums.length;
        int total = 0;
        for (int num : nums) {
            total += num;
        }
        // partition nums into to sets -> positive set P and negative set N
        // sum(P) - sum(N) = target
        // sum(P) + sum(N) = total
        // 2 sum(P) = S + total
        // sum(P) = (S + total) / 2;
        int target = total + S;
        if (total < S || target % 2 != 0) return 0;
        target /= 2;
        // find a subset sum equals to S + total
        // dp[i][j] -> pick any number from [0, i) -> sum to j
        int[][] dp = new int[len + 1][target + 1];
        for (int i = 0; i <= len; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= len; i++) {
            for (int s = 0; s <= target; s++) {
                // if we don't pick current nums[i - 1]
                dp[i][s] = dp[i - 1][s];
                if (s >= nums[i - 1]) {
                    dp[i][s] += dp[i - 1][s - nums[i - 1]];
                }
            }
        }
        return dp[len][target];
    }
}

362. Design Hit Counter

Version #1 Circular Array

69.23 %
class HitCounter {
    int[] time;
    int[] count;
    /** Initialize your data structure here. */
    public HitCounter() {
        // time index = timestamp % 300, we can override the previous value since it has expired
        time = new int[300];
        count = new int[300];
    }
   
    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    public void hit(int timestamp) {
        int index = timestamp % 300;
        if (time[index] != timestamp) {
            time[index] = timestamp;
            count[index] = 1;
        } else {
            count[index]++;
        }
    }
   
    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    public int getHits(int timestamp) {
        int result = 0;
        for (int i = 0; i < 300; i++) {
            if (time[i] + 300 > timestamp) {
                result += count[i];
            }
        }
        return result;
    }
}

304. Range Sum Query 2D - Immutable

二刷 08/2022

Version #1 2D PrefixSum

Time O(MN) for constructor, O(1) for query

Space O(MN)

Runtime: 215 ms, faster than 46.65% of Java online submissions for Range Sum Query 2D - Immutable.

Memory Usage: 127.3 MB, less than 62.68% of Java online submissions for Range Sum Query 2D - Immutable.

class NumMatrix {

    int[][] sums;

    public NumMatrix(int[][] matrix) {

        int rows = matrix.length;

        int cols = matrix[0].length;

        sums = new int[rows][cols];

        for (int y = 0; y < rows; y++) {

            for (int x = 0; x < cols; x++) {

                sums[y][x] = matrix[y][x];

                if (y - 1 >= 0) {

                    sums[y][x] += sums[y - 1][x];

                }

                if (x - 1 >= 0) {

                    sums[y][x] += sums[y][x - 1];

                }

                if (y - 1 >= 0 && x - 1 >= 0) {

                    sums[y][x] -= sums[y - 1][x - 1];

                }

            }

        }

    }

    //   (0,0) (0,1)

    //    -4   -5

    

    public int sumRegion(int row1, int col1, int row2, int col2) {

        //  (row1 - 1, col1 - 1)                     (row1 - 1, col2)

        //                        (row1, col1)       (row1, col2)

        //  (row2, col1 - 1)      (row2, col1)       (row2, col2)

        int sum = sums[row2][col2];

        if (col1 - 1 >= 0) {

            sum -= sums[row2][col1 - 1];

        }

        if (row1 - 1 >= 0) {

            sum -= sums[row1 - 1][col2];

        }

        if (row1 - 1 >= 0 && col1 - 1 >= 0) {

            sum += sums[row1 - 1][col1 - 1];

        }

        return sum;

    }

}

一刷

Version #1 2D PrefixSum

97.29 %
class NumMatrix {

    private int[][] prefixSum;
    private int rows, cols;
    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return;
        this.rows = matrix.length;
        this.cols = matrix[0].length;
        prefixSum = new int[rows + 1][cols + 1];
        // prefixSum[i][j] = matrix[i - 1][j - 1] + prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1]
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                prefixSum[i][j] = matrix[i - 1][j - 1] + prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1];
            }
        }
    }
 
    public int sumRegion(int row1, int col1, int row2, int col2) {
        if (rows == 0 || cols == 0) return 0;
        // row2,col1      row2,col2
        // row1,col1      row1,col2
        return prefixSum[row2 + 1][col2 + 1] - prefixSum[row2 + 1][col1] - prefixSum[row1][col2 + 1]
            + prefixSum[row1][col1];
    }
}

308. Range Sum Query 2D - Mutable

Version #1 2D Fenwick Tree

77.62 %
class NumMatrix {

    int[][] tree;
    int rows, cols;
    int[][] matrix;
    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return;
        this.matrix = matrix;
        rows = matrix.length;
        cols = matrix[0].length;
        tree = new int[rows + 1][cols + 1]; // 1 indexed
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                updateTree(i, j, matrix[i][j]);
            }
        }
    }
   
    public void update(int row, int col, int val) {
        if (rows == 0 || cols == 0) return;
        updateTree(row, col, val - matrix[row][col]);
        matrix[row][col] = val;
    }
   
    private void updateTree(int row, int col, int diff) {
        for (int i = row + 1; i <= rows; i += (i & (-i))) {
            for (int j = col + 1; j <= cols; j += (j & (-j))) {
                tree[i][j] += diff;
            }
        }
    }
   
    public int sumRegion(int row1, int col1, int row2, int col2) {
        if (rows == 0 || cols == 0) return 0;
        // (row2, col1)       (row2, col2)
        // (row1, col1)       (row1, col2)
        return sum(row2, col2) - sum(row2, col1 - 1) - sum(row1 - 1, col2) + sum(row1 - 1, col1 - 1);
    }
   
    private int sum(int row, int col) {
        int sum = 0;
        for (int i = row + 1; i > 0; i -= (i & (-i))) {
            for (int j = col + 1; j > 0; j -= (j & (-j))) {
                sum += tree[i][j];
            }
        }
        return sum;
    }
}

303. Range Sum Query - Immutable

Version #1 PrefixSum

class NumArray {
    // prefixSum i -> sum[0, i)
    private int[] prefixSum;
    public NumArray(int[] nums) {
        this.prefixSum = new int[nums.length + 1];
        for (int i = 1; i <= nums.length; i++) {
            prefixSum[i] = nums[i - 1] + prefixSum[i - 1];
        }
    }
   
    public int sumRange(int i, int j) {
        return prefixSum[j + 1] - prefixSum[i];
    }
}

274. H-Index

Version #1 Bucket sort

See comments
100.00 %
class Solution {
    public int hIndex(int[] citations) {
        if (citations == null || citations.length == 0) return 0;
        int len = citations.length;
        int[] count = new int[len + 1];
        // count[i] -> number of parpers with citations equals to i
        // e.g. i  0  1  2  3  4
        //         1  1     1
        // if (i == len) -> we must have all papers citation larger than or equals to i
        // say we have 5 numbers and they are 6 7 8 9 10
        // since h index cannot exceed len, we can just put all number larger than len into len
        for (int citation : citations) {
            if (citation >= len) {
                count[len]++;
            } else {
                count[citation]++;
            }
        }
        int sum = 0;
        for (int i = len; i >= 0; i--) {
            sum += count[i]; // there are sum parpers whose citations larger than or equals to i
            if (sum >= i) {
                return i;
            }
        }
        return 0;
    }
}

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;
    }
}

983. Minimum Cost For Tickets

二刷 07/2022

Version #1 DP

感觉这题有点难，想了很久想不出来

看了一刷的答案感觉一刷写的更好 用了一个pointer for days

一开始写了bug就是只有当i >= 7的时候才检查min，这种情况在7日票价低于1日票价的时候是有错误的

Time O(D) - D = 365

Space O(D) - D = 365

Runtime: 6 ms, faster than 17.80% of Java online submissions for Minimum Cost For Tickets.

Memory Usage: 42.4 MB, less than 33.67% of Java online submissions for Minimum Cost For Tickets.

class Solution {

    public int mincostTickets(int[] days, int[] costs) {

        Set<Integer> daySet = new HashSet<>();

        for (int d : days) {

            daySet.add(d);

        }

        // The min cost to cover travel until day i

        int[] dp = new int[366];

        for (int i = 1; i <= 365; i++) {

            if (!daySet.contains(i)) {

                dp[i] = dp[i - 1];

            } else {

                dp[i] = dp[i - 1] + costs[0];

                dp[i] = Math.min(dp[i], (i >= 7 ? dp[i - 7] : 0) + costs[1]);

                dp[i] = Math.min(dp[i], (i >= 30 ? dp[i - 30] : 0) + costs[2]);

            }

        }

        return dp[365];

    }

}

一刷

Version #1 DP

100.00 %
class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        // dp[i] - minimum cost to travel to day i
        int[] dp = new int[366];
        int daysIndex = 0;
        // Easy to know that dp[i] >= dp[j] when i > j
        for (int i = 1; i <= 365; i++) {
            if (daysIndex >= days.length || days[daysIndex] != i) {
                dp[i] = dp[i - 1];
            } else {
                daysIndex++;
                dp[i] = Math.min(dp[Math.max(0, i - 1)] + costs[0],
                                Math.min(dp[Math.max(0, i - 7)] + costs[1],
                                dp[Math.max(0, i - 30)] + costs[2]));
            }
        }
        return dp[365];
    }
}

982. Triples with Bitwise AND Equal To Zero

Version #1 DP

37.50 %
class Solution {
    public int countTriplets(int[] A) {
        int N = 1 << 16;
        int[] dp = new int[N];
        for (int a : A) {
            dp[a] += 1;
        }
        for (int i = 0; i < 2; i++) {
            int[] temp = new int[N];
            for (int k = 0; k < N; k++) {
                for (int a : A) {
                    temp[k & a] += dp[k];
                }
            }
            dp = temp;
        }
        return dp[0];
    }
}

556. Next Greater Element III

96.55 %
class Solution {
    public int nextGreaterElement(int n) {
        char[] chars = String.valueOf(n).toCharArray();
        int i = 0;
        for (i = chars.length - 1; i > 0; i--) {
            if (chars[i] > chars[i - 1]) break;
        }
        int nextLargerDigit = i;
        if (i != 0) {
            for (int j = chars.length - 1; j > i; j--) {
                if (chars[j] > chars[i - 1] && chars[j] < chars[nextLargerDigit]) {
                    nextLargerDigit = j;
                }
            }
            char temp = chars[i - 1];
            chars[i - 1] = chars[nextLargerDigit];
            chars[nextLargerDigit] = temp;
            Arrays.sort(chars, i, chars.length);
        } else {
            return -1;
        }
        long result = Long.valueOf(new String(chars));
        return result > Integer.MAX_VALUE ? -1 : (int) result;
    }
}

249. Group Shifted Strings

3.04 %
public List<List<String>> groupStrings(String[] strings) {
Map<String, List<String>> map = new HashMap<>();
for (String str : strings) {
map.computeIfAbsent(normalize(str), list -> new ArrayList<>()).add(str);
}
List<List<String>> result = new ArrayList<>();
for (List<String> list : map.values()) {
result.add(list);
}
return result;
}

private String normalize(String s) {
int offset = (int)(s.charAt(0) - 'a');
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
sb.append((char) ('a' + ((s.charAt(i) - offset + 26) % 26)));
}
// System.out.println(sb.toString());
return sb.toString();
}

616. Add Bold Tag in String

Version #1 Merge Intervals

13.51 %
class Solution {
    public String addBoldTag(String s, String[] dict) {
// [interval[0], interval[1])
List<int[]> intervals = new ArrayList<>();
for (String word : dict) {
int start = 0;
while (start >= 0) {
start = s.indexOf(word, start);
if (start == -1) {
break;
}
intervals.add(new int[]{start, start + word.length()});
start++;
}
}
Collections.sort(intervals, Comparator.comparing(a -> a[0])); // only compare the start index
int i = 0;
List<int[]> merged = new ArrayList<>();
while (i < intervals.size()) {
int[] curr = intervals.get(i);
while (i < intervals.size() - 1 && intervals.get(i + 1)[0] <= curr[1]) {
curr[1] = Math.max(curr[1], intervals.get(i + 1)[1]);
i++;
}
merged.add(curr);
i++;
}
StringBuilder sb = new StringBuilder();
int prev = 0;
for (int[] interval : merged) {
sb.append(s.substring(prev, interval[0])).append("<b>").append(s.substring(interval[0], interval[1])).append("</b>");
prev = interval[1];
}
sb.append(s.substring(prev));
return sb.toString();
}
}

935. Knight Dialer

Version #1 DP

71.11 %
class Solution {
    public int knightDialer(int N) {
        int[][] map = new int[][]{{4, 6}, {6, 8}, {7, 9}, {4, 8}, {3, 9, 0}, {}, {1, 7, 0}, {2, 6}, {1, 3}, {2, 4}};
        int[] prev = new int[10];
        int mod = (int)(1e9 + 7);
        Arrays.fill(prev, 1);
        for (int i = 2; i <= N; i++) {
            int[] curr = new int[10];
            for (int x = 0; x <= 9; x++) {
                for (int last : map[x]) {
                    curr[x] = (curr[x] + prev[last]) % mod;
                }
            }
            prev = curr;
        }
        int sum = 0;
        for (int i = 0; i <= 9; i++) {
            sum = (sum + prev[i]) % mod;
        }
        return sum;
    }
}

421. Maximum XOR of Two Numbers in an Array

Version #1 PrefixTrie + DFS

We are passing two nodes into dfs simultaneously,  if we can choose branch of different value, we choose. Otherwise choose the same value

95.05 %
class Solution {
    class TrieNode {
TrieNode[] children;
public TrieNode() {
children = new TrieNode[2];
}
}
public int findMaximumXOR(int[] nums) {
TrieNode root = new TrieNode();
for (int num : nums) {
insert(root, num);
}
return dfs(root.children[0], root.children[1] == null ? root.children[0] : root.children[1], 0);
}

private int dfs(TrieNode left, TrieNode right, int diff) {
TrieNode left0 = left.children[0], left1 = left.children[1];
TrieNode right0 = right.children[0], right1 = right.children[1];

if (left0 == null && left1 == null) {
return diff;
} else if (left0 != null && left1 != null && right0 != null && right1 != null) {
return Math.max(dfs(left0, right1, (diff << 1) + 1), dfs(left1, right0, (diff << 1) + 1));
} else if (left0 != null && right1 != null) {
return dfs(left0, right1, (diff << 1) + 1);
} else if (left1 != null && right0 != null) {
return dfs(left1, right0, (diff << 1) + 1);
} else if (left0 != null && right0 != null){
return dfs(left0, right0, (diff << 1));
} else if (left1 != null && right1 != null) {
return dfs(left1, right1, (diff << 1));
}
return 0;
}

private void insert(TrieNode root, int num) {
TrieNode curr = root;
for (int i = 31; i >= 0; i--) {
int bit = (num >> i) & 1;
if (curr.children[bit] == null) {
curr.children[bit] = new TrieNode();
}
curr = curr.children[bit];
}
}
}

448. Find All Numbers Disappeared in an Array

69.09 %
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        // If we see this number, we mark the number that at this index as negative
        for (int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i]) - 1;
            if (nums[index] > 0) {
                nums[index] = -nums[index];
            }
        }
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                result.add(i + 1);
            }
        }
        return result;
    }
}

463. Island Perimeter

86.10 %
class Solution {
    public int islandPerimeter(int[][] grid) {
        // try to add 4 edges to each node
        // if there are to node connect to each other, then 2 edges should be subtracted
        int result = 0;
        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) return 0;
        for (int y = 0; y < grid.length; y++) {
            for (int x = 0; x < grid[0].length; x++) {
                if (grid[y][x] == 1) {
                    result += 4;
                    if (y + 1 < grid.length && grid[y + 1][x] == 1) {
                        result -= 2;
                    }
                    if (x + 1 < grid[0].length && grid[y][x + 1] == 1) {
                        result -= 2;
                    }
                }
            }
        }
        return result;
    }
}

657. Robot Return to Origin

91.43 %
class Solution {
    public boolean judgeCircle(String moves) {
        int y = 0;
        int x = 0;
        for (int i = 0; i < moves.length(); i++) {
            char c = moves.charAt(i);
            if (c == 'U') {
                y--;
            } else if (c == 'D') {
                y++;
            } else if (c == 'L') {
                x--;
            } else {
                x++;
            }
        }
        return x == 0 && y == 0;
    }
}

972. Equal Rational Numbers

68.52 %
class Solution {
    public boolean isRationalEqual(String S, String T) {
        return Double.valueOf(normalize(S)).compareTo(
            Double.valueOf(normalize(T))) == 0;
    }
   
    private String normalize(String s) {
        int index = s.indexOf("(");
        String result = s;
        if (index > 0) {
            result = s.substring(0, index);
            for (int i = 0; i < 20; i++) {
               result += s.substring(index + 1, s.length() - 1);
            }
        }
        return result;
    }
}

958. Check Completeness of a Binary Tree

Version #2 BFS[TODO]


Version #1 DFS

98.36 
class Solution {
    int count;
    public boolean isCompleteTree(TreeNode root) {
        count = getCount(root);
        return validate(root, 1);
    }
   
    private boolean validate(TreeNode node, int id) {
        if (node == null) return true;
        if (id > count) return false;
        return validate(node.left, id * 2) && validate(node.right, id * 2 + 1);
    }
   
   
    private int getCount(TreeNode node) {
        if (node == null) return 0;
        return 1 + getCount(node.left) + getCount(node.right);
    }
}

943. Find the Shortest Superstring

Version #1 DP

非常难的一道题
bug出在了当A[i] 为第一个word的时候，如果不设parent[1 << i][i] = i 而default为0的话就会陷入死循环
其余的思路其实和knapsack有点类似
关键在于状态压缩
把两个word之间的连接状态，压缩成一个已知的set，append一个word的状态

95.59 %
class Solution {
    public String shortestSuperstring(String[] A) {
        // int state -> which words index have been visited
        // dp[state][i] -> minimum superstring length to cover state, and i is the last word
        // having dp[state][j] -> try to expand to word that have not been visited before
        // dp[state][i] = Math.min(dp[state][i], dp[state][j] + cost[j][i])
        // store the last index j for dp[state][i] -> parent[state][i] = j
        // cost[i][j] -> the length increased to append A[j] after A[i], not including length of A[i]
        int len = A.length;
        int[][] cost = new int[len][len];
        int endState = 0; // if state reached this state, we know that all words have been used
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < i; j++) {
                cost[i][j] = getCost(A[i], A[j]);
                cost[j][i] = getCost(A[j], A[i]);
            }
            endState += 1 << i;
        }
        int totalCost = Integer.MAX_VALUE;
        int lastIndex = 0;
        int[][] dp = new int[endState + 1][len];
        int[][] parent = new int[endState + 1][len]; // parent index for min cost
        for (int i = 0; i < len; i++) {
            dp[1 << i][i] = A[i].length(); // A[i] is the first word, cost is it self
            parent[1 << i][i] = i;
        }
        for (int s = 0; s <= endState; s++) {
            for (int i = 0; i < len; i++) {
                // check if this state has visited A[i] or not
                if ((s & (1 << i)) == 0 || s == (1 << i)) continue;
                dp[s][i] = Integer.MAX_VALUE;
                int prevState = s & (~(1 << i)); // reset bit i
                for (int j = 0; j < len; j++) {
                    if ((prevState & (1 << j)) == 0) continue;
                    // All possible prev states
                    if (dp[prevState][j] + cost[j][i] < dp[s][i]) {
                        dp[s][i] = dp[prevState][j] + cost[j][i];
                        parent[s][i] = j;
                    }
                }
                if (s == endState && dp[s][i] < totalCost) {
                    totalCost = dp[s][i];
                    lastIndex = i;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        while (endState != 0) {
            int curr = lastIndex;
            lastIndex = parent[endState][curr];
            endState = endState & (~(1 << curr)); // reset lastIndex
            String temp = A[curr].substring(A[curr].length() - cost[lastIndex][curr]);
            sb.insert(0, temp);
        }
        sb.insert(0, A[lastIndex]);
        return sb.toString();
    }
   
    private int getCost(String first, String second) {
        // abcd     cdef
        int overlap = 0;
        for (int i = 0; i < first.length(); i++) {
            if (second.startsWith(first.substring(i))) {
                overlap = first.length() - i;
                break;
            }
        }
        return second.length() - overlap;
    }
}

347. Top K Frequent Elements

二刷 06/2022

Version #3 Quick Select

和973用了不同的partition方法

这里没有把pivot swap到它正确的位置

返回的index是left - 1, 表示从(0-index) >= partition, (index+1, len-1) <= partition

如果index<k-1表示从0到index不足k个数，这时候要start=index+1，如果不+1会infinite loop

表示从0到index有大于等于k个数，这时候要end=index

Time O(N)

Space O(#distinct number)

Runtime: 16 ms, faster than 58.05% of Java online submissions for Top K Frequent Elements.

Memory Usage: 50.2 MB, less than 59.80% of Java online submissions for Top K Frequent Elements.

class Solution {

    public int[] topKFrequent(int[] nums, int k) {

        if (nums == null || nums.length == 0) {

            return new int[0];

        }

        Map<Integer, Integer> count = new HashMap<>();

        for (int num : nums) {

            count.put(num, count.getOrDefault(num, 0) + 1);

        }

        int[] unique = new int[count.size()];

        int i = 0;

        for (int num : count.keySet()) {

            unique[i++] = num;

        }

        int index = unique.length;

        int start = 0, end = unique.length - 1;

        while (index != k - 1) {

            index = partition(unique, start, end, count);

            // System.out.printf("start=%d,end=%d,index=%d\n", start, end, index);

            if (index < k - 1) {

                start = index + 1;

            } else {

                end = index;

            }

        }

        int[] result = new int[k];

        for (int j = 0; j < k; j++) {

            result[j] = unique[j];

        }

        return result;

    }

    

    private int partition(int[] nums, int start, int end, Map<Integer, Integer> count) {

        int pivot = nums[start + (end - start) / 2];

        int pivotCnt = count.get(pivot);

        int left = start, right = end;

        while (left <= right) {

            while (left <= right && count.get(nums[left]) > pivotCnt) {

                left++;

            }

            while (left <= right && count.get(nums[right]) < pivotCnt) {

                right--;

            }

            if (left <= right) {

                swap(nums, left, right);

                left++;

                right--;

            }

        }

        return left - 1;

    }

    

    private void swap(int[] nums, int a, int b) {

        int temp = nums[a];

        nums[a] = nums[b];

        nums[b] = temp;

    }

}

Version #2 Bucket Sort
有一个bug
因为count 是从1开始，所以生成的bucket size 需要 是length + 1

Time O(n)
95.43 %
class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        // key-num, value-count
        for (int num : nums) {
            map.put(num, 1 + map.getOrDefault(num, 0));
        }
        // the frequency can't exceed total number of nums
        List<Integer>[] bucket = new List[nums.length + 1];
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int count = entry.getValue();
            if (bucket[count] == null) {
                bucket[count] = new ArrayList<>();
            }
            bucket[count].add(entry.getKey());
        }
        List<Integer> result = new ArrayList<>();
        int i = nums.length;
        while (i >= 0 && result.size() < k) {
            if (bucket[i] != null) {
                result.addAll(bucket[i]);
            }
            i--;
        }
        return result;
    }
}

Version #1 HashMap + minHeap
Time O(nlogk)
Space O(count of unique values)

51.98 %
class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        // Count frequency -> Map<num, count> -> O(n) for all nums
        // get most k count
        // retrieve from map
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            int count = 1 + map.getOrDefault(num, 0);
            map.put(num, count);
        }
        // O(nlogk)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int count : map.values()) {
            if (minHeap.size() < k) {
                minHeap.offer(count);
            } else if (count > minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(count);
            }
        }
        Set<Integer> countK = new HashSet<>(minHeap);
        List<Integer> result = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (countK.contains(entry.getValue())) {
                result.add(entry.getKey());
            }
        }
        return result;
    }
}

760. Find Anagram Mappings

92.70 %
class Solution {
    public int[] anagramMappings(int[] A, int[] B) {
// key-num, value-index
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < B.length; i++) {
            map.putIfAbsent(B[i], i);
        }
        int[] result = new int[A.length];
        for (int i = 0; i < A.length; i++) {
            result[i] = map.get(A[i]);
        }
        return result;
    }
}