Leecode双周赛（2022-04-30晚）_ranking of biweekly-contest

双周赛

先上链接 ； https://leetcode-cn.com/contest/biweekly-contest-77/ranking/

第一题

6051. 统计是给定字符串前缀的字符串数目

难度简单1收藏分享切换为英文接收动态反馈

给你一个字符串数组 words 和一个字符串 s ，其中 words[i] 和 s 只包含 小写英文字母 。

请你返回 words 中是字符串 s 前缀 的 字符串数目 。

一个字符串的 前缀 是出现在字符串开头的子字符串。子字符串 是一个字符串中的连续一段字符序列。

示例 1：

输入：words = ["a","b","c","ab","bc","abc"], s = "abc"
输出：3
解释：
words 中是 s = "abc" 前缀的字符串为：
"a" ，"ab" 和 "abc" 。
所以 words 中是字符串 s 前缀的字符串数目为 3 。
1
2
3
4
5
6

示例 2：

输入：words = ["a","a"], s = "aa"
输出：2
解释：
两个字符串都是 s 的前缀。
注意，相同的字符串可能在 words 中出现多次，它们应该被计数多次。
1
2
3
4
5

提示：

• 1 <= words.length <= 1000
• 1 <= words[i].length, s.length <= 10
• words[i] 和 s 只 包含小写英文字母。

code

class Solution {
    public int countPrefixes(String[] words, String s) {
        int count = 0;
        for(String word :  words){
            if(s.startsWith(word)){
                count++;
            }
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11

第二题

6052. 最小平均差

难度中等3收藏分享切换为英文接收动态反馈

给你一个下标从 0 开始长度为 n 的整数数组 nums 。

下标 i 处的 平均差 指的是 nums 中 前 i + 1 个元素平均值和 后 n - i - 1 个元素平均值的 绝对差 。两个平均值都需要 向下取整 到最近的整数。

请你返回产生 最小平均差 的下标。如果有多个下标最小平均差相等，请你返回 最小 的一个下标。

注意：

• 两个数的 绝对差 是两者差的绝对值。
• n 个元素的平均值是 n 个元素之 和 除以（整数除法） n 。
• 0 个元素的平均值视为 0 。

示例 1：

输入：nums = [2,5,3,9,5,3]
输出：3
解释：
- 下标 0 处的平均差为：|2 / 1 - (5 + 3 + 9 + 5 + 3) / 5| = |2 / 1 - 25 / 5| = |2 - 5| = 3 。
- 下标 1 处的平均差为：|(2 + 5) / 2 - (3 + 9 + 5 + 3) / 4| = |7 / 2 - 20 / 4| = |3 - 5| = 2 。
- 下标 2 处的平均差为：|(2 + 5 + 3) / 3 - (9 + 5 + 3) / 3| = |10 / 3 - 17 / 3| = |3 - 5| = 2 。
- 下标 3 处的平均差为：|(2 + 5 + 3 + 9) / 4 - (5 + 3) / 2| = |19 / 4 - 8 / 2| = |4 - 4| = 0 。 
- 下标 4 处的平均差为：|(2 + 5 + 3 + 9 + 5) / 5 - 3 / 1| = |24 / 5 - 3 / 1| = |4 - 3| = 1 。
- 下标 5 处的平均差为：|(2 + 5 + 3 + 9 + 5 + 3) / 6 - 0| = |27 / 6 - 0| = |4 - 0| = 4 。
下标 3 处的平均差为最小平均差，所以返回 3 。
1
2
3
4
5
6
7
8
9
10

示例 2：

输入：nums = [0]
输出：0
解释：
唯一的下标是 0 ，所以我们返回 0 。
下标 0 处的平均差为：|0 / 1 - 0| = |0 - 0| = 0 。
1
2
3
4
5

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 105

code

class Solution {
    public int minimumAverageDifference(int[] nums) {
        long[] sums = new long[nums.length];
        sums[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sums[i] = sums[i-1] + nums[i];
        }
        int length = nums.length;
        long min = Integer.MAX_VALUE;
        int minIndex = 0;
        for (int i = 0; i < sums.length; i++) {
            long avg1 = sums[i] / (i + 1);
            long avg2 = i == nums.length - 1 ? 0 : (sums[length - 1] - sums[i]) / (length - (i + 1));
            if(min > Math.abs(avg1 - avg2)){
                min = Math.abs(avg1 - avg2);
                minIndex = i;
            }
        }
        return minIndex;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

第三题

6053. 统计网格图中没有被保卫的格子数

难度中等3收藏分享切换为英文接收动态反馈

给你两个整数 m 和 n 表示一个下标从 0 开始的 m x n 网格图。同时给你两个二维整数数组 guards 和 walls ，其中 guards[i] = [rowi, coli] 且 walls[j] = [rowj, colj] ，分别表示第 i 个警卫和第 j 座墙所在的位置。

一个警卫能看到 4 个坐标轴方向（即东、南、西、北）的 所有 格子，除非他们被一座墙或者另外一个警卫 挡住 了视线。如果一个格子能被 至少 一个警卫看到，那么我们说这个格子被 保卫 了。

请你返回空格子中，有多少个格子是 没被保卫 的。

示例 1：

输入：m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]]
输出：7
解释：上图中，被保卫和没有被保卫的格子分别用红色和绿色表示。
总共有 7 个没有被保卫的格子，所以我们返回 7 。
1
2
3
4

示例 2：

输入：m = 3, n = 3, guards = [[1,1]], walls = [[0,1],[1,0],[2,1],[1,2]]
输出：4
解释：上图中，没有被保卫的格子用绿色表示。
总共有 4 个没有被保卫的格子，所以我们返回 4 。
1
2
3
4

提示：

• 1 <= m, n <= 105
• 2 <= m * n <= 105
• 1 <= guards.length, walls.length <= 5 * 104
• 2 <= guards.length + walls.length <= m * n
• guards[i].length == walls[j].length == 2
• 0 <= rowi, rowj < m
• 0 <= coli, colj < n
• guards 和 walls 中所有位置 互不相同 。

思路：

遍历每个战士，然后把每个方格用bitmap 来标记是否已经扫描过了。

code

class Solution {
    public int countUnguarded(int m, int n, int[][] guards, int[][] walls) {
        byte[][] grap = new byte[m][n];
        for(int[] wall : walls){
            grap[wall[0]][wall[1]] = 2;
        }
        for(int[] guard : guards){
            grap[guard[0]][guard[1]] = 1;
            for(int i = guard[0] + 1 ; i < m; i++){
                if(grap[i][guard[1]] == 2 || (grap[i][guard[1]] & (1 << 3)) > 0){
                    break;
                }
                grap[i][guard[1]] |= 1 << 3 ;
            }
            for(int i = guard[0] - 1 ; i >= 0; i--){
                if(grap[i][guard[1]] == 2 || (grap[i][guard[1]] & (1 << 4)) > 0){
                    break;
                }
                grap[i][guard[1]] |= 1 << 4;
            }
            for(int i = guard[1] - 1 ; i >= 0; i--){
                if(grap[guard[0]][i] == 2 || (grap[guard[0]][i] & (1 << 5)) > 0){
                    break;
                }
                grap[guard[0]][i] |= 1 << 5;
            }
            for(int i = guard[1] + 1 ; i < n; i++){
                if(grap[guard[0]][i] == 2 || (grap[guard[0]][i] & (1 << 6)) > 0){
                    break;
                }
                grap[guard[0]][i] |= 1 << 6;
            }
        }
        int count = 0;
        for(int i = 0; i < m ;i++){
            for(int j = 0; j < n; j++){
                if(grap[i][j] == 0){
                    count ++;
                }
            }
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

第四题

6054. 逃离火灾

难度困难6收藏分享切换为英文接收动态反馈

给你一个下标从 0 开始大小为 m x n 的二维整数数组 grid ，它表示一个网格图。每个格子为下面 3 个值之一：

• 0 表示草地。
• 1 表示着火的格子。
• 2 表示一座墙，你跟火都不能通过这个格子。

一开始你在最左上角的格子 (0, 0) ，你想要到达最右下角的安全屋格子 (m - 1, n - 1) 。每一分钟，你可以移动到 相邻 的草地格子。每次你移动 之后 ，着火的格子会扩散到所有不是墙的 相邻 格子。

请你返回你在初始位置可以停留的 最多 分钟数，且停留完这段时间后你还能安全到达安全屋。如果无法实现，请你返回 -1 。如果不管你在初始位置停留多久，你 总是 能到达安全屋，请你返回 109 。

注意，如果你到达安全屋后，火马上到了安全屋，这视为你能够安全到达安全屋。

如果两个格子有共同边，那么它们为 相邻 格子。

示例 1：

输入：grid = [[0,2,0,0,0,0,0],[0,0,0,2,2,1,0],[0,2,0,0,1,2,0],[0,0,2,2,2,0,2],[0,0,0,0,0,0,0]]
输出：3
解释：上图展示了你在初始位置停留 3 分钟后的情形。
你仍然可以安全到达安全屋。
停留超过 3 分钟会让你无法安全到达安全屋。
1
2
3
4
5

示例 2：

输入：grid = [[0,0,0,0],[0,1,2,0],[0,2,0,0]]
输出：-1
解释：上图展示了你马上开始朝安全屋移动的情形。
火会蔓延到你可以移动的所有格子，所以无法安全到达安全屋。
所以返回 -1 。
1
2
3
4
5

示例 3：

输入：grid = [[0,0,0],[2,2,0],[1,2,0]]
输出：1000000000
解释：上图展示了初始网格图。
注意，由于火被墙围了起来，所以无论如何你都能安全到达安全屋。
所以返回 109 。
1
2
3
4
5

提示：

• m == grid.length
• n == grid[i].length
• 2 <= m, n <= 300
• 4 <= m * n <= 2 * 104
• grid[i][j] 是 0 ，1 或者 2 。
• grid[0][0] == grid[m - 1][n - 1] == 0

思路：

BFS + 二分

1. 先计算火什么时候到每个方格
2. 计算人到方格的时间，
3. 火最后到终点的时间，二分。

code

class Solution {
    int[][] vectors = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int maximumMinutes(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] huo = new int[m][n];
        LinkedList<Integer> arrayDeque = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    arrayDeque.add(i << 16 | j);
                    huo[i][j] = 1;
                }
            }
        }
        Integer num = 0;
        while ((num = arrayDeque.peek()) != null) {
            arrayDeque.pop();
            for (int i = 0; i < vectors.length; i++) {
                int a = (num >> 16) + vectors[i][0];
                int b = (num & 0xffff) + vectors[i][1];
                if (a < m && a >= 0 && b >= 0 && b < n && huo[a][b] == 0 && grid[a][b] == 0) {
                    arrayDeque.add(a << 16 | b);
                    huo[a][b] = huo[num >> 16][num & 0xffff] + 1;
                }
            }
        }
        if(!check(0,huo,grid)){
            return -1;
        }
        if(huo[m - 1][n - 1] == 0){
            return 1000000000;
        }
        int left = 0, right = m * n;
        while(left < right) {
            int mid  = (left+right + 1) >> 1;
            if(check(mid,huo,grid)) left = mid;
            else right = mid - 1;
        }
        return left;
    }

    public boolean check(int step, int[][] huo,int[][] grid){
        int m = grid.length, n = grid[0].length;
        int[][] ren = new int[m][n];
        LinkedList<Integer> arrayDeque = new LinkedList<>();
        arrayDeque.add(0);
        ren[0][0] = step + 1;
        Integer num = 0;
        while ((num = arrayDeque.peek()) != null) {
            arrayDeque.pop();
            for (int i = 0; i < vectors.length; i++) {
                int a = (num >> 16) + vectors[i][0];
                int b = (num & 0xffff) + vectors[i][1];
                if (a < m && a >= 0 && b >= 0 && b < n && ren[a][b] == 0 && grid[a][b] == 0) {
                    ren[a][b] = ren[num >> 16][num & 0xffff] + 1;
                    if(a == m - 1 && b == n -1){
                        return ren[a][b] <= huo[a][b] || huo[a][b] == 0;
                    }
                    if(ren[a][b] < huo[a][b] || huo[a][b] == 0){
                        arrayDeque.add(a << 16 | b);
                    }
                }
            }
        }
        return false;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69