第一题:力扣46题
解题思路:
排序问题作为一个典型的回溯问题,其实和组合问题、回文字符串问题都有着密切的联系,只不过排序问题是有序的,这里在代码中给有详细注释。
代码如下:
class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> permute(int[] nums) {
boolean[] used = new boolean[nums.length];
backTracking(nums, used);
return res;
}
private void backTracking(int[] nums, boolean[] used) {
//终止条件
if(path.size() == nums.length) {
res.add(new ArrayList<>(path));
return;
}
//单例循环
//为什么i从0开始,而不是定义一个startIndex呢?因为这个是排列,[1,2] 和 [2,1]是不一样的
for(int i = 0; i < nums.length; i++) {
if(used[i] == true) {
continue;
}
used[i] = true;
path.add(nums[i]);
backTracking(nums, used);
path.removeLast();
used[i] = false;
}
}
}
该题的升级版(所给数组中的元素是有重复的):力扣47题
思路:
那就是要去重呗!去重条件在代码中写的很清楚,这也是与上一个题的区别所在。我这里想说的是 去重为什么要先给数组排个序呢?我查了很多人写的版本,我是这么理解的===>去重的时候比较的是相邻数组元素,排序就是为了让相同的元素排在一起,这样才能达到去重的目的。
代码如下:
class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
boolean[] used = new boolean[nums.length];
//为什么要先对数组进行排序呢?
Arrays.sort(nums);
backTracking(nums, used);
return res;
}
private void backTracking(int[] nums, boolean[] used) {
//终止条件
if(path.size() == nums.length) {
res.add(new ArrayList<>(path));
return;
}
//单例循环
//为什么i从0开始,而不是定义一个startIndex呢?因为这个是排列,[1,2] 和 [2,1]是不一样的
for(int i = 0; i < nums.length; i++) {
//每层有重复,跳过
if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
}
if(used[i] != true) {
used[i] = true;
path.add(nums[i]);
backTracking(nums, used);
path.removeLast();
used[i] = false;
}
}
}
}
第二题:力扣51题
解题思路:
N皇后问题的结果 其实也是 找树的叶子节点,那么也就和之前的回溯问题类似了。
我们需要把棋盘做出来,之后从每行开始遍历每一列。
代码如下:
class Solution {
List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
//定义一个棋盘
char[][] chessBoard = new char[n][n];
//把棋盘初始化
for(char[] c : chessBoard) {
Arrays.fill(c, '.');
}
backTracking(n, 0, chessBoard);
return res;
}
//递归回溯棋盘
private void backTracking(int n, int row, char[][] chessBoard) {
//终止条件
if(row == n) {
res.add(Array2List(chessBoard));
return;
}
//递归过程
for(int col = 0; col < n; col++) {
if(isValid(row, col, chessBoard, n)) {
chessBoard[row][col] = 'Q';
backTracking(n, row + 1, chessBoard);
chessBoard[row][col] = '.';
}
}
}
//将二维数组转换成List
public List Array2List(char[][] chessBoard) {
List<String> list = new ArrayList<>();
for (char[] c : chessBoard) {
list.add(String.copyValueOf(c));
}
return list;
}
//判断是不是有效的放置方案
private boolean isValid(int row, int col, char[][] chessBoard, int n) {
//有三种情况是无效的: 1. 同一行不行 2. 同一列不行 3. 同一对角线不行
//排除情况2
for(int i = 0; i < n; i++) {
if(chessBoard[i][col] == 'Q') {
return false;
}
}
//排除情况3
for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if(chessBoard[i][j] == 'Q') {
return false;
}
}
for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if(chessBoard[i][j] == 'Q') {
return false;
}
}
return true;
}
}
还有一个难题,可以挑战一下:
力扣37题
回溯问题暂时就刷这么多题吧!刷不动了,累了