leetcode思路-回溯最后一节（131.分割回文串、51.N皇后）

131.分割回文串

给你一个字符串s，请你将s分割成一些 子串，使每个子串都是回文串。返回s所有可能的分割方案。

思路：

用成员变量ans和path来维护所有达到标准的分割子串集合以及当前分割子串集合

枚举子串的结束位置判断是否回文

递归结束条件：

子串的起点等于s的长度，即s已经分割完毕，加入当前路径到ans中

当前递归做的事情:

列举当前起点所有可能的终点，判断是否有回文子串，如果有，对字符串进行分割，并将剩下的字符串起点递归传入下一次继续分割寻找回文子串，注意递归后面要恢复现场。

class Solution { List<List<String>> ans; List<String> path; public List<List<String>> partition(String s) { ans = new ArrayList<>(); path = new ArrayList<>(); DFS(0,s); return ans; } //传入剩下未被分割的部分和字符串 public void DFS(int i,String s){ if(i == s.length()){ ans.add(new ArrayList<>(path)); return; } //列举所有可能的终点 for(int j = i;j < s.length();j++){ //如果当前终点符合，递归判断剩下的字符串是否能达到符合条件 if(isPalindrome(i,j,s)){ path.add(s.substring(i, j + 1)); DFS(j + 1,s); //恢复现场 path.remove(path.size() - 1); } } } public boolean isPalindrome(int l,int r,String s){ while(l < r){ if(s.charAt(l++) != s.charAt(r--)){ return false; } } return true; } }

51.N皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

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

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

思路：

要解决N皇后问题，首先是处理1.同行冲突 2.同列冲突 3.同斜线冲突

1.同行冲突：

在构建遍历数组时，直接规定一行只存放一个皇后，这样的稀疏矩阵可以压缩成数组，下标表示皇后所在的行数，数组值表示该行皇后所在的列数

2.同列冲突

构建数组 isChoose[n]存储该列有没有放皇后

3.同斜线冲突

因为根据推理可得，↗ 方向，如果冲撞，则行号加列号为常数，这样的常数理论上有2n - 1个，因此构建数组 diag1[2n - 1]。

↖方向，如果冲撞，则行号减列号为常数，这样的常数理论上有2n - 1个，因此构建数组 diag2[2n - 1]。

构建函数DFS(r:标记当前放置到第几个皇后 n:传入一共有几个皇后 path:存储所有放置过的皇后位置信息 isChoose:用来排除同列冲突 diag1、diag2:用来排除斜线冲突）

使用成员变量ans存储所有可能的皇后放置组合

递归结束条件：

所有皇后放置完成 r==n

当前递归做的事情：

遍历每一个列看能不能把当前的皇后放进去，剪枝去掉有行冲突斜线冲突的路径（注意这里diag2要加一个偏移量、因为行号减列号有可能是负的，负的值一共有 n-1个，故加上n-1，让原本的数组下标范围由[-（n -1 ）,n-1]到[0,2n -1]）

如果能放进去，那么进入下一个递归放下一个皇后，注意递归完后要恢复现场

List<List<String>> ans; public List<List<String>> solveNQueens(int n) { ans = new ArrayList<>(); //path[n] = m:表示在第n行第m列放了一个皇后，因为我们一行只放一个皇后，所以可以这样简化存储 int[] path = new int[n]; //当前列有没有放皇后 boolean[] isChoose = new boolean[n]; //↗ 方向，如果冲撞，则行号加列号为常数，此斜对角线最多有2n - 1个元素，记录当前斜对角线有没有放皇后 boolean[] diag1 = new boolean[2*n - 1]; //↖方向，如果冲撞，则行号减列号为常数，此斜对角线最多有2n - 1个元素，记录当前斜对角线有没有放皇后 boolean[] diag2 = new boolean[2*n - 1]; DFS(0,n,path,isChoose,diag1,diag2); return ans; } public void DFS(int r,int n,int[] path,boolean[] isChoose,boolean[] diag1,boolean[] diag2){ //如果皇后已经放完，添加当前路径到ans中 if(r == n){ ans.add(new ArrayList<>(build(path))); return; } //遍历每一个列看能否将当前行的元素放进去 for (int c = 0; c < n; c++) { //剪枝 if(!isChoose[c] && !diag1[r + c] && !diag2[r - c + n - 1]){ path[r] = c; isChoose[c] = diag1[r + c] = diag2[r - c + n - 1] = true; DFS(r + 1,n,path,isChoose,diag1,diag2); isChoose[c] = diag1[r + c] = diag2[r - c + n - 1] = false; } } } public List<String> build(int[] path){ int n = path.length; List<String> res = new ArrayList<>(); for(int i:path){ char[] str = new char[n]; for(int j = 0;j < n;j++){ str[j] = j == i ? 'Q':'.'; } res.add(new String(str)); } return res; }