fucking-algorithm
fucking-algorithm copied to clipboard
Published
20 hours ago •
labuladong
labuladong
回溯（DFS）算法解题套路框架 :: labuladong的算法小抄
合法了就做选择，做下一层决策，省了一个continue语句 ，这样好不好
for (int col = 0; col < n; col++) {
// 选择合法位置
if (isValid(board, row, col)) {
// 做选择
board[row][col] = 'Q';
// 进入下一行决策
backtrack(board, row + 1);
// 撤销选择
board[row][col] = '.';
}
}
合法了就做选择，做下一层决策，省了一个continue语句 ，这样好不好
continue的写法更好，guard clauses 参见这篇文章 https://betterprogramming.pub/refactoring-guard-clauses-2ceeaa1a9da
@xiangyueerli 因为这个 track 是一个外部引用，在遍历过程中track 中的数据会不断变化，所以装入 res 的时候应该把 track 里面的值做一次拷贝。Java 可以这样用 new 实现拷贝的效果，其他语言各有自己的方式。
【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;
}
}
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;
}
}
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));
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
左右斜和竖线都可以用数组记录是否已被占据，代码更简洁高效
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;
}
}
};
package leetcode.backtrack;
import java.util.LinkedList;
import java.util.List;
public class SolveNQueens51 {
List<List<String>> result = new LinkedList<>();//存放所有结果
public List<List<String>> solveNQueens(int n) {
//新建一个棋盘
List<String> board = new LinkedList<>();
StringBuilder stringBuilder = new StringBuilder();
//初始化棋盘 全部置空
stringBuilder.append(".".repeat(n));
for (int i = 0; i < n; i++) {
board.add(stringBuilder.toString());
}
backTrack(0,board);
return result;
}
/**
* @param board 棋盘情况
* @param row 当前游标处于第几行
* */
private void backTrack(int row,List<String> board){
//回溯终止条件
if (row == board.size()){//终止条件 递归到了最后一个行 直接跳出
result.add(new LinkedList<>(board));//将目前的结果中的添加到result中
return;
}
int n = board.get(row).length();//获取当前游标所在的行的 String长度
//开始穷举 从 当前行的 第0 列开始 处理节点
for (int col = 0; col < n ; col++) {
//处理节点 （检查节点合法性 ， 如果合法 ）
if (!isValid(row,col,board)){//检查 当前行 的 所有列的节点是否合法
continue;//如果不合法直接跳过
}
String str = board.get(row).substring(0,col) + 'Q' + board.get(row).substring(col+1);
board.set(row,str);//将上述的替换后的String 代替到 游标所在的row
//递归 深入子树
backTrack(row+1,board);//对深入的下一行进行递归操作
//回溯 ，撤销处理结果
str = board.get(row).substring(0,col) + '.' + board.get(row).substring(col+1);
board.set(row,str);
}
}
/**
* @param row // 检查游标 目前 所有在的行位置
* @param column //检查游标 目前的 所在的列位置
* @param board //当前的棋盘状态
* @apiNote 判断是否当前位置是否合法
* */
private boolean isValid(int row,int column,List<String> board){
int n = board.size();
//判断列位置是否合法
for (int i = 0; i < n; i++) {
if (board.get(i).charAt(column) == 'Q'){//第 i行 第 column 列 的字符
return false;
}
}
//判断是否与右上方发生冲突
for (int i = row -1,j = column + 1; i >= 0 && j < n; i--,j++ ) {
if (board.get(i).charAt(j) == 'Q'){
return false;
}
}
//判断 是否与 左上方冲突
for (int i = row -1,j = column -1 ; i >=0 && j>=0 ; i--,j--) {
if (board.get(i).charAt(j) == 'Q'){
return false;
}
}
return true;
}
}
同列判断用y记录，斜线判断xdy，xay PS：开200 是为了防止出现负数下标
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
typedef vector<string> vs;
vector<vs>ans;
vs path(n,string(n,'.'));
bool y[10]={0},xdy[200]={0},xay[200]={0};
function<void(int)>backtrack=[&](int row){
if(row==n){
ans.push_back(path);
return ;
}
for(int i=0;i<n;i++){
if(xdy[row-i+100]||xay[row+i]||y[i])continue;
path[row][i]='Q';
xdy[row-i+100]=1,xay[row+i]=1,y[i]=1;
backtrack(row+1);
xdy[row-i+100]=0,xay[row+i]=0,y[i]=0;
path[row][i]='.';
}
};
backtrack(0);
return ans;
}
};
java版，用二维char数组来表示棋盘
class Solution {
List<List<String>> result = new ArrayList<>();
char[][] board = null;
public List<List<String>> solveNQueens(int n) {
board = new char[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = '.';
}
}
solve(n, 0);
return result;
}
private void solve(int n, int rowNum) {
if (rowNum == n) {
List<String> boardResult = new ArrayList<>(n);
for (char[] row : board) {
boardResult.add(new String(row));
}
result.add(boardResult);
return;
}
for (int col = 0; col < n; col++) {
if (isValid(rowNum, col, n)) {
board[rowNum][col] = 'Q';
solve(n, rowNum + 1);
board[rowNum][col] = '.';
}
}
}
private boolean isValid(int rowNum, int col, int n) {
// 检查行
for (int i = 0; i < rowNum; i++) {
if (board[i][col] == 'Q') {
return false;
}
}
// 检查列
for (int i = 0; i < n; i++) {
if (i != col && board[rowNum][i] == 'Q') {
return false;
}
}
// 检查左上
int i = rowNum - 1;
int j = col - 1;
while (i >= 0 && j >= 0) {
if (board[i][j] == 'Q') {
return false;
}
i--;
j--;
}
// 检查右上
i = rowNum - 1;
j = col + 1;
while (i >= 0 && j < n) {
if (board[i][j] == 'Q') {
return false;
}
i--;
j++;
}
return true;
}
}
全排列js版本
/**
* @param {number[]} nums
* @return {number[][]}
*/
var res = [];
var permute = function (nums) {
const backtrack = (nums, track, used) => {
if (nums.length === track.length) {
res.push(track.slice());
return;
}
const length = nums.length;
for (let i = 0; i < length; i++) {
if (used[i]) {
continue;
}
track.push(nums[i]);
used[i] = true;
backtrack(nums, track, used);
used[i] = false;
track.pop();
}
};
const track = [],
used = new Array(nums.length);
backtrack(nums, track, used);
return res;
};
@TimurJiangShan 回溯算法就是单纯的穷举所有可能性，然后从所有可能的结果中选择出真正满足条件的结果。那么每找到一个结果后，需要把之前做的选择撤销掉，然后才能去寻找新的结果。
// 提交一份 Golang的写法
func solveNQueens(n int) [][]string {
return NBoard(n)
}
func Board(n int, str string) [][]string {
res := make([][]string, n)
for i, _ := range res {
// 第二维数组数据填
v2 := make([]string, n)
for j, _ := range v2 {
v2[j] = str
}
res[i] = v2
}
return res
}
func NBoard(n int) [][]string {
res := make([][]string, 0, n)
// 结果集初始化
for i, _ :=range res {
res[i] = make([]string, 0, n)
}
var dfs func(board [][]string, row int)
dfs = func(board [][]string, row int) {
// 结束条件,row的长度等于board长度
if row == len(board) {
// 复制这个数组
res1 := make([]string,0, n)
for i := 0 ;i <n ; i++ {
//RowTemp := make([]string, n)
//copy(RowTemp, board[i])
res1 = append(res1, strings.Join(board[i], ""))
}
res = append(res, res1)
return
}
// 获取当前棋盘的列数量
n := len(board[row])
// 对该列进行遍历
for col := 0 ; col < n ; col++ {
// 排除不合法的选择
if !IsVaild(board, row, col) {
continue
}
// 做选择
board[row][col] = "Q"
// 进行下一项决策
dfs(board, row+1)
// 撤销选择
board[row][col] = "."
}
}
board := Board(n, ".")
dfs(board, 0)
return res
}
// 判断当前位置是否可以放置皇后
func IsVaild(board [][]string, row ,col int) bool {
// 获取棋盘的宽度
n := len(board)
// 检查该列是否有皇后冲突
for i :=0 ; i < n; i ++ {
if board[i][col] == "Q" {
return false
}
}
// 检查左上角是否有冲突，遍历条件行减列减
i := row - 1
j := col -1
for i >= 0 && j >= 0 {
if board[i][j] == "Q" {
return false
}
i--
j--
}
// 检查右上角是否有冲突，遍历条件行减列加
i1 := row -1
j1 := col + 1
for i1 >= 0 && j1 < n {
if board[i1][j1] == "Q" {
return false
}
i1--
j1++
}
return true
}
请问什么时候用List 什么时候用LinkedList？ 这儿两个data structure有什么优劣吗
关于这个问题，建议先去好好复习一下java，这里简单讲述一下： 一个是抽象接口，一个是具体实现类，这里是体现了多态而已，建议回去好好再复习一下java容器相关。
N皇后 ==Java版本== 感谢东哥
class Solution {
List<List<String>> res = new LinkedList<>();
public List<List<String>> solveNQueens(int n) {
List<StringBuffer> board = new ArrayList<>();
StringBuffer sb = new StringBuffer();
for (int i = 0; i < n; i++) {
sb.append(".");
}
// 初始化空棋盘
for (int i = 0; i < n; i++) {
board.add(new StringBuffer(sb.toString()));
}
backtrack(board, 0);
return res;
}
void backtrack(List<StringBuffer> board, int row) {
int n = board.size();
if (n == row) {
List<String> t = new ArrayList<>();
for (StringBuffer s : board) {
t.add(s.toString());
}
res.add(t);
return;
}
int x = board.size();
for (int col = 0; col < x; col++) {
if (!isVaild(board, row, col)) {
// 不合法的选择
continue;
}
board.get(row).replace(col, col + 1, "Q");
backtrack(board, row + 1);
board.get(row).replace(col, col + 1, ".");
}
}
// 是否可以在 row col 放置皇后
boolean isVaild(List<StringBuffer> board, int row, int col) {
int n = board.size();
// 检查列
for (int i = 0; i < n; i++) {
if (board.get(i).charAt(col) == 'Q') {
return false;
}
}
// 检查右上方
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board.get(i).charAt(j) == 'Q') {
return false;
}
}
// 检查左上方
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board.get(i).charAt(j) == 'Q') {
return false;
}
}
return true;
}
}
