LeetCode刷题：图

关于图的几个必知必会的代码实现

图

• 实现有向图、无向图、有权图、无权图的邻接矩阵和邻接表表示方法

• 实现图的深度优先搜索、广度优先搜索

• 实现 Dijkstra 算法、A* 算法

• 实现拓扑排序的 Kahn 算法、DFS 算法

题目

Number of Islands（岛屿的个数）

思路

想到了深度优先搜素，先遍历找到是 1 的，岛屿数量加 1 ，然后递归的把周围的 1 都标记为已访问，代码如下

代码

public int numIslands(char[][] grid) {
    int island = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[i].length; j++) {
            //是陆地
            if (grid[i][j] == '1') {
                marked(grid, i ,j);
                island ++;
            }
        }
    }
    return island;
}

private void marked(char[][] grid, int i, int j) {
    if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') {
        return;
    }
    grid[i][j] = '2';
    //分别往 上 下 左 右 递归
    marked(grid, i + 1, j);
    marked(grid, i - 1, j);
    marked(grid, i, j - 1);
    marked(grid, i, j + 1);
}

Valid Sudoku（有效的数独）

思路

暴力法解决问题

代码

public boolean isValidSudoku(char[][] board) {
    for (int i = 0; i < board.length; i++) {
        int[] numMapCol = new int[9];
        int[] numMapRow = new int[9];
        for (int j = 0; j < board[i].length; j++) {
            if (board[i][j] != '.') {
                numMapRow[board[i][j] - '1']++;
                if (numMapRow[board[i][j] - '1'] > 1) {
                    return false;
                }
            }
            if (board[j][i] != '.') {
                numMapCol[board[j][i] - '1']++;
                if (numMapCol[board[j][i] - '1'] > 1) {
                    return false;
                }
            }
        }
    }
    for (int i = 1; i < 9; i += 3) {
        for (int j = 1; j < 9; j += 3) {
            int[] numMapRow = new int[9];
            if (board[i][j] != '.') {
                numMapRow[board[i][j] - '1']++;
                if (numMapRow[board[i][j] - '1'] > 1) {
                    return false;
                }
            }
            if (board[i + 1][j] != '.') {
                numMapRow[board[i + 1][j] - '1']++;
                if (numMapRow[board[i + 1][j] - '1'] > 1) {
                    return false;
                }
            }
            if (board[i - 1][j] != '.') {
                numMapRow[board[i - 1][j] - '1']++;
                if (numMapRow[board[i - 1][j] - '1'] > 1) {
                    return false;
                }
            }
            if (board[i][j - 1] != '.') {
                numMapRow[board[i][j - 1] - '1']++;
                if (numMapRow[board[i][j - 1] - '1'] > 1) {
                    return false;
                }
            }
            if (board[i][j + 1] != '.') {
                numMapRow[board[i][j + 1] - '1']++;
                if (numMapRow[board[i][j + 1] - '1'] > 1) {
                    return false;
                }
            }
            if (board[i - 1][j - 1] != '.') {
                numMapRow[board[i - 1][j - 1] - '1']++;
                if (numMapRow[board[i - 1][j - 1] - '1'] > 1) {
                    return false;
                }
            }
            if (board[i - 1][j + 1] != '.') {
                numMapRow[board[i - 1][j + 1] - '1']++;
                if (numMapRow[board[i - 1][j + 1] - '1'] > 1) {
                    return false;
                }
            }
            if (board[i + 1][j - 1] != '.') {
                numMapRow[board[i + 1][j - 1] - '1']++;
                if (numMapRow[board[i + 1][j - 1] - '1'] > 1) {
                    return false;
                }
            }
            if (board[i + 1][j + 1] != '.') {
                numMapRow[board[i + 1][j + 1] - '1']++;
                if (numMapRow[board[i + 1][j + 1] - '1'] > 1) {
                    return false;
                }
            }
        }
    }
    return true;
}

优化后的代码如下

public boolean isValidSudoku(char[][] board) {
    // 记录某行，某位数字是否已经被摆放
    boolean[][] row = new boolean[9][9];
    // 记录某列，某位数字是否已经被摆放
    boolean[][] col = new boolean[9][9];
    // 记录某 3x3 宫格内，某位数字是否已经被摆放
    boolean[][] block = new boolean[9][9];

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] != '.') {
                int num = board[i][j] - '1';
                int blockIndex = i / 3 * 3 + j / 3;
                if (row[i][num] || col[j][num] || block[blockIndex][num]) {
                    return false;
                } else {
                    row[i][num] = true;
                    col[j][num] = true;
                    block[blockIndex][num] = true;
                }
            }
        }
    }
    return true;
}