回溯（DFS）算法解题套路框架 :: labuladong的算法小抄 #1013
Replies: 89 comments 16 replies
-
|
合法了就做选择，做下一层决策，省了一个continue语句 ，这样好不好 for (int col = 0; col < n; col++) {
// 选择合法位置
if (isValid(board, row, col)) {
// 做选择
board[row][col] = 'Q';
// 进入下一行决策
backtrack(board, row + 1);
// 撤销选择
board[row][col] = '.';
}
} |
Beta Was this translation helpful? Give feedback.
-
|
没啥区别 |
Beta Was this translation helpful? Give feedback.
-
|
有啥区别 |
Beta Was this translation helpful? Give feedback.
-
|
这种写法习惯会容易造成if层数嵌套太多 |
Beta Was this translation helpful? Give feedback.
-
|
不好，代码尽量避免嵌套结构 |
Beta Was this translation helpful? Give feedback.
-
|
@tinyhare 一样的 |
Beta Was this translation helpful? Give feedback.
-
|
意思是一样的 |
Beta Was this translation helpful? Give feedback.
-
|
请问N皇后问题，[".Q...","...Q.","Q....","....Q","..Q.."]满不满足条件 |
Beta Was this translation helpful? Give feedback.
-
continue的写法更好，guard clauses |
Beta Was this translation helpful? Give feedback.
-
|
东哥东哥,res.add(new LinkedList(track)); 改成res.add(track);怎么就不对了呢 |
Beta Was this translation helpful? Give feedback.
-
|
为什么这里是new LinkedList(track)，是因为后面取消选择的时候会removeLast，最终会把当前track元素都移除掉，导致最后添加进去的数组都是空的 |
Beta Was this translation helpful? Give feedback.
-
|
@xiangyueerli 因为这个 |
Beta Was this translation helpful? Give feedback.
-
|
写python得时候 就是因为忘记 深拷贝一下，导致debug了很久 |
Beta Was this translation helpful? Give feedback.
-
|
妙啊 |
Beta Was this translation helpful? Give feedback.
-
|
N皇后有java版本嘛 |
Beta Was this translation helpful? Give feedback.
-
|
flip是异或, 第一次写入, 第二次擦除. 看力扣解数独的解法改的. class Solution {
List<List<String>> res;
char[] ch;
int slash;
int div;
int vertical;
public List<List<String>> solveNQueens(int n) {
res = new ArrayList<>();
ch = new char[n];
Arrays.fill(ch, '.');
backtrack(new LinkedList<>(), n, 0);
return res;
}
void backtrack(LinkedList<String> board, int n, int i) {
if (n == i) {
res.add(new ArrayList<>(board));
return;
}
char[] clone = ch.clone();
int a, b, c;
for (int j = 0; j < n; j++) {
if ((vertical & (a = 1 << j)) != 0 ||
(slash & (b = 1 << i - j + n)) != 0 ||
(div & (c = 1 << (n << 1) - i - j)) != 0) {
continue;
}
clone[j] = 'Q';
board.add(new String(clone));
flip(a, b, c);
backtrack(board, n, i + 1);
board.removeLast();
flip(a, b, c);
clone[j] = '.';
}
}
void flip(int a, int b, int c) {
vertical ^= a;
slash ^= b;
div ^= c;
}
} |
Beta Was this translation helpful? Give feedback.
-
class Solution {
List<List<String>> res;
char[] ch;
int slash;
int div;
int vertical;
String[] stack;
int top;
public List<List<String>> solveNQueens(int n) {
res = new ArrayList<>();
ch = new char[n];
stack = new String[n];
Arrays.fill(ch, '.');
backtrack(n, 0);
return res;
}
void backtrack(int n, int i) {
if (n == i) {
String[] clone = stack.clone();
res.add(Arrays.asList(clone));
return;
}
char[] clone = ch.clone();
int a, b, c, digit;
for (int mask = ~vertical & (1 << n) - 1; mask != 0; mask ^= digit) {
digit = mask & (-mask);
int j = Integer.bitCount(digit - 1);
if ((vertical & (a = 1 << j)) != 0 ||
(slash & (b = 1 << i - j + n)) != 0 ||
(div & (c = 1 << (n << 1) - i - j)) != 0) {
continue;
}
clone[j] = 'Q';
stack[top++] = new String(clone);
flip(a, b, c);
backtrack(n, i + 1);
top--;
flip(a, b, c);
clone[j] = '.';
}
}
void flip(int a, int b, int c) {
vertical ^= a;
slash ^= b;
div ^= c;
}
} |
Beta Was this translation helpful? Give feedback.
-
public class $51 {
public final static List<List<String>> res = new ArrayList<>();
public static List<List<String>> solveNQueens(int n) {
char[][] board = new char[n][n];
for (char[] row : board) {
Arrays.fill(row, '.');
}
backtrack(board, 0);
return res;
}
public static void backtrack(char[][] board, int row) {
if(row == board.length) {
res.add(Arrays.stream(board).map(String::valueOf).collect(Collectors.toList()));
return;
}
int length = board[row].length;
for (int i = 0; i < length; i++) {
if(!isValid(board, row, i)) continue;
board[row][i] = 'Q';
backtrack(board, row + 1);
board[row][i] = '.';
}
}
public static boolean isValid(char[][] board, int row, int col) {
// 检查列
for (int i = 0; i < row; i++) {
if(board[i][col] == 'Q') {
return false;
}
}
// 检查左上是否冲突
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if(board[i][j] == 'Q') {
return false;
}
}
// 检查右上
for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
if(board[i][j] == 'Q') {
return false;
}
}
return true;
}
public static void main(String[] args) {
List<List<String>> lists = solveNQueens(1);
for (List<String> list : lists) {
for (String s : list) {
System.out.println(s);
}
System.out.println("------------------");
}
System.out.println(lists.size());
}
} |
Beta Was this translation helpful? Give feedback.
-
|
【Java版】不过我可能写得有点麻烦了，都是用的笨办法操作字符串😄 class Solution {
List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
ArrayList<String> board = new ArrayList<>();
StringBuilder sb = new StringBuilder();
for(int i = 0; i < n; i++){
sb.append('.');
}
for(int i = 0; i < n; i++){
board.add(sb.toString());
}
backtrack(board, 0);
return res;
}
private void backtrack(ArrayList<String> board, int row){
if(row == board.size()){
res.add(new ArrayList<>(board));
return;
}
int n = board.get(row).length();
for(int col = 0; col < n; col++){
if(!isValid(board, row, col)){
continue;
}
String r = board.remove(row);
StringBuilder sb = new StringBuilder(r);
sb.replace(col, col+1, "Q");
board.add(row, sb.toString());
backtrack(board, row+1);
r = board.remove(row);
sb = new StringBuilder(r);
sb.replace(col, col+1, ".");
board.add(row, sb.toString());
}
}
private boolean isValid(ArrayList<String> board, int row, int col){
int n = board.size();
for(int i = 0; i < n; i++){
String r = board.get(i);
if(r.charAt(col) == 'Q'){
return false;
}
}
for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--,j++){
String r = board.get(i);
if(r.charAt(j) == 'Q'){
return false;
}
}
for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){
String r = board.get(i);
if(r.charAt(j) == 'Q'){
return false;
}
}
return true;
}
} |
Beta Was this translation helpful? Give feedback.
-
|
优雅，永不过时！ public class $51 {
public final static List<List<String>> res = new ArrayList<>();
public static List<List<String>> solveNQueens(int n) {
char[][] board = new char[n][n];
for (char[] row : board) {
Arrays.fill(row, '.');
}
backtrack(board, 0);
return res;
}
public static void backtrack(char[][] board, int row) {
if(row == board.length) {
res.add(Arrays.stream(board).map(String::valueOf).collect(Collectors.toList()));
return;
}
int length = board[row].length;
for (int i = 0; i < length; i++) {
if(!isValid(board, row, i)) continue;
board[row][i] = 'Q';
backtrack(board, row + 1);
board[row][i] = '.';
}
}
public static boolean isValid(char[][] board, int row, int col) {
// 检查列
for (int i = 0; i < row; i++) {
if(board[i][col] == 'Q') {
return false;
}
}
// 检查左上是否冲突
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if(board[i][j] == 'Q') {
return false;
}
}
// 检查右上
for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
if(board[i][j] == 'Q') {
return false;
}
}
return true;
}
public static void main(String[] args) {
List<List<String>> lists = solveNQueens(1);
for (List<String> list : lists) {
for (String s : list) {
System.out.println(s);
}
System.out.println("------------------");
}
System.out.println(lists.size());
}
} |
Beta Was this translation helpful? Give feedback.
-
class Solution {
List<List<String>> res = new ArrayList<>();
/* 输入棋盘的边长n，返回所有合法的放置 */
public List<List<String>> solveNQueens(int n) {
// "." 表示空，"Q"表示皇后，初始化棋盘
char[][] board = new char[n][n];
for (char[] c : board) {
Arrays.fill(c, '.');
}
backtrack(board, 0);
return res;
}
public void backtrack(char[][] board, int row) {
// 每一行都成功放置了皇后，记录结果
if (row == board.length) {
res.add(charToList(board));
return;
}
int n = board[row].length;
// 在当前行的每一列都可能放置皇后
for (int col = 0; col < n; col++) {
// 排除可以相互攻击的格子
if (!isValid(board, row, col)) {
continue;
}
// 做选择
board[row][col] = 'Q';
// 进入下一行放皇后
backtrack(board, row + 1);
// 撤销选择
board[row][col] = '.';
}
}
/* 判断是否可以在 board[row][col] 放置皇后 */
public boolean isValid(char[][] board, int row, int col) {
int n = board.length;
// 检查列是否有皇后冲突
for (int i = 0; i < n; i++) {
if (board[i][col] == 'Q') {
return false;
}
}
// 检查右上方是否有皇后冲突
for (int i = row - 1, j = col + 1; i >=0 && j < n; i--, j++) {
if (board[i][j] == 'Q') {
return false;
}
}
// 检查左上方是否有皇后冲突
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') {
return false;
}
}
return true;
}
public List charToList(char[][] board) {
List<String> list = new ArrayList<>();
for (char[] c : board) {
list.add(String.copyValueOf(c));
}
return list;
}
} |
Beta Was this translation helpful? Give feedback.
-
|
js 版本，利用闭包，省去了很多中间变量。 /* 输入棋盘边长 n，返回所有合法的放置 */
function solveNQueens(n) {
// '.' 表示空，'Q' 表示皇后，初始化空棋盘。
const board = new Array(n).fill(0).map(() => new Array(n).fill("."));
const res = [];
backtrack(0);
return res;
function isValid(row, col) {
// 检查列是否有皇后互相冲突
for (let i = 0; i < n; i++) {
if (board[i][col] === "Q") return false;
}
// 检查右上方是否有皇后互相冲突
for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] === "Q") return false;
}
// 检查左上方是否有皇后互相冲突
for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] === "Q") return false;
}
return true;
}
// 路径：board 中小于 row 的那些行都已经成功放置了皇后
// 选择列表：第 row 行的所有列都是放置皇后的选择
// 结束条件：row 超过 board 的最后一行
function backtrack(row) {
// 触发结束条件;
if (row === board.length) {
res.push(board.map((row) => row.join("")));
return;
}
for (let col = 0; col < n; col++) {
// 排除不合法选择;
if (!isValid(row, col)) {
continue;
}
// 做选择;
board[row][col] = "Q";
// 进入下一行决策;
backtrack(row + 1);
// 撤销选择;
board[row][col] = ".";
}
}
}
console.log(solveNQueens(4)); |
Beta Was this translation helpful? Give feedback.
-
|
Python3版本 class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
result = []
board = []
for i in range(n):
board.append(['.'] * n)
def isValid(row, col):
# 检查列是否有皇后
for i in range(n):
if board[i][col] == 'Q':
return False
# 检查右上方是否有皇后
i = row - 1
j = col + 1
while i >= 0 and j < n:
if board[i][j] == 'Q':
return False
i -= 1
j += 1
# 检查左上方是否有皇后
i = row - 1
j = col - 1
while i >= 0 and j >= 0:
if board[i][j] == 'Q':
return False
i -= 1
j -= 1
return True
def backtrack(row):
# 超出左后一行
if row == n:
result.append([''.join(b) for b in board])
return
for col in range(n):
# 排除不合法选择
if not isValid(row, col):
continue
# 做选择
board[row][col] = 'Q'
# 进入下一秒决策
backtrack(row + 1)
# 撤销选择
board[row][col] = '.'
backtrack(0)
return result |
Beta Was this translation helpful? Give feedback.
-
|
左右斜和竖线都可以用数组记录是否已被占据，代码更简洁高效 class Solution {
public:
vector<vector<string>> res;
vector<vector<string>> solveNQueens(int n) {
/*左斜编号由board[n-1][0]->l[0]，往右上依次记录每条斜线,右斜由[0][0]->[0]往下*/
vector<bool> colflag(n,false),ldiag(2*n-1,false),rdiag(2*n-1,false);
vector<string> board(n,string(n,'.'));
backtrack(board,n,0,colflag,ldiag,rdiag);
return res;
}
void backtrack(vector<string>& board,int n,int row,vector<bool>& colflag,vector<bool>&ldiag,vector<bool>&rdiag){
if(row==n){res.push_back(board);return;}
for(int col=0;col<n;col++){
if(colflag[col]||ldiag[n-1-row+col]||rdiag[row+col])continue;
board[row][col]='Q';
colflag[col]=ldiag[n-1-row+col]=rdiag[row+col]=true;
backtrack(board,n,row+1,colflag,ldiag,rdiag);
board[row][col]='.';
colflag[col]=ldiag[n-1-row+col]=rdiag[row+col]=false;
}
}
}; |
Beta Was this translation helpful? Give feedback.
-
|
东哥YYDS！ |
Beta Was this translation helpful? Give feedback.
-
|
感谢大佬的backtrack框架！ |
Beta Was this translation helpful? Give feedback.
-
二刷打卡 |
Beta Was this translation helpful? Give feedback.
-
|
打卡 看得太舒服了 |
Beta Was this translation helpful? Give feedback.
-
|
for (int i = row - 1; i >= 0; i--) {
if (board[i][col] == 'Q')
return false;
} |
Beta Was this translation helpful? Give feedback.
-
|
可以这样写，就一致了。并且更简洁些。 # check the diagonal (top left to bottom right)
for i, j in zip(range(row), range(col)):
if board[i][j] == 'Q':
return False 好像本页面使用的 giscus，没有修改自己评论的功能？ |
Beta Was this translation helpful? Give feedback.
-
|
My bad。上面的代码还是应该写成（倒着查）： # check the diagonal (top left to bottom right)
for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
if board[i][j] == 'Q':
return False |
Beta Was this translation helpful? Give feedback.
-
|
在检查 column 是否有冲突的时候，应该不需要 loop 到 row，到 row-1 就够了 # check the column
for i in range(row):
if board[i][col] == 'Q':
return False |
Beta Was this translation helpful? Give feedback.
-
|
回溯算法是在遍历「树枝」，DFS 算法是在遍历「节点」，总结的太好了 |
Beta Was this translation helpful? Give feedback.
-
|
牛逼，赞了 |
Beta Was this translation helpful? Give feedback.
-
|
可视化动画太赞了！ |
Beta Was this translation helpful? Give feedback.
-
|
52、N皇后II Python版本打卡 class Solution:
def totalNQueens(self, n: int) -> int:
self.res=0
temp=[['.']*n for _ in range(n)]
self.backtrack(n,0,temp)
return self.res
def backtrack(self,n,row,temp):
#结束条件
if row==n:
self.res+=1
for col in range(n):
if not self.isValid(row,col,temp,n):
continue
temp[row][col]='Q'
self.backtrack(n,row+1,temp)
temp[row][col]='.'
def isValid(self,row,col,temp,n):
#判断上方是否有皇后出没
for r in range(row):
if temp[r][col]=='Q':
return False
#判断左上方是否有皇后出没
r1,c1=row-1,col-1
while r1>=0 and c1>=0:
if temp[r1][c1]=='Q':
return False
r1-=1
c1-=1
#判断右上方是否有皇后出没
r2,c2=row-1,col+1
while r2>=0 and c2<n:
if temp[r2][c2]=='Q':
return False
r2-=1
c2+=1
return True |
Beta Was this translation helpful? Give feedback.
-
|
判断列上边是否有皇后，感觉不需要小于n，小于当前层row就可以了，和不用判断左下右下一个原因 |
Beta Was this translation helpful? Give feedback.
-
|
请问一下大家，对于这个问题，有没有一个比较好记忆的理解： 这个回溯的时候，添加和去除是在for循环里面，但是前文中图算法中的环检测（course schedule）的题中，添加和去除是在for循环外面的。不是很理解，为什么一个在里面，一个在外面。单看每一种算法，我可以理解，但是为什么两个问题的处理方法不一样呢？谢谢大家！ |
Beta Was this translation helpful? Give feedback.
-
这里直接小于row,第row行不用判断，对不对？因为就是要放到这一行的 |
Beta Was this translation helpful? Give feedback.
-
|
每次写backtracking没啥问题，但一问complexity就卡壳，尤其是变种题或者有直接数学方法求组合数的题 |
Beta Was this translation helpful? Give feedback.
-
|
邮件已收到，谢谢。
华南理工大学2015级控制理论与控制工程 徐将将 tel：13560349491（629491） 地址：华工（五三
|
Beta Was this translation helpful? Give feedback.
-
|
在 “全排列问题” 的 C++ 解题方案中，作者用的是 譬如对于下面的代码： std::vector<bool> a = { false, true, false };
auto b = a[0];
bool c = a[0];对于变量 当然就 LeetCode 而言，这样用并不会报错，但是仍然不推荐这样使用。如果想使用 |
Beta Was this translation helpful? Give feedback.
and others
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
文章链接点这里：回溯（DFS）算法解题套路框架
评论礼仪 见这里，违者直接拉黑。
Beta Was this translation helpful? Give feedback.
All reactions