Leetcode 第 77 场双周赛

Posted on | Edited on | In ,
| 15k | 2:07

RT...

好不容易昨天把 290 场周赛的问题写完了~
这也是前面参加的周赛系列...

2255. Count Prefixes of a Given String

Analysis

题意比较直接，给一系列字符串，判断这些字符串是不是 s 的前缀。
实际上，需要满足 2 个条件：

  1. 第一个字符相同。
  2. 是 s 的子串。

Code

这是当时提交的代码：

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int countPrefixes(vector<string>& words, string s) {
        int size = words.size(), cnt = 0;
        for(int i = 0; i < size; i++) {
            if(s.find(words[i]) == 0) cnt++;
        }
        return cnt;
    }
};

其实不用 find 函数，用 substr 函数也是可以的：

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int countPrefixes(vector<string>& words, string s) {
        int cnt = 0;
        for(auto &w: words) {
            if(s.substr(0, w.length()) == w) cnt++;
        }
        return cnt;
    }
};

也可以全部自己写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isprefix(string &w, string &s) {
        if(w.length() > s.length()) return false;
        for(int i = 0; i < w.length(); i++) {
            if(w[i] != s[i]) return false;
        }
        return true;
    }
    int countPrefixes(vector<string>& words, string s) {
        int cnt = 0;
        for(string &w: words) {
            if(isprefix(w, s)) cnt++;
        }
        return cnt;
    }
};

思路都是一样的...

2256. Minimum Average Difference

Analysis

题目稍微有点长，不过意思也很直接，就是将元素分成两部分，算出平均值后，作差取绝对值。

Code

这是当时提交的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minimumAverageDifference(vector<int>& nums) {
        int size = nums.size();
        if(size == 1) return 0;
        vector<long long> pre(size + 1), ave(size + 1);
        for(int i = 0; i < size; i++) {
            pre[i + 1] = pre[i] + nums[i];
        }
        for(int i = 0; i < size - 1; i++) {
            ave[i] = abs(pre[i + 1] / (i + 1) - (pre[size] - pre[i + 1]) / (size - i - 1));
        }
        ave[size - 1] = pre[size] / size;
        int pos = 0;
        for(int i = 1; i < size; i++) {
            if(ave[i] < ave[pos]) pos = i;
        }
        return pos;
    }
};

基本思路是求前缀和，然后再遍历数组算出所有的绝对差，再查找最小的。
当时没看数据规模是 $1 \le nums.length \le 10^5$，$0 \le nums[i] \le 10^5$，忽略了在计算过程中可能出现的溢出，结果 WA 了一次，把 vector 的类型改成 long long 后就通过了，坑爹啊。

当时思考的时候，在下标的运算上思考了一会。其实是最后一个数字，出现了 0 作为除数的情况，特别处理一下就可以了。
现在看来就没有必要用重新在用数组保存每一个元素的绝对差了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minimumAverageDifference(vector<int>& nums) {
        int size = nums.size();
        if(size == 1) return 0;
        vector<long long> pre(size + 1);
        for(int i = 0; i < size; i++) {
            pre[i + 1] = pre[i] + nums[i];
        }
        long long minabsave = LONG_MAX, tmp;
        int pos = -1;
        for(int i = 0; i < size - 1; i++) {
            tmp = abs(pre[i + 1] / (i + 1) - (pre[size] - pre[i + 1]) / (size - i - 1));
            if(tmp < minabsave) {
                minabsave = tmp;
                pos = i;
            }
        }
        tmp = pre[size] / size;
        if(tmp < minabsave) pos = size - 1;
        return pos;
    }
};

仔细观察可以发现，如果一开始就把数组的和求出来，那么好像前缀和数组也不需要了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minimumAverageDifference(vector<int>& nums) {
        int size = nums.size();
        if(size == 1) return 0;
        long long minabsave = LONG_MAX, tmp, sum = 0, pre = 0;
        for(int i = 0; i < size; i++) {
            sum += nums[i];
        }
        int pos = -1;
        for(int i = 0; i < size - 1; i++) {
            pre += nums[i];
            tmp = abs(pre / (i + 1) - (sum - pre) / (size - i - 1));
            if(tmp < minabsave) {
                minabsave = tmp;
                pos = i;
            }
        }
        tmp = sum / size;
        if(tmp < minabsave) pos = size - 1;
        return pos;
    }
};

2257. Count Unguarded Cells in the Grid

Analysis

题目意思其实很简单，警卫所有能看见的格子都是被保卫的，被墙堵着，看不见的就是没被保卫的。
当时做的时候，总以为是个图的题目，结果写半天 bfs。写完运行发现，结果不对，仔细一想，这好像就是个模拟题？
结果又全删了，重新再写。

Code

这是当时提交的代码：

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
class Solution {
public:
    int countUnguarded(int m, int n, vector<vector<int>>& guards, vector<vector<int>>& walls) {
        vector<vector<int>> matrix(m, vector<int>(n));
        int size = guards.size();
        for(int i = 0; i < walls.size(); i++) {
            matrix[walls[i][0]][walls[i][1]] = 2;
        }
        for(int i = 0; i < size; i++) {
            int x = guards[i][0], y = guards[i][1], tmpx, tmpy;
            matrix[x][y] = 3;
            // up
            tmpx = x - 1, tmpy = y;
            while(tmpx >= 0) {
                if(matrix[tmpx][tmpy] == 2) break;
                matrix[tmpx][tmpy] = 1;
                tmpx--;
            }
            // down
            tmpx = x + 1, tmpy = y;
            while(tmpx < m) {
                if(matrix[tmpx][tmpy] == 2) break;
                matrix[tmpx][tmpy] = 1;
                tmpx++;
            }
            // left
            tmpx = x, tmpy = y - 1;
            while(tmpy >= 0) {
                if(matrix[tmpx][tmpy] == 2) break;
                matrix[tmpx][tmpy] = 1;
                tmpy--;
            }
            // right
            tmpx = x, tmpy = y + 1;
            while(tmpy < n) {
                if(matrix[tmpx][tmpy] == 2) break;
                matrix[tmpx][tmpy] = 1;
                tmpy++;
            }
        }
        int cnt = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(matrix[i][j] == 0) cnt++;
            }
        }
        return cnt;
    }
};

上面是当时写的暴力解法，可惜死在第 38 个用例了。
基本思路就是用不同的标记来表示某个格子是被保卫的、墙、警卫或没被保卫的，这与现在题目给出的提示是一致的思路。仔细看下上面这段代码，实际上最后一个 $O(n^2)$ 的循环可以省去，直接用矩阵总数减去被标记的格子数目即可。

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
class Solution {
public:
    int countUnguarded(int m, int n, vector<vector<int>>& guards, vector<vector<int>>& walls) {
        vector<vector<int>> matrix(m, vector<int>(n));
        int size = guards.size(), cnt = walls.size();
        for(int i = 0; i < cnt; i++) {
            matrix[walls[i][0]][walls[i][1]] = 2;
        }
        for(int i = 0; i < size; i++) {
            matrix[guards[i][0]][guards[i][1]] = 3;
        }
        cnt += size;
        for(int i = 0; i < size; i++) {
            int x = guards[i][0], y = guards[i][1], tmpx, tmpy;
            matrix[x][y] = 3;
            // up
            tmpx = x - 1, tmpy = y;
            while(tmpx >= 0) {
                if(matrix[tmpx][tmpy] == 2) break;
                else if(matrix[tmpx][tmpy] == 0) {
                    matrix[tmpx][tmpy] = 1;
                    cnt++;
                }
                tmpx--;
            }
            // down
            tmpx = x + 1, tmpy = y;
            while(tmpx < m) {
                if(matrix[tmpx][tmpy] == 2) break;
                else if(matrix[tmpx][tmpy] == 0) {
                    matrix[tmpx][tmpy] = 1;
                    cnt++;
                }
                tmpx++;
            }
            // left
            tmpx = x, tmpy = y - 1;
            while(tmpy >= 0) {
                if(matrix[tmpx][tmpy] == 2) break;
                else if(matrix[tmpx][tmpy] == 0) {
                    matrix[tmpx][tmpy] = 1;
                    cnt++;
                }
                tmpy--;
            }
            // right
            tmpx = x, tmpy = y + 1;
            while(tmpy < n) {
                if(matrix[tmpx][tmpy] == 2) break;
                else if(matrix[tmpx][tmpy] == 0) {
                    matrix[tmpx][tmpy] = 1;
                    cnt++;
                }
                tmpy++;
            }
        }
        return m * n - cnt;
    }
};

可惜这样还是过不去 38 个用例。
仔细想想，每个警卫可能存在横坐标或者纵坐标相同的时候，这样按照上面的代码就会产生重复标记的过程。得想办法去除这部分重复的过程，可以使用 set 存入所有的横坐标与纵坐标，然后再分别遍历，但这样无法判断墙是在点的左边还是右边（上边还是下边），这样就会漏解了。
看了别人的题解，才发现自己忽略了一个细节...那就是从警卫开始遍历的时候，如果遇到警卫了，也可以直接退出循环（与墙是一样的）。因为，遇到的这个警卫之前的遍历过程也是这样的😂。

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
class Solution {
public:
    int countUnguarded(int m, int n, vector<vector<int>>& guards, vector<vector<int>>& walls) {
        vector<vector<int>> matrix(m, vector<int>(n));
        int size = guards.size(), cnt = walls.size();
        for(int i = 0; i < cnt; i++) {
            matrix[walls[i][0]][walls[i][1]] = 2;
        }
        for(int i = 0; i < size; i++) {
            matrix[guards[i][0]][guards[i][1]] = 3;
        }
        cnt += size;
        for(int i = 0; i < size; i++) {
            int x = guards[i][0], y = guards[i][1], tmpx, tmpy;
            matrix[x][y] = 3;
            // up
            tmpx = x - 1, tmpy = y;
            while(tmpx >= 0) {
                if(matrix[tmpx][tmpy] == 0) {
                    matrix[tmpx][tmpy] = 1;
                    cnt++;
                } else if(matrix[tmpx][tmpy] != 1) break;
                tmpx--;
            }
            // down
            tmpx = x + 1, tmpy = y;
            while(tmpx < m) {
                if(matrix[tmpx][tmpy] == 0) {
                    matrix[tmpx][tmpy] = 1;
                    cnt++;
                } else if(matrix[tmpx][tmpy] != 1) break;
                tmpx++;
            }
            // left
            tmpx = x, tmpy = y - 1;
            while(tmpy >= 0) {
                if(matrix[tmpx][tmpy] == 0) {
                    matrix[tmpx][tmpy] = 1;
                    cnt++;
                } else if(matrix[tmpx][tmpy] != 1) break;
                tmpy--;
            }
            // right
            tmpx = x, tmpy = y + 1;
            while(tmpy < n) {
                if(matrix[tmpx][tmpy] == 0) {
                    matrix[tmpx][tmpy] = 1;
                    cnt++;
                } else if(matrix[tmpx][tmpy] != 1) break;
                tmpy++;
            }
        }
        return m * n - cnt;
    }
};

em，总算是通过了...忽略了细节啊...
不过这段代码看的有点废劲，借用一下图的 bfs 写法，改一下：

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
class Solution {
public:
    int X[4] = {1, -1, 0, 0};
    int Y[4] = {0, 0, 1, -1};
    int countUnguarded(int m, int n, vector<vector<int>>& guards, vector<vector<int>>& walls) {
        vector<vector<int>> matrix(m, vector<int>(n));
        int size = guards.size(), cnt = walls.size();
        for(int i = 0; i < cnt; i++) {
            matrix[walls[i][0]][walls[i][1]] = 2;
        }
        for(int i = 0; i < size; i++) {
            matrix[guards[i][0]][guards[i][1]] = 3;
        }
        cnt += size;
        for(int i = 0; i < size; i++) {
            int x = guards[i][0], y = guards[i][1], tmpx, tmpy;
            for(int j = 0; j < 4; j++) {
                int newx = x + X[j], newy = y + Y[j];
                while(newx >= 0 && newx < m && newy >= 0 && newy < n) {
                    if(matrix[newx][newy] == 0) {
                        matrix[newx][newy] = 1;
                        cnt++;
                    } else if(matrix[newx][newy] != 1) break;
                    newx += X[j];
                    newy += Y[j];
                }
            }
        }
        return m * n - cnt;
    }
};

好多了，看来还是跟 bfs 有点瓜葛的...😑

2258. Escape the Spreading Fire

Analysis

题目略长，读完之后，感觉像是第 3 题的加强版...
也可以认为是走迷宫的加强版，知道是跟 bfs 相关的题，无奈，没什么思路...

Code

读了一下大佬们的思路，记录一下。
首先要注意到题目要求的是初始位置可以停留的最多分钟数，所以在枚举时间的时候，需要找到一个合适的方式来枚举。
另外，题目说明了什么样的情况算是安全到达了——在火蔓延到之前到达安全屋。那么也就是说，人在某个时刻 t 开始逃生，只要能在火势蔓延之前到达安全屋即可。

但是要注意人逃生与火势蔓延的差别，人是在 t 时刻之后才开始逃生（开始动），火是从 0 时刻就开始蔓延了。
也就是说，需要先用 bfs 让火势蔓延 t 时刻，然后再用 bfs 得出人逃生的路径的同时让火势继续蔓延，比对二者之间到达相同格子的时刻。

如果人在中途与火相遇了，那肯定就无法逃生了，但人若是与火同时到达安全屋，那也是可以逃生的。

再回头想想如何枚举时间比较合理，按照 $O(n)$ 的时间来枚举肯定不太行，比它更短的时间就是 $O(logn)$ 了，想到这里，脑子里自然就会浮现二分的影子。

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
class Solution {
    const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
public:
    bool check(vector<vector<int>>& grid, int t) {
        int m = grid.size(), n = grid[0].size();
        bool fire[m][n]; memset(fire, 0, sizeof(fire));
        vector<pair<int, int>> f, q;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 1) {
                    fire[i][j] = true;
                    f.emplace_back(i, j);
                }
            }
        }
        auto separate_fire = [&] () {
            vector<pair<int, int>> nf;
            for(auto &[i, j]: f) {
                for(auto [dx, dy]: dirs) {
                    int x = i + dx, y = j + dy;
                    if(0 <= x && x < m && 0 <= y && y < n && !fire[x][y] && grid[x][y] != 2) {
                        fire[x][y] = true;
                        nf.emplace_back(x, y);
                    }
                }
            }
            f = move(nf);
        };
        while(t-- && !f.empty()) separate_fire();
        if(fire[0][0]) return false;
        bool vis[m][n]; memset(vis, 0, sizeof(vis));
        vis[0][0] = true;
        q.emplace_back(0, 0);
        while(!q.empty()) {
            vector<pair<int, int>> nq;
            for(auto &[i, j]: q) {
                if(!fire[i][j]) {
                    for(auto [dx, dy]: dirs) {
                        int x = i + dx, y = j + dy;
                        if(0 <= x && x < m && 0 <= y && y < n && !fire[x][y] && !vis[x][y] && grid[x][y] != 2) {
                            if(x == m - 1 && y == n - 1) return true;
                            vis[x][y] = true;
                            nq.emplace_back(x, y);
                        }
                    }
                }
            }
            q = move(nq);
            separate_fire();
        }
        return false;
    }
    int maximumMinutes(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int left = -1, right = m * n;
        while(left < right) {
            int mid = (left + right + 1) / 2;
            if(check(grid, mid)) left = mid;
            else right = mid - 1;
        }
        return left < m * n ? left : 1e9;
    }
};

姑且算是搞清楚了大致的求解过程。不过很显然，对于图的内容早忘完了的我，现在琢磨这个问题有点浪费时间了，暂时先放着。

Summary

额，这次周赛之后，从做一个题签个到，变成了做二个题，再签到了，哈哈🤣。
回过头来看，第三个题其实已经想到了做法了，只是在如何优化时间上没有经验啊。直接原因是忽略了一些细节，根本原因还是不熟练。仔细想想，第 3 题跟第 4 题好像是递进关系的题目，第 4 题好像是第 3 题的加强版一样，都是 bfs。

Buy me a coffee ? :)
0%