仰望星空

位我上者，灿烂星空；道德律令，在我心中。

0%

DFS算法

发表于 更新于 分类于 ，
本文字数： 6.9k 阅读时长 ≈ 6 分钟

【道德经·第十五章】豫兮其若冬涉川，犹兮其若畏四邻，俨兮其若容，涣兮若冰之将释，敦兮其若朴，旷兮其若谷，混兮其若浊。孰能浊以静之徐清？孰能安以久动之徐生？

200. 岛屿数量

给你一个由 ‘1’（陆地）和 ‘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
int numIslands(vector<vector<char>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    
    int res = 0;
    for(int i = 0; i < m; ++i) {
        for(int j = 0; j < n; ++j) {
            if(grid[i][j] == '1') {
                dfs(grid, i, j);
                res++;
            }
        }
    }
    
    return res;
}

void dfs(vector<vector<char>>& grid, int r, int c) {
    int m = grid.size();
    int n = grid[0].size();
    
    grid[r][c] = '0';
    
    if(r-1> 0 && grid[r-1][c]=='1') 
        dfs(grid, r-1, c);
    if(r+1<m && grid[r+1][c]=='1')
        dfs(grid, r+1, c);
    if(c-1>=0 && grid[r][c-1]=='1')
        dfs(grid, r, c-1);
    if(c+1<n && grid[r][c+1]=='1')
        dfs(grid, r, c+1);
}

463. 岛屿周长

计算岛屿的周长。

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
int islandPerimeter(vector<vector<int>>& grid) {
    if(grid.size()==0 || grid[0].size()==0)
        return 0;

    int n = grid.size();
    int m = grid[0].size();

    int ans = 0;
    for(int i = 0; i <n; i++) {
        for(int j = 0; j < m; j++) {
            if(grid[i][j] == 1) 
                ans = dfs(grid, n, m, i, j);
        }
    }

    return ans;
}

int dfs(vector<vector<int> >& grid, int n, int m, int i, int j) {
    if(i<0 || i>=n || j<0 || j>=m)
        return 1;
    
    if(grid[i][j] == 0) 
        return 1;

    if(grid[i][j] != 1)
        return 0;

    grid[i][j] = 2;

    return dfs(grid, n, m, i+1, j) + dfs(grid, n, m, i, j+1) +
        dfs(grid, n, m, i-1, j) + dfs(grid, n, m, i, j-1);
}

695. 岛屿的最大面积

计算并返回 grid 中最大的岛屿面积。

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
int maxAreaOfIsland(vector<vector<int>>& grid) {
    int h = grid.size();
    // if(h == 0) return 0;
    
    int w = grid[0].size();
    
    int res = 0;
    for(int i = 0; i < h; ++i) {
        for(int j = 0; j < w; ++j) {
            res = max(res, area(grid, j, i, w, h));
        }
    }
    
    return res;
}

int area(vector<vector<int>>& grid, int x, int y, int w, int h) {
    if(x < 0 || y < 0 || x >= w || y >= h || grid[y][x] == 0)
        return 0;
    
    grid[y][x] = 0;
    
    return area(grid, x-1, y, w, h) + area(grid, x+1, y, w, h) + area(grid, x, y-1, w, h)
        + area(grid, x, y+1, w, h) + 1;   
}

785. 判断二分图

如果图是二分图，返回 true ；否则，返回 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
bool isBipartite(vector<vector<int>>& graph) {
    int n = graph.size();
    
    vector<int> colors(n, -1);
    for(int i = 0; i < n; i++) {
        if(colors[i] == -1) {
            if(!dfs(graph, colors, i, 0)) {
                return false;
            }
        }
    }
    
    return true;
}

bool dfs(vector<vector<int> >& graph, vector<int>& colors, int i, int color) {
    if(colors[i] >= 0) {
        return colors[i]==color;
    }
    
    colors[i] = color;
    for(int neighbor : graph[i]) {
        if(!dfs(graph, colors, neighbor, 1-color)) {
            return false;
        }
    }
    
    return true;
}

431. 找无向图的连通块

找出无向图中所有的连通块。

1、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
unordered_set<UndirectedGraphNode*> vis;
vector<vector<int>> connectedSet(vector<UndirectedGraphNode*> nodes) {
    // write your code here
    vector<vector<int> > res;

    for(int i = 0; i < nodes.size(); i++) {
        if(!vis.count(nodes[i])) {
            vector<int> cur;
            dfs(nodes[i], cur);
            sort(cur.begin(), cur.end());
            res.push_back(cur);
        }
    }

    return res;
}

void dfs(UndirectedGraphNode* node, vector<int>& cur) {
    vis.insert(node);
    cur.push_back(node->label);
    for(int i = 0; i < node->neighbors.size(); i++) {
        if(vis.count(node->neighbors[i])) continue;
        dfs(node->neighbors[i], cur);
    }      
}

2、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
unordered_set<UndirectedGraphNode*> vis;
vector<vector<int>> connectedSet(vector<UndirectedGraphNode*> nodes) {
    // write your code here
    vector<vector<int> > res;

    for(int i = 0; i < nodes.size(); i++) {
        if(!vis.count(nodes[i])) {
            vector<int> cur;
            // dfs(nodes[i], cur);
            bfs(nodes[i], cur);
            sort(cur.begin(), cur.end());
            res.push_back(cur);
        }
    }

    return res;
}

void bfs(UndirectedGraphNode* node, vector<int>& cur) {
    queue<UndirectedGraphNode*> q;
    vis.insert(node);
    q.push(node);
    cur.push_back(node->label);

    while(!q.empty()) {
        UndirectedGraphNode* tnode = q.front();
        q.pop();
        for(auto neighbor : tnode->neighbors) {
            if(vis.count(neighbor)) continue;
            q.push(neighbor);
            cur.push_back(neighbor->label);
            vis.insert(neighbor);
        }
    }
}

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

示例 1：

1
2
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

1
2
输入：n = 1
输出：["()"]

提示：

  • 1 <= n <= 8

实现代码（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
vector<string> generateParenthesis(int n) {
    // write code here
    vector<string> res;
    string cur;
    
    dfs(res, cur, n, n);
    return res;
}

void dfs(vector<string>& res, string& cur, int left, int right) {
    if(left<0 || right<0) return;
    
    if(right < left) return;
    
    if(left==0 && right==0) {
        res.push_back(cur);
        return;
    }
    
    cur.push_back('(');
    dfs(res, cur, left-1, right);
    cur.pop_back();
    
    cur.push_back(')');
    dfs(res, cur, left, right-1);
    cur.pop_back();
}

329. 矩阵中的最长递增路径

给定一个mxn整数矩阵matrix ，找出其中最长递增路径的长度。

示例 1：

1
2
3
输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4 
解释：最长递增路径为 [1, 2, 6, 9]。

示例 2：

1
2
3
输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出：4 
解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

代码：

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
int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int n = 0, m = 0;
int dfs(vector<vector<int> >& matrix, vector<vector<int> >& dp, int i, int j) {
    if(dp[i][j] != 0) return dp[i][j];

    dp[i][j]++;
    for(int k = 0; k < 4; k++) {
        int nexti = i+dirs[k][0];
        int nextj = j+dirs[k][1];

        if(nexti>=0 && nexti<n && nextj>=0 && nextj<m && matrix[i][j]<matrix[nexti][nextj]) {
            dp[i][j] = max(dp[i][j], dfs(matrix, dp, nexti, nextj)+1);
        }
    }

    return dp[i][j];
}

int longestIncreasingPath(vector<vector<int>>& matrix) {
    if(matrix.size()==0 || matrix[0].size()==0) 
        return 0;

    int res = 0;

    n = matrix.size();
    m = matrix[0].size();

    vector<vector<int> > dp(n, vector<int>(m, 0));
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            res = max(res, dfs(matrix, dp, i, j));
        }
    }

    return res;
}

不同路径的数目(一)

一个机器人在m×n大小的地图的左上角（起点）。机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。可以有多少种不同的路径从起点走到终点？

示例1

1
2
输入：2,1
返回值：1

示例2

1
2
输入：2,2
返回值：2

动态规划解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int uniquePaths(int m, int n) {
    // write code here
    vector<vector<int> > dp(m, vector<int>(n, 0));
    for(int i = 0; i < m; i++)
        dp[i][0] = 1;
    for(int i = 0; i < n; i++)
        dp[0][i] = 1;
    
    for(int i = 1; i < m; i++) {
        for(int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    
    return dp[m-1][n-1];
}

dfs+备忘录

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int dfs(int m, int n, vector<vector<int> >& memo, int x, int y) {
    if(x==m-1 || y==n-1) {
        return 1;
    }
    
    if(memo[x][y]) return memo[x][y];
    memo[x][y] = dfs(m, n, memo, x+1, y) + dfs(m, n, memo, x, y+1);
    return memo[x][y];
}

int uniquePaths(int m, int n) {
    // write code here
    vector<vector<int> > memo(m, vector<int>(n, 0));
    return dfs(m, n, memo, 0, 0);
    
}

位我上者，灿烂星空；道德律令，在我心中。