目录
1. 没有重复项数字的全排列（中等）
1.1. 题目描述
1.2 解题思路
这道题目就是很典型的回溯类题目。
回溯其实也是暴力解法，但是又一些题目可以通过剪枝对算法进行优化，这道题目要找出所有的排列，其实还是
比较简单的。
算法的思路主要就是：选择与撤销
例如：1开头的有，[1,2,3]，接着3撤销，2撤销，然后选择3，再选择2，就有了[1,3,2]。
整体用一个图来观看整个过程
1.3 代码实现
方法一：递归
permute：置换
backTrack：回溯
import java.util.*;
public class Solution {
// 存所有排列的集合
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
public ArrayList<ArrayList<Integer>> permute(int[] num) {
// 存一种排列
LinkedList<Integer> list = new LinkedList<>();
// 递归进行
backTrack(num,list);
return res;
}
public void backTrack(int[] num, LinkedList<Integer> list){
// 当list中的长度等于数组的长度，则证明此时已经找到一种排列了
if(list.size() == num.length){
// add进返回结果集中
res.add(new ArrayList<>(list));
return;
}
// 遍历num数组
for(int i = 0; i < num.length; i++){
// 若当前位置中的数已经添加过了则跳过
if(list.contains(num[i]))
continue;
// 选择该数
list.add(num[i]);
// 继续寻找
backTrack(num,list);
// 撤销最后一个
list.removeLast();
}
}
}
方法二：非递归版
这种方法不使用递归，其实也是一个选择和撤销的过程，只是不使用递归来完成。
通过插入的方式，一次性找到所有的情况。
例如：第一次选择1，接着可以在1前面和后面插入2，则变为 1，2 和 2，1；接着可选择3，3插入到1，2中有三
种分别为 3，1，2；1，3，2；1，2，3；然后3插入2，1也有三种。
其实就是找到能插的位置，同一个数可以插在不同的位置，则构成了另外的排列。
public class Solution {
// 所有的排列结果集
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
public ArrayList<ArrayList<Integer>> permute(int[] num) {
ArrayList<Integer> list = new ArrayList<>();
// 先对res中加入一个空的list，给第一次插入制造一个空间。
res.add(list);
// 整个循环的次数为num的元素个数
for(int i = 0; i < num.length; i++){
ArrayList<ArrayList<Integer>> tmp = new ArrayList<>();
// 遍历此时的排列结果
for(ArrayList<Integer> r:res){
// 根据集合的大小，使用for循环在可插入的位置进行插入
for(int j = 0; j < r.size()+1; j++){
// 在第j个位置插入
r.add(j,num[i]);
// 此时构成新的排列集合，可能是不完整的排列集合（例如：[1,2];[2,1]这类）
ArrayList<Integer> temp = new ArrayList<>(r);
// 放进去tmp临时集合中
tmp.add(temp);
// 将刚插入的数移除掉，为了将同样的这个插入不同的位置
r.remove(j);
}
}
// 最后赋给res进行返回
res = new ArrayList<>(tmp);
}
return res;
}
}
2. 有重复项数字的全排列（中等）
2.1. 题目描述
2.2. 解题思路
题目主要信息:
- 给定一组可能有重复数字的数组，输出该数组的全部排列
- 输出结果按照字典序升序排列
举一反三：
学习完本题的思路你可以解决如下题目：
知识点：递归与回溯
递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层
转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解
为更小的子问题，这是使用递归的关键。
如果是线型递归，子问题直接回到父问题不需要回溯，但是如果是树型递归，父问题有很多分支，我需要从子问
题回到父问题，进入另一个子问题。因此回溯是指在递归过程中，从某一分支的子问题回到父问题进入父问题的
另一子问题分支，因为有时候进入第一个子问题的时候修改过一些变量，因此回溯的时候会要求改回父问题时的
样子才能进入第二子问题分支。
思路：
这道题类似没有重复项数字的全排列，但是因为交换位置可能会出现相同数字交换的情况，出现的结果需要去
重，因此不便于使用交换位置的方法。
我们就使用临时数组去组装一个排列的情况：每当我们选取一个数组元素以后，就确定了其位置，相当于对数组
中剩下的元素进行全排列
添加在该元素后面，给剩余部分进行全排列就是一个子问题，因此可以使用递归。
- 终止条件： 临时数组中选取了n个元素，已经形成了一种排列情况了，可以将其加入输出数组中。
- 返回值： 每一层给上一层返回的就是本层级在临时数组中添加的元素，递归到末尾的时候就能添加全部元素。
- 本级任务： 每一级都需要选择一个不重复元素加入到临时数组末尾（遍历数组选择）。
回溯的思想也与没有重复项数字的全排列类似，对于数组[1,2,2,3]，如果事先在临时数组中加入了1，后续子问题
只能是[2,2,3]的全排列接在1后面，对于2开头的分支达不到，因此也需要回溯：将临时数组刚刚加入的数字pop
掉，同时vis修改为没有加入，这样才能正常进入别的分支。
//标记为使用过
vis[i] = true;
//加入数组
temp.add(num[i]);
recursion(res, num, temp, vis);
//回溯
vis[i] = false;
temp.remove(temp.size() - 1);具体做法：
- step 1：先对数组按照字典序排序，获取第一个排列情况。
- step 2：准备一个数组暂存递归过程中组装的排列情况。使用额外的vis数组用于记录哪些位置的数字被加入了。
- step 3：每次递归从头遍历数组，获取数字加入：首先根据vis数组，已经加入的元素不能再次加入了；同时，如果当前的元素num[i]与同一层的前一个元素num[i-1]相同且num[i-1]已经用，也不需要将其纳入。
- step 4：进入下一层递归前将vis数组当前位置标记为使用过。
- step 5：回溯的时候需要修改vis数组当前位置标记，同时去掉刚刚加入数组的元素，
- step 6：临时数组长度到达原数组长度就是一种排列情况。
图示：
2.3. 代码实现
递归+回溯（推荐使用）
结果列表
数组
临时列表
布尔数组
import java.util.*;
public class Solution {
public void recursion(ArrayList<ArrayList<Integer>> res, int[] num, ArrayList<Integer> temp, Boolean[] vis){
//临时数组满了加入输出
if(temp.size() == num.length){
res.add(new ArrayList<Integer>(temp));
return;
}
//遍历所有元素选取一个加入
for(int i = 0; i < num.length; i++){
//如果该元素已经被加入了则不需要再加入了
if(vis[i])
continue;
if(i > 0 && num[i - 1] == num[i] && !vis[i - 1])
//当前的元素num[i]与同一层的前一个元素num[i-1]相同且num[i-1]已经用过了
continue;
//标记为使用过
vis[i] = true;
//加入数组
temp.add(num[i]);
recursion(res, num, temp, vis);
//回溯
vis[i] = false;
temp.remove(temp.size() - 1);
}
}
public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
//先按字典序排序
Arrays.sort(num);
Boolean[] vis = new Boolean[num.length];
Arrays.fill(vis, false);
ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> temp = new ArrayList<Integer>();
recursion(res, num, temp, vis);
return res;
}
}
3. 岛屿数量（中等）
3.1. 题目描述
3.2. 解题思路
题目主要信息：
- 给一个01矩阵，1代表是陆地，0代表海洋，如果两个1相邻，则这两个1属于同一个岛
- 只考虑上下左右为相邻
- 判断岛屿的个数
举一反三：
学习完本题的思路你可以解决如下题目：
3.3 代码实现
方法一：dfs（推荐使用）
知识点：深度优先搜索（dfs） 深度优先搜索一般用于树或者图的遍历，其他有分支的（如二维矩阵）也
适用。它的原理是从初始点开始，一直沿着同一个分支遍历，直到该分支结束，然后回溯到上一级继续
沿着一个分支走到底，如此往复，直到所有的节点都有被访问到。
思路：
矩阵中多处聚集着1，要想统计1聚集的堆数而不重复统计，那我们可以考虑每次找到一堆相邻的1，就将
其全部改成0，而将所有相邻的1改成0的步骤又可以使用深度优先搜索（dfs）：当我们遇到矩阵的某个
元素为1时，首先将其置为了0，然后查看与它相邻的上下左右四个方向，如果这四个方向任意相邻元素
为1，则进入该元素，进入该元素之后我们发现又回到了刚刚的子问题，又是把这一片相邻区域的1全
部置为0，因此可以用递归实现。
//后续四个方向遍历
if(i - 1 >= 0 && grid[i - 1][j] == '1')
dfs(grid, i - 1, j);
if(i + 1 < n && grid[i + 1][j] == '1')
dfs(grid, i + 1,j);
if(j - 1 >= 0 && grid[i][j - 1] == '1')
dfs(grid, i, j - 1);
if(j + 1 < m && grid[i][j + 1] == '1')
dfs(grid, i, j + 1);- 终止条件： 进入某个元素修改其值为0后，遍历四个方向发现周围都没有1，那就不用继续递归，返回即可，或者递归到矩阵边界也同样可以结束。
- 返回值： 每一级的子问题就是把修改后的矩阵返回，因为其是函数引用，也不用管。
- 本级任务： 对于每一级任务就是将该位置的元素置为0，然后查询与之相邻的四个方向，看看能不能进入子问题。
具体做法：
- step 1：优先判断空矩阵等情况。
- step 2：从上到下从左到右遍历矩阵每一个位置的元素，如果该元素值为1，统计岛屿数量。
- step 3：接着将该位置的1改为0，然后使用dfs判断四个方向是否为1，分别进入4个分支继续修改。
图示：
Java实现代码：
import java.util.*;
public class Solution {
//深度优先遍历与i，j相邻的所有1
public void dfs(char[][] grid, int i, int j) {
int n = grid.length;
int m = grid[0].length;
// 置为0
grid[i][j] = '0';
//后续四个方向遍历
if(i - 1 >= 0 && grid[i - 1][j] == '1')
dfs(grid, i - 1, j);
if(i + 1 < n && grid[i + 1][j] == '1')
dfs(grid, i + 1,j);
if(j - 1 >= 0 && grid[i][j - 1] == '1')
dfs(grid, i, j - 1);
if(j + 1 < m && grid[i][j + 1] == '1')
dfs(grid, i, j + 1);
}
public int solve (char[][] grid) {
int n = grid.length;
//空矩阵的情况
if (n == 0)
return 0;
int m = grid[0].length;
//记录岛屿数
int count = 0;
//遍历矩阵
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
//遍历到1的情况
if(grid[i][j] == '1'){
//计数
count++;
//将与这个1相邻的所有1置为0
dfs(grid, i, j);
}
}
}
return count;
}
}
方法二：bfs（扩展思路）
知识点：广度优先搜索（bfs）
广度优先搜索与深度优先搜索不同，它是将与某个节点直接相连的其它所有节点依次访问一次之后，再
往更深处，进入与其他节点直接相连的节点。bfs的时候我们常常会借助队列的先进先出，因为从某个节
点出发，我们将与它直接相连的节点都加入队列，它们优先进入，则会优先弹出，在它们弹出的时候再
将与它们直接相连的节点加入，由此就可以依次按层访问。
思路：
统计岛屿的方法可以和方法一同样遍历解决，为了去重我们还是要将所有相邻的1一起改成0，这时候同
样遍历连通的广度优先搜索（bfs）可以代替dfs。
具体做法：
- step 1：优先判断空矩阵等情况。
- step 2：从上到下从左到右遍历矩阵每一个位置的元素，如果该元素值为1，统计岛屿数量。
- step 3：使用bfs将遍历矩阵遇到的1以及相邻的1全部置为0：利用两个队列辅助（C++可以使用pair），每次队列进入第一个进入的1，然后遍历队列，依次探讨队首的四个方向，是否符合，如果符合则置为0，且位置坐标加入队列，继续遍历，直到队列为空。
图示：
Java实现代码：
import java.util.*;
public class Solution {
public int solve (char[][] grid) {
int n = grid.length;
//空矩阵的情况
if (n == 0)
return 0;
int m = grid[0].length;
//记录岛屿数
int count = 0;
//遍历矩阵
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
//遇到1要将这个1及与其相邻的1都置为0
if(grid[i][j] == '1'){
//岛屿数增加
count++;
grid[i][j] = '0';
//记录后续bfs的坐标
Queue<Integer> q1 = new LinkedList<Integer>();
Queue<Integer> q2 = new LinkedList<Integer>();
q1.offer(i);
q2.offer(j);
//bfs
while(!q1.isEmpty()){
int row = q1.poll();
int col = q2.poll();
//四个方向依次检查：不越界且为1
if(row - 1 >= 0 && grid[row - 1][col] == '1'){
q1.offer(row - 1);
q2.offer(col);
grid[row - 1][col] = '0';
}
if(row + 1 < n && grid[row + 1][col] == '1'){
q1.offer(row + 1);
q2.offer(col);
grid[row + 1][col] = '0';
}
if(col - 1 >= 0 && grid[row][col - 1] == '1'){
q1.offer(row);
q2.offer(col - 1);
grid[row][col - 1] = '0';
}
if(col + 1 < m && grid[row][col + 1] == '1'){
q1.offer(row);
q2.offer(col + 1);
grid[row][col + 1] = '0';
}
}
}
}
}
return count;
}
}
4. 字符串的排列（中等）
4.1. 题目描述
4.2. 题目分析
题目主要信息:
- 给定一个长度为n的字符串，求其中所有字符的全排列
- 字符串中可能有重复字符，打印顺序任意
- 字符串中只包含大小写字母
举一反三：
学习完本题的思路你可以解决如下题目：
4.3 解题思路
知识点：递归与回溯
递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的
问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能
讲原本的问题分解为更小的子问题，这是使用递归的关键。
如果是线型递归，子问题直接回到父问题不需要回溯，但是如果是树型递归，父问题有很多分支，我需
要从子问题回到父问题，进入另一个子问题。因此回溯是指在递归过程中，从某一分支的子问题回到父
问题进入父问题的另一子问题分支，因为有时候进入第一个子问题的时候修改过一些变量，因此回溯的
时候会要求改回父问题时的样子才能进入第二子问题分支。
思路：
都是求元素的全排列，字符串与数组没有区别，一个是数字全排列，一个是字符全排列，因此大致思路
与有重复项数字的全排列类似，只是这道题输出顺序没有要求。但是为了便于去掉重复情况，我们还是
应该参照数组全排列，优先按照字典序排序，因为排序后重复的字符就会相邻，后续递归找起来也很方
便。
使用临时变量去组装一个排列的情况：每当我们选取一个字符以后，就确定了其位置，相当于对字符串
中剩下的元素进行全排列添加在该元素后面，给剩余部分进行全排列就是一个子问题，因此可以使用递
归。
- 终止条件： 临时字符串中选取了n个元素，已经形成了一种排列情况了，可以将其加入输出数组中。
- 返回值： 每一层给上一层返回的就是本层级在临时字符串中添加的元素，递归到末尾的时候就能添加全部元素。
- 本级任务： 每一级都需要选择一个元素加入到临时字符串末尾（遍历原字符串选择）。
递归过程也需要回溯，比如说对于字符串“abbc”，如果事先在临时字符串中加入了a，后续子问题只能
是"bbc"的全排列接在a后面，对于b开头的分支达不到，因此也需要回溯：将临时字符串刚刚加入的字符
去掉，同时vis修改为没有加入，这样才能正常进入别的分支。
具体做法：
- step 1：先对字符串按照字典序排序，获取第一个排列情况。
- step 2：准备一个空串暂存递归过程中组装的排列情况。使用额外的vis数组用于记录哪些位置的字符被加入了。
- step 3：每次递归从头遍历字符串，获取字符加入：首先根据vis数组，已经加入的元素不能再次加入了；同时，如果当前的元素str[i]与同一层的前一个元素str[i-1]相同且str[i-1]已经用，也不需要将其纳入。
- step 4：进入下一层递归前将vis数组当前位置标记为使用过。
- step 5：回溯的时候需要修改vis数组当前位置标记，同时去掉刚刚加入字符串的元素，
- step 6：临时字符串长度到达原串长度就是一种排列情况。
图示：
4.4 代码实现
方法：递归+回溯（推荐使用）
import java.util.*;
public class Solution {
public void recursion(ArrayList<String> res, char[] str, StringBuffer temp, boolean[] vis){
//临时字符串满了加入输出
if(temp.length() == str.length){
res.add(new String(temp));
return;
}
//遍历所有元素选取一个加入
for(int i = 0; i < str.length; i++){
//如果该元素已经被加入了则不需要再加入了
if(vis[i])
continue;
if(i > 0 && str[i - 1] == str[i] && !vis[i - 1])
//当前的元素str[i]与同一层的前一个元素str[i-1]相同且str[i-1]已经用过了
continue;
//标记为使用过
vis[i] = true;
//加入临时字符串
temp.append(str[i]);
recursion(res, str, temp, vis);
//回溯
vis[i] = false;
temp.deleteCharAt(temp.length() - 1);
}
}
public ArrayList<String> Permutation(String str) {
ArrayList<String> res = new ArrayList<String>();
if(str == null || str.length() == 0)
return res;
//转字符数组
char[] charStr = str.toCharArray();
// 按字典序排序
Arrays.sort(charStr);
boolean[] vis = new boolean[str.length()];
//标记每个位置的字符是否被使用过
Arrays.fill(vis, false);
StringBuffer temp = new StringBuffer();
//递归获取
recursion(res, charStr, temp, vis);
return res;
}
}
5. N皇后问题（较难）
5.1. 题目描述
5.2. 解题思路
题目主要信息:
- 在一个n∗n的棋盘上要摆放n个皇后，求摆的方案数，不同位置就是不同方案数
- 摆放要求：任何两个皇后不同行，不同列也不在同一条斜线上
举一反三：
学习完本题的思路你可以解决如下题目：
知识点：递归与回溯
递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的
问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能
讲原本的问题分解为更小的子问题，这是使用递归的关键。
如果是线型递归，子问题直接回到父问题不需要回溯，但是如果是树型递归，父问题有很多分支，我需
要从子问题回到父问题，进入另一个子问题。因此回溯是指在递归过程中，从某一分支的子问题回到父
问题进入父问题的另一子问题分支，因为有时候进入第一个子问题的时候修改过一些变量，因此回溯的
时候会要求改回父问题时的样子才能进入第二子问题分支。
n个皇后，不同行不同列，那么肯定棋盘每行都会有一个皇后，每列都会有一个皇后。如果我们确定了第
一个皇后的行号与列号，则相当于接下来在n−1n-1n−1行中查找n−1n-1n−1个皇后，这就是一个子问
题，因此使用递归：
- 终止条件： 当最后一行都被选择了位置，说明n个皇后位置齐了，增加一种方案数返回。
- 返回值： 每一级要将选中的位置及方案数返回。
- 本级任务： 每一级其实就是在该行选择一列作为该行皇后的位置，遍历所有的列选择一个符合条件的位置加入数组，然后进入下一级。
具体做法：
- step 1：对于第一行，皇后可能出现在该行的任意一列，我们用一个数组pos记录皇后出现的位置，下标为行号，元素值为列号。
- step 2：如果皇后出现在第一列，那么第一行的皇后位置就确定了，接下来递归地在剩余的n−1行中找n−1个皇后的位置。
- step 3：每个子问题检查是否符合条件，我们可以对比所有已经记录的行，对其记录的列号查看与当前行列号的关系：即是否同行、同列或是同一对角线。
图示：
5.3. 代码实现
方法：递归（推荐使用）
import java.util.*;
public class Solution {
private int res;
//判断皇后是否符合条件
public boolean isValid(int[] pos, int row, int col){
//遍历所有已经记录的行
for(int i = 0; i < row; i++){
//不能同行同列同一斜线
if(row == i || col == pos[i] || Math.abs(row - i) == Math.abs(col - pos[i]))
return false;
}
return true;
}
//递归查找皇后种类
public void recursion(int n, int row, int[] pos){
//完成全部行都选择了位置
if(row == n){
res++;
return;
}
//遍历所有列
for(int i = 0; i < n; i++){
//检查该位置是否符合条件
if(isValid(pos, row, i)){
//加入位置
pos[row] = i;
//递归继续查找
recursion(n, row + 1, pos);
}
}
}
public int Nqueen (int n) {
res = 0;
//下标为行号，元素为列号，记录皇后位置
int[] pos = new int[n];
Arrays.fill(pos, 0);
//递归
recursion(n, 0, pos);
return res;
}
}复杂度分析：
- 时间复杂度：O(n∗n!)，isValid函数每次检查复杂度为O(n)，递归过程相当于对长度为nnn的数组求全排列，复杂度为O(n!)
- 空间复杂度：O(n)，辅助数组和栈空间最大为O(n)
6. 括号生成（中等）
6.1. 题目描述
6.2. 解题思路
题目主要信息：
- 求n对括号的全部合法组合，左右括号之间任意组合，只要合法就行
- 需要输出所有的结果
举一反三：
学习完本题的思路你可以解决如下题目：
知识点：递归与回溯
递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的
问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能
讲原本的问题分解为更小的子问题，这是使用递归的关键。
如果是线型递归，子问题直接回到父问题不需要回溯，但是如果是树型递归，父问题有很多分支，我需
要从子问题回到父问题，进入另一个子问题。因此回溯是指在递归过程中，从某一分支的子问题回到父
问题进入父问题的另一子问题分支，因为有时候进入第一个子问题的时候修改过一些变量，因此回溯的
时候会要求改回父问题时的样子才能进入第二子问题分支。
思路：
相当于一共n个左括号和n个右括号，可以给我们使用，我们需要依次组装这些括号。每当我们使用一个
左括号之后，就剩下n−1个左括号和n个右括号给我们使用，结果拼在使用的左括号之后就行了，因此后
者就是一个子问题，可以使用递归：
- 终止条件： 左右括号都使用了n个，将结果加入数组。
- 返回值： 每一级向上一级返回后续组装后的字符串，即子问题中搭配出来的括号序列。
- 本级任务： 每一级就是保证左括号还有剩余的情况下，使用一次左括号进入子问题，或者右括号还有剩余且右括号使用次数少于左括号的情况下使用一次右括号进入子问题。
但是这样递归不能保证括号一定合法，我们需要保证左括号出现的次数比右括号多时我们再使用右括号
就一定能保证括号合法了，因此每次需要检查左括号和右括号的使用次数。
//使用一次左括号
if(left < n){
recursion(left + 1, right, temp + "(", res, n);
}
//使用右括号个数必须少于左括号
if(right < n && left > right){
recursion(left, right + 1, temp + ")", res, n);
}具体做法：
- step 1：将空串与左右括号各自使用了0个送入递归。
- step 2：若是左右括号都使用了n个，此时就是一种结果。
- step 3：若是左括号数没有到达n个，可以考虑增加左括号，或者右括号数没有到达n个且左括号的使用次数多于右括号就可以增加右括号。
图示：
6.3. 代码实现
方法：递归（推荐使用）
import java.util.*;
public class Solution {
public void recursion(int left, int right, String temp, ArrayList<String> res, int n){
//左右括号都用完了，就加入结果
if(left == n && right == n){
res.add(temp);
return;
}
//使用一次左括号
if(left < n){
recursion(left + 1, right, temp + "(", res, n);
}
//使用右括号个数必须少于左括号
if(right < n && left > right){
recursion(left, right + 1, temp + ")", res, n);
}
}
public ArrayList<String> generateParenthesis (int n) {
//记录结果
ArrayList<String> res = new ArrayList<String>();
//递归
recursion(0, 0, "", res, n);
return res;
}
}
7. 矩阵最长递增路径（中等）
7.1. 题目描述
7.2. 解题思路
题目主要信息：
- 矩阵内是非负数，求最长的递增路径的长度
- 移动方向可以是上下左右，不能超出边界，这将是递归的判定条件
- 同一条路径不能有重复的单元格，需要有记忆
举一反三：
学习完本题的思路你可以解决如下题目：
7.3. 代码实现
方法一：深度优先搜索(推荐使用)
知识点：深度优先搜索（dfs）
深度优先搜索一般用于树或者图的遍历，其他有分支的（如二维矩阵）也适用。它的原理是从初始点开
始，一直沿着同一个分支遍历，直到该分支结束，然后回溯到上一级继续沿着一个分支走到底，如此往
复，直到所有的节点都有被访问到。
思路：
既然是查找最长的递增路径长度，那我们首先要找到这个路径的起点，起点不好直接找到，就从上到下
从左到右遍历矩阵的每个元素。
然后以每个元素都可以作为起点查找它能到达的最长递增路径。
如何查找以某个点为起点的最长递增路径呢？我们可以考虑深度优先搜索，因为我们查找递增路径的时
候，每次选中路径一个点，然后找到与该点相邻的递增位置，相当于进入这个相邻的点，继续查找递增
路径，这就是递归的子问题。因此递归过程如下：
- 终止条件： 进入路径最后一个点后，四个方向要么是矩阵边界，要么没有递增的位置，路径不能再增长，返回上一级。
- 返回值： 每次返回的就是本级之后的子问题中查找到的路径长度加上本级的长度。
- 本级任务： 每次进入一级子问题，先初始化后续路径长度为0，然后遍历四个方向（可以用数组表示，下标对数组元素的加减表示去往四个方向），进入符合不是边界且在递增的邻近位置作为子问题，查找子问题中的递增路径长度。因为有四个方向，所以最多有四种递增路径情况，因此要维护当级子问题的最大值。
具体做法：
- step 1：使用一个dp数组记录i，j处的单元格拥有的最长递增路径，这样在递归过程中如果访问到就不需要重复访问。
- step 2：遍历矩阵每个位置，都可以作为起点，并维护一个最大的路径长度的值。
- step 3：对于每个起点，使用dfs查找最长的递增路径：只要下一个位置比当前的位置数字大，就可以深入，同时累加路径长度。
图示：
Java实现代码：
import java.util.*;
public class Solution {
//记录四个方向
private int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
private int n, m;
//深度优先搜索，返回最大单元格数
public int dfs(int[][] matrix, int[][] dp, int i, int j) {
if(dp[i][j] != 0)
return dp[i][j];
dp[i][j]++;
for (int k = 0; k < 4; k++) {
int nexti = i + dirs[k][0];
int nextj = j + dirs[k][1];
//判断条件
if(nexti >= 0 && nexti < n && nextj >= 0 && nextj < m && matrix[nexti][nextj] > matrix[i][j])
dp[i][j] = Math.max(dp[i][j], dfs(matrix, dp, nexti, nextj) + 1);
}
return dp[i][j];
}
public int solve (int[][] matrix) {
//矩阵不为空
if (matrix.length == 0 || matrix[0].length == 0)
return 0;
int res = 0;
n = matrix.length;
m = matrix[0].length;
//i，j处的单元格拥有的最长递增路径
int[][] dp = new int[m + 1][n + 1];
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
//更新最大值
res = Math.max(res, dfs(matrix, dp, i, j));
return res;
}
}
方法二：广度优先搜索（扩展思路）
知识点：广度优先搜索（bfs）
广度优先搜索与深度优先搜索不同，它是将与某个节点直接相连的其它所有节点依次访问一次之后，再
往更深处，进入与其他节点直接相连的节点。bfs的时候我们常常会借助队列的先进先出，因为从某个节
点出发，我们将与它直接相连的节点都加入队列，它们优先进入，则会优先弹出，在它们弹出的时候再
将与它们直接相连的节点加入，由此就可以依次按层访问。
思路：
我们可以将矩阵看成是一个有向图，一个元素到另一个元素递增，代表有向图的箭头。这样我们可以根
据有向图的出度入度找到最长的路径，且这个路径在矩阵中就是递增的。
具体做法：
- step 1：计算每个节点（单元格）所对应的出度（符合边界条件且递增），对于作为边界条件的单元格，它的值比所有的相邻单元格的值都要大，因此作为边界条件的单元格的出度都为0。利用一个二维矩阵记录每个单元格的出度
- step 2：利用拓扑排序的思想，从所有出度为0的单元格开始进行广度优先搜索。
- step 3：借助队列来广度优先搜索，队列中每次加入出度为0的点，即路径最远点，每次从A点到B点，便将A点出度减一。
- step 4：每次搜索都会遍历当前层的所有单元格，更新其余单元格的出度，并将出度变为0的单元格加入下一层搜索。
- step 5：当搜索结束时，搜索的总层数即为矩阵中的最长递增路径的长度，因为bfs的层数就是路径增长的层数。
图示：
Java实现代码：
import java.util.*;
public class Solution {
//记录四个方向
private int[][] dirs = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
private int n, m;
public int solve (int[][] matrix) {
//矩阵不为空
if (matrix.length == 0 || matrix[0].length == 0)
return 0;
int res = 0;
n = matrix.length;
m = matrix[0].length;
//i，j处的单元格拥有的最长递增路径
int[][] outdegrees = new int[m + 1][n + 1];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
for(int k = 0; k < 4; k++){
int nexti = i + dirs[k][0];
int nextj = j + dirs[k][1];
if(nexti >= 0 && nexti < n && nextj >= 0 && nextj < m && matrix[nexti][nextj] > matrix[i][j]){
//符合条件，记录出度
outdegrees[i][j]++;
}
}
}
}
//辅助队列
Queue<Integer> q1 = new LinkedList<Integer>();
Queue<Integer> q2 = new LinkedList<Integer>();
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(outdegrees[i][j] == 0){
//找到出度为0的入队列
q1.offer(i);
q2.offer(j);
}
}
}
while(!q1.isEmpty()){
res++;
int size = q1.size();
for(int x = 0; x < size; x++){
int i = q1.poll();
int j = q2.poll();
//四个方向
for(int k = 0; k < 4; k++){
int nexti = i + dirs[k][0];
int nextj = j + dirs[k][1];
//逆向搜索，所以下一步是小于
if (nexti >= 0 && nexti < n && nextj >= 0 && nextj < m && matrix[nexti][nextj] < matrix[i][j]) {
//符合条件，出度递减
outdegrees[nexti][nextj]--;
if (outdegrees[nexti][nextj] == 0) {
q1.offer(nexti);
q2.offer(nextj);
}
}
}
}
}
return res;
}
}
8. 重建二叉树（中等）
8.1. 题目描述
8.2. 解题思路
方法：分治思想
参考代码 1：
import java.util.HashMap;
import java.util.Map;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public class Solution {
// 使用全局变量是为了让递归方法少传一些参数，不一定非要这么做
private Map<Integer, Integer> reverses;
private int[] preorder;
public TreeNode buildTree(int[] preorder, int[] inorder) {
int preLen = preorder.length;
int inLen = inorder.length;
// 可以不做判断，因为题目中给出的数据都是有效的
if (preLen != inLen) {
return null;
}
this.preorder = preorder;
// 以空间换时间，否则，找根结点在中序遍历中的位置需要遍历
reverses = new HashMap<>(inLen);
for (int i = 0; i < inLen; i++) {
reverses.put(inorder[i], i);
}
return buildTree(0, preLen - 1, 0, inLen - 1);
}
/**
* 根据前序遍历数组的 [preL, preR] 和 中序遍历数组的 [inL, inR] 重新组建二叉树
*
* @param preL 前序遍历数组的区间左端点
* @param preR 前序遍历数组的区间右端点
* @param inL 中序遍历数组的区间左端点
* @param inR 中序遍历数组的区间右端点
* @return 构建的新二叉树的根结点
*/
private TreeNode buildTree(int preL, int preR,
int inL, int inR) {
if (preL > preR || inL > inR) {
return null;
}
// 构建的新二叉树的根结点一定是前序遍历数组的第 1 个元素
int pivot = preorder[preL];
TreeNode root = new TreeNode(pivot);
int pivotIndex = reverses.get(pivot);
// 这一步得画草稿，计算边界的取值，必要时需要解方程，并不难
root.left = buildTree(preL + 1, preL + (pivotIndex - inL), inL, pivotIndex - 1);
root.right = buildTree(preL + (pivotIndex - inL) + 1, preR, pivotIndex + 1, inR);
return root;
}
}9. 数值的整数次方
9.1. 题目描述
9.2. 解题思路
方法一：快速幂 + 递归
class Solution {
public double myPow(double x, int n) {
long N = n;
return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}
public double quickMul(double x, long N) {
if (N == 0) {
return 1.0;
}
double y = quickMul(x, N / 2);
return N % 2 == 0 ? y * y : y * y * x;
}
}
方法二：快速幂 + 迭代
class Solution {
public double myPow(double x, int n) {
long N = n;
return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}
public double quickMul(double x, long N) {
double ans = 1.0;
// 贡献的初始值为 x
double x_contribute = x;
// 在对 N 进行二进制拆分的同时计算答案
while (N > 0) {
if (N % 2 == 1) {
// 如果 N 二进制表示的最低位为 1，那么需要计入贡献
ans *= x_contribute;
}
// 将贡献不断地平方
x_contribute *= x_contribute;
// 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
N /= 2;
}
return ans;
}
}
10. 二叉搜索树的后序遍历序列
10.1. 题目描述
10.2. 解题思路
方法一：递归分治
class Solution {
public boolean verifyTreeOrder(int[] postorder) {
return recur(postorder, 0, postorder.length - 1);
}
boolean recur(int[] postorder, int i, int j) {
if(i >= j) return true;
int p = i;
while(postorder[p] < postorder[j]) p++;
int m = p;
while(postorder[p] > postorder[j]) p++;
return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
}
}
方法二：辅助单调栈
class Solution {
public boolean verifyTreeOrder(int[] postorder) {
Stack<Integer> stack = new Stack<>();
int root = Integer.MAX_VALUE;
for(int i = postorder.length - 1; i >= 0; i--) {
if(postorder[i] > root) return false;
while(!stack.isEmpty() && stack.peek() > postorder[i])
root = stack.pop();
stack.add(postorder[i]);
}
return true;
}
}
11.
11. 报数（简单）
11.1. 题目描述
11.2. 解题思路
方法一：普通解法
class Solution {
public int[] printNumbers(int n) {
int[] res = new int[(int)Math.pow(10, n) - 1];
for(int i = 0; i < res.length; i++){
res[i] = i + 1;
}
return res;
}
}方法二：全排列解法
class Solution {
int[] res;
int count = 0;
public int[] printNumbers(int n) {
res = new int[(int)Math.pow(10, n) - 1];
for(int digit = 1; digit < n + 1; digit++){
for(char first = '1'; first <= '9'; first++){
char[] num = new char[digit];
num[0] = first;
dfs(1, num, digit);
}
}
return res;
}
private void dfs(int index, char[] num, int digit){
if(index == digit){
res[count++] = Integer.parseInt(String.valueOf(num));
return;
}
for(char i = '0'; i <= '9'; i++){
num[index] = i;
dfs(index + 1, num, digit);
}
}
}
12. 交易逆序对的总数
12.1. 题目描述
12.2. 解题思路
方法一：归并排序
public class Solution {
public int reversePairs(int[] record) {
int len = record.length;
if (len < 2) {
return 0;
}
int[] copy = new int[len];
for (int i = 0; i < len; i++) {
copy[i] = record[i];
}
int[] temp = new int[len];
return reversePairs(copy, 0, len - 1, temp);
}
private int reversePairs(int[] record, int left, int right, int[] temp) {
if (left == right) {
return 0;
}
int mid = left + (right - left) / 2;
int leftPairs = reversePairs(record, left, mid, temp);
int rightPairs = reversePairs(record, mid + 1, right, temp);
if (record[mid] <= record[mid + 1]) {
return leftPairs + rightPairs;
}
int crossPairs = mergeAndCount(record, left, mid, right, temp);
return leftPairs + rightPairs + crossPairs;
}
private int mergeAndCount(int[] record, int left, int mid, int right, int[] temp) {
for (int i = left; i <= right; i++) {
temp[i] = record[i];
}
int i = left;
int j = mid + 1;
int count = 0;
for (int k = left; k <= right; k++) {
if (i == mid + 1) {
record[k] = temp[j];
j++;
} else if (j == right + 1) {
record[k] = temp[i];
i++;
} else if (temp[i] <= temp[j]) {
record[k] = temp[i];
i++;
} else {
record[k] = temp[j];
j++;
count += (mid - i + 1);
}
}
return count;
}
}
方法二：离散化树状数组
class Solution {
public int reversePairs(int[] record) {
int n = record.length;
int[] tmp = new int[n];
System.arraycopy(record, 0, tmp, 0, n);
// 离散化
Arrays.sort(tmp);
for (int i = 0; i < n; ++i) {
record[i] = Arrays.binarySearch(tmp, record[i]) + 1;
}
// 树状数组统计逆序对
BIT bit = new BIT(n);
int ans = 0;
for (int i = n - 1; i >= 0; --i) {
ans += bit.query(record[i] - 1);
bit.update(record[i]);
}
return ans;
}
}
class BIT {
private int[] tree;
private int n;
public BIT(int n) {
this.n = n;
this.tree = new int[n + 1];
}
public static int lowbit(int x) {
return x & (-x);
}
public int query(int x) {
int ret = 0;
while (x != 0) {
ret += tree[x];
x -= lowbit(x);
}
return ret;
}
public void update(int x) {
while (x <= n) {
++tree[x];
x += lowbit(x);
}
}
}
13. 全排列（中等）
13.1. 题目描述
13.2. 解题思路
方法一：回溯
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> output = new ArrayList<Integer>();
for (int num : nums) {
output.add(num);
}
int n = nums.length;
backtrack(n, output, res, 0);
return res;
}
public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
// 所有数都填完了
if (first == n) {
res.add(new ArrayList<Integer>(output));
}
for (int i = first; i < n; i++) {
// 动态维护数组
Collections.swap(output, first, i);
// 继续递归填下一个数
backtrack(n, output, res, first + 1);
// 撤销操作
Collections.swap(output, first, i);
}
}
}
14. 子集（中等)
14.1. 题目描述
14.2. 解题思路
方法一：迭代法实现子集枚举
class Solution {
List<Integer> t = new ArrayList<Integer>();
List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> subsets(int[] nums) {
int n = nums.length;
for (int mask = 0; mask < (1 << n); ++mask) {
t.clear();
for (int i = 0; i < n; ++i) {
if ((mask & (1 << i)) != 0) {
t.add(nums[i]);
}
}
ans.add(new ArrayList<Integer>(t));
}
return ans;
}
}
方法二：递归法实现子集枚举
vector<int> t;
void dfs(int cur, int n) {
if (cur == n) {
// 记录答案
// ...
return;
}
// 考虑选择当前位置
t.push_back(cur);
dfs(cur + 1, n, k);
t.pop_back();
// 考虑不选择当前位置
dfs(cur + 1, n, k);
}15. 电话号码的字母组合
15.1. 题目描述
15.2. 解题思路
方法一：回溯
class Solution {
public List<String> letterCombinations(String digits) {
List<String> combinations = new ArrayList<String>();
if (digits.length() == 0) {
return combinations;
}
Map<Character, String> phoneMap = new HashMap<Character, String>() {{
put('2', "abc");
put('3', "def");
put('4', "ghi");
put('5', "jkl");
put('6', "mno");
put('7', "pqrs");
put('8', "tuv");
put('9', "wxyz");
}};
backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
return combinations;
}
public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
if (index == digits.length()) {
combinations.add(combination.toString());
} else {
char digit = digits.charAt(index);
String letters = phoneMap.get(digit);
int lettersCount = letters.length();
for (int i = 0; i < lettersCount; i++) {
combination.append(letters.charAt(i));
backtrack(combinations, phoneMap, digits, index + 1, combination);
combination.deleteCharAt(index);
}
}
}
}
16. 组合总和（中等）
16.1. 题目描述
16.2. 解题思路
方法一：搜索回溯
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
List<Integer> combine = new ArrayList<Integer>();
dfs(candidates, target, ans, combine, 0);
return ans;
}
public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
if (idx == candidates.length) {
return;
}
if (target == 0) {
ans.add(new ArrayList<Integer>(combine));
return;
}
// 直接跳过
dfs(candidates, target, ans, combine, idx + 1);
// 选择当前数
if (target - candidates[idx] >= 0) {
combine.add(candidates[idx]);
dfs(candidates, target - candidates[idx], ans, combine, idx);
combine.remove(combine.size() - 1);
}
}
}
17.
17. 括号生成（中等）
17.1. 题目描述
17.2. 解题思路
方法一：暴力法
class Solution {
public List<String> generateParenthesis(int n) {
List<String> combinations = new ArrayList<String>();
generateAll(new char[2 * n], 0, combinations);
return combinations;
}
public void generateAll(char[] current, int pos, List<String> result) {
if (pos == current.length) {
if (valid(current)) {
result.add(new String(current));
}
} else {
current[pos] = '(';
generateAll(current, pos + 1, result);
current[pos] = ')';
generateAll(current, pos + 1, result);
}
}
public boolean valid(char[] current) {
int balance = 0;
for (char c: current) {
if (c == '(') {
++balance;
} else {
--balance;
}
if (balance < 0) {
return false;
}
}
return balance == 0;
}
}
方法二：回溯法
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<String>();
backtrack(ans, new StringBuilder(), 0, 0, n);
return ans;
}
public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
if (cur.length() == max * 2) {
ans.add(cur.toString());
return;
}
if (open < max) {
cur.append('(');
backtrack(ans, cur, open + 1, close, max);
cur.deleteCharAt(cur.length() - 1);
}
if (close < open) {
cur.append(')');
backtrack(ans, cur, open, close + 1, max);
cur.deleteCharAt(cur.length() - 1);
}
}
}
方法三：按括号序列的长度递归
class Solution {
ArrayList[] cache = new ArrayList[100];
public List<String> generate(int n) {
if (cache[n] != null) {
return cache[n];
}
ArrayList<String> ans = new ArrayList<String>();
if (n == 0) {
ans.add("");
} else {
for (int c = 0; c < n; ++c) {
for (String left: generate(c)) {
for (String right: generate(n - 1 - c)) {
ans.add("(" + left + ")" + right);
}
}
}
}
cache[n] = ans;
return ans;
}
public List<String> generateParenthesis(int n) {
return generate(n);
}
}
18. 单词搜索（中等）
18.1. 题目描述
18.2. 解题思路
方法一：回溯
class Solution {
public boolean exist(char[][] board, String word) {
int h = board.length, w = board[0].length;
boolean[][] visited = new boolean[h][w];
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
boolean flag = check(board, visited, i, j, word, 0);
if (flag) {
return true;
}
}
}
return false;
}
public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
if (board[i][j] != s.charAt(k)) {
return false;
} else if (k == s.length() - 1) {
return true;
}
visited[i][j] = true;
int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
boolean result = false;
for (int[] dir : directions) {
int newi = i + dir[0], newj = j + dir[1];
if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
if (!visited[newi][newj]) {
boolean flag = check(board, visited, newi, newj, s, k + 1);
if (flag) {
result = true;
break;
}
}
}
}
visited[i][j] = false;
return result;
}
}
19. 分割回文串（中等）
19.1. 题目描述
19.2. 解题思路
方法一：回溯 + 动态规划预处理
class Solution {
boolean[][] f;
List<List<String>> ret = new ArrayList<List<String>>();
List<String> ans = new ArrayList<String>();
int n;
public List<List<String>> partition(String s) {
n = s.length();
f = new boolean[n][n];
for (int i = 0; i < n; ++i) {
Arrays.fill(f[i], true);
}
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
f[i][j] = (s.charAt(i) == s.charAt(j)) && f[i + 1][j - 1];
}
}
dfs(s, 0);
return ret;
}
public void dfs(String s, int i) {
if (i == n) {
ret.add(new ArrayList<String>(ans));
return;
}
for (int j = i; j < n; ++j) {
if (f[i][j]) {
ans.add(s.substring(i, j + 1));
dfs(s, j + 1);
ans.remove(ans.size() - 1);
}
}
}
}
方法二：回溯 + 记忆化搜索
class Solution {
int[][] f;
List<List<String>> ret = new ArrayList<List<String>>();
List<String> ans = new ArrayList<String>();
int n;
public List<List<String>> partition(String s) {
n = s.length();
f = new int[n][n];
dfs(s, 0);
return ret;
}
public void dfs(String s, int i) {
if (i == n) {
ret.add(new ArrayList<String>(ans));
return;
}
for (int j = i; j < n; ++j) {
if (isPalindrome(s, i, j) == 1) {
ans.add(s.substring(i, j + 1));
dfs(s, j + 1);
ans.remove(ans.size() - 1);
}
}
}
// 记忆化搜索中，f[i][j] = 0 表示未搜索，1 表示是回文串，-1 表示不是回文串
public int isPalindrome(String s, int i, int j) {
if (f[i][j] != 0) {
return f[i][j];
}
if (i >= j) {
f[i][j] = 1;
} else if (s.charAt(i) == s.charAt(j)) {
f[i][j] = isPalindrome(s, i + 1, j - 1);
} else {
f[i][j] = -1;
}
return f[i][j];
}
}
20. N皇后（困难）
20.1. 题目描述
20.2. 解题思路
方法一：基于集合的回溯
class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> solutions = new ArrayList<List<String>>();
int[] queens = new int[n];
Arrays.fill(queens, -1);
Set<Integer> columns = new HashSet<Integer>();
Set<Integer> diagonals1 = new HashSet<Integer>();
Set<Integer> diagonals2 = new HashSet<Integer>();
backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);
return solutions;
}
public void backtrack(List<List<String>> solutions, int[] queens, int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
if (row == n) {
List<String> board = generateBoard(queens, n);
solutions.add(board);
} else {
for (int i = 0; i < n; i++) {
if (columns.contains(i)) {
continue;
}
int diagonal1 = row - i;
if (diagonals1.contains(diagonal1)) {
continue;
}
int diagonal2 = row + i;
if (diagonals2.contains(diagonal2)) {
continue;
}
queens[row] = i;
columns.add(i);
diagonals1.add(diagonal1);
diagonals2.add(diagonal2);
backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);
queens[row] = -1;
columns.remove(i);
diagonals1.remove(diagonal1);
diagonals2.remove(diagonal2);
}
}
}
public List<String> generateBoard(int[] queens, int n) {
List<String> board = new ArrayList<String>();
for (int i = 0; i < n; i++) {
char[] row = new char[n];
Arrays.fill(row, '.');
row[queens[i]] = 'Q';
board.add(new String(row));
}
return board;
}
}
方法二：基于位运算的回溯
class Solution {
public List<List<String>> solveNQueens(int n) {
int[] queens = new int[n];
Arrays.fill(queens, -1);
List<List<String>> solutions = new ArrayList<List<String>>();
solve(solutions, queens, n, 0, 0, 0, 0);
return solutions;
}
public void solve(List<List<String>> solutions, int[] queens, int n, int row, int columns, int diagonals1, int diagonals2) {
if (row == n) {
List<String> board = generateBoard(queens, n);
solutions.add(board);
} else {
int availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));
while (availablePositions != 0) {
int position = availablePositions & (-availablePositions);
availablePositions = availablePositions & (availablePositions - 1);
int column = Integer.bitCount(position - 1);
queens[row] = column;
solve(solutions, queens, n, row + 1, columns | position, (diagonals1 | position) << 1, (diagonals2 | position) >> 1);
queens[row] = -1;
}
}
}
public List<String> generateBoard(int[] queens, int n) {
List<String> board = new ArrayList<String>();
for (int i = 0; i < n; i++) {
char[] row = new char[n];
Arrays.fill(row, '.');
row[queens[i]] = 'Q';
board.add(new String(row));
}
return board;
}
}
21. 彩灯装饰记录 I（中等）
21.1. 题目描述
21.2. 解题思路
方法一：迭代 BFS
使用「迭代」进行求解是容易的，只需使用常规的BFS 方法进行层序遍历即可。
class Solution {
public int[] levelOrder(TreeNode root) {
List<Integer> list = new ArrayList<>();
Deque<TreeNode> d = new ArrayDeque<>();
if (root != null) d.addLast(root);
while (!d.isEmpty()) {
TreeNode t = d.pollFirst();
list.add(t.val);
if (t.left != null) d.addLast(t.left);
if (t.right != null) d.addLast(t.right);
}
int n = list.size();
int[] ans = new int[n];
for (int i = 0; i < n; i++) ans[i] = list.get(i);
return ans;
}
}- 时间复杂度：O(n)
- 空间复杂度：O(n)
方法二：递归 DFS
使用「递归」来进行「层序遍历」虽然不太符合直观印象，但也是可以的。
此时我们需要借助「哈希表」来存储起来每一层的节点情况。
首先我们按照「中序遍历」的方式进行 DFS，同时在 DFS 过程中传递节点所在的深度（root 节点默认
在深度最小的第 000 层），每次处理当前节点时，通过哈希表获取所在层的数组，并将当前节点值追加
到数组尾部，同时维护一个最大深度 max，在 DFS 完成后，再使用深度范围 [0,max] 从哈希表中进行构
造答案。
class Solution {
Map<Integer, List<Integer>> map = new HashMap<>();
int max = -1, cnt = 0;
public int[] levelOrder(TreeNode root) {
dfs(root, 0);
int[] ans = new int[cnt];
for (int i = 0, idx = 0; i <= max; i++) {
for (int x : map.get(i)) ans[idx++] = x;
}
return ans;
}
void dfs(TreeNode root, int depth) {
if (root == null) return ;
max = Math.max(max, depth);
cnt++;
dfs(root.left, depth + 1);
List<Integer> list = map.getOrDefault(depth, new ArrayList<Integer>());
list.add(root.val);
map.put(depth, list);
dfs(root.right, depth + 1);
}
}- 时间复杂度：O(n)
- 空间复杂度：O(n)
22. 彩灯装饰记录 II（简单）
22.1. 题目描述
22.2. 解题思路
方法一：迭代 BFS
只需要在每次 BFS 拓展时，将完整的层进行取出，存如独立数组后再加入答案。
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Deque<TreeNode> d = new ArrayDeque<>();
if (root != null) d.addLast(root);
List<List<Integer>> ans = new ArrayList<>();
while (!d.isEmpty()) {
int sz = d.size();
List<Integer> list = new ArrayList<>();
while (sz-- > 0) {
TreeNode t = d.pollFirst();
list.add(t.val);
if (t.left != null) d.addLast(t.left);
if (t.right != null) d.addLast(t.right);
}
ans.add(list);
}
return ans;
}
}- 时间复杂度：O(n)
- 空间复杂度：O(n)
方法二：递归 DFS
同理，可以使用「递归」来进行「层序遍历」。
此时我们需要借助「哈希表」来存储起来每一层的节点情况。
首先我们按照「中序遍历」的方式进行 DFS，同时在 DFS 过程中传递节点所在的深度（root 节点默认
在深度最小的第 000 层），每次处理当前节点时，通过哈希表获取所在层的数组，并将当前节点值追加
到数组尾部，同时维护一个最大深度 max，在 DFS 完成后，再使用深度范围 [0,max] 从哈希表中进行构
造答案。
class Solution {
Map<Integer, List<Integer>> map = new HashMap<>();
int max = -1;
public List<List<Integer>> levelOrder(TreeNode root) {
dfs(root, 0);
List<List<Integer>> ans = new ArrayList<>();
for (int i = 0; i <= max; i++) ans.add(map.get(i));
return ans;
}
void dfs(TreeNode root, int depth) {
if (root == null) return ;
max = Math.max(max, depth);
dfs(root.left, depth + 1);
List<Integer> list = map.getOrDefault(depth, new ArrayList<>());
list.add(root.val);
map.put(depth, list);
dfs(root.right, depth + 1);
}
}- 时间复杂度：O(n)
- 空间复杂度：O(n)
23. 彩灯装饰记录 III（中等）
23.1. 题目描述
23.2. 解题思路
方法一：层序遍历 + 双端队列
class Solution {
public List<List<Integer>> decorateRecord(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
if(root != null) queue.add(root);
while(!queue.isEmpty()) {
LinkedList<Integer> tmp = new LinkedList<>();
for(int i = queue.size(); i > 0; i--) {
TreeNode node = queue.poll();
if(res.size() % 2 == 0) tmp.addLast(node.val);
else tmp.addFirst(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
res.add(tmp);
}
return res;
}
}
方法二：层序遍历 + 双端队列（奇偶层逻辑分离）
class Solution {
public List<List<Integer>> decorateRecord(TreeNode root) {
Deque<TreeNode> deque = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
if(root != null) deque.add(root);
while(!deque.isEmpty()) {
// 打印奇数层
List<Integer> tmp = new ArrayList<>();
for(int i = deque.size(); i > 0; i--) {
// 从左向右打印
TreeNode node = deque.removeFirst();
tmp.add(node.val);
// 先左后右加入下层节点
if(node.left != null) deque.addLast(node.left);
if(node.right != null) deque.addLast(node.right);
}
res.add(tmp);
if(deque.isEmpty()) break; // 若为空则提前跳出
// 打印偶数层
tmp = new ArrayList<>();
for(int i = deque.size(); i > 0; i--) {
// 从右向左打印
TreeNode node = deque.removeLast();
tmp.add(node.val);
// 先右后左加入下层节点
if(node.right != null) deque.addFirst(node.right);
if(node.left != null) deque.addFirst(node.left);
}
res.add(tmp);
}
return res;
}
}
方法三：层序遍历 + 倒序
代码：
class Solution {
public List<List<Integer>> decorateRecord(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
if(root != null) queue.add(root);
while(!queue.isEmpty()) {
List<Integer> tmp = new ArrayList<>();
for(int i = queue.size(); i > 0; i--) {
TreeNode node = queue.poll();
tmp.add(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
if(res.size() % 2 == 1) Collections.reverse(tmp);
res.add(tmp);
}
return res;
}
}
24. 子结构判断（中等）
24.1. 题目描述
24.2. 解题思路
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
}
boolean recur(TreeNode A, TreeNode B) {
if(B == null) return true;
if(A == null || A.val != B.val) return false;
return recur(A.left, B.left) && recur(A.right, B.right);
}
}
25. 字母迷宫（中等）
25.1. 题目描述
25.2. 解题思路
方法一：回溯
class Solution {
public boolean wordPuzzle(char[][] grid, String word) {
int h = grid.length, w = grid[0].length;
boolean[][] visited = new boolean[h][w];
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
boolean flag = exist(grid, visited, i, j, word, 0);
if (flag) {
return true;
}
}
}
return false;
}
public boolean exist(char[][] grid, boolean[][] visited, int i, int j, String s, int k) {
if (grid[i][j] != s.charAt(k)) {
return false;
} else if (k == s.length() - 1) {
return true;
}
visited[i][j] = true;
int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
boolean result = false;
for (int[] dir : directions) {
int newi = i + dir[0], newj = j + dir[1];
if (newi >= 0 && newi < grid.length && newj >= 0 && newj < grid[0].length) {
if (!visited[newi][newj]) {
boolean flag = exist(grid, visited, newi, newj, s, k + 1);
if (flag) {
result = true;
break;
}
}
}
}
visited[i][j] = false;
return result;
}
}
26. 衣橱整理（中等）
26.1. 题目描述
26.2. 解题思路
方法一：广度优先搜索
class Solution {
public int wardrobeFinishing(int m, int n, int cnt) {
if (cnt == 0) {
return 1;
}
Queue<int[]> queue = new LinkedList<int[]>();
// 向右和向下的方向数组
int[] dx = {0, 1};
int[] dy = {1, 0};
boolean[][] vis = new boolean[m][n];
queue.offer(new int[]{0, 0});
vis[0][0] = true;
int ans = 1;
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int x = cell[0], y = cell[1];
for (int i = 0; i < 2; ++i) {
int tx = dx[i] + x;
int ty = dy[i] + y;
if (tx < 0 || tx >= m || ty < 0 || ty >= n || vis[tx][ty] || get(tx) + get(ty) > cnt) {
continue;
}
queue.offer(new int[]{tx, ty});
vis[tx][ty] = true;
ans++;
}
}
return ans;
}
private int get(int x) {
int res = 0;
while (x != 0) {
res += x % 10;
x /= 10;
}
return res;
}
}
方法二：递推
class Solution {
public int wardrobeFinishing(int m, int n, int cnt) {
if (cnt == 0) {
return 1;
}
boolean[][] vis = new boolean[m][n];
int ans = 1;
vis[0][0] = true;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if ((i == 0 && j == 0) || get(i) + get(j) > cnt) {
continue;
}
// 边界判断
if (i - 1 >= 0) {
vis[i][j] |= vis[i - 1][j];
}
if (j - 1 >= 0) {
vis[i][j] |= vis[i][j - 1];
}
ans += vis[i][j] ? 1 : 0;
}
}
return ans;
}
private int get(int x) {
int res = 0;
while (x != 0) {
res += x % 10;
x /= 10;
}
return res;
}
}
27. 寻找二叉搜索树中的目标节点（简单）
27.1. 题目描述
27.2. 解题思路
class Solution {
int res, cnt;
public int findTargetNode(TreeNode root, int cnt) {
this.cnt = cnt;
dfs(root);
return res;
}
void dfs(TreeNode root) {
if(root == null) return;
dfs(root.right);
if(cnt == 0) return;
if(--cnt == 0) res = root.val;
dfs(root.left);
}
}
28. 二叉树的最大深度（简单）
28.1. 题目描述
28.2. 解题思路
方法一：深度优先搜索
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
} else {
int leftHeight = maxDepth(root.left);
int rightHeight = maxDepth(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
}
}
方法二：广度优先搜索
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int ans = 0;
while (!queue.isEmpty()) {
int size = queue.size();
while (size > 0) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
size--;
}
ans++;
}
return ans;
}
}
29. 平衡二叉树
29.1. 题目描述
29.2. 解题思路
方法一：自顶向下的递归
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
} else {
return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
}
public int height(TreeNode root) {
if (root == null) {
return 0;
} else {
return Math.max(height(root.left), height(root.right)) + 1;
}
}
}
方法二：自底向上的递归
class Solution {
public boolean isBalanced(TreeNode root) {
return height(root) >= 0;
}
public int height(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = height(root.left);
int rightHeight = height(root.right);
if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
return -1;
} else {
return Math.max(leftHeight, rightHeight) + 1;
}
}
}
30. 设计机械累加器（中等）
30.1. 题目描述
30.2. 解题思路
方法一：递归
class Solution {
public int mechanicalAccumulator(int target) {
boolean flag = target > 0 && (target += mechanicalAccumulator(target - 1)) > 0;
return target;
}
}
方法二：快速乘
class Solution {
public int mechanicalAccumulator(int target) {
int ans = 0, A = target, B = target + 1;
boolean flag;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
flag = ((B & 1) > 0) && (ans += A) > 0;
A <<= 1;
B >>= 1;
return ans >> 1;
}
}
31. 组合总和 III（中等）
31.1. 题目描述
31.2. 解题思路
方法一：二进制（子集）枚举
class Solution {
List<Integer> temp = new ArrayList<Integer>();
List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> combinationSum3(int k, int n) {
for (int mask = 0; mask < (1 << 9); ++mask) {
if (check(mask, k, n)) {
ans.add(new ArrayList<Integer>(temp));
}
}
return ans;
}
public boolean check(int mask, int k, int n) {
temp.clear();
for (int i = 0; i < 9; ++i) {
if (((1 << i) & mask) != 0) {
temp.add(i + 1);
}
}
if (temp.size() != k) {
return false;
}
int sum = 0;
for (int num : temp) {
sum += num;
}
return sum == n;
}
}
方法二：组合枚举
class Solution {
List<Integer> temp = new ArrayList<Integer>();
List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> combinationSum3(int k, int n) {
dfs(1, 9, k, n);
return ans;
}
public void dfs(int cur, int n, int k, int sum) {
if (temp.size() + (n - cur + 1) < k || temp.size() > k) {
return;
}
if (temp.size() == k) {
int tempSum = 0;
for (int num : temp) {
tempSum += num;
}
if (tempSum == sum) {
ans.add(new ArrayList<Integer>(temp));
return;
}
}
temp.add(cur);
dfs(cur + 1, n, k, sum);
temp.remove(temp.size() - 1);
dfs(cur + 1, n, k, sum);
}
}
32. 位1的个数（简单）
32.1. 题目描述
32.2 解题思路
方法一：循环检查二进制位
public class Solution {
public int hammingWeight(int n) {
int ret = 0;
for (int i = 0; i < 32; i++) {
if ((n & (1 << i)) != 0) {
ret++;
}
}
return ret;
}
}
方法二：位运算优化
public class Solution {
public int hammingWeight(int n) {
int ret = 0;
while (n != 0) {
n &= n - 1;
ret++;
}
return ret;
}
}
33. 加密运算
33.1. 题目描述
33.2. 解题思路
代码：
class Solution {
public int encryptionCalculate(int dataA, int dataB) {
while(dataB != 0) { // 当进位为 0 时跳出
int c = (dataA & dataB) << 1; // c = 进位
dataA ^= dataB; // dataA = 非进位和
dataB = c; // dataB = 进位
}
return dataA;
}
}
34. 撞色搭配
34.1. 题目描述
34.2. 解题思路
方法一：分组异或
class Solution {
public int[] sockCollocation(int[] sockets) {
int ret = 0;
for (int n : sockets) {
ret ^= n;
}
int div = 1;
while ((div & ret) == 0) {
div <<= 1;
}
int a = 0, b = 0;
for (int n : sockets) {
if ((div & n) != 0) {
a ^= n;
} else {
b ^= n;
}
}
return new int[]{a, b};
}
}
35. 训练计划 VI
35.1. 题目描述
35.2. 解题思路
方法一：有限状态自动机
class Solution {
public int trainingPlan(int[] actions) {
int ones = 0, twos = 0;
for(int action : actions){
ones = ones ^ action & ~twos;
twos = twos ^ action & ~ones;
}
return ones;
}
}
方法二：遍历统计
class Solution {
public int trainingPlan(int[] actions) {
int[] counts = new int[32];
for(int action : actions) {
for(int i = 0; i < 32; i++) {
counts[i] += action & 1; // 更新第 i 位 1 的个数之和
action >>= 1; // 第 i 位 --> 第 i 位
}
}
int res = 0, m = 3;
for(int i = 31; i >= 0; i--) {
res <<= 1;
res |= counts[i] % m; // 恢复第 i 位
}
return res;
}
}
36. 比特位计数（简单）
36.1. 题目描述
36.2. 解题思路
方法一：Brian Kernighan 算法
class Solution {
public int[] countBits(int n) {
int[] bits = new int[n + 1];
for (int i = 0; i <= n; i++) {
bits[i] = countOnes(i);
}
return bits;
}
public int countOnes(int x) {
int ones = 0;
while (x > 0) {
x &= (x - 1);
ones++;
}
return ones;
}
}
方法二：动态规划——最高有效位
class Solution {
public int[] countBits(int n) {
int[] bits = new int[n + 1];
int highBit = 0;
for (int i = 1; i <= n; i++) {
if ((i & (i - 1)) == 0) {
highBit = i;
}
bits[i] = bits[i - highBit] + 1;
}
return bits;
}
}
方法三：动态规划——最低有效位
class Solution {
public int[] countBits(int n) {
int[] bits = new int[n + 1];
for (int i = 1; i <= n; i++) {
bits[i] = bits[i >> 1] + (i & 1);
}
return bits;
}
}
方法四：动态规划——最低设置位
class Solution {
public int[] countBits(int n) {
int[] bits = new int[n + 1];
for (int i = 1; i <= n; i++) {
bits[i] = bits[i & (i - 1)] + 1;
}
return bits;
}
}
37. 搜索推荐系统（中等）
37.1. 题目描述
37.2. 解题思路
方法一：排序 + 字典树 + 哈希表
class Solution {
int[][] tr = new int[20010][26];
int idx = 0;
Map<Integer, Integer> min = new HashMap<>(), max = new HashMap<>();
void add(String s, int num) {
int p = 0;
for (int i = 0; i < s.length(); i++) {
int u = s.charAt(i) - 'a';
if (tr[p][u] == 0) {
tr[p][u] = ++idx;
min.put(tr[p][u], num);
}
max.put(tr[p][u], num);
p = tr[p][u];
}
}
int[] query(String s) {
int a = -1, b = -1, p = 0;
for (int i = 0; i < s.length(); i++) {
int u = s.charAt(i) - 'a';
if (tr[p][u] == 0) return new int[]{-1, -1};
a = min.get(tr[p][u]); b = max.get(tr[p][u]);
p = tr[p][u];
}
return new int[]{a, b};
}
public List<List<String>> suggestedProducts(String[] ps, String w) {
Arrays.sort(ps);
List<List<String>> ans = new ArrayList<>();
for (int i = 0; i < ps.length; i++) add(ps[i], i);
for (int i = 0; i < w.length(); i++) {
List<String> list = new ArrayList<>();
int[] info = query(w.substring(0, i + 1));
int l = info[0], r = info[1];
for (int j = l; j <= Math.min(l + 2, r) && l != -1; j++) list.add(ps[j]);
ans.add(list);
}
return ans;
}
}
方法二：排序 + 二分
class Solution {
public List<List<String>> suggestedProducts(String[] ps, String w) {
Arrays.sort(ps);
int n = ps.length;
List<List<String>> ans = new ArrayList<>();
for (int i = 0; i < w.length(); i++) {
String cur = w.substring(0, i + 1);
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (ps[mid].compareTo(cur) >= 0) r = mid;
else l = mid + 1;
}
List<String> list = new ArrayList<>();
if (ps[r].compareTo(cur) >= 0) {
for (int j = r; j <= Math.min(n - 1, r + 2); j++) {
if (ps[j].length() < cur.length()) break;
if (!ps[j].substring(0, i + 1).equals(cur)) break;
list.add(ps[j]);
}
}
ans.add(list);
}
return ans;
}
}