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