今日主题：回溯。
回溯算法的模板
image.png
其中，
1、路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也无法再做选择的条件
46. 全排列
问题描述
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
解题思路
路径：track，表示全排列的一种情况
选择列表：choices，nums数组中未被排列的元素
结束条件：choices为空，所有的元素均已被排列
做选择：从选择列表中拿出一个元素、将其加入路径
代码实现
class Solution {
private List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> permute(int[] nums) {
LinkedList<Integer> track = new LinkedList<>();
List<Integer> choices = new ArrayList<>();
for(int num : nums){
choices.add(num);
}
backtrack(choices,track);
return res;
}
//路径：track
//选择列表：choices
//结束条件：choices为空
//做选择：元素移出选择列表、加入路径
public void backtrack(List<Integer> choices, LinkedList<Integer> track){
if(choices.size() == 0){
res.add(new LinkedList(track));
return;
}
for(int i = 0; i < choices.size(); i++){
int temp = choices.get(i);
//做选择
track.add(temp);
choices.remove(i);
backtrack(choices,track);
//撤销选择
track.removeLast();
choices.add(i,temp);
}
}
}
47. 全排列 II
问题描述
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
解题思路
解决此题的关键在于如何去除结果中的重复全排列。
经过观察，产生重复全排列的情况是，进入回溯函数的路径列表与选择列表相同。
因此，在做选择之前，判断是否已经有与当前元素相同的元素进入过递归回溯，如果有，则进行剪枝。
代码实现
class Solution {
private List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
LinkedList<Integer> track = new LinkedList<>();
//对数组进行升序排列
Arrays.sort(nums);
List<Integer> choices = new ArrayList<>();
for(int num : nums){
choices.add(num);
}
backtrack(choices,track);
return res;
}
//路径：track
//选择列表：choices
//结束条件：choices为空
//做选择：元素移出选择列表、加入路径
public void backtrack(List<Integer> choices, LinkedList<Integer> track){
if(choices.size() == 0){
res.add(new LinkedList(track));
return;
}
for(int i = 0; i < choices.size(); i++){
if(i > 0 && choices.get(i) == choices.get(i - 1)){
//排除当前元素与上一个元素相同的选择，因为得到的路径是重复的
continue;
}
int temp = choices.get(i);
//做选择
track.add(temp);
choices.remove(i);
backtrack(choices,track);
//撤销选择
track.removeLast();
choices.add(i,temp);
}
}
}
51. N 皇后
问题描述
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
解题思路
路径：track，前row-1行的皇后已被正确放置
选择列表：第row行的n个格子
结束条件：row == n
做选择：将皇后放入格子中
代码实现
class Solution {
private List<List<String>> res = new LinkedList<>();
private String blankRow;
public List<List<String>> solveNQueens(int n) {
ArrayList<String> track = new ArrayList<>(n);
//初始化n个空格组成的空行blankRow"......"
StringBuilder sb = new StringBuilder();
for(int i = 0 ; i < n; i++){
sb.append(".");
}
blankRow = sb.toString();
//初始化棋盘，每个格子都填上空位
for(int i = 0 ; i < n; i++){
//初始化n个空行组成的棋盘
track.add(blankRow);
}
backtrack(0,track);
return res;
}
//路径：track，前row-1行的皇后已被正确放置
//选择列表：第row行的n个格子
//结束条件：row == n
//做选择：将皇后放入格子中
public void backtrack(int row, ArrayList<String> track){
System.out.println(row);
if(row == track.size()){
System.out.println("+");
res.add(new ArrayList(track));
return;
}
for(int col = 0; col < track.size(); col++){
//剪枝
if(beAttacked(track,row,col)){
System.out.println("剪枝");
continue;
}
//做选择
StringBuilder sb = new StringBuilder();
for(int i = 0 ; i < track.size(); i++){
if(i == col){
sb.append("Q");
}else{
sb.append(".");
}
}
//System.out.println(sb.toString());
track.set(row,sb.toString());
backtrack(row + 1, track);
//撤销选择
track.set(row, blankRow);
}
}
//判断棋盘中皇后是否会相互攻击
public boolean beAttacked(ArrayList<String> track, int row, int col){
//1.上述放置方法保证了，每行只有一个皇后，所以横行攻击不会出现
//2.判断是否会有纵行攻击
for(int i = 0; i < track.size(); i++){
if('Q' == track.get(i).charAt(col)){
return true;
}
}
//3.判断是否会有右上角斜线攻击
for(int m = row - 1, n = col + 1; m >= 0 && n < track.size(); m--,n++){
if('Q' == track.get(m).charAt(n)){
return true;
}
}
//4.判断是否会有左上角斜线攻击
for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--,j-- ){
if('Q' == track.get(i).charAt(j)){
return true;
}
}
return false;
}
}
第一次写hard级别的题，debug两个多小时，也是醉了......流下了小辣鸡的眼泪（=.=）
(但是npy快睡了爬起来陪我一起debug，内心得到了一丝安慰嘻嘻嘻嘻
网友评论