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

��        解数独，单词搜索，被围绕的区域。每题做详细思路梳理，配套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  
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