Leetcode review

399. Evaluate Division

问题描述：

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

Note: The variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them.

Example 1:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation: 
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? 
return: [6.0, 0.5, -1.0, 1.0, -1.0 ]
note: x is undefined => -1.0

Example 2:

Input: equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75000,0.40000,5.00000,0.20000]

Example 3:

Input: equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.50000,2.00000,-1.00000,-1.00000]

这是一道典型的图论相关问题，思路是构造一个邻接矩阵matrix， matrix[i][j]代表i/j的值，如果没有这个值就为0。

构造好这个矩阵之后就可以通过BFS去递归的寻找关系，比如在Example 1中需要找到a/c，那么就可以先通过dfs找到a/b，然后再通过dfs进一步找到b/c从而获得a/c。

具体的代码思路如下

class Solution {
    Map<String, Integer> map;
    double[][] matrix;
    int cnt = 0;
    double[] res;
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        map = new HashMap<>();
        for(List<String> list: equations) {
            for(String str: list) {
                if(!map.containsKey(str)) {
                    map.put(str, cnt ++);
                }
            }
        }
        int num = map.size();
        matrix = new double[num][num];
        for(int i = 0; i < num; i ++) {
            matrix[i][i] = 1.0;
        }
        for(int i = 0; i < equations.size(); i ++) {
            String from = equations.get(i).get(0);
            String to = equations.get(i).get(1);
            matrix[map.get(from)][map.get(to)] = values[i];
            matrix[map.get(to)][map.get(from)] = 1.0 / values[i];
        }
        res = new double[queries.size()];
        cnt = 0;
        for(List<String> list: queries) {
            if(!map.containsKey(list.get(0)) || !map.containsKey(list.get(1))) {
                res[cnt] = -1.0;
            } else {
                int from = map.get(list.get(0));
                int to = map.get(list.get(1));
                dfs(from, to, 1.0, new HashSet<>());
                if(res[cnt] == 0) {
                    res[cnt] = -1.0;
                }
            }   
            cnt ++;
        }
        return res;
    }
    private void dfs(int from, int to, double multiple, Set<Integer> set) {
        if(set.contains(from)) {
            return;
        }
        for(int i = 0; i < matrix[from].length; i ++) {
            if(i == to && matrix[from][to] != 0.0) {
                res[cnt] = multiple * matrix[from][to];
                return;
            }
            if(matrix[from][i] != 0.0) {
                set.add(from);
                dfs(i, to, multiple * matrix[from][i], set);
                set.remove(from);
            }
        }
    }
}

时间复杂度分析：

• 构建map映射，即字符串和matrix中对应下标时的复杂度为O(E),E为Equations的大小。

• 构建邻接矩阵时的复杂度为O(E)。

• dfs方法在调用时最坏情况下会遍历邻接矩阵的每一个值，假设共有n个不同的字符串，即邻接矩阵有n^2个值，所以时间复杂度为O(n^2)。

• for循环遍历queries时，假设共有Q个query，那么每次调用一次dfs，时间复杂度为O(Q * n^2)

综上时间复杂度为O(E + Q * n^2)。

空间复杂度分析：

• matrix共有n^2个节点，复杂度为O(n^2)
• map共存储n个节点，复杂度为O(n)
• dfs时递归的深度可能会达到所有节点，复杂度为O(n)
• dfs时的set最坏情况会包含所有节点，复杂度为O(n)
• res数组假设有Q个query，复杂度为O(Q)

综上空间复杂度为O(Q + n^2)

994. Rotting Oranges

问题描述：


思路是先遍历grid，如果找到“烂橘子”就加入到Queue中，遍历完成之后对Queue中的所有“烂橘子”进行BFS并记录每次BFS的时间，动态更新最长时间。最后检查一遍grid，如果还存在新鲜的橘子就返回-1，如果没有就返回最长时间。

代码如下：

class Solution {
    public int orangesRotting(int[][] grid) {
        Queue<int[]> queue = new LinkedList<>();
        int res = 0;
        for(int i = 0; i < grid.length; i ++) {
            for(int j = 0; j < grid[i].length; j ++) {
                if(grid[i][j] == 2) {
                    queue.offer(new int[] {i, j, 0});
                }
            }
        }
        int[][] directions = new int[][] {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            for(int[] direction: directions) {
                int x = cur[0] + direction[0];
                int y = cur[1] + direction[1];
                if(x < 0 || x >= grid.length || y < 0 || y >= grid[x].length || grid[x][y] == 2 || grid[x][y] == 0) {
                    res = Math.max(res, cur[2]);
                } else {
                    grid[x][y] = 2;
                    queue.offer(new int[] {x, y, cur[2] + 1});
                }
            }
        }
        for(int i = 0; i < grid.length; i ++) {
            for(int j = 0; j < grid[i].length; j ++) {
                if(grid[i][j] == 1) {
                    return -1;
                }
            }
        }
        return res;
    }
}

时间复杂度分析：

• 两个for循环的时间复杂度为O(n*m)，n和m分别为grid的长和宽
• bfs最坏情况下会遍历每一个节点，时间复杂度为O(n*m)。

综上时间复杂度为O(n*m)

空间复杂度分析：

• queue最坏情况下会包含所有节点，空间复杂度为O(n*m)

综上空间复杂度为O(n*m)

875. Koko Eating Bananas

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Example 1:

Input: piles = [3,6,7,11], h = 8
Output: 4

Example 2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], h = 6
Output: 23

可以使用二分查找不断缩小符合要求的最小速度，直到找到最小的速度

代码如下：

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int slow = 1;
        int fast = 1000000000;
        int result = -1;
        while(slow <= fast) {
            int mid = slow + (fast - slow) / 2;
            if(check(mid, piles, h)) {
                result = mid;
                fast = mid - 1;
            } else {
                slow = mid + 1;
            }
        }
        return result;
    }

    private boolean check(int speed, int[] piles, int h) {
        long hours = 0;
        for(Integer pile: piles) {
            hours += pile % speed == 0 ? pile / speed : pile / speed + 1;
        }
        if(hours <= h) {
            return true;
        }
        return false;
    }
}

因为每一堆香蕉的最大数量为10^9，所以可以设置最大速度为10^9，最小速度为1。然后就可以进行二分查找，不断缩小速度。

值得注意的是在check()方法中用于记录用时的变量hours需要设置为long，不然会有溢出的风险。

时间复杂度分析：

• piles的长度为n，每次二分查找都需要遍历一次piles数组，复杂度为O(n)
• 二分查找的范围是1-10^9，所以复杂度为O(10^9)
• 综上时间复杂度为O(10^9n)

空间复杂度为O(1)

962. Maximum Width Ramp

A ramp in an integer array nums is a pair (i, j) for which i < j and nums[i] <= nums[j]. The width of such a ramp is j - i.

Given an integer array nums, return the maximum width of a ramp in nums. If there is no ramp in nums, return 0.

Example 1:

Input: nums = [6,0,8,2,1,5]
Output: 4
Explanation: The maximum width ramp is achieved at (i, j) = (1, 5): nums[1] = 0 and nums[5] = 5.

Example 2:

Input: nums = [9,8,1,0,1,9,4,0,4,1]
Output: 7
Explanation: The maximum width ramp is achieved at (i, j) = (2, 9): nums[2] = 1 and nums[9] = 1.

这道题其实简单来说就是找到和每个元素对应的不小于它的最远的元素，并且得到距离的最大值。

具体的做法是维护一个单调递减栈，从左向右遍历。再从右向左遍历，如果栈顶的元素小于等于遍历到的元素，就出栈并记录最大距离，知道栈空。

代码如下：

class Solution {
    public int maxWidthRamp(int[] nums) {
        Deque<Integer> stack = new LinkedList<>();
        for(int i = 0; i < nums.length; i ++) {
            if(stack.isEmpty() || nums[stack.peekLast()] > nums[i]) {
                stack.offerLast(i);
            }
        }

        int res = 0;
        for(int i = nums.length - 1; i >= 0; i --) {
            while(!stack.isEmpty() && nums[stack.peekLast()] <= nums[i]) {
                res = Math.max(res, i - stack.pollLast());
            }
        } 
        return res;
    }
}

时间复杂度分析：

• 维护单调栈需要遍历每个元素， O(n)。
• 第二次从右向左遍历元素最坏情况下需要遍历全部元素，O(n)。

时间复杂度为O(n)。

空间复杂度分析:

• 最坏情况stack需要记录全部元素， O(n)。

空间复杂度为O(n)。

2406. Divide Intervals Into Minimum Number of Groups

You are given a 2D integer array intervals where intervals[i] = [lefti, righti] represents the inclusive interval [lefti, righti].

You have to divide the intervals into one or more groups such that each interval is in exactly one group, and no two intervals that are in the same group intersect each other.

Return the minimum number of groups you need to make.

Two intervals intersect if there is at least one common number between them. For example, the intervals [1, 5] and [5, 8] intersect.

Example 1:

Input: intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]]
Output: 3
Explanation: We can divide the intervals into the following groups:
- Group 1: [1, 5], [6, 8].
- Group 2: [2, 3], [5, 10].
- Group 3: [1, 10].
It can be proven that it is not possible to divide the intervals into fewer than 3 groups.

Example 2:

Input: intervals = [[1,3],[5,6],[8,10],[11,13]]
Output: 1
Explanation: None of the intervals overlap, so we can put all of them in one group.

这道题可以用时间线和事件的思路去解决，不必拘泥于时间对，而是把每一个时间对拆开，将其视为开始时间和结束时间。

同时使用一个最小堆对时间进行排序，当存在开始时间和结束时间相同时先处理开始时间。维护一个变量记录同时存在的事件的最大数量，即为答案。

代码如下：

class Solution {
    public int minGroups(int[][] intervals) {
        Queue<int[]> events = new PriorityQueue<>((a, b) -> {
            if(a[0] == b[0]) {
                return b[1] - a[1];
            }
            return a[0] - b[0];
        });
        for(int[] interval: intervals) {
            events.offer(new int[] {interval[0], 1}); // 1 is starting
            events.offer(new int[] {interval[1], -1}); // 0 is ending
        }

        int cur = 0;
        int res = 0;
        while(!events.isEmpty()) {
            int[] curEvent = events.poll();
            cur += curEvent[1];
            res = Math.max(cur, res);
        }
        return res;
    }
}

时间复杂度分析：

• 假设intervals有n个事件，那么一共有2n个时间点，插入堆的复杂度为O(log2n),综合复杂度为O(2nlog(2n)) = O(nlogn)。

空间复杂度分析：

• 堆需要O(2n) = O(n)的空间

632. Smallest Range Covering Elements from K Lists

You have k lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k lists.

We define the range [a, b] is smaller than range [c, d] if b - a < d - c or a < c if b - a == d - c.

Example 1:

Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20,24]
Explanation: 
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].

Example 2:

Input: nums = [[1,2,3],[1,2,3],[1,2,3]]
Output: [1,1]

涉及到“最大”“最小”问题时，往往需要考虑使用heap，因为这类问题需要频繁地获得最大最小值，而堆可以实现在O(1)的复杂度下得到最值，从而降低时间复杂度。

每一轮将一列元素存入heap，将最小值移出，并且动态的更新最大最小值，并记录range，再将移出元素的下一个元素加入heap，直到heap中的元素数量小于nums中数组的数量，最终获得的最小range即为答案。

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        Queue<int[]> pq = new PriorityQueue<>((a, b) -> {
            return a[0] - b[0];
        });
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < nums.size(); i ++) {
            pq.offer(new int[] {nums.get(i).get(0), i, 0});
            max = Math.max(max, nums.get(i).get(0));
        }
        int[] res = new int[2];
        int range = Integer.MAX_VALUE;
        while(pq.size() == nums.size()) {
            int[] cur = pq.poll();
            int min = cur[0];
            if(range > max - min) {
                range = max - min;
                res[0] = min;
                res[1] = max;
            }

            if(cur[2] < nums.get(cur[1]).size() - 1) {
                pq.offer(new int[] {nums.get(cur[1]).get(cur[2] + 1), cur[1], cur[2] + 1});
                max = Math.max(max, nums.get(cur[1]).get(cur[2] + 1));
            }
        }
        return res;
    }
}

例一的每一轮处理过程如下

heap 0 4 5
max 5
min 0
range 5

heap 4 5 9
max 9
min 4
range 5

heap 5 9 10
max 10
min 5
range 5

heap 9 10 18
max 18
min 9
range 9

heap 10 12 18
max 18
min 10
range 8

heap 12 15 18
max 18
min 12 
range 6

heap 15 18 20
min 15
max 20
range 5

heap 18 20 24
min 18
max 24
range 6

heap 20 22 24
min 20
max 24
range 4

时间复杂度分析：

• 设nums中共有k个数组，设共有N个元素，最坏情况下heap需要遍历每一个元素，每次插入和删除元素的复杂度为O(logk)，时间复杂度为O(Nlogk)。

空间复杂度分析：

• heap中始终存在k个元素，空间复杂度为O(k)

1942. The Number of the Smallest Unoccupied Chair

There is a party where n friends numbered from 0 to n - 1 are attending. There is an infinite number of chairs in this party that are numbered from 0 to infinity. When a friend arrives at the party, they sit on the unoccupied chair with the smallest number.

• For example, if chairs 0, 1, and 5 are occupied when a friend comes, they will sit on chair number 2.

When a friend leaves the party, their chair becomes unoccupied at the moment they leave. If another friend arrives at that same moment, they can sit in that chair.

You are given a 0-indexed 2D integer array times where times[i] = [arrivali, leavingi], indicating the arrival and leaving times of the ith friend respectively, and an integer targetFriend. All arrival times are distinct.

Return the chair number that the friend numbered targetFriend will sit on.

Example 1:

Input: times = [[1,4],[2,3],[4,6]], targetFriend = 1
Output: 1
Explanation: 
- Friend 0 arrives at time 1 and sits on chair 0.
- Friend 1 arrives at time 2 and sits on chair 1.
- Friend 1 leaves at time 3 and chair 1 becomes empty.
- Friend 0 leaves at time 4 and chair 0 becomes empty.
- Friend 2 arrives at time 4 and sits on chair 0.
Since friend 1 sat on chair 1, we return 1.

Example 2:

Input: times = [[3,10],[1,5],[2,6]], targetFriend = 0
Output: 2
Explanation: 
- Friend 1 arrives at time 1 and sits on chair 0.
- Friend 2 arrives at time 2 and sits on chair 1.
- Friend 0 arrives at time 3 and sits on chair 2.
- Friend 1 leaves at time 5 and chair 0 becomes empty.
- Friend 2 leaves at time 6 and chair 1 becomes empty.
- Friend 0 leaves at time 10 and chair 2 becomes empty.
Since friend 0 sat on chair 2, we return 2.

• 这个问题可以考虑将每个人的时间拆开，分成开始时间和结束时间。将拆开后的时间以数组的形式存入小顶堆中，arr[0]是时间，arr[1]用来记录是第几个人，arr[2]用来记录是到达时间还是离开时间。以arr[0]为依据排序。
• 同时，一个优先队列来记录当前时刻下空的椅子，这样总是可以得到最小的可以利用的椅子。
• 用一个Map来记录当前时刻下已经被占用的椅子，key为人的徐浩，value是椅子序号。
• 具体的流程是，按发生顺序依次遍历每一个时间。如果为到达时间，就从availableChairs中分配一把椅子，并存入occupiedChairs。并且检查是否是targetFriend；如果为结束时间，就将对应的occupiedChairs中的椅子放回avaliableChairs。

class Solution {
    public int smallestChair(int[][] times, int targetFriend) {
      	
        Queue<int[]> events = new PriorityQueue<>((a, b) -> {
            if(a[0] == b[0]) {
                return a[2] - b[2];
            }
            return a[0] - b[0];
        });

        Queue<Integer> avaliableChairs = new PriorityQueue<>();
        Map<Integer, Integer> occupiedChairs = new HashMap<>();

        for(int i = 0; i < times.length; i ++) {
            events.offer(new int[] {times[i][0], i, 1}); // arrival
            events.offer(new int[] {times[i][1], i, 0}); // leaving
        }

        for(int i = 0; i < times.length; i ++) {
            avaliableChairs.offer(i);
        }

        while(!events.isEmpty()) {
            int[] cur = events.poll();
            int time = cur[0];
            int number = cur[1];
            int event = cur[2];

            if(event == 1) { // arrival
                int chair = avaliableChairs.poll();
                if(number == targetFriend) {
                    return chair;
                }
                occupiedChairs.put(number, chair);
            } else { // leaving
                int chair = occupiedChairs.get(number);
                avaliableChairs.offer(chair);
            }
        }
        return -1;
    }
}

时间复杂度分析：

• 设一共有n个人，events共插入2n次，每次插入的时间复杂度为O(logn)，复杂度为O(2nlog2n) = O(nlogn)。
• 将所有椅子加入avaliableChairs，时间复杂度为O(nlogn)。
• 依次遍历每个event，最坏情况下每次都要取一个新的椅子，从avaliableChairs取椅子复杂度为O(logn), 插入occupiedChairs复杂度为(O(1))，总复杂度为2n(O(logn) + O(1)) = O(nlogn)。

综上时间复杂度为O(nlogn)。

空间复杂度分析：

• events需要O(2n)
• avaliableChair最多需要O(n)
• occupiedChair最多需要O(n)

综上空间复杂度为O(n)。