755. Pour Water

755. Pour Water

Medium

We are given an elevation map, heights[i] representing the height of the terrain at that index. The width at each index is 1. After Vunits of water fall at index K, how much water is at each index?

Water first drops at index K and rests on top of the highest terrain or water at that index. Then, it flows according to the following rules:

If the droplet would eventually fall by moving left, then move left.

Otherwise, if the droplet would eventually fall by moving right, then move right.

Otherwise, rise at it's current position.

Here, "eventually fall" means that the droplet will eventually be at a lower level if it moves in that direction. Also, "level" means the height of the terrain plus any water in that column.

We can assume there's infinitely high terrain on the two sides out of bounds of the array. Also, there could not be partial water being spread out evenly on more than 1 grid block - each unit of water has to be in exactly one block.

Example 1:

Input: heights = [2,1,1,2,1,2,2], V = 4, K = 3
Output: [2,2,2,3,2,2,2]
Explanation:
#       #
#       #
##  # ###
#########
 0123456    <- index

The first drop of water lands at index K = 3:

#       #
#   w   #
##  # ###
#########
 0123456    

When moving left or right, the water can only move to the same level or a lower level.
(By level, we mean the total height of the terrain plus any water in that column.)
Since moving left will eventually make it fall, it moves left.
(A droplet "made to fall" means go to a lower height than it was at previously.)

#       #
#       #
## w# ###
#########
 0123456    

Since moving left will not make it fall, it stays in place.  The next droplet falls:

#       #
#   w   #
## w# ###
#########
 0123456  

Since the new droplet moving left will eventually make it fall, it moves left.
Notice that the droplet still preferred to move left,
even though it could move right (and moving right makes it fall quicker.)

#       #
#  w    #
## w# ###
#########
 0123456  

#       #
#       #
##ww# ###
#########
 0123456  

After those steps, the third droplet falls.
Since moving left would not eventually make it fall, it tries to move right.
Since moving right would eventually make it fall, it moves right.

#       #
#   w   #
##ww# ###
#########
 0123456  

#       #
#       #
##ww#w###
#########
 0123456  

Finally, the fourth droplet falls.
Since moving left would not eventually make it fall, it tries to move right.
Since moving right would not eventually make it fall, it stays in place:

#       #
#   w   #
##ww#w###
#########
 0123456  

The final answer is [2,2,2,3,2,2,2]:

    #    
 ####### 
 ####### 
 0123456 

Example 2:

Input: heights = [1,2,3,4], V = 2, K = 2
Output: [2,3,3,4]
Explanation:
The last droplet settles at index 1, since moving further left would not cause it to eventually fall to a lower height.

Example 3:

Input: heights = [3,1,3], V = 5, K = 1
Output: [4,4,4]

Note:

1. heights will have length in [1, 100] and contain integers in [0, 99].
2. V will be in range [0, 2000].
3. K will be in range [0, heights.length - 1].

---------------------
暴解
O(m * n), heights的长度 ＊ 水滴个个数

class Solution {
    public int[] pourWater(int[] heights, int water, int pos) {
        
        while (water > 0) {
            water--;
            int left = pos;
            
            while (left > 0 && heights[left - 1] <= heights[left]) {
                left--;
            }
            
            if (heights[left] < heights[pos]) {
                heights[left]++;
                continue;
            }
            
            int right = pos;
            while (right < heights.length - 1 && heights[right + 1] <= heights[right]) {
                right++;
            }
            
            if (heights[right] < heights[pos]) {
                heights[right]++;
            }else {
                heights[pos]++;
            }            
        }
        
        return heights;
    }
}

460. LFU Cache

460. LFU Cache

Hard

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LFUCache cache = new LFUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.get(3);       // returns 3.
cache.put(4, 4);    // evicts key 1.
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

--------------------
1个hashmap存key - value
1个存key - frequency
1个存 frequency - keys

用min来存最小的frequency
LinkedHashSet里面是hashset + doubly linked list的实现方式，所以是有序的

class LFUCache {

    private Map<Integer, Integer> map;
    private Map<Integer, Integer> keyToFrq;
    private Map<Integer, LinkedHashSet<Integer>> frqToKeys;
    private int cap;
    private int min;
    
    public LFUCache(int capacity) {
        min = -1;
        cap = capacity;
        map = new HashMap<>();
        keyToFrq = new HashMap<>();
        frqToKeys = new HashMap<>();
    }
    
    public int get(int key) {

        if (!map.containsKey(key)) return-1;
        int frq = keyToFrq.get(key);
        frqToKeys.get(frq).remove(key);
        if (min == frq && frqToKeys.get(frq).isEmpty()) min++;
        
        frq++;
        if (!frqToKeys.containsKey(frq)) frqToKeys.put(frq, new LinkedHashSet<Integer>());
        frqToKeys.get(frq).add(key);
        keyToFrq.put(key, keyToFrq.get(key) + 1);
        
        return map.get(key);
    }
    
    public void put(int key, int value) {
        if (cap <= 0) return;
        if (map.containsKey(key)) {
            map.put(key, value);
            get(key);
            return;
        }
        
        if (map.size() >= cap) {
            
            int evit = frqToKeys.get(min).iterator().next();
            frqToKeys.get(min).remove(evit);
            map.remove(evit);
            keyToFrq.remove(evit);
        }
        
        map.put(key, value);
        min = 1;
        keyToFrq.put(key, min);
        if (!frqToKeys.containsKey(min)) frqToKeys.put(min, new LinkedHashSet<Integer>());
        frqToKeys.get(min).add(key);
    }
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

759. Employee Free Time

759. Employee Free Time

Hard

We are given a list schedule of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

Example 1:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
Explanation:
There are a total of three employees, and all common
free time intervals would be [-inf, 1], [3, 4], [10, inf].
We discard any intervals that contain inf as they aren't finite.

Example 2:

Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
Output: [[5,6],[7,9]]

(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined.)

Also, we wouldn't include intervals like [5, 5] in our answer, as they have zero length.

Note:

1. schedule and schedule[i] are lists with lengths in range [1, 50].
2. 0 <= schedule[i].start < schedule[i].end <= 10^8.

----------------------
不用想太复杂
把所有的interval都插入到priorityQueue，然后找gap。题目中给的多少个人其实没有什么意义
O(n), n为总的interval数量

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        PriorityQueue<Interval> que = new PriorityQueue<>((a, b) -> a.start - b.start);
        
        for (List<Interval> list : schedule) {
            for (Interval i : list) {
                que.add(i);
            }
        }
        
        List<Interval> rt = new ArrayList<>();
        int max = -1;
        while (!que.isEmpty()) {
            Interval top = que.poll();
            if (max != -1 && top.start > max) {
                rt.add(new Interval(max, top.start));
            }
            max = Math.max(max, top.end);
        }
        
        return rt;
    }
}

829. Consecutive Numbers Sum

829. Consecutive Numbers Sum

Hard

Given a positive integer N, how many ways can we write it as a sum of consecutive positive integers?

Example 1:

Input: 5
Output: 2
Explanation: 5 = 5 = 2 + 3

Example 2:

Input: 9
Output: 3
Explanation: 9 = 9 = 4 + 5 = 2 + 3 + 4

Example 3:

Input: 15
Output: 4
Explanation: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

Note: 1 <= N <= 10 ^ 9.

---------------------
求等差数列为1，和为N的数列的个数，假设数列的首项为x，项数是m，则如果存在这一数列，N = (x + (x + m - 1)) * m / 2. 那么我们就遍历m的可能性

O(lgN)
ref: https://zhanghuimeng.github.io/post/leetcode-829-consecutive-numbers-sum/

class Solution {
    public int consecutiveNumbersSum(int N) {
        int rt = 0;
        
        for (int m = 1; ; m++) {
            int mx = N - (m - 1) * m / 2;
            if (mx <= 0) break;
            if (mx % m == 0) rt++;
        }
        
        return rt;
    }
}

542. 01 Matrix

542. 01 Matrix

Medium

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1: 
Input:

0 0 0
0 1 0
0 0 0

Output:

0 0 0
0 1 0
0 0 0

Example 2: 
Input:

0 0 0
0 1 0
1 1 1

Output:

0 0 0
0 1 0
1 2 1

Note:

1. The number of elements of the given matrix will not exceed 10,000.
2. There are at least one 0 in the given matrix.
3. The cells are adjacent in only four directions: up, down, left and right.

---------------------
Solution #1
BFS, 把所有的0放入queue中，用额外数组记录visited情况
O(m*n) time and space

class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] rt = new int[m][n];
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> que = new LinkedList<>();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) que.add(new int[]{i,j});
            }
        }
        
        int dis = 0;
        while (!que.isEmpty()) {
            for (int size = que.size(); size > 0; size--) {
                int[] top = que.poll();
                int r = top[0], c = top[1];
                
                if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c]) continue;
                visited[r][c] = true;
                rt[r][c] = dis;
                que.add(new int[]{r - 1, c});
                que.add(new int[]{r + 1, c});
                que.add(new int[]{r, c + 1});
                que.add(new int[]{r, c - 1});
            }
            
            dis++;
        }
        
        return rt;
    }
}

Solution #2， DP，每个点有上下左右4个方向可以选择，如果符合条件，选每个方向路径都增加1。那我们先从matrix左上走到右下，再右下到左上。这样4个方向全部检查过
跟#1一样的复杂度
ref: https://leetcode.com/problems/01-matrix/discuss/101039/Java-33ms-solution-with-two-sweeps-in-O(n)

255. Verify Preorder Sequence in Binary Search Tree

255. Verify Preorder Sequence in Binary Search Tree

Medium

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

Consider the following binary search tree: 

     5
    / \
   2   6
  / \
 1   3

Example 1:

Input: [5,2,6,1,3]
Output: false

Example 2:

Input: [5,2,1,3,6]
Output: true

Follow up:
Could you do it using only constant space complexity?

Accepted

32,826

Submissions

76,719

Seen this question in a real interview before?

-----------------------
Solution #1, O(n) time and space
stack里保证的是递增（从top到底下），遇到比top大说明是走到了右子树，然后把之前左子树跟root全部pop掉，取root为lower bound（之后再也不会遇到比这更小，如果有，说明顺序有错误）
这方法是模拟preorder traversal的iterative的版本

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        Stack<Integer> st = new Stack<>();
        int low = Integer.MIN_VALUE;
        for (int i : preorder) {
            if (i < low) return false;
            
            while (!st.isEmpty() && st.peek() < i) {
                low = st.pop();
            }
            st.push(i);
        }
        
        return true;
    }
    
}

Solution #2 O(n) time, O(1) space, 把给定的preorder数组利用起来，当作stack来存

934. Shortest Bridge

934. Shortest Bridge

In a given 2D binary array A, there are two islands.  (An island is a 4-directionally connected group of 1s not connected to any other 1s.)

Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.

Return the smallest number of 0s that must be flipped.  (It is guaranteed that the answer is at least 1.)

Example 1:

Input: [[0,1],[1,0]]
Output: 1

Example 2:

Input: [[0,1,0],[0,0,0],[0,0,1]]
Output: 2

Example 3:

Input: [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
Output: 1

Note:

1. 1 <= A.length = A[0].length <= 100
2. A[i][j] == 0 or A[i][j] == 1

-------------------
BFS
先标记出一个岛，然后做BFS直到碰到另一个岛
注意dis的初始值是 -1

class Solution {
    public int shortestBridge(int[][] arr) {

        Queue<int[]> que = new LinkedList<>();

        for (int i = 0; i < arr.length; i++) {
            boolean f = false;
            for (int j = 0; j < arr[0].length; j++) {
                if (arr[i][j] == 1) {
                    dfs(arr, i, j, que);
                    f = true;
                    break;
                }
            }
            if (f) break;
        }

        int dis = -1;
        while (!que.isEmpty()) {
            
            for (int size = que.size(); size > 0; size--) {
                int[] top = que.poll();
                int i = top[0], j = top[1];
                if (i < 0 || j < 0 || i >= arr.length || j >= arr[0].length || arr[i][j] == 3) continue;
                if (arr[i][j] == 1) return dis;
                arr[i][j] = 3;
                que.add(new int[]{i + 1, j});
                que.add(new int[]{i, j + 1});
                que.add(new int[]{i - 1, j});
                que.add(new int[]{i, j - 1});
            }
            dis++;
        }


        return 0;
    }

    private void dfs(int[][] arr, int i, int j, Queue<int[]> que) {
        if (i < 0 || j < 0 || i >= arr.length || j >= arr[0].length || arr[i][j] == 0 || arr[i][j] == 2) return;

        arr[i][j] = 2;
        que.add(new int[]{i, j});
        dfs(arr, i + 1, j, que);
        dfs(arr, i - 1, j, que);
        dfs(arr, i, j + 1, que);
        dfs(arr, i, j - 1, que);
    }
}

640. Solve the Equation

640. Solve the Equation

Solve a given equation and return the value of x in the form of string "x=#value". The equation contains only '+', '-' operation, the variable x and its coefficient.

If there is no solution for the equation, return "No solution".

If there are infinite solutions for the equation, return "Infinite solutions".

If there is exactly one solution for the equation, we ensure that the value of x is an integer.

Example 1:

Input: "x+5-3+x=6+x-2"
Output: "x=2"

Example 2:

Input: "x=x"
Output: "Infinite solutions"

Example 3:

Input: "2x=x"
Output: "x=0"

Example 4:

Input: "2x+3x-6x=x+2"
Output: "x=-1"

Example 5:

Input: "x=x+2"
Output: "No solution"

--------------------
解一元一次方程。难点在处理string parsing上。计算左右2边常数项和变量各自的差，sign表示等号左右

class Solution {
    public String solveEquation(String equation) {
        int i = 0, start = 0, cof = 0, cos = 0, sign = 1;
        
        for (; i < equation.length(); i++) {
            if (equation.charAt(i) == '+' || equation.charAt(i) == '-') {
                if (i > start) cos += sign * Integer.parseInt(equation.substring(start,i));
                start = i;
            }else if (equation.charAt(i) == 'x') {
                if (i == start || equation.charAt(i - 1) == '+') {
                    cof += sign;
                }else if (equation.charAt(i - 1) == '-') {
                    cof -= sign;
                }else {
                    cof += sign * Integer.parseInt(equation.substring(start,i));
                }
                
                start = i + 1;
            }else if (equation.charAt(i) == '=') {
                if (i > start) cos += sign * Integer.parseInt(equation.substring(start,i));
                sign = -1;
                start = i + 1;
            }
        }
        
        if (start < equation.length()) cos += sign * Integer.parseInt(equation.substring(start));
        if (cof == 0 && cos == 0) return "Infinite solutions";
        if (cof == 0) return "No solution";
        return "x=" + Integer.toString(- cos / cof);
    }
}

361. Bomb Enemy

361. Bomb Enemy

Given a 2D grid, each cell is either a wall 'W', an enemy 'E' or empty '0' (the number zero), return the maximum enemies you can kill using one bomb.
The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since the wall is too strong to be destroyed.
Note: You can only put the bomb at an empty cell.

Example:

Input: [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
Output: 3 
Explanation: For the given grid,

0 E 0 0 
E 0 W E 
0 E 0 0

Placing a bomb at (1,1) kills 3 enemies.

-------------------------
很直接的遍历。row里存的是当前横向杀人的敌人个数，cols[j]存的是在col j杀伤的敌人个数
只有在前一位是'W'的时候，才会检查杀伤到多少敌人

O(m * n) time, O(n) space

class Solution {
    public int maxKilledEnemies(char[][] grid) {
        if (grid.length == 0) return 0;
        int max = 0;
        int row = 0;
        int[] cols = new int[grid[0].length];
        
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 'W') continue;
                if (j == 0 || grid[i][j - 1] == 'W') {
                    row = getRow(grid, i, j);
                }
                
                if (i == 0 || grid[i - 1][j] == 'W') {
                    cols[j] = getCol(grid, i, j);
                }
                
                if (grid[i][j] == '0' && row + cols[j] > max) {
                    max = row + cols[j];
                }
            }
        }
        
        return max;
    }
    
    private int getRow(char[][] grid, int i, int j) {
        int rt = 0;
        while (j < grid[0].length && grid[i][j] != 'W') {
            if (grid[i][j] == 'E') rt++;
            j++;
        }
        
        return rt;
    }
    
    private int getCol(char[][] grid, int i, int j) {
        int rt = 0;
        while (i < grid.length && grid[i][j] != 'W') {
            if (grid[i][j] == 'E') rt++;
            i++;
        }
        
        return rt;
    }
}

353. Design Snake Game

353. Design Snake Game

Design a Snake game that is played on a device with screen size = width x height. Play the game online if you are not familiar with the game.

The snake is initially positioned at the top left corner (0,0) with length = 1 unit.

You are given a list of food's positions in row-column order. When a snake eats the food, its length and the game's score both increase by 1.

Each food appears one by one on the screen. For example, the second food will not appear until the first food was eaten by the snake.

When a food does appear on the screen, it is guaranteed that it will not appear on a block occupied by the snake.

Example:

Given width = 3, height = 2, and food = [[1,2],[0,1]].

Snake snake = new Snake(width, height, food);

Initially the snake appears at position (0,0) and the food at (1,2).

|S| | |
| | |F|

snake.move("R"); -> Returns 0

| |S| |
| | |F|

snake.move("D"); -> Returns 0

| | | |
| |S|F|

snake.move("R"); -> Returns 1 (Snake eats the first food and right after that, the second food appears at (0,1) )

| |F| |
| |S|S|

snake.move("U"); -> Returns 1

| |F|S|
| | |S|

snake.move("L"); -> Returns 2 (Snake eats the second food)

| |S|S|
| | |S|

snake.move("U"); -> Returns -1 (Game over because snake collides with border)

-----------------------
用Deque
注意点：要额外用一个set来存蛇身，用O(1)检测是否会撞到本身
head要额外复制一个数组

class SnakeGame {

    private Deque<int[]> snake;
    private Set<Integer> set; 
    private int score;
    private int width;
    private int height;
    private int[][] food;
    /** Initialize your data structure here.
        @param width - screen width
        @param height - screen height 
        @param food - A list of food positions
        E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0]. */
    public SnakeGame(int width, int height, int[][] food) {
        this.width = width;
        this.height = height;
        this.food = food;
        snake = new LinkedList<>();
        set = new HashSet<>();
        score = 0;
        snake.addFirst(new int[]{0,0});
        set.add(0);
    }
    
    /** Moves the snake.
        @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down 
        @return The game's score after the move. Return -1 if game over. 
        Game over when snake crosses the screen boundary or bites its body. */
    public int move(String direction) {
        if (score == -1) return -1;

        int[] head = new int[]{snake.peekFirst()[0],snake.peekFirst()[1]};
        int[] tail = snake.pollLast();
        
        set.remove(tail[0] * width + tail[1]);
        
        if (direction.equals("U")) {
            head[0]--;
        }else if (direction.equals("L")) {
            head[1]--; 
        }else if (direction.equals("R")) {
            head[1]++;
        }else if (direction.equals("D")) {
            head[0]++;
        }

        if (head[0] < 0 || head[0] >= height || head[1] < 0 || head[1] >= width 
            || set.contains(head[0] * width + head[1])) {
            
            score = -1;
            return -1;
        }
        
        snake.addFirst(head);
        set.add(head[0] * width + head[1]);
        
        if (score < food.length && food[score][0] == head[0] && food[score][1] == head[1]) {
            score++;
            snake.addLast(tail);
            set.add(tail[0] * width + tail[1]);
        }
        
        return score;
    }
        
}

/**
 * Your SnakeGame object will be instantiated and called as such:
 * SnakeGame obj = new SnakeGame(width, height, food);
 * int param_1 = obj.move(direction);
 */

780. Reaching Points

780. Reaching Points

A move consists of taking a point (x, y) and transforming it to either (x, x+y) or (x+y, y).

Given a starting point (sx, sy) and a target point (tx, ty), return True if and only if a sequence of moves exists to transform the point (sx, sy) to (tx, ty). Otherwise, return False.

Examples:
Input: sx = 1, sy = 1, tx = 3, ty = 5
Output: True
Explanation:
One series of moves that transforms the starting point to the target is:
(1, 1) -> (1, 2)
(1, 2) -> (3, 2)
(3, 2) -> (3, 5)

Input: sx = 1, sy = 1, tx = 2, ty = 2
Output: False

Input: sx = 1, sy = 1, tx = 1, ty = 1
Output: True

Note:

• sx, sy, tx, ty will all be integers in the range [1, 10^9].

---------------
Solution #1, 因为给定的都是正数，所有可以对比tx跟ty，大的减去小的就是之前的那一对数

class Solution {
    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        while (tx >= sx && ty >= sy) {
            if (tx == sx && ty == sy) return true;
            if (tx > ty) {
                tx -= ty;
            }else {
                ty -= tx;
            }
        }
        
        return false;
    }
}

Solution #2, 跟#1类似，但是我们需要快速收敛。考虑以下例子
2, 12
2, 8
2, 6
2, 4
2, 2

class Solution {
    public boolean reachingPoints(int sx, int sy, int tx, int ty) {
        while (tx >= sx && ty >= sy) {
            if (tx == sx && ty == sy) return true;
            if (tx > ty) {
                if (ty == sy) return (tx - sx) % ty == 0;
                tx %= ty;
            }else {
                if (tx == sx) return (ty - sy) % tx == 0;
                ty %= tx;
            }
        }
        
        return false;
    }
}