Leetcode_14 天算法入门_day9

Posted on | Edited on | In ,
| 5.8k | 48 mins.

今天好像还真的给图？

542. 01 Matrix

Analysis

看到这个题，很容易想到的思路就是 bfs，每个点逐一使用 bfs 然后返回离这个点最近的 0 的层数就好了。

Code

bfs

尝试用 bfs 写了一下，结果超时了，应该是因为每个点逐一使用 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/* bfs, these codes will cause time limited exceeded. */
class Solution {
public:
    int X[4] = {1, -1, 0, 0};
    int Y[4] = {0, 0, 1, -1};
    bool isvalid(vector<vector<int>>& mat, int x, int y) {
        if(x < 0 || x >= mat.size() || y < 0 || y >= mat[0].size()) return false;
        return true; 
    }
    int bfs(vector<vector<int>>& mat, int sr, int sc) {
        set<pair<int, int>> ht;
        int level = 0;
        if(mat[sr][sc] == 0) return level;
        queue<pair<int, int>> q;
        q.emplace(sr, sc);
        ht.insert(make_pair(sr, sc));
        while(!q.empty()) {
            int size = q.size();
            level++;
            for(int i = 0; i < size; i++) {
                int x = q.front().first, y = q.front().second;
                q.pop();
                for(int j = 0; j < 4; j++) {
                    int newx = x + X[j], newy = y + Y[j];
                    if(isvalid(mat, newx, newy) && ht.find(make_pair(newx, newy)) == ht.end()) {
                        if(mat[newx][newy] == 0) return level;
                        q.emplace(newx, newy);
                        ht.insert(make_pair(newx, newy));
                    }
                }
            }
        }
        return -1;
    }
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        vector<vector<int>> ret = mat;
        int m = mat.size(), n = mat[0].size();
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                ret[i][j] = bfs(mat, i, j);
            }
        }
        return ret;
    }
};

回头想想，上面代码在做什么事情？将每一个点到 0 的距离求出来，换而言之，就是在求单源最短路径。
按照这样的思路，单源超时了，不妨在试试多源的思路。
假设所有的 0 到一个超级 0 点的距离是 1，这样矩阵中非 0 点的到 0 点的距离就是其到达超级 0 点的距离减一。这样在 bfs 开始的第一步，将所有的 0 点入队，这样就可以找到所有与 0 点距离为 1 的非 0 点，然后再根据这些点找到距离为 2 的非 0 点，依次执行就可以得到最终的结果了。

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
/* bfs: version 2 */
class Solution {
private:
    static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> dist(m, vector<int>(n));
        vector<vector<int>> inq(m, vector<int>(n));
        queue<pair<int, int>> q;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(mat[i][j] == 0) {
                    q.emplace(i, j);
                    inq[i][j] = 1;
                }
            }
        }
        while(!q.empty()) {
            int x = q.front().first, y = q.front().second;
            q.pop();
            for(int d = 0; d < 4; d++) {
                int newx = x + dirs[d][0], newy = y + dirs[d][1];
                if(newx >= 0 && newx < m && newy >= 0 && newy < n && !inq[newx][newy]) {
                    dist[newx][newy] = dist[x][y] + 1;
                    q.emplace(newx, newy);
                    inq[newx][newy] = 1;
                }
            }
        }
        return dist;
    }
};

按照多源最短路的思路就可以很好的解决这道题了，inq 这个数组是用来标记是否入过队。
实际上这个题，还可以从 dp 的角度思考，等做了 dp 的简单题后再回头来看。

994. Rotting Oranges

Analysis

这个题跟上面的题是一样的思路，所以偷一下懒，直接用上面写好的代码。不过，有些地方要改成满足这道题的条件。
首先，按照这个题的过程，只需要访问为 1 或者 2 的结点，为 0 的结点不需要访问。再者，由于一开始需要将所有烂橘子入队，此时可以同时算出好橘子的总数 cnt，这样在腐烂的过程中，可以依次减去腐烂的橘子个数。bfs 结束后，就可以用 cnt 来判断是否所有的橘子都腐烂了，这样就不用再重新遍历 grid 与 dist 是否全部橘子都腐烂了。

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
class Solution {
private:
    static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public:
    int dist[10][10];
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        memset(dist, -1, sizeof(dist));
        vector<vector<int>> inq(m, vector<int>(n));
        queue<pair<int, int>> q;
        int cnt = 0, ans = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] == 2) {
                    q.emplace(i, j);
                    dist[i][j] = 0;
                    inq[i][j] = 1;
                } else if(grid[i][j] == 1) cnt++;
            }
        }
        while(!q.empty()) {
            int x = q.front().first, y = q.front().second;
            q.pop();
            for(int d = 0; d < 4; d++) {
                int newx = x + dirs[d][0], newy = y + dirs[d][1];
                if(newx >= 0 && newx < m && newy >= 0 && newy < n && !inq[newx][newy] && grid[newx][newy]) {
                    dist[newx][newy] = dist[x][y] + 1;
                    q.emplace(newx, newy);
                    inq[newx][newy] = 1;
                    if(grid[newx][newy] == 1) {
                        cnt--;
                        ans = dist[newx][newy];
                        if(cnt == 0) break;
                    }
                }
            }
        }
        return cnt ? -1 : ans;
    }
};

Summary

今天做的两道题本质上是最短路的问题，这类问题的难点在于理解题目的条件，只要能理解题目，就是一道简单题，但是代码量一般都比较长。所以，还是需要多做才能熟练。不得不再说一句，不了解树和图的知识，做这种题的效果就不是很好...

Buy me a coffee ? :)
0%