LeetCode精选题之搜索（BFS/DFS/回溯法）
程序员文章站
2022-03-13 13:05:18
...
文章目录
- LeetCode精选题之搜索（BFS/DFS/回溯法）
- 第一部分：BFS
- 1 二进制矩阵中的最短路径--LeetCode1091(Medium)
- 2 完全平方数--LeetCode279(Medium)
- 3 单词接龙--LeetCode127(Medium)
- 第二部分：DFS
- 1 岛屿的最大面积--LeetCode695(Medium)
- 2 岛屿数量--LeetCode200(Medium)
- 3 朋友圈--LeetCode547(Medium)
- 4 被围绕的区域--LeetCode130(Medium)
- 5 太平洋大西洋水流问题--LeetCode417(Medium)
- 第三部分：回溯法
- 1 电话号码的字母组合--LeetCode17(Medium)
- 2 复原IP地址--LeetCode93(Medium)
- 3 单词搜索--LeetCode79(Medium)
- 4 二叉树的所有路径--LeetCode257(Easy)
- 5 全排列--LeetCode46(Medium)
- 6 全排列II--LeetCode47(Medium)
- 7 组合--LeetCode77(Medium)
- 8 组合求和--LeetCode39(Medium)
- 9 组合求和II--LeetCode40(Medium)
- 10 组合求和III--LeetCode216(Medium)
- 11 子集--LeetCode78(Medium)
- 12 子集II--LeetCode90(Medium)
- 13 分割回文串--LeetCode131(Medium)
- 14 N皇后--LeetCode51(Hard)
- 15 解数独--LeetCode37(Hard)
LeetCode精选题之搜索（BFS/DFS/回溯法）
参考资料：
1、CyC2018的LeetCode题解
2、liuyubobobo的LeetCode课程
3、labuladong的题解
4、解数独的官方题解以及vivi的评论
第一部分：BFS
总结：BFS即广度优先遍历，一层一层地进行遍历，每层遍历都是以上一层遍历的结果作为起点，遍历一个距离能访问到的所有节点。
每一层遍历的节点都与根节点距离相同。设 di表示第 i个节点与根节点的距离，推导出一个结论：对于先遍历的节点 i与后遍历的节点 j，有 di <= dj。利用这个结论，可以求解最短路径等 最优解 问题：第一次遍历到目的节点，其所经过的路径为最短路径。应该注意的是，使用 BFS 只能求解无权图的最短路径，无权图是指从一个节点到另一个节点的代价都记为 1。
具体实现时借助的工具是队列，用来存储每一轮遍历得到的节点，且每次是对同一层的节点同时进行处理，这样就很容易求路径最短的问题。需要注意的是，遍历过的节点不能再次被遍历。
1 二进制矩阵中的最短路径–LeetCode1091(Medium)
在一个 N × N 的方形网格中，每个单元格有两种状态：空（0）或者阻塞（1）。一条从左上角到右下角、长度为 k 的畅通路径，由满足下述条件的单元格 C_1, C_2, ..., C_k组成：
- 相邻单元格
C_i和C_{i+1}在八个方向之一上连通（此时，C_i和C_{i+1}不同且共享边或角） -
C_1位于(0, 0)（即，值为grid[0][0]） -
C_k位于(N-1, N-1)（即，值为grid[N-1][N-1]） - 如果
C_i位于(r, c)，则grid[r][c]为空（即，grid[r][c] == 0）
返回这条从左上角到右下角的最短畅通路径的长度。如果不存在这样的路径，返回 -1 。
提示：
1 <= grid.length == grid[0].length <= 100-
grid[i][j]为 0 或 1
代码如下：
class Solution {
public int shortestPathBinaryMatrix(int[][] grid) {
if (grid[0][0] != 0) {
return -1;
}
int n = grid.length;
Queue<int[]> queue = new LinkedList<>();
boolean[][] isVisited = new boolean[n][n];
int[][] distance = new int[n][n];
int[] dx = {-1,-1,-1, 0,0, 1,1,1};
int[] dy = {-1, 0, 1,-1,1,-1,0,1};//对应8个方向
queue.offer(new int[]{0,0});// 首先把(0,0)加入队列
isVisited[0][0] = true;// 并标记已访问
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int x = curr[0], y = curr[1];// 当前的位置
for (int i = 0; i < 8; i++) {
int newX = x + dx[i];
int newY = y + dy[i];// 新的位置
if (newX >= 0 && newX < n && newY >= 0 && newY < n
&& grid[newX][newY] != 1 && !isVisited[newX][newY]) {// 新的位置(newX, newY)满足要求才会进行更新
distance[newX][newY] = 1 + distance[x][y];
isVisited[newX][newY] = true;
queue.offer(new int[]{newX, newY});
}
}
}
if (n > 1 && distance[n-1][n-1] == 0) {
return -1;// 如果不存在通畅路径则返回-1
}
return distance[n-1][n-1]+1;
}
}
2 完全平方数–LeetCode279(Medium)
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1：
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
示例 2：
输入: n = 13
输出: 2
解释: 13 = 4 + 9.
图的BFS：根据题目较难联想到是图的BFS，下面的示意图来自bobo老师。表示每个数可以通过哪个数来到达0。
class Solution {
public int numSquares(int n) {
int step = 0;
boolean[] isVisited = new boolean[n+1];
Queue<Integer> queue = new LinkedList<>();
queue.offer(n);
isVisited[n] = true;
// 一层一层向外BFS
while (!queue.isEmpty()) {
int size = queue.size();
for (int k = 0; k < size; k++) {//对同一层的数同时处理
int curr = queue.poll();
if (curr == 0) {
return step;
}
int a = 0;
for (int i = 1; (a = curr - i*i) >= 0; i++) {
if (!isVisited[a]) {
queue.offer(a);
isVisited[a] = true;
}
}
}
step++;
}
return n;// 步长最大值是n，即每次减一
}
}
补充动态规划的解法：
class Solution {
public int numSquares(int n) {
int[] dp = new int[n+1];
for (int i = 1; i <= n; i++) {
dp[i] = i;// 这是最坏情况，全是由1相加而得
for (int j = 1; i - j*j >= 0; j++) {
dp[i] = Math.min(dp[i], dp[i - j*j]+1);
}
}
return dp[n];
}
}
3 单词接龙–LeetCode127(Medium)
给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
- 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典中的单词。
说明:
- 如果不存在这样的转换序列，返回 0。
- 所有单词具有相同的长度。
- 所有单词只由小写字母组成。
- 字典中不存在重复的单词。
- 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
输出: 5
解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
返回它的长度 5。
示例 2:
输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出: 0
解释: endWord "cog" 不在字典中，所以无法进行转换。
BFS：每一层向外扩展到可以到达的字符串，直到遇到endWord。“可以到达的字符串”是指在List中的字符串没有被访问过，且和当前字符串只相差一位字符。
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if (!wordList.contains(endWord)) {
return 0;
}
Queue<String> queue = new LinkedList<>();
boolean[] isVisited = new boolean[wordList.size()];//需要标记List中的元素是否访问过，不然会出现"hot" -> "dot" -> "hot"的循环
queue.offer(beginWord);
int step = 0;//走过的步数
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String curr = queue.poll();
if (curr.equals(endWord)) {
return step+1;
}
// 判断List中哪些和curr只相差一位字符
for (int j = 0; j < wordList.size(); j++) {
if (!isVisited[j] && diffCharNum(curr, wordList.get(j))==1) {
queue.offer(wordList.get(j));
isVisited[j] = true;
}
}
}
step++;
}
return 0;
}
private int diffCharNum(String target, String word) {
// 题目已经保证所有单词有相同的长度
int n = target.length();
int diffCnt = 0;
for (int i = 0; i < n; i++) {
if (target.charAt(i) != word.charAt(i)) {
diffCnt++;
}
}
return diffCnt;
}
}
第二部分：DFS
DFS深度优先搜索在得到一个新节点时立即对新节点进行遍历，从一个节点出发，使用 DFS 对一个图进行遍历时，能够遍历到的节点都是从初始节点可达的，DFS 常用来求解这种 可达性 问题。
具体实现：用栈来保存当前节点信息，当遍历新节点返回时能够继续遍历当前节点。可以使用递归栈。注意：和 BFS 一样同样需要对已经遍历过的节点进行标记。
1 岛屿的最大面积–LeetCode695(Medium)
给定一个包含了一些 0 和 1 的非空二维数组 grid 。一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 )
示例 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。
示例 2:
[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0。
注意: 给定的矩阵grid 的长度和宽度都不超过 50。
class Solution {
private int m, n;
private int[] dx = {1,-1, 0, 0};
private int[] dy = {0, 0, 1,-1};
public int maxAreaOfIsland(int[][] grid) {
m = grid.length;
n = grid[0].length;
int maxArea = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
maxArea = Math.max(maxArea, dfs(grid, i, j));
}
}
return maxArea;
}
private int dfs(int[][] grid, int x, int y) {
if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0) {
return 0;
}
grid[x][y] = 0;
int area = 1;
for (int i = 0; i < 4; i++) {
area += dfs(grid, x+dx[i], y+dy[i]);
}
return area;
}
}
2 岛屿数量–LeetCode200(Medium)
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出: 1
示例 2:
输入:
11000
11000
00100
00011
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
代码如下：
class Solution {
private int[][] bias = {{1,0},{-1,0},{0,1},{0,-1}};//偏移量
private int m, n;
private boolean[][] isVisited = null;
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
m = grid.length;
n = grid[0].length;
int cnt = 0;// 岛屿数量
isVisited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1' && !isVisited[i][j]) {
cnt++;
searchGrid(grid, i, j);
}
}
}
return cnt;
}
private void searchGrid(char[][] grid, int x, int y) {
isVisited[x][y] = true;
for (int i = 0; i < 4; i++) {
int newX = x + bias[i][0];
int newY = y + bias[i][1];
if (newX >= 0 && newX < m && newY >= 0 && newY < n
&& !isVisited[newX][newY]
&& grid[newX][newY] == '1') {
searchGrid(grid, newX, newY);
}
}
return;
}
}
3 朋友圈–LeetCode547(Medium)
班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。
给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i个和j个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
示例 1:
输入:
[[1,1,0],
[1,1,0],
[0,0,1]]
输出: 2
说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。
示例 2:
输入:
[[1,1,0],
[1,1,1],
[0,1,1]]
输出: 1
说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。
注意：
- N 在[1,200]的范围内。
- 对于所有学生，有
M[i][i] = 1。 - 如果有
M[i][j] = 1````，则有M[j][i] = 1```。
BFS：
class Solution {
private int n;// 学生的个数
private boolean[] isVisited = null;
public int findCircleNum(int[][] M) {
n = M.length;
isVisited = new boolean[n];
int circleNum = 0;
for (int i = 0; i < n; i++) {
if (!isVisited[i]) {
circleNum++;
dfs(M, i);
}
}
return circleNum;
}
private void dfs(int[][] M, int curr) {
isVisited[curr] = true;// 自己被标记出已访问
for (int i = 0; i < n; i++) {
if (!isVisited[i] && M[curr][i]==1) {
dfs(M, i);//深度优先遍历体现朋友的传递性
}
}
return ;
}
}
并查集：
class Solution {
public int findCircleNum(int[][] M) {
int n = M.length;
UF uf = new UF(n);
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if (M[i][j] == 1) {
uf.union(i, j);
}
}
}
return uf.count();
}
}
class UF {
private int count;
private int[] parent;
private int[] size;
public UF(int n) {
count = n;
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
private int find(int p) {
// 路径压缩
while (p != parent[p]) {
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) {
return;
}
// 基于size的优化，即节点少的树合并到节点多的树上
if (size[rootP] < size[rootQ]) {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
}else {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
}
count--;
}
public boolean isConnected(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
return rootP == rootQ;
}
public int count() {
return count;
}
}
参考资料：labuladong的题解
4 被围绕的区域–LeetCode130(Medium)
给定一个二维的矩阵，包含 'X'和 'O'（字母 O）。
找到所有被 'X'围绕的区域，并将这些区域里所有的'O'用 'X'填充。
示例:
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'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
思路：使用DFS将外侧的'O'以及所有与外侧的'O'相连的'O'都替换成其它字符'#'，那么剩下的'O'就是被'X'包围的'O'，最后将'O'替换成'X'，将'#'替换成'O'即可。
class Solution {
private int m, n;
private int[] dx = {1,-1,0,0};
private int[] dy = {0,0,1,-1};
public void solve(char[][] board) {
if (board == null || board.length == 0) {
return;
}
m = board.length;
n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
boolean isEdge = i == 0 || i == m-1 || j == 0 || j == n-1;
if (isEdge && board[i][j] == 'O') {
dfs(board, i, j);
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}else if (board[i][j] == '#') {
board[i][j] = 'O';
}
}
}
return ;
}
private void dfs(char[][] board, int x, int y) {
if (x < 0 || x >= m || y < 0 || y >= n || board[x][y]!='O') {
return;
}
board[x][y] = '#';
for (int i = 0; i < 4; i++) {
dfs(board, x+dx[i], y+dy[i]);
}
}
}
5 太平洋大西洋水流问题–LeetCode417(Medium)
给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。
提示：
- 输出坐标的顺序不重要
- m 和 n 都小于150
示例：
给定下面的 5x5 矩阵:
太平洋 ~ ~ ~ ~ ~
~ 1 2 2 3 (5) *
~ 3 2 3 (4) (4) *
~ 2 4 (5) 3 1 *
~ (6) (7) 1 4 5 *
~ (5) 1 1 2 4 *
* * * * * 大西洋
返回:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).
class Solution {
private int m, n;
private int[] dx = {1,-1,0,0};
private int[] dy = {0,0,1,-1};
public List<List<Integer>> pacificAtlantic(int[][] matrix) {
List<List<Integer>> res = new ArrayList<>();
if (matrix == null || matrix.length == 0) {
return res;
}
m = matrix.length;
n = matrix[0].length;
boolean[][] canReachP = new boolean[m][n];
boolean[][] canReachA = new boolean[m][n];
for (int i = 0; i < m; i++) {
dfs(matrix, i, 0, canReachP);
dfs(matrix, i, n-1, canReachA);
}
for (int i = 0; i < n; i++) {
dfs(matrix, 0, i, canReachP);
dfs(matrix, m-1, i, canReachA);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (canReachP[i][j] && canReachA[i][j]) {
res.add(Arrays.asList(i, j));
}
}
}
return res;
}
private void dfs(int[][] matrix, int x, int y, boolean[][] canReach) {
if (canReach[x][y]) {
return;
}
canReach[x][y] = true;
for (int i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (newX < 0 || newX >= m || newY < 0 || newY >= n
|| matrix[x][y] > matrix[newX][newY]) {
continue;
}
dfs(matrix, newX, newY, canReach);
}
return ;
}
}
总结：被围绕的区域–LeetCode130和太平洋大西洋水流问题–LeetCode417这两道题需要转换一下思维（从里向外→从外向里），从而代码实现起来就比较直观易懂。
第三部分：回溯法
总结：Backtracking（回溯）属于 DFS。（摘自CyC2018大佬的总结）
- 普通 DFS 主要用在 可达性问题 ，这种问题只需要执行到特点的位置然后返回即可。
- 而 Backtracking 主要用于求解 排列组合 问题，例如有 { ‘a’,‘b’,‘c’ } 三个字符，求解所有由这三个字符排列得到的字符串，这种问题在执行到特定的位置返回之后还会继续执行求解过程。
因为 Backtracking 不是立即返回，而要继续求解，因此在程序实现时，需要注意对元素的标记问题：
- 在访问一个新元素进入新的递归调用时，需要将新元素标记为已经访问，这样才能在继续递归调用时不用重复访问该元素；
- 但是在递归返回时，需要将元素标记为未访问，因为只需要保证在一个递归链中不同时访问一个元素，可以访问已经访问过但是不在当前递归链中的元素。
自己在做题过程中的总结：
回溯法是暴力解法的一个主要实现手段，其本质就是在一个树形问题上做深度优先遍历。
- 对于求路径、排列等问题，以下是一个参考模式：用全局变量保存最终的返回结果（list），递归函数的定义中使用另一个容器来保存已经遍历过的路径或排列信息，比如电话号码的字母组合问题中的递归函数
private void findCombinations(String digits, int index, String s)其中s保存了已经遍历过的组合信息；全排列问题中的递归函数private void generatePermutation(int[] nums, int index, List<Integer> p)其中p保存了已经遍历过的排列信息。 - 回溯法中
boolean[] isVisited的使用，它标记了某个元素是否已经被访问过了，所以需要格外注意题目中要求元素只能使用一次还是可以重复使用。对某个元素遍历完发现不满足要求，此时需要回溯，回溯的时候需要把当前元素标记为未访问状态。 - 对于二维平面上使用回溯法，因为不确定起点位置或者说可能有多个起点位置，因此需要两层for循环来遍历整个二维数组。
- 二维平面上使用回溯法，有一个小技巧：设置偏移数组。比如单词搜索问题中的
int[][] bias = {{1,0},{-1,0},{0,1},{0,-1}}，这个数组表示的偏移分别是向上、向下、向右、向左，方向并没有限制，因为for循环遍历的时候肯定四个方向都会遍历到。但是对于有些题目可能对遍历方向有要求，比如要求顺时针或者逆时针遍历，此时就需要注意一下。
1 电话号码的字母组合–LeetCode17(Medium)
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明：尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
思路：这个题目本质上是树形问题，使用递归来求解。
时间复杂度：3n = O(2n)
class Solution {
private List<String> list = new ArrayList<>();
private String[] numMap = {
" ",//0
"",//1
"abc",//2
"def",//3
"ghi",//4
"jkl",//5
"mno",//6
"pqrs",//7
"tuv",//8
"wxyz"//9
};
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) {
return list;
}
findCombinations(digits, 0, "");
return list;
}
// index表示当前在访问的数字字符串中的索引
// s表示digits[0, index-1]组合的字符串
private void findCombinations(String digits, int index, String s) {
// 递归终止条件
if (index == digits.length()) {
list.add(s);
return;
}
char curr = digits.charAt(index);
String letters = numMap[curr-'0'];
for (int i = 0; i < letters.length(); i++) {
findCombinations(digits, index+1, s+letters.charAt(i));
}
return;
}
}
2 复原IP地址–LeetCode93(Medium)
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.'分隔。
示例:
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
class Solution {
private List<String> res = new ArrayList<>();// 最终返回结果
public List<String> restoreIpAddresses(String s) {
// 特殊情况的判断
if (s == null || s.length() < 4 || s.length() > 12) {
return res;
}
// 从索引为0的位置开始，只能放置三个点
generateIPAddr(s, 0, 3, "");
return res;
}
// index表示当前正在考虑字符串中的位置，points表示还可以插入多少个分隔点，sInfo用于保存index之前的字符串
private void generateIPAddr(String s, int index, int points, String sInfo) {
if (points == 0
&& isInteger(s.substring(index))
&& s.substring(index).length() <= 3
&& Integer.parseInt(s.substring(index)) <= 255) {
sInfo += s.substring(index);
res.add(sInfo);
return;
}
for (int i = index+1; i < s.length(); i++) {
if (Integer.parseInt(s.substring(index, i)) > 255) {
break;
}
if (isInteger(s.substring(index, i))) {
generateIPAddr(s, i, points-1, sInfo+s.substring(index, i)+'.');
}
}
return;
}
// 判断是否是合法的数据，00 010这样的数字不合法
private boolean isInteger(String str) {
if (str.length() == 0) {
return false;
}
if (str.length() == 1 && str.equals("0")) {
return true;
}
if (str.charAt(0) == '0') {
return false;
}
return true;
}
}
上述代码就是将字符串划分成IP地址这个过程，在一个树形中不断搜索，将满足要求的IP地址输出。但是有些分支可以提前判断出肯定是不合法的，所以就不需要再进行下去了，这就是“剪枝”。官方解法中的剪枝图示如下：
主要的区别是在递归函数上，未剪枝运行耗时9ms，剪枝之后耗时6ms。
// index表示当前正在考虑字符串中的位置
// points表示还可以插入多少个分隔点
// sInfo用于保存index之前的字符串
private void generateIPAddr(String s, int index, int points, String sInfo) {
if (points == 0
&& isInteger(s.substring(index))
&& s.substring(index).length() <= 3
&& Integer.parseInt(s.substring(index)) <= 255) {
sInfo += s.substring(index);
res.add(sInfo);
return;
}
for (int i = index+1; i < s.length(); i++) {
if (Integer.parseInt(s.substring(index, i)) > 255) {
break;
}
// 剪枝的操作
// s.lenght()-i表示还剩下的字符数量
// 这里的points表示的含义是还有几段地址，每段地址最多有三位数字
if (s.length()-i > 3 * points) {
continue;
}
if (isInteger(s.substring(index, i))) {
generateIPAddr(s, i, points-1, sInfo+s.substring(index, i)+'.');
}
}
return;
}
3 单词搜索–LeetCode79(Medium)
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false
二维平面上的回溯法：
class Solution {
private int[][] bias = {{1,0},{-1,0},{0,1},{0,-1}};//偏移量
private int m, n;
private boolean[][] isVisited = null;
public boolean exist(char[][] board, String word) {
m = board.length;
n = board[0].length;
isVisited = new boolean[m][n];
// 起点位置不固定，因此需要遍历二维数组
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (search(board, i, j, word, 0)) {
return true;
}
}
}
return false;
}
private boolean search(char[][] board, int x, int y, String word, int index) {
if (index == word.length()-1) {
return board[x][y] == word.charAt(index);
}
if (board[x][y] == word.charAt(index)) {
isVisited[x][y] = true;
// 从 (x, y) 出发，向四个方向寻找
for (int i = 0; i < 4; i++) {
int newX = x + bias[i][0];
int newY = y + bias[i][1];
if (newX >= 0 && newX < m && newY >= 0 && newY < n
&& !isVisited[newX][newY]
&& search(board, newX, newY, word, index+1)) {
return true;
}
}
isVisited[x][y] = false;
}
return false;
}
}
4 二叉树的所有路径–LeetCode257(Easy)
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
输入:
1
/ \
2 3
\
5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
代码如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
if (root == null) {
return res;
}
if (root.left == null && root.right == null) {
res.add(String.valueOf(root.val));
//res.add(root.val+"");//会产生两个String对象
return res;
}
List<String> leftList = binaryTreePaths(root.left);
for (int i = 0; i < leftList.size(); i++) {
res.add(root.val+"->"+leftList.get(i));
}
List<String> rightList = binaryTreePaths(root.right);
for (int i = 0; i < rightList.size(); i++) {
res.add(root.val+"->"+rightList.get(i));
}
return res;
}
}
5 全排列–LeetCode46(Medium)
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例：
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
排列问题的示意图如下：
代码如下：
class Solution {
private List<List<Integer>> res = new ArrayList<>();//保存最终结果
private boolean[] isVisited = null;//标记数字是否被访问过
public List<List<Integer>> permute(int[] nums) {
if (nums == null || nums.length == 0) {
return res;
}
List<Integer> p = new ArrayList<>();
isVisited = new boolean[nums.length];
generatePermutation(nums, 0, p);
return res;
}
// index表示已考虑元素的个数，p中保存了有index个元素的排列
// 向这个排列的末尾添加第index+1个元素，获得一个有index+1个元素的排列
private void generatePermutation(int[] nums, int index, List<Integer> p) {
// 递归终止条件
if (index == nums.length) {
List<Integer> temp = new ArrayList<>(p);
res.add(temp);
return;
}
for (int i = 0; i < nums.length; i++) {
if (!isVisited[i]) {
p.add(nums[i]);
isVisited[i] = true;
generatePermutation(nums, index+1, p);
p.remove(p.size()-1);// 注意这里进行回溯
isVisited[i] = false;
}
}
return;
}
}
6 全排列II–LeetCode47(Medium)
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
思路：和全排列问题的区别主要在重复元素的判断上。我这里是每层都用一个Set，如果元素在Set中已经存在则跳过。注意条件的先后顺序，先判断是否访问过if (!isVisited[i])，再判断是否在Set中if (numSet.contains(nums[i]))以及添加元素到Set中numSet.add(nums[i])，如果这个顺序反了，会出现已访问的元素被添加到Set中来，而这里的Set是在同一层起作用的。
class Solution {
private List<List<Integer>> res = new ArrayList<>();
private boolean[] isVisited = null;
public List<List<Integer>> permuteUnique(int[] nums) {
if (nums == null || nums.length == 0) {
return res;
}
int n = nums.length;
isVisited = new boolean[n];
List<Integer> p = new ArrayList<>();
generateUniquePermutation(nums, 0, p);
return res;
}
private void generateUniquePermutation(int[] nums, int index, List<Integer> p) {
// 递归终止条件
if (index == nums.length) {
res.add(new ArrayList<Integer>(p));
return ;
}
Set<Integer> numSet = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (!isVisited[i]) {
if (numSet.contains(nums[i])) {
continue;
}
numSet.add(nums[i]);
p.add(nums[i]);
isVisited[i] = true;
generateUniquePermutation(nums, index+1, p);
p.remove(p.size()-1);
isVisited[i] = false;
}
}
return;
}
}
7 组合–LeetCode77(Medium)
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
这道题的示意图如下：
class Solution {
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
List<Integer> list = new ArrayList<>();
generateCombinations(n, k, 1, list);
return res;
}
// start表示可以访问的起始位置，list保存了start之前的组合
private void generateCombinations(int n, int k, int start, List<Integer> list) {
if (list.size() == k) {
List<Integer> temp = new ArrayList<>(list);
res.add(temp);
return;
}
for (int i = start; i <= n; i++) {
list.add(i);
generateCombinations(n, k, i+1, list);
list.remove(list.size()-1);
}
return;
}
}
对组合问题的优化：剪枝。剪枝的意思是没必要遍历到最后一个数 n ，遍历可以提前结束，上面示意图中的最右边取4的分支就可以去掉了。
class Solution {
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
List<Integer> list = new ArrayList<>();
generateCombinations(n, k, 1, list);
return res;
}
private void generateCombinations(int n, int k, int start, List<Integer> list) {
if (list.size() == k) {
List<Integer> temp = new ArrayList<>(list);
res.add(temp);
return;
}
// 优化：剪枝
// 还有k-list.size()个空位，所以[i...n]中至少要有k-list.size()个元素
// i最多为 n - (k-list.size()) + 1
for (int i = start; i <= n-(k-list.size())+1; i++) {
list.add(i);
generateCombinations(n, k, i+1, list);
list.remove(list.size()-1);
}
return;
}
}
8 组合求和–LeetCode39(Medium)
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
- 所有数字（包括 target）都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]
示例 2:
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
class Solution {
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
if (candidates == null || candidates.length == 0) {
return res;
}
Arrays.sort(candidates);
List<Integer> comb = new ArrayList<>();
generateCombination(candidates, 0, target, comb);
return res;
}
private void generateCombination(int[] candidates, int start, int target, List<Integer> comb) {
// 递归终止条件
if (target == 0) {
res.add(new ArrayList<Integer>(comb));
return;
}
// 对于已排序数组，[start, candidates.length)中candidates[start]是最小的，如果target比最小值都小，那肯定不满足
if (target < candidates[start]) {
return;
}
for (int i = start; i < candidates.length; i++ ) {
comb.add(candidates[i]);
generateCombination(candidates, i, target-candidates[i], comb);
comb.remove(comb.size()-1);
}
return;
}
}
9 组合求和II–LeetCode40(Medium)
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]
代码如下：
class Solution {
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
if (candidates == null || candidates.length == 0) {
return res;
}
Arrays.sort(candidates);
List<Integer> comb = new ArrayList<>();
generateCombination(candidates, 0, target, comb);
return res;
}
private void generateCombination(int[] candidates, int start, int target, List<Integer> comb) {
if (target == 0) {
res.add(new ArrayList<Integer>(comb));
return;
}
Set<Integer> set = new HashSet<>();
for (int i = start; i < candidates.length; i++) {
if (set.contains(candidates[i])) {
continue;
}
set.add(candidates[i]);
if (target >= candidates[i]) {
comb.add(candidates[i]);
generateCombination(candidates, i+1, target-candidates[i], comb);
comb.remove(comb.size()-1);
}
}
}
}
组合求和和组合求和II的对比总结：
-
组合求和特点是无重复元素但元素可以重复使用，比如[2,3,5]；组合求和II特点是有重复元素，但是每个位置上的元素只能使用一次，注意是不同位置上，如果两个1在不同的位置上，它们可以同时使用，只是说同一个位置上的1不可以重复使用，比如[2,5,2,1,2]。 - 代码实现上，
组合求和问题中的递归部分：generateCombination(candidates, i, target-candidates[i], comb);，组合求和II问题中的递归部分：generateCombination(candidates, i+1, target-candidates[i], comb);可以看出差别是在i和i+1。数组中当前位置是i，那么在列表中考虑了数组当前位置的元素之后，列表中下一个元素是否还是可以从数组当前位置考虑，就可以区分出元素能否重复使用。组合求和可以重复使用，所以还是从i开始，组合求和II不可以重复使用，所以从i+1开始。 - 上面两道我都是先对数组排序，根据
target和数组当前位置的元素candidates[i]二者的大小关系来做出逻辑判断。组合求和II问题中我使用了Set来避免结果集中出现重复的解。例如[10,1,2,7,6,1,5]首先排序变为[1,1,2,5,6,7,10]，第一个1作为结果集的第一个元素，和后面的元素可以构成的解有[1,1,6],[1,2,5],[1,7]，此时将1加入到Set中，然后考虑将第二个1作为结果集的第一个元素，发现此时1已经在Set中，那么就跳过这个1。
10 组合求和III–LeetCode216(Medium)
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
- 所有数字都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
代码如下：
class Solution {
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
if (k < 1) {
return res;
}
List<Integer> comb = new ArrayList<>();
generateCombination(1, k, n, comb);
return res;
}
private void generateCombination(int start, int k, int sum, List<Integer> comb) {
if (k == 0) {
if (sum == 0) {
res.add(new ArrayList<>(comb));
}
return;
}
for (int i = start; i <= 9; i++) {
comb.add(i);
generateCombination(i+1, k-1, sum-i, comb);
comb.remove(comb.size()-1);
}
return;
}
}
11 子集–LeetCode78(Medium)
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。
示例：
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
代码如下：
class Solution {
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
res.add(new ArrayList<>());
if (nums == null || nums.length == 0) {
return res;
}
List<Integer> comb = new ArrayList<>();
generateSubset(nums, 0, comb);
return res;
}
private void generateSubset(int[] nums, int start, List<Integer> comb) {
if (start >= nums.length) {
return;
}
for (int i = start; i < nums.length; i++) {
comb.add(nums[i]);
res.add(new ArrayList<>(comb));
generateSubset(nums, i+1, comb);
comb.remove(comb.size()-1);
}
}
}
12 子集II–LeetCode90(Medium)
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。
示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
class Solution {
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
res.add(new ArrayList<>());
if (nums == null || nums.length == 0) {
return res;
}
Arrays.sort(nums);
List<Integer> comb = new ArrayList<>();
generateSubset(nums, 0, comb);
return res;
}
private void generateSubset(int[] nums, int start, List<Integer> comb) {
if (start >= nums.length) {
return;
}
Set<Integer> set = new HashSet<>();
for (int i = start; i < nums.length; i++) {
if (set.contains(nums[i])) {
continue;
}
set.add(nums[i]);
comb.add(nums[i]);
res.add(new ArrayList<>(comb));
generateSubset(nums, i+1, comb);
comb.remove(comb.size()-1);
}
}
}
注意：必须要对数组排序，如果不排序，对于[4,4,4,1,4]，那么输出结果是[[],[4],[4,4],[4,4,4],[4,4,4,1],[4,4,4,1,4],[4,4,4,4],[4,4,1],[4,4,1,4],[4,1],[4,1,4],[1],[1,4]]，其中就会存在重复，比如[4,1]和[1,4]。对于子集来说，元素相同，顺序不同，是同一个子集。那么排序的作用就是消除了这种顺序的差异性。
13 分割回文串–LeetCode131(Medium)
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。
示例：
输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]
代码如下：
class Solution {
private List<List<String>> res = new ArrayList<>();
public List<List<String>> partition(String s) {
if (s == null || s.length() == 0) {
return res;
}
List<String> p = new ArrayList<>();
generatePartition(s, 0, p);
return res;
}
private void generatePartition(String s, int index, List<String> p) {
// 递归终止条件
if (index == s.length()) {
List<String> temp = new ArrayList<>(p);
res.add(temp);
return;
}
for (int i = index+1; i <= s.length(); i++) {//这里i可以取到等号是因为substring不包含右边的索引
String subStr = s.substring(index, i);
if (isPalin(subStr)) {
p.add(subStr);
generatePartition(s, i, p);
p.remove(p.size()-1);
}
}
return;
}
// 判断是否是回文字符串，方法是双指针
private boolean isPalin(String str) {
if (str.length() == 0) {
return false;
}
if (str.length() == 1) {
return true;
}
int i = 0, j = str.length()-1;
while (i < j) {
if (str.charAt(i) != str.charAt(j)) {
return false;
}
i++;
j--;
}
return true;
}
}
14 N皇后–LeetCode51(Hard)
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q'和 '.'分别代表了皇后和空位。
示例:
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
思路：在棋盘上保证同一列，向下的对角线，向上的对角线不能有超过一个皇后。这里采用三个布尔数组来保存是否存在皇后：
col = new boolean[n];//保存第i列是否有皇后
dia1 = new boolean[2*n-1];//保存向下的对角线是否有皇后
dia2 = new boolean[2*n-1];//保存向上的对角线是否有皇后
其中2 * n - 1表示有2 * n - 1条向下的对角线和2 * n - 1条向上的对角线，每条对角线上都需要监控是否有皇后。
递归和回溯的过程和之前的题目类似。
import java.util.List;
import java.util.ArrayList;
class Solution {
private List<List<String>> res = new ArrayList<>();// 存储皇后的棋盘信息
private boolean[] col = null;
private boolean[] dia1 = null;
private boolean[] dia2 = null;
public List<List<String>> solveNQueens(int n) {
col = new boolean[n];//保存第i列是否有皇后
dia1 = new boolean[2*n-1];//保存向下的对角线是否有皇后
dia2 = new boolean[2*n-1];//保存向上的对角线是否有皇后
List<Integer> row = new ArrayList<>();
generateNQueens(n, 0, row);
return res;
}
// index表示当前正在考虑的行索引
private void generateNQueens(int n, int index, List<Integer> row) {
// 递归终止条件
if (index == n) {
List<Integer> temp = new ArrayList<>(row);
res.add(generateBoard(n, temp));
return;
}
for (int i = 0; i < n; i++) {
if (!col[i] && !dia1[index-i+n-1] && !dia2[index+i]) {
row.add(i);
col[i] = true;
dia1[index-i+n-1] = true;
dia2[index+i] = true;
generateNQueens(n, index+1, row);
row.remove(row.size()-1);
col[i] = false;
dia1[index-i+n-1] = false;
dia2[index+i] = false;
}
}
return;
}
private List<String> generateBoard(int n, List<Integer> row) {
List<String> board = new ArrayList<>();//棋盘信息
StringBuilder sb = new StringBuilder(n);
for (int i = 0; i < n; i++) {
sb.append('.');
}
for (int i = 0; i < n; i++) {
sb.setCharAt(row.get(i), 'Q');
board.add(sb.toString());
sb.setCharAt(row.get(i), '.');
}
return board;
}
}
15 解数独–LeetCode37(Hard)
编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 ‘.’ 表示。
一个数独。
答案被标成红色。
Note：
- 给定的数独序列只包含数字 1-9 和字符 ‘.’ 。
- 你可以假设给定的数独只有唯一解。
- 给定数独永远是 9x9 形式的。
class Solution {
public void solveSudoku(char[][] board) {
// 从第一个位置(0,0)开始回溯法求解
generateSudoku(board, 0, 0);
return;
}
// 遍历方式：逐行遍历，每一行从左到右遍历，当前行遍历完就切换到下一行
private boolean generateSudoku(char[][] board, int row, int col) {
int n = board.length;
// 当前行遍历完，切换到下一行
if (col == n) {
return generateSudoku(board, row+1, 0);
}
// 全部遍历完，返回true
if (row == n) {
return true;
}
// 若该位置已经给出数字，直接跳过考虑下一个位置
if (board[row][col] != '.') {
return generateSudoku(board, row, col+1);
}
// 对当前位置的所有可能选项进行遍历
for (char c = '1'; c <= '9'; c++) {
// 如果字符c在这一行或这一列或所在的子数独已经出现过，则字符c不能放在当前位置
if (!isValid(board, row, col, c)) {
continue;
}
board[row][col] = c;
// 进行下一步试探，发现当前选择能成功进行下去，就继续往下
if (generateSudoku(board, row, col+1)) {
return true;
}
// 上面的下一步试探不成功，则进行回溯
board[row][col] = '.';
}
return false;
}
private boolean isValid(char[][] board, int row, int col, char c) {
for (int k = 0; k < 9; k++) {
// 同一行九个位置是否出现字符c
if (board[row][k] == c) {
return false;
}
// 同一列九个位置是否出现字符c
if (board[k][col] == c) {
return false;
}
// 当前位置(row, col)所在的子数独的九个位置是否出现字符c，确定所在的子数独的分析如下：
// 因为 row 和 col 是确定的，所以 row / 3 * 3可以确定他所在的子数独在第一个三行，还是第二个三行，还是第三个三行，
// col / 3 * 3可以确定它所在的子数独是前三列还是中三列还是后三列，
// 故[row/3*3, col/3*3]确定了这个【子数独的左上角坐标】，而需要借助 k 完全对这个9个位置的扫描
if (board[row/3*3+k/3][col/3*3+k%3] == c) {
return false;
}
}
return true;
}
}
参考资料：解数独的官方题解