2022-1-19DFSday1

题1：

46. 全排列labuladong 题解思路

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数 互不相同

 1 class Solution {
 2     List> ans;
 3     int n;
 4     public List> permute(int[] nums) {
 5         n=nums.length;
 6         boolean[] visit=new boolean[n];
 7         ans=new ArrayList<>();
 8         for (int i=0;i){
 9             List list=new ArrayList();
10             list.add(nums[i]);
11             visit[i]=true;
12             dfs(nums,visit,1,list);
13             visit[i]=false;
14         }
15         return ans;
16     }
17 
18 
19     public void dfs(int[] num,boolean[] visit,int len,List list){
20         if (len==n) {
21             ans.add(new ArrayList<>(list));
22             return;
23         }
24         for (int i=0;i) {
25             if (!visit[i]){
26                 visit[i]=true;
27                 list.add(num[i]);
28                 dfs(num,visit,len+1,list);
29                 visit[i]=false;
30                 list.remove(list.size()-1);
31             }
32             
33         }
34     }
35 }

思路：暴力搜索。遍历排列的第一个字母，将所有可能的排列加入到答案中。注意，加入答案的时候要深拷贝，否则会出错。ans.add(new ArrayList<>(list));

题2:

51. N 皇后labuladong 题解思路

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

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

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

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[["Q"]]

提示：

• 1 <= n <= 9

 1 class Solution {
 2     List> ans;
 3     List<int[]> pos;
 4     char[][] chess;
 5     public List> solveNQueens(int n) {
 6         chess=new char[n][n];
 7         ans=new ArrayList<>();
 8         pos=new ArrayList<>();
 9         for (int i=0;i);
10         dfs(0,n);
11         return ans;
12     }
13 
14     public void dfs(int num,int n){
15         if (num==n){
16             //记录答案
17             List list=new ArrayList<>();
18             for (int i=0;i){
19                 StringBuffer sb=new StringBuffer();
20                 for (int j=0;j){
21                     sb.append(chess[i][j]);
22                 }
23                 list.add(sb.toString());
24             }
25             ans.add(list);
26             return;
27         }
28         for (int i=0;i){
29             if (check(num,i)){
30                     pos.add(new int[]{num,i});
31                     chess[num][i]='Q';
32                     dfs(num+1,n);
33                     chess[num][i]='.';
34                     pos.remove(pos.size()-1);
35                 }
36             }
37     }
38 
39     public boolean check(int x,int y){
40         for (int i=0;i){
41             int dx=pos.get(i)[0],dy=pos.get(i)[1];
42             if (dx==x||dy==y) return false; //同一行或者同一列
43             if (Math.abs(dx-x)==Math.abs(dy-y)) return false;//对角线
44         }
45         return true;
46     }
47 }

思路：一行一行填王后，利用pos列表记录已经填的位置，check判断当前行的位置能否填。