算法思想：回溯 (Backtracking)
DFS（深度优先搜索）使用的就是回溯的方法。我们将回溯描述为这样一种方法：每次在分支选择的时候先随意选择一个分支，如果这个分支是不符合期望的，那么我们再回到分支选择的路口重新选择其他分支。
思想
回溯通常使用在在所有可能的解中寻找满足期望的解（一个或多个）。其本质是摊开所有的可能解，然后选择符合期望的解。
为了列出所有可能的解，我们需要将问题有规律的分阶段处理。每个阶段我们都有多个分支供我们选择，然后我们选择一个分支，如果分支不符合期望，则回到这个阶段，再选择其他分支。
分治是将大问题拆解成小问题通过解决小问题来解决大问题。回溯是将问题分阶段分步骤处理，每个步骤都进行所有的尝试，通过尝试所有可能来寻找问题的解。
N皇后问题
问题描述如下：
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
**n 皇后问题** 研究的是如何将 `n` 个皇后放置在 `n×n` 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 `n` ，返回所有不同的 **n 皇后问题** 的解决方案。
每一种解法包含一个不同的 **n 皇后问题** 的棋子放置方案，该方案中 `'Q'` 和 `'.'` 分别代表了皇后和空位。
**示例 1：**
**输入：**n = 4
**输出：**
[
[
".Q..",
"...Q",
"Q...",
"..Q."
],
[
"..Q.",
"Q...",
"...Q",
".Q.."
]
]
**解释：**4 皇后问题存在两个不同的解法。
**示例 2：**
**输入：**n = 1
**输出：**[["Q"]]
思路是我们逐行放置皇后位置，假设第x行的皇后在第y列，然后检查与在此行之前的皇后是否有交叉，如果没有则将当前皇后放到(x,y)，然后对下一行进行相同的假设，直到尝试完所有的位置或者完成最后一行的放置以后依然通过了交叉校验。
- 第x行假设放在y位置
- 检查是否交叉（在横、纵、斜向都没有其他皇后）
- 如果有交叉则继续假设放在下一个
y+1位置 - 如果没有交叉则确认放在x，y位置；然后继续处理下一行x+1
- 直到所有行都被放置完成且没有交叉；或者直到这一行的所有位置都尝试过了。
public class LeetCode51 {
private static final String QUEEN = "Q";
private static final String SPACE = "*";
/**
* 回溯法处理
* @param n
* @return
*/
public static List<List<String>> solveNQueens(int n) {
int[] state = new int[n];
Arrays.fill(state, -1);
// 考察每一行每一列
List<List<String>> res = new ArrayList<>();
nQueen(state,0,n,res);
return res;
}
/**
* 回溯法处理
* @param n
* @return
*/
private static void nQueen(int[] state, int rows, int n,List<List<String>> res){
if(rows == n){
// 前面的处理都没有问题，构建结果
List<String> list = new ArrayList<>();
for (int i = 0; i < state.length; i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < state.length; j++) {
if(state[i] == j){
sb.append("Q");
}else {
sb.append("*");
}
}
list.add(sb.toString());
}
res.add(list);
return; }
for (int j = 0; j < n; j++) {
if(!cross(state, rows, j)){
state[rows] = j;
// 下一行
nQueen(state, rows + 1, n,res);
}
}
}
private static boolean cross(int[] state,int row,int col) {
// 同一行肯定没有交叉
// 需要检查同一列和斜边情况
for (int i = row-1; i >=0 ; i--) {
// 检查三个位置
int before = state[i];
if (before == col) {
// 在同一列
return true;
}
// 斜边
int distance = row - i;
// 右倾斜边,左倾斜边,前面的行一定已经处理了
if (before == (distance + col) || (before == (col - distance))) {
return true;
}
}
return false;
}
}这里需要注意的是，if(!cross(state, rows, j)) 交叉检测只决定了是否要进一步在下一行进行尝试，没有退出循环。不论是否交叉都会尝试所有的位置，这样才能找到所有的情况。
这个问题还有变体，是求排列的数量。
public class LeetCode52 {
public static int resolveNQueen(int n) {
AtomicInteger count = new AtomicInteger(0);
int[] states = new int[n];
nQueen(states,0,n,count);
return count.get();
}
/**
* 回溯法处理
* @param n
* @return
*/
private static void nQueen(int[] state, int rows, int n,AtomicInteger count){
if(rows == n){
count.getAndIncrement();
return; }
for (int j = 0; j < n; j++) {
if(!cross(state, rows, j)){
state[rows] = j;
// 下一行
nQueen(state, rows + 1, n,count);
}
}
}
private static boolean cross(int[] state,int row,int col) {
// 同一行肯定没有交叉
// 需要检查同一列和斜边情况
for (int i = row-1; i >=0 ; i--) {
// 检查三个位置
int before = state[i];
if (before == col) {
// 在同一列
return true;
}
// 斜边
int distance = row - i;
// 右倾斜边,左倾斜边,前面的行一定已经处理了
if (before == (distance + col) || (before == (col - distance))) {
return true;
}
}
return false;
}
}正则表达式
问题描述如下：
给你一个字符串 `s` 和一个字符规律 `p`，请你来实现一个支持 `'.'` 和 `'*'` 的正则表达式匹配。
- `'.'` 匹配任意单个字符
- `'*'` 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 **整个** 字符串 `s` 的，而不是部分字符串。
**示例 1：**
**输入：**s = "aa", p = "a"
**输出：**false
**解释：**"a" 无法匹配 "aa" 整个字符串。
**示例 2:**
**输入：**s = "aa", p = "a*"
**输出：**true
**解释：**因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
**示例 3：**
**输入：**s = "ab", p = ".*"
**输出：**true
**解释：**".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。- 我们对字符串进行逐字匹配
- 如果不匹配，则检查模式串字符是不是单匹配字符，如果是则接着向下匹配
- 如果是多匹配字符则先进行无字符匹配尝试
- 如果无字符匹配失败则回溯再进行单字符匹配尝试
- 如果单字符匹配失败则回溯进行多字符匹配尝试
最终匹配的字符串，模式串和主串的指针都是指向末尾的。我们通过两个指针分别指向正在匹配的字符。
public class LeetCode10 {
private final static char SINGLE = '.';
private final static char MULTI = '*';
/**
* 回溯法
* @param s
* @param p
* @return
*/
public static boolean match(String s, String p) {
char[] sChars= s.toCharArray();
char[] pChars= p.toCharArray();
return match(sChars,pChars,0,0);
// return match(sChars, pChars);
}
/**
* 需要注意递归深度不适合长字符串
* @param sChars
* @param pChars
* @param i
* @param j
* @return
*/
private static boolean match(char[] sChars, char[] pChars,int i,int j) {
if(i == sChars.length && j == pChars.length){
return true;
}
// 一方已经用完了所有的字符，另一方还有剩余
if(i == sChars.length || j == pChars.length){
return false;
}
if(pChars[j] != MULTI){
// 非多字符情况
if (sChars[i] == pChars[j]) {
return match(sChars, pChars, i+1, j+1);
}
// 如果时单字通配符则直接匹配成功，继续向下
if (SINGLE == pChars[j]){
return match(sChars, pChars, i+1, j+1);
}
return false;
}else {
// 多字符时
// 首先尝试无字符匹配
boolean match = match(sChars, pChars, i, j + 1);
// 再进行单字符匹配
if (!match){
match = match(sChars, pChars, i + 1, j + 1);
}
// 再进行多字符匹配
if (!match) {
// 如果时false则j不变向下匹配
match = match(sChars, pChars, i+1, j);
}
return match;
}
}
/**
* 循环处理
*/
private static boolean match(char[] sChars, char[] pChars) {
int i=0;
int j=0;
int multi = -1;
while (i < sChars.length || j < pChars.length){
// 模式已耗尽则需要回退
if (j == pChars.length){
if (multi != -1){
j = multi;
}else {
break;
}
}
// 源已耗尽则结束
if(i==sChars.length){
break;
}
if(pChars[j] != MULTI){
// 非多字符情况
if (sChars[i] == pChars[j]) {
i++;
j++;
}
// 如果时单字通配符则直接匹配成功，继续向下
else if (SINGLE == pChars[j]){
i++;
j++;
}else {
if (multi != -1){
// 回退
j = multi;
}else {
return false;
}
}
}else {
// 回退回来的则进行单字符匹配尝试
if(multi == j){
i++;
}
// 标记回退位置
multi = j;
// 先进行无字符匹配尝试
j++;
}
}
if(i == sChars.length && j == pChars.length){
return true;
}
// 一方已经用完了所有的字符，另一方还有剩余
return false;
}
}由于栈的深度一般很有限，我这里添加了一个循环匹配的实现，核心依然是在匹配失败时对多匹配字符进行回溯。
评论已关闭