东莞最好的网站建设,扬州门户网站开发公司,建设局电话,四川省建设厅注册管理中心网站首页文章目录 2141. 同时运行 N 台电脑的最长时间解法1——二分答案补充#xff1a;求一个int数组的和#xff0c;但数组和会超int 解法2——贪心解法 2251. 花期内花的数目解法1——二分答案代码1——朴素二分写法代码2——精简二分⭐ 解法2——差分⭐⭐⭐ 2258. 逃离火灾解法1—… 文章目录 2141. 同时运行 N 台电脑的最长时间解法1——二分答案补充求一个int数组的和但数组和会超int 解法2——贪心解法 2251. 花期内花的数目解法1——二分答案代码1——朴素二分写法代码2——精简二分⭐ 解法2——差分⭐⭐⭐ 2258. 逃离火灾解法1——两次bfs解法2——二分 BFS 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) {MapInteger, 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];Queueint[] 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 ArrayListint[]();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 ArrayListint[]();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; // 寄}ArrayListint[] spreadFire(int[][] grid, boolean[][] fire, ArrayListint[] 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;}
} 仅作了解即可。
