LeetCode 回溯篇(46、51)

46. 全排列

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

solution1

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> permute(int[] nums) {
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(nums,track);
        return res;
    }
    public void backtrack(int[] nums, LinkedList<Integer> track){
        //满足结束条件
        if (track.size() == nums.length){
            res.add(new LinkedList(track));
            return;
        }
        for (int i = 0; i < nums.length; i++){
            if(track.contains(nums[i])) continue;
            // 路径选择
            track.add(nums[i]);
            backtrack(nums,track);
            // 撤销选择
            track.removeLast();
        }
    }
}
//回溯模版 遍历一个回溯树
//result = []
// def backtrack(路径, 选择列表):
//     if 满足结束条件:
//         result.add(路径)
//         return

//     for 选择 in 选择列表:
//         做选择
//         backtrack(路径, 选择列表)
//         撤销选择

51. N皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q‘ 和 ‘.‘ 分别代表了皇后和空位。

示例:

输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],

["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

提示：

皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一到七步，可进可退。（引用自 百度百科 - 皇后 ）

思路

//回溯1 先填满‘.‘, 递归放q时，计算该点的对角线是否存在q，存在即回溯
//回溯1 对列、主次对角线的点保存起来,主对角线x+y相等，次对角线x-y相等
//hill 山丘 上升 主对角线
//dale 山谷 下降 次对角线
//List<String> curr = new ArrayList<>(Collections.nCopies(n,"...."));新建填满数的list<String>
//Arrays.fill(charArray, ‘.‘);新建填满数的char[]

solution1

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        char[][] curr = new char[n][n];
        for (int i =0;i<n;i++){
            for(int j = 0;j<n;j++){
                curr[i][j] = ‘.‘;
            }
        }
        helper(res,curr,0,n);
        return res;
    }
    public void helper(List<List<String>> res,char[][] curr,int col,int n){
        if (col == n){
            res.add(construt(curr));
            return;
        }
        for(int row=0; row < n; row++){
            if (isValid(curr,row,col,n)){
                curr[row][col] = ‘Q‘;
                helper(res,curr,col+1,n);
                curr[row][col] = ‘.‘;
            }
        }
    }
    public boolean isValid(char[][] curr,int row,int col,int n){
        for (int i = 0;i<=col;i ++) {
            if (curr[row][i] == ‘Q‘) return false;
            if (row-i>=0 && curr[row-i][col-i] == ‘Q‘) return false;
            if (row+i<n && curr[row+i][col-i] == ‘Q‘) return false;
        }
        // for (int i = 0; i<n; i++){
        //     for(int j = 0;j < col; j++){
        //         if (curr[i][j] == ‘Q‘ && (row+col == i+j || row-col == i-j || row==i))
        //          {return false;}
        //         }
        // }
        return true;
        
    }
    public List<String> construt(char[][] curr){
        List<String> list = new ArrayList<>();
        for (int i=0;i<curr.length;i++){
            String s = new String(curr[i]);
            list.add(s);
        }
        return list;  
    }
}

solution2 回溯

class Solution {
    private Set<Integer> col = new HashSet<>();
    private Set<Integer> hill = new HashSet<>();
    private Set<Integer> dale = new HashSet<>();

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        
        helper(res,new ArrayList<String>(),0,n);
        return res;
    }
    public void helper(List<List<String>> res,List<String> curr,int y,int n){
        if (y == n){
            res.add(new ArrayList<>(curr));
            return;
        }
        for (int x = 0;x<n;x++){
            if (col.contains(x) || hill.contains(y+x) || dale.contains(x-y)) continue;
            //确定行char转string
            char[] charArray = new char[n];
            Arrays.fill(charArray, ‘.‘);
            charArray[x] = ‘Q‘;
            String str = new String(charArray);
            curr.add(str);
            //攻击距离
            col.add(x);
            hill.add(x+y);
            dale.add(x-y);
            //下一层
            helper(res,curr,y+1,n);
            //清理当前层（回溯）
            curr.remove(curr.size()-1);
            col.remove(x);
            hill.remove(x+y);
            dale.remove(x-y);   
        }
    }
}

LeetCode 回溯篇(46、51)

原文：https://www.cnblogs.com/gg12138/p/13586501.html