365天挑战LeetCode1000题——Day 080 寻找重复的子树 岛屿的最大面积 统计子岛屿

652. 寻找重复的子树

代码实现（看题解）

class Solution {
public:
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        dfs(root);
        return {repeat.begin(), repeat.end()};
    }

    int dfs(TreeNode* node) {
        if (!node) {
            return 0;
        }
        auto tri = tuple{node->val, dfs(node->left), dfs(node->right)};
        if (auto it = seen.find(tri); it != seen.end()) {
            repeat.insert(it->second.first);
            return it->second.second;
        }
        else {
            seen[tri] = {node, ++idx};
            return idx;
        }
    }

private:
    static constexpr auto tri_hash = [fn = hash<int>()](const tuple<int, int, int>& o) -> size_t {
        auto&& [x, y, z] = o;
        return (fn(x) << 24) ^ (fn(y) << 8) ^ fn(z);
    };

    unordered_map<tuple<int, int, int>, pair<TreeNode*, int>, decltype(tri_hash)> seen{0, tri_hash};
    unordered_set<TreeNode*> repeat;
    int idx = 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

695. 岛屿的最大面积

代码实现

class Solution {
private:
    int m, n;
    int dfs(vector<vector<int>>& grid, int i, int j) {
        int ans = 1;
        grid[i][j] = 0;
        // 上
        if (i - 1 >= 0 && grid[i - 1][j] == 1) ans += dfs(grid, i - 1, j);
        // 下
        if (i + 1 < m && grid[i + 1][j] == 1) ans += dfs(grid, i + 1, j);
        // 左
        if (j - 1 >= 0 && grid[i][j - 1] == 1) ans += dfs(grid, i, j - 1);
        // 右
        if (j + 1 < n && grid[i][j + 1] == 1) ans += dfs(grid, i, j + 1);
        return ans;
    }
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    ans = max(ans, dfs(grid, i, j));
                }
            }
        }
        return ans;
    }
};
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

1905. 统计子岛屿

代码实现（自解）

class Solution {
private:
    int m, n;
    bool dfs(vector<vector<int>>& grid1, vector<vector<int>>& grid2, int i, int j) {
        bool ans = true;
        if (!grid1[i][j]) return false;
        grid2[i][j] = 0;
        // 上
        if (i - 1 >= 0 && grid2[i - 1][j] == 1) ans = dfs(grid1, grid2, i - 1, j) && ans;
        // 下
        if (i + 1 < m && grid2[i + 1][j] == 1) ans = dfs(grid1, grid2, i + 1, j) && ans;
        // 左
        if (j - 1 >= 0 && grid2[i][j - 1] == 1) ans = dfs(grid1, grid2, i, j - 1) && ans;
        // 右
        if (j + 1 < n && grid2[i][j + 1] == 1) ans = dfs(grid1, grid2, i, j + 1) && ans;
        return ans;
    }
public:
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        int ans = 0;
        m = grid2.size();
        n = grid2[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid2[i][j] == 1) {
                    ans += dfs(grid1, grid2, i, j);
                }
            }
        }
        return ans;
    }
};
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