美文网首页
图 2019-04-20

图 2019-04-20

作者: 小爆爆就是我 | 来源:发表于2019-04-22 20:31 被阅读0次


    实现有向图、无向图、有权图、无权图的邻接矩阵和邻接表表示方法
    实现图的深度优先搜索、广度优先搜索
    实现 Dijkstra 算法、A* 算法
    实现拓扑排序的 Kahn 算法、DFS 算法
    对应的 练习题
    1Number of Islands(岛屿的个数)
    英文版:https://leetcode.com/problems/number-of-islands/description/
    中文版:https://leetcode-cn.com/problems/number-of-islands/description/

    采用DFS深度优先搜索算法,从一个顶点开始,对一个路劲进行深入搜索直到尽头,之后查询其他路径;搜索完全部路径之后检查有没有其他顶点需要进行搜索。

    class Solution {
    public:
        int numIslands(vector<vector<char>>& grid) {
            
            int m = grid.size();
            if(!m) return 0;
            int n = grid[0].size();
            int count = 2;
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (grid[i][j] == '1')
                    {
                        bl(grid, count, i, j, m, n);
                        count++;
                    }
                }
            }
            return count - 2;
        }
        void bl(vector<vector<char>>& grid, int count, int i, int j, int m, int n)
        {
            grid[i][j] = (char)('0' + count);
            if (j + 1 < n && grid[i][j + 1] == '1') bl(grid, count, i, j + 1, m, n);
            if (i + 1 < m && grid[i + 1][j] == '1') bl(grid, count, i + 1, j, m, n);
            if (j - 1 >= 0 && grid[i][j - 1] == '1') bl(grid, count, i, j - 1, m, n);
            if (i - 1 >= 0 && grid[i - 1][j] == '1') bl(grid, count, i - 1, j, m, n);
        }
    
    
    };
    

    2Valid Sudoku(有效的数独)
    英文版:https://leetcode.com/problems/valid-sudoku/
    中文版:https://leetcode-cn.com/problems/valid-sudoku/

    数独成九宫格排布,数字1~9在每行每列每个小九宫格均只会出现一次。

    class Solution {
    public:
        bool isValidSudoku(vector<vector<char>>& board) {
            const int cnt = 9;
            bool rowMap[cnt][cnt] = {false};        //行初始化
            bool colMap[cnt][cnt] = {false};        //列初始化
            bool smallBoardMask[cnt][cnt] = {false};//小九宫格初始化
            
            for(int i = 0; i < board.size(); ++i){  //行、列、小九都是9个,所以一个循环遍历
                for (int j = 0; j < board[i].size(); ++j){
                    if (board[i][j] == '.'){
                        continue;
                    }
                    int idx =  board[i][j] - '0' - 1;
                    
                    // 行
                    if (rowMap[i][idx] == true){
                        return false;
                    }
                    rowMap[i][idx] = true;
                    
                    // 列
                    if (colMap[j][idx] == true) {
                        return false;
                    }
                    colMap[j][idx] = true;
                    
                    // 小九宫格
                    int area = (i/3) * 3 + (j/3);
                    if (smallBoardMask[area][idx] == true) {
                        return false;
                    }
                    smallBoardMask[area][idx] = true;
                }
            }
            
            return true;
        }
            
    };
    

    相关文章

      网友评论

          本文标题:图 2019-04-20

          本文链接:https://www.haomeiwen.com/subject/grprgqtx.html