力扣第 77 场双周赛
大约 4 分钟
力扣第 77 场双周赛
2022 四月的最后一天。本场周赛国服共 245 人 AK。
T1. 统计是给定字符串前缀的字符串数目（3 分）
解题思路
模拟。直接用库函数 String#startsWith(String prefix) 判断是否为前缀即可。
时间复杂度：库函数不讨论时间复杂度。
参考代码
class Solution {
public int countPrefixes(String[] words, String s) {
int cnt = 0;
for (String word : words) {
if (s.startsWith(word)) {
cnt++;
}
}
return cnt;
}
}
T2. 最小平均差（4 分）
解题思路
前缀和 + 模拟。枚举每个下标，分别计算出前 i+1 个元数和后 n-i-1 个元素的平均值绝对差，需注意边界条件 n-i-1 为 0 的情况。
时间复杂度：O(n)。
参考代码
class Solution {
public int minimumAverageDifference(int[] nums) {
int n = nums.length;
// 前缀和
long[] preSum = new long[n + 1];
for (int i = 0; i < n; i++) {
preSum[i + 1] = preSum[i] + nums[i];
}
int min = Integer.MAX_VALUE;
int minIdx = n - 1;
// 如果有多个下标最小平均差相等，请你返回 最小 的一个下标。
for (int i = n - 1; i >= 0; i--) {
long leftSum = preSum[i + 1] - preSum[0];
long rightSum = preSum[n] - leftSum;
int leftAvg = (int) (leftSum / (i + 1));
int rightAvg = (n - i - 1 == 0) ? (int) rightSum : (int) (rightSum / (n - i - 1));
int diff = Math.abs(leftAvg - rightAvg);
if (diff <= min) {
min = diff;
minIdx = i;
}
}
return minIdx;
}
}
T3. 统计网格图中没有被保卫的格子数（5 分）
解题思路
模拟。数据范围 m * n <= 10^5，咋眼一看直接模拟会超时，但注意题目条件 除非他们被一座墙或者另外一个警卫 挡住 了视线，相当于一个幅度很大的剪枝。
时间复杂度约为：O(m * n)，可以过。
参考代码
class Solution {
public int countUnguarded(int m, int n, int[][] guards, int[][] walls) {
char[][] grid = new char[m][n];
// 初始状态 置为未被保卫
for (char[] chars : grid) {
Arrays.fill(chars, 'F');
}
// 警卫
for (int[] guard : guards) {
grid[guard[0]][guard[1]] = 'G';
}
// 墙
for (int[] wall : walls) {
grid[wall[0]][wall[1]] = 'W';
}
// 模拟
for (int[] guard : guards) {
mock(m, n, grid, guard[0], guard[1]);
}
int cnt = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 'F') {
cnt++;
}
}
}
return cnt;
}
private void mock(int m, int n, char[][] grid, int guardX, int guardY) {
// up
for (int i = guardX - 1; i >= 0 && grid[i][guardY] != 'W' && grid[i][guardY] != 'G'; i--) {
if (grid[i][guardY] == 'F') {
grid[i][guardY] = 'T';
}
}
// down
for (int i = guardX + 1; i < m && grid[i][guardY] != 'W' && grid[i][guardY] != 'G'; i++) {
if (grid[i][guardY] == 'F') {
grid[i][guardY] = 'T';
}
}
// left
for (int j = guardY - 1; j >= 0 && grid[guardX][j] != 'W' && grid[guardX][j] != 'G'; j--) {
if (grid[guardX][j] == 'F') {
grid[guardX][j] = 'T';
}
}
// right
for (int j = guardY + 1; j < n && grid[guardX][j] != 'W' && grid[guardX][j] != 'G'; j++) {
if (grid[guardX][j] == 'F') {
grid[guardX][j] = 'T';
}
}
}
}
T4. 逃离火灾（6 分）
解题思路
BFS + 二分。着火的格子扩散和人能到达的位置均满足 BFS 模型。停留时间也显然满足单调性（如果能停留到 n 分钟，则必定也能停留 n-1 分钟），可用二分法求出在初始位置可以停留的 最多 分钟数。
因为数据范围 m * n <= 2 * 10^4，着火的格子每分钟扩散 1 格，所以二分上界可以设置为 2 * 10^4（当然设置为 10^9 也能过）。
时间复杂度：O(m*n*logT)，其中 T = 2 * 10^4。
参考代码
class Solution {
private static final int[][] DIRECTIONS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
private int M;
private int N;
public int maximumMinutes(int[][] grid) {
M = grid.length;
N = grid[0].length;
int left = 0;
int right = 20000;
while (left < right) {
int mid = left + (right - left) / 2;
int[][] gridClone = new int[M][N];
for (int i = 0; i < M; i++) {
if (N >= 0) {
System.arraycopy(grid[i], 0, gridClone[i], 0, N);
}
}
// 边界二分 F, F,..., F, [T, T,..., T] checkMid(mid) == T
// ----------------------^
if (!checkMid(gridClone, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
// 左边界二分
return left == 20000 ? 1000000000 : left - 1;
}
private boolean checkMid(int[][] grid, int mid) {
Queue<int[]> fires = new LinkedList<>();
// 在初始位置停留 mid 分钟 火势蔓延
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
if (grid[i][j] == 1) {
fires.add(new int[]{i, j});
}
}
}
int minutes = 0;
while (!fires.isEmpty()) {
int size = fires.size();
if (minutes == mid) {
break;
}
minutes++;
for (int i = 0; i < size; i++) {
int[] cur = fires.remove();
// 烧到人，直接 G
if (cur[0] == 0 && cur[1] == 0) {
return false;
}
for (int[] dir : DIRECTIONS) {
int nextM = cur[0] + dir[0];
int nextN = cur[1] + dir[1];
if (nextM >= 0 && nextM < M && nextN >= 0 && nextN < N && grid[nextM][nextN] == 0) {
grid[nextM][nextN] = 1;
fires.add(new int[]{nextM, nextN});
}
}
}
}
// 开始逃离火灾
Queue<int[]> player = new LinkedList<>();
boolean[][] visited = new boolean[M][N];
player.add(new int[]{0, 0});
visited[0][0] = true;
while (!player.isEmpty()) {
int size = player.size();
for (int i = 0; i < size; i++) {
int[] cur = player.remove();
if (cur[0] == M - 1 && cur[1] == N - 1) {
return true;
}
if (grid[cur[0]][cur[1]] == 1) {
continue;
}
for (int[] dir : DIRECTIONS) {
int nextM = cur[0] + dir[0];
int nextN = cur[1] + dir[1];
if (nextM >= 0 && nextM < M && nextN >= 0 && nextN < N && !visited[nextM][nextN] && grid[nextM][nextN] == 0) {
visited[nextM][nextN] = true;
player.add(new int[]{nextM, nextN});
}
}
}
int fireSize = fires.size();
for (int i = 0; i < fireSize; i++) {
int[] cur = fires.remove();
// 烧到 安全屋，直接 G
if (cur[0] == M - 1 && cur[1] == N - 1) {
return false;
}
for (int[] dir : DIRECTIONS) {
int nextM = cur[0] + dir[0];
int nextN = cur[1] + dir[1];
if (nextM >= 0 && nextM < M && nextN >= 0 && nextN < N && grid[nextM][nextN] == 0) {
grid[nextM][nextN] = 1;
fires.add(new int[]{nextM, nextN});
}
}
}
}
return false;
}
}
（全文完）