Leetcode_14 天算法入门_day7

Posted on | Edited on | In ,
| 7k | 58 mins.

滑动窗口还没练够啊，就到 DFS 了...14 天显然不够用。

废话少说，一道简单题，一道中等题。

733. Flood Fill

Analysis

这个题是个很明显的搜索题，思考了一下 dfs 的做法，没想出来...然后就从 bfs 的角度来做，做出来了，就是代码写的比较乱...

Code

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
class Solution {
public:
    bool isvisited[55][55] = {false};
    int X[4] = {-1, 1, 0, 0};
    int Y[4] = {0, 0, 1, -1};
    struct Node {
        int x, y;
    } node;
    bool isvalid(vector<vector<int>>& image, int x, int y, int m, int n, int value) {
        if(x < 0 || x >= m || y < 0 || y >= n) return false;
        if(isvisited[x][y]) return false;
        if(image[x][y] != value) return false;
        return true;
    }
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        int m = image.size(), n = image[0].size(), value = image[sr][sc];
        node.x = sr, node.y = sc;
        queue<Node> q;
        q.push(node);
        isvisited[node.x][node.y] = true;
        while(!q.empty()) {
            Node tmp = q.front();
            q.pop();
            for(int i = 0; i < 4; i++) {
                int x = tmp.x + X[i];
                int y = tmp.y + Y[i];
                if(isvalid(image, x, y, m, n, value)) {
                    node.x = x;
                    node.y = y;
                    isvisited[x][y] = true;
                    image[x][y] = newColor;
                    q.push(node);
                }
            }
        }
        image[sr][sc] = newColor;
        return image;
    }
};

好吧，来简化一下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        if(newColor == image[sr][sc]) return image;
        int X[4] = {1, -1, 0, 0};
        int Y[4] = {0, 0, 1, -1};
        int m = image.size(), n = image[0].size(), value = image[sr][sc];
        queue<pair<int, int>> q;
        q.emplace(sr, sc);
        image[sr][sc] = newColor;
        while(!q.empty()) {
            int x = q.front().first, y = q.front().second;
            q.pop();
            for(int i = 0; i < 4; i++) {
                int newX = x + X[i], newY = y + Y[i];
                if(newX >= 0 && newX < m && newY >= 0 && newY < n && image[newX][newY] == value) {
                    q.emplace(newX, newY);
                    image[newX][newY] = newColor;
                }
            }
        }
        return image;
    }
};

需要注意的是，上面的这段 bfs 代码并没有对点是否入队进行判断，所以当 newColor 与 image[sr][sc] 相等的时候，会陷入死循环。但是按照这个题目的条件，如果二者相等了，就可以直接返回了。为什么能直接返回？因为当源点上下左右四个相邻点的值与源点值相等时，那么也一定与 newColor 相等了。

dfs

为什么总觉得 dfs 的递归很怪呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int X[4] = {1, -1, 0, 0};
    int Y[4] = {0, 0, 1, -1};
    void dfs(vector<vector<int>>& image, int x, int y, int color, int newColor) {
        if(image[x][y] == color) {
            image[x][y] = newColor;
            for(int i = 0; i < 4; i++) {
                int newX = x + X[i], newY = y + Y[i];
                if(newX >= 0 && newX < image.size() && newY >= 0 && newY < image[0].size()) {
                    dfs(image, newX, newY, color, newColor);
                }
            }
        }
    }
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        int curColor = image[sr][sc];
        if(curColor != newColor) dfs(image, sr, sc, curColor, newColor);
        return image;
    }
};

695. 岛屿的最大面积

Analysis

这个题实质上就是在找由相邻的 1 组成的最大块...
换句话讲，这个题其实也就是在找图的极大连通子图，并返回最大结点数。

Code

bfs

感觉对 bfs 的熟悉程度要深一点，dfs 总是摸不清楚递归边界，不知道把递归边界写在哪里，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
/* bfs */
class Solution {
public:
    bool inq[55][55] = {false};
    int X[4] = {1, -1, 0, 0};
    int Y[4] = {0, 0, 1, -1};
    int bfs(vector<vector<int>>& grid, int sr, int sc, int m, int n) {
        int count = 0;
        queue<pair<int, int>> q;
        q.emplace(sr, sc);
        while(!q.empty()) {
            int x = q.front().first, y = q.front().second;
            q.pop();
            inq[x][y] = true;
            count++;
            for(int i = 0; i < 4; i++) {
                int newX = x + X[i], newY = y + Y[i];
                if(newX < m && newX >= 0 && newY < n && newY >= 0 && grid[newX][newY] && !inq[newX][newY]) {
                    inq[newX][newY] = true;
                    q.emplace(newX, newY);
                }
            }
        }
        return count;
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size(), ans = 0;
        for(int x = 0; x < m; x++) {
            for(int y = 0; y < n; y++) {
                if(grid[x][y] && !inq[x][y]) {
                    int tmp = bfs(grid, x, y, m, n);
                    ans = tmp > ans ? tmp : ans;
                }
            }
        }
        return ans;
    }
};

bfs 内的 if 的条件，一定要先判断是否越界，不然会 rumtime error（也就是越界），这其实是个不算 bug 的 bug😂，不过还是让我琢磨了快 20 分钟。

dfs

还是写个判断点是否符合条件的函数吧，这样看着条理会清晰一点。

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
/* dfs */
class Solution {
public:
    bool inq[55][55] = {false};
    int X[4] = {1, -1, 0, 0};
    int Y[4] = {0, 0, 1, -1};
    bool isvalid(vector<vector<int>>& grid, int x, int y) {
        if(x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size()) return false;
        if(inq[x][y] || grid[x][y] == 0) return false;
        return true;
    }
    int dfs(vector<vector<int>>& grid, int x, int y) {
        if(!isvalid(grid, x, y)) return 0;
        inq[x][y] = true;
        int count = 1;
        for(int i = 0; i < 4; i++) {
            int newX = x + X[i], newY = y + Y[i];
            count += dfs(grid, newX, newY);
        }
        return count;
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size(), ans = 0;
        for(int x = 0; x < m; x++) {
            for(int y = 0; y < n; y++) {
                if(grid[x][y] && !inq[x][y]) {
                    int tmp = dfs(grid, x, y);
                    ans = tmp > ans ? tmp : ans;
                }
            }
        }
        return ans;
    }
};

用不好 dfs 的原因，应该是对递归边界的理解很迷。

Summary

今天的两道题应该算是很常规的 dfs、bfs 入门题型了，感觉这部分内容已经跟图沾上边了。尽管代码一般都比较长，但是感觉还是滑动窗口、DP 之类的题目更难理解一点，这些反而比较易于理解，也可能是还没碰到难题吧。

Buy me a coffee ? :)
0%