【综合算法学习】（第十三篇）

解数独（hard）

题目解析

讲解算法原理

编写代码

单词搜索（medium）

题目解析

解析算法原理

编写代码

解数独（hard）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

编写⼀个程序，通过填充空格来解决数独问题。
数独的解法需遵循如下规则：
数字1-9在每⼀⾏只能出现⼀次。
数字1-9在每⼀列只能出现⼀次。
数字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"]]
解释：输⼊的数独如上图所⽰，唯⼀有效的解决⽅案如下所⽰：

• 提⽰：
board.length==9
board[i].length==9
board[i][j]是⼀位数字或者'.'题⽬数据保证输⼊数独仅有⼀个解

讲解算法原理

解法：算法思路：

为了存储每个位置的元素，我们需要定义⼀个⼆维数组。⾸先，我们记录所有已知的数据，然后遍历所有需要处理的位置，并遍历数字1~9。对于每个位置，我们检查该数字是否可以存放在该位置，同时检查⾏、列和九宫格是否唯⼀。
我们可以使⽤⼀个⼆维数组来记录每个数字在每⼀⾏中是否出现，⼀个⼆维数组来记录每个数字在每⼀列中是否出现。对于九宫格，我们可以以⾏和列除以3得到的商作为九宫格的坐标，并使⽤⼀个三维数组来记录每个数字在每⼀个九宫格中是否出现。在检查是否存在冲突时，只需检查⾏、列和九宫格⾥对应的数字是否已被标记。如果数字⾄少有⼀个位置（⾏、列、九宫格）被标记，则存在冲突，因此不能在该位置放置当前数字。
• 特别地，在本题中，我们需要直接修改给出的数组，因此在找到⼀种可⾏的⽅法时，应该停⽌递
归，以防⽌正确的⽅法被覆盖。
初始化定义：
1. 定义⾏、列、九宫格标记数组以及找到可⾏⽅法的标记变量，将它们初始化为false。

2. 定义⼀个数组来存储每个需要处理的位置。
3. 将题⽬给出的所有元素的⾏、列以及九宫格坐标标记为true。4. 将所有需要处理的位置存⼊数组。
递归函数设计：voiddfs(vector<vector<char>>&board,intpos)参数：pos（当前需要处理的坐标）；
返回值：⽆；
函数作⽤：在当前坐标填⼊合适数字，查找数独答案。
递归流程如下：
1. 结束条件：已经处理完所有需要处理的元素。如果找到了可⾏的解决⽅案，则将标记变量更新为true并返回。
2. 获取当前需要处理的元素的⾏列值。
3. 遍历数字1~9。如果当前数字可以填⼊当前位置，并且标记变量未被赋值为true，则将当前位置的⾏、列以及九宫格坐标标记为true，将当前数字赋值给board数组中的相应位置元素，然后对下⼀个位置进⾏递归。
4. 递归结束时，撤回标记。

编写代码

c++算法代码：

class Solution
{bool row[9][10], col[9][10], grid[3][3][10];
public:void solveSudoku(vector<vector<char>>& board) {// 初始化for(int i = 0; i < 9; i++){for(int j = 0; j < 9; j++){if(board[i][j] != '.'){int num = board[i][j] - '0';row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;}}}dfs(board);}bool dfs(vector<vector<char>>& board){for(int i = 0; i < 9; i++){for(int j = 0; j < 9; j++){if(board[i][j] == '.'){// 填数for(int num = 1; num <= 9; num++){if(!row[i][num] && !col[j][num] && !grid[i / 3][j / 3]
[num]){board[i][j] = '0' + num;row[i][num] = col[j][num] = grid[i / 3][j / 3]
[num] = true;if(dfs(board) == true) return true; // 重点理解 // 恢复现场board[i][j] = '.';row[i][num] = col[j][num] = grid[i / 3][j / 3]
[num] = false;}}return false; // 重点理解}}}return true; // 重点理解}
};

java算法代码：

class Solution
{boolean[][] row, col;boolean[][][] grid;public void solveSudoku(char[][] board) {row = new boolean[9][10];col = new boolean[9][10];grid = new boolean[3][3][10];// 初始化for(int i = 0; i < 9; i++)for(int j = 0; j < 9; j++)if(board[i][j] != '.'){int num = board[i][j] - '0';row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;}dfs(board);}public boolean dfs(char[][] board){for(int i = 0; i < 9; i++){for(int j = 0; j < 9; j++){if(board[i][j] == '.'){// 填数for(int num = 1; num <= 9; num++){// 剪枝if(!row[i][num] && !col[j][num] && !grid[i / 3][j / 3]
[num]){board[i][j] = (char)('0' + num);row[i][num] = col[j][num] = grid[i / 3][j / 3]
[num] = true;if(dfs(board) == true) return true; // 重点理解 // 恢复现场board[i][j] = '.';row[i][num] = col[j][num] = grid[i / 3][j / 3]
[num] = false;}}return false; // 重点理解}}}return true; // 重点理解}
}

单词搜索（medium）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

给定⼀个mxn⼆维字符⽹格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仅由⼤⼩写英⽂字⺟组成

解析算法原理

解法：算法思路：

我们需要假设每个位置的元素作为第⼀个字⺟，然后向相邻的四个⽅向进⾏递归，并且不能出现重复使⽤同⼀个位置的元素。通过深度优先搜索的⽅式，不断地枚举相邻元素作为下⼀个字⺟出现的可能性，并在递归结束时回溯，直到枚举完所有可能性，得到正确的结果。
递归函数设计：booldfs(intx,inty,intstep,vector<vector<char>>&board,stringword,vector<vector<bool>>&vis,int&n,int&m,int&len)
参数：x（当前需要进⾏处理的元素横坐标），y（当前需要进⾏处理的元素横坐标），step（当前已经处理的元素个数），word（当前的字符串状态）；
返回值：当前坐标元素作为字符串中下标step的元素出现是否可以找到成⽴的字符串。

函数作⽤：判断当前坐标的元素作为字符串中下标step的元素出现时，向四个⽅向传递，查找是否存在路径结果与字符串相同。
递归函数流程：

1. 遍历每个位置，标记当前位置并将当前位置的字⺟作为⾸字⺟进⾏递归，并且在回溯时撤回标记。

2. 在每个递归的状态中，我们维护⼀个步数step，表⽰当前已经处理了⼏个字⺟。
◦ 若当前位置的字⺟与字符串中的第step个字⺟不相等，则返回false。◦ 若当前step的值与字符串⻓度相等，表⽰存在⼀种路径使得word成⽴，返回true。
3. 对当前位置的上下左右四个相邻位置进⾏递归，若递归结果为true，则返回true。

4. 若相邻的四个位置的递归结果都为false，则返回false。
• 特别地，如果使⽤将当前遍历到的字符赋值为空格，并在回溯时恢复为原来的字⺟的⽅法，则在递归时不会重复遍历当前元素，可达到不使⽤标记数组的⽬的。

编写代码

c++算法代码：

class Solution
{bool vis[7][7];int m, n;
public:bool exist(vector<vector<char>>& board, string word) {m = board.size(), n = board[0].size();for(int i = 0; i < m; i++)for(int j = 0; j < n; j++){if(board[i][j] == word[0]){vis[i][j] = true;if(dfs(board, i, j, word, 1)) return true;vis[i][j] = false;}}return false;}int dx[4] = {0, 0, -1, 1};int dy[4] = {1, -1, 0, 0};bool dfs(vector<vector<char>>& board, int i, int j, string& word, int pos){if(pos == word.size()) return true;// 向量的⽅式，定义上下左右四个位置for(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && board[x][y] 
== word[pos]){vis[x][y] = true;if(dfs(board, x, y, word, pos + 1)) return true;vis[x][y] = false;}}return false;}
};

java算法代码：

class Solution
{boolean[][] vis;int m, n;char[] word;public boolean exist(char[][] board, String _word) {m = board.length; n = board[0].length;word = _word.toCharArray();vis = new boolean[m][n];for(int i = 0; i < m; i++)for(int j = 0; j < n; j++){if(board[i][j] == word[0]){vis[i][j] = true;if(dfs(board, i, j, 1)) return true;vis[i][j] = false;}}return false;}int[] dx = {0, 0, 1, -1};int[] dy = {1, -1, 0, 0};public boolean dfs(char[][] board, int i, int j, int pos){if(pos == word.length){return true;}// 上下左右去匹配 word[pos]// 利⽤向量数组，⼀个 for 搞定上下左右四个⽅向for(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && board[x][y] 
== word[pos]){vis[x][y] = true;if(dfs(board, x, y, pos + 1)) return true;vis[x][y] = false;}}return false;}
}