力扣大厂热门面试算法题 - 矩阵

         解数独，单词搜索，被围绕的区域。每题做详细思路梳理，配套Python&Java双语代码， 2024.03.07 可通过leetcode所有测试用例。

目录

37. 解数独

解题思路

完整代码

Python

Java 

79. 单词搜索

解题思路

完整代码

Python

Java 

130. 被围绕的区域

解题思路

完整代码

Python

Java 

---

37. 解数独

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1：

输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

解题思路

        解决数独问题通常可以使用回溯算法，这是一种深度优先搜索的策略，用于尝试填充数独的每个空格，直到找到有效解为止。算法的基本思想是：

1. 从数独的第一个空格开始。
2. 尝试在当前空格中填入1到9之间的任何一个数字。
3. 检查当前填入的数字是否满足数独的规则（即该数字在当前行、列、以及3x3的宫内没有重复）。
4. 如果当前数字有效，则递归地继续填写下一个空格。如果遇到某个空格没有有效数字可以填入，则回溯到上一个空格，更换上一个空格的数字，再次尝试。
5. 重复上述过程，直到所有的空格都被正确填满，解决数独问题。

完整代码

Python

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
 
        def isValid(row, col, ch):
            for i in range(9):
                if board[i][col] == ch or board[row][i] == ch:  # 检查行和列
                    return False
                if board[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == ch:  # 检查3x3的宫
                    return False
            return True
 
        def backtrack(board):
            for i in range(9):
                for j in range(9):
                    if board[i][j] != '.':  # 跳过非空格
                        continue
                    for k in range(1, 10):
                        if isValid(i, j, str(k)):
                            board[i][j] = str(k)  # 做选择
                            if backtrack(board):  # 如果找到一种解决方案
                                return True
                            board[i][j] = '.'  # 撤销选择
                    return False  # 试遍了1-9都不行，返回False
            return True  # 遍历完没有返回False，说明找到了解决方案
 
        backtrack(board)

Java 

class Solution {
    public void solveSudoku(char[][] board) {
        solve(board);
    }
 
    private boolean solve(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] != '.') continue;
                for (char c = '1'; c <= '9'; c++) {  // 尝试1到9
                    if (isValid(board, i, j, c)) {
                        board[i][j] = c;  // 做选择
                        if (solve(board)) return true;  // 如果找到一种解决方案
                        board[i][j] = '.';  // 撤销选择
                    }
                }
                return false;  // 试遍1-9都不行，返回false
            }
        }
        return true;  // 找到解决方案
    }
 
    private boolean isValid(char[][] board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == c) return false;  // 检查列
            if (board[row][i] == c) return false;  // 检查行
            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false;  // 检查3x3宫
        }
        return true;
    }
}

79. 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

示例 3：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

提示：

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board 和 word 仅由大小写英文字母组成

进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

解题思路

        这个问题可以通过深度优先搜索(DFS)和回溯算法来解决。算法的基本思想是遍历二维网格的每一个格子，从每个格子开始，尝试所有可能的路径去匹配给定的单词。如果某条路径上的字符序列与单词匹配，则说明单词存在于网格中。为了确保同一个单元格内的字母不被重复使用，我们需要记录已经访问过的单元格位置，并在递归调用后撤销该记录（回溯）。搜索剪枝的技术可以用于优化解决方案，比如当当前路径上的字符序列与单词不匹配时，提前结束当前路径的搜索。

1. 遍历二维网格的每个格子。
2. 从当前格子开始，使用深度优先搜索遍历相邻的格子。
3. 检查当前路径上的字符序列是否与单词匹配。
   • 如果当前字符与单词中对应的字符不匹配，回溯。
   • 如果路径上的所有字符都匹配且路径长度等于单词长度，返回 true。
4. 如果遍历了所有可能的路径都没有找到匹配的单词，返回 false。

完整代码

Python

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not board:
            return False
 
        # 深度优先搜索函数
        def dfs(board, i, j, word, index):
            # 判断当前位置是否越界或者字符是否不匹配
            if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[index]:
                return False
            # 如果当前字符是单词的最后一个字符，则找到匹配的路径
            if index == len(word) - 1:
                return True
 
            # 暂时标记当前单元格，防止重复访问
            temp, board[i][j] = board[i][j], '#'
            # 搜索四个方向
            found = dfs(board, i + 1, j, word, index + 1) or \
                    dfs(board, i - 1, j, word, index + 1) or \
                    dfs(board, i, j + 1, word, index + 1) or \
                    dfs(board, i, j - 1, word, index + 1)
            # 回溯，恢复单元格的原始值
            board[i][j] = temp
            return found
 
        # 遍历整个网格
        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(board, i, j, word, 0):  # 从每个单元格开始尝试搜索
                    return True
        return False

Java 

public class Solution {
    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(board, i, j, word, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
 
    private boolean dfs(char[][] board, int x, int y, String word, int index) {
        if (index == word.length()) {
            return true;
        }
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] != word.charAt(index)) {
            return false;
        }
        char temp = board[x][y];
        board[x][y] = '/';  // 标记当前格子为已访问
        boolean found = dfs(board, x + 1, y, word, index + 1) || dfs(board, x - 1, y, word, index + 1) ||
                        dfs(board, x, y + 1, word, index + 1) || dfs(board, x, y - 1, word, index + 1);
        board[x][y] = temp;  // 回溯，撤销标记
        return found;
    }
}

130. 被围绕的区域

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例 1：

输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

示例 2：

输入：board = [["X"]]
输出：[["X"]]

提示：

• m == board.length
• n == board[i].length
• 1 <= m, n <= 200
• board[i][j] 为 'X' 或 'O'

解题思路

        从矩阵的边界开始，找到所有的'O'字符，并通过深度优先搜索（DFS）标记所有与这些边界'O'相连的内部'O'字符。这样，未被标记的'O'即为被'X'完全包围的区域，随后将它们填充为'X'。

1. 边界探索：

   • 首先，从矩阵的边界出发，找到所有位于边界上的 'O'。
   • 对于每个边界上的 'O'，使用深度优先搜索（DFS）或广度优先搜索（BFS）来探索与之相连的所有 'O'（即在水平或垂直方向上相邻的 'O'）。
   • 在探索过程中，将这些与边界上的 'O' 相连的 'O' 暂时标记为另一个字符（比如 'T'），以表示这些 'O' 不应该被填充为 'X'，因为它们不是完全被 'X' 围绕的。

2. 填充内部 'O'：

   • 遍历整个矩阵，将所有未标记的 'O'（即那些被 'X' 完全围绕的 'O'）替换为 'X'。

3. 恢复标记：

   • 再次遍历矩阵，将步骤1中暂时标记为 'T' 的所有单元格恢复为 'O'。

通过以上步骤，所有被 'X' 完全围绕的 'O' 都会被填充为 'X'，而与边界相连的 'O' 保持不变。

完整代码

Python

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        if not board or not board[0]:
            return
 
        rows, cols = len(board), len(board[0])
 
        def dfs(i, j):
            if 0 <= i < rows and 0 <= j < cols and board[i][j] == 'O':
                board[i][j] = 'M'
                dfs(i + 1, j)
                dfs(i - 1, j)
                dfs(i, j + 1)
                dfs(i, j - 1)
 
        for i in range(rows):
            dfs(i, 0)
            dfs(i, cols - 1)
 
        for j in range(cols):
            dfs(0, j)
            dfs(rows - 1, j)
 
        for i in range(rows):
            for j in range(cols):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == 'M':
                    board[i][j] = 'O'

Java 

public class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) return;
 
        int rows = board.length, cols = board[0].length;
 
        for (int i = 0; i < rows; i++) {
            dfs(board, i, 0);
            dfs(board, i, cols - 1);
        }
 
        for (int j = 0; j < cols; j++) {
            dfs(board, 0, j);
            dfs(board, rows - 1, j);
        }
 
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                else if (board[i][j] == 'M') board[i][j] = 'O';
            }
        }
    }
 
    private void dfs(char[][] board, int i, int j) {
        int rows = board.length, cols = board[0].length;
        if (i < 0 || i >= rows || j < 0 || j >= cols || board[i][j] != 'O') return;
 
        board[i][j] = 'M';
        dfs(board, i + 1, j);
        dfs(board, i - 1, j);
        dfs(board, i, j + 1);
        dfs(board, i, j - 1);
    }
}