【LeetCode周赛】2022上半年题目精选集——二分

2141. 同时运行 N 台电脑的最长时间

2141. 同时运行 N 台电脑的最长时间

提示：
1 <= n <= batteries.length <= 10^5
1 <= batteries[i] <= 10^9

解法1——二分答案

二分答案。

解释见：【LeetCode周赛】2022上半年题目精选集——贪心

class Solution {public long maxRunTime(int n, int[] batteries) {// long sum = Arrays.stream(batteries).asLongStream().sum();long sum = Arrays.stream(batteries).mapToLong(Long::valueOf).sum();long l = 0, r = sum / n;while (l < r) {long mid = l + r + 1 >> 1;if (check(n, batteries, mid)) l = mid;else r = mid - 1;}return l;}public boolean check(int n, int[] batteries, long k) {long sum = 0;for (int battery: batteries) sum += Math.min(k, battery);return n <= sum / k;}
}

补充：求一个int数组的和，但数组和会超int

解法——将 int 转成 long

写法1：

long sum = Arrays.stream(batteries).asLongStream().sum();

写法2：

long sum = Arrays.stream(batteries).mapToLong(Long::valueOf).sum();

解法2——贪心解法

见：【LeetCode周赛】2022上半年题目精选集——贪心

2251. 花期内花的数目

2251. 花期内花的数目

解法1——二分答案

枚举每个人。

每个人看到花的数量，通过二分法得出，等于 start <= time 且 end >= time 的花的数量，可以通过 start <= time 减去 end < time 的数量得到每个人的答案。
（即从一个合理的范围内减去不合理的那部分）。

代码1——朴素二分写法

（其实就是笔者自己写的代码）

class Solution {public int[] fullBloomFlowers(int[][] flowers, int[] people) {int m = flowers.length, n = people.length;int[] ans = new int[n];int[] start = new int[m], end = new int[m];for (int i = 0; i < m; ++i) {start[i] = flowers[i][0];end[i] = flowers[i][1];}Arrays.sort(start);Arrays.sort(end);for (int i = 0; i < n; ++i) {ans[i] = op(start, end, people[i]);}return ans;}public int op(int[] start, int[] end, int time) {int n = start.length;if (start[0] > time || end[n - 1] < time) return 0;// 找到最后一个开花时间<=time的花int l = 0, r = n - 1; while (l < r) {int mid = l + r + 1 >> 1;if (start[mid] > time) r = mid - 1;else l = mid;}int x = l;// 找到第一个结束时间>=time的花l = 0;r = n - 1;while (l < r) {int mid = l + r >> 1;if (end[mid] < time) l = mid + 1;else r = mid;}// 在开花时间<=time的花中减去结束时间<time的花就是答案return x - l + 1;}
}

代码2——精简二分⭐

计算 x = start 中 >= p + 1 的下标， y = end 中 >= p 的下标。
结果为 x - y。

class Solution {public int[] fullBloomFlowers(int[][] flowers, int[] persons) {int[] starts = Arrays.stream(flowers).mapToInt(f -> f[0]).sorted().toArray();int[] ends = Arrays.stream(flowers).mapToInt(f -> f[1]).sorted().toArray();return Arrays.stream(persons).map(p -> lowerBound(starts, p + 1) - lowerBound(ends, p)).toArray();}// 找到第一个>=x的值,即x的下界int lowerBound(int[] arr, int x) {int left = 0, right = arr.length;   // 注意r的初始值是n而不是n-1while (left < right) {int mid = (left + right) >>> 1;if (arr[mid] >= x) right = mid;else left = mid + 1;}return left;}
}

这种方法通过 lowerBound() 方法避免了写两次二分。

解法2——差分⭐⭐⭐

由于数据范围的原因，我们需要使用 map 而不是数组来存储 差分结果。

关于差分可见：【算法基础】1.5 前缀和与差分

class Solution {public int[] fullBloomFlowers(int[][] flowers, int[] people) {Map<Integer, Integer> diff = new HashMap();for (int[] flower: flowers) {diff.merge(flower[0], 1, Integer::sum);diff.merge(flower[1] + 1, -1, Integer::sum);}// 去除差分哈希表中的所有时间点int[] times = diff.keySet().stream().mapToInt(Integer::intValue).sorted().toArray();int n = people.length;Integer[] ids = IntStream.range(0, n).boxed().toArray(Integer[]::new);Arrays.sort(ids, (i, j) -> people[i] - people[j]);  // 按时间升序取出people数组下标int[] ans = new int[n];int i = 0, sum = 0;for (int id: ids) {while (i < times.length && times[i] <= people[id]) {sum += diff.get(times[i++]);}ans[id] = sum;}return ans;}
}

2258. 逃离火灾

2258. 逃离火灾

难度：2347

解法1——两次bfs

先对火焰进行多源 bfs ，计算出火焰达到每个位置的时间。

然后对人进行 bfs，记录每条路径上最多能等待多少时间，每条路径达到终点时更新答案。

class Solution {public int maximumMinutes(int[][] grid) {int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};// 先处理出火达到每个地方的时间，如果达到不了，设置成最大值int m = grid.length, n = grid[0].length;int[][] times = new int[m][n];Queue<int[]> q = new LinkedList();for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (grid[i][j] != 1) {times[i][j] = Integer.MAX_VALUE;    // 表示火还没有到} else {q.offer(new int[]{i, j});           // 加入当前有火的队列    times[i][j] = 1;}}}// 计算火焰达到每个位置的时间int t = 2;while (!q.isEmpty()) {int sz = q.size();for (int i = 0; i < sz; ++i) {int[] cur = q.poll();int x = cur[0], y = cur[1];for (int k = 0; k < 4; ++k) {int nx = x + dx[k], ny = y + dy[k];if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 0) {grid[nx][ny] = 1;times[nx][ny] = t;q.offer(new int[]{nx, ny});}}}t++;}// bfs 人int ans = -1;t = 2;grid[0][0] = 2;q.offer(new int[]{0, 0, times[0][0] - 1});  // 最后一个元素记录当前时间的冗余while (!q.isEmpty()) {int sz = q.size();for (int i = 0; i < sz; ++i) {int[] cur = q.poll();int x = cur[0], y = cur[1], curLeftTime = cur[2];for (int k = 0; k < 4; ++k) {int nx = x + dx[k], ny = y + dy[k];if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] != 2) {// 把走过的地方标记成墙壁,但是终点可以以不同方式到达多次if (nx != m - 1 || ny != n - 1) grid[nx][ny] = 2;               int leftTime;// 如果到了终点就不用考虑当前时刻被火追上if (nx == m - 1 && ny == n - 1) leftTime = Math.min(curLeftTime, times[nx][ny] - t);else leftTime = Math.min(curLeftTime, times[nx][ny] - t - 1);if (leftTime < 0) continue;     // 时间不够这条路走不通if (nx == m - 1 && ny == n - 1) ans = Math.max(ans, leftTime);q.offer(new int[]{nx, ny, leftTime});}}}t++;}return ans > m * n? (int)1e9: ans;}
}

解法2——二分 + BFS

https://leetcode.cn/problems/escape-the-spreading-fire/solution/er-fen-bfspythonjavacgo-by-endlesscheng-ypp1/

注意！：实际上笔者认为这道题目是不需要二分的，使用二分反倒时间复杂度上去了。

class Solution {static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};public int maximumMinutes(int[][] grid) {int m = grid.length, n = grid[0].length;int left = -1, right = m * n;while (left < right) {var mid = (left + right + 1) / 2;if (check(grid, mid)) left = mid;else right = mid - 1;}return left < m * n ? left : (int) 1e9;}boolean check(int[][] grid, int t) {int m = grid.length, n = grid[0].length;var fire = new boolean[m][n];var f = new ArrayList<int[]>();for (var i = 0; i < m; i++)for (var j = 0; j < n; j++)if (grid[i][j] == 1) {fire[i][j] = true;f.add(new int[]{i, j});}while (t-- > 0 && f.size() > 0)f = spreadFire(grid, fire, f); // 蔓延至多 t 分钟的火势if (fire[0][0]) return false; // 起点着火，寄var vis = new boolean[m][n];vis[0][0] = true;var q = new ArrayList<int[]>();q.add(new int[]{0, 0});while (q.size() > 0) {var tmp = q;q = new ArrayList<>();for (var p : tmp)if (!fire[p[0]][p[1]])for (var d : dirs) {int x = p[0] + d[0], y = p[1] + d[1];if (0 <= x && x < m && 0 <= y && y < n && !fire[x][y] && !vis[x][y] && grid[x][y] == 0) {if (x == m - 1 && y == n - 1) return true; // 我们安全了…暂时。vis[x][y] = true;q.add(new int[]{x, y});}}f = spreadFire(grid, fire, f); // 蔓延 1 分钟的火势}return false; // 寄}ArrayList<int[]> spreadFire(int[][] grid, boolean[][] fire, ArrayList<int[]> f) {int m = grid.length, n = grid[0].length;var tmp = f;f = new ArrayList<>();for (var p : tmp)for (var d : dirs) {int x = p[0] + d[0], y = p[1] + d[1];if (0 <= x && x < m && 0 <= y && y < n && !fire[x][y] && grid[x][y] == 0) {fire[x][y] = true;f.add(new int[]{x, y});}}return f;}
}    

仅作了解即可。