N-Queens And N-Queens II [LeetCode] + Generate Parentheses[LeetCode] + 回溯法

时间:2022-09-17 19:45:30

回溯法

百度百科:回溯法(探索与回溯法)是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步又一次选择,这样的走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。

在包括问题的全部解的解空间树中,依照深度优先搜索的策略,从根结点出发深度探索解空间树。当探索到某一结点时,要先推断该结点是否包括问题的解,假设包括,就从该结点出发继续探索下去,假设该结点不包括问题的解,则逐层向其祖先结点回溯。(事实上回溯法就是对隐式图的深度优先搜索算法)。
若用回溯法求问题的全部解时,要回溯到根,且根结点的全部可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时,仅仅要搜索到问题的一个解就能够结束。

做完以下几题,应该会对回溯法的掌握有非常大帮助

N-Queens http://oj.leetcode.com/problems/n-queens/N-Queens II   http://oj.leetcode.com/problems/n-queens-ii/Generate Parentheses http://oj.leetcode.com/problems/generate-parentheses/

N-Queens

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

N-Queens And N-Queens II [LeetCode] + Generate Parentheses[LeetCode] + 回溯法

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both
indicate a queen and an empty space respectively.

For example,

There exist two distinct solutions to the 4-queens puzzle:

[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."], ["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]

经典的八皇后问题的扩展,利用回溯法,

(1)从第一列開始试探性放入一枚皇后

(2)推断放入后棋盘是否安全,调用checkSafe()推断

(3)若checkSafe()返回true,继续放下一列,若返回false,回溯到上一列,又一次寻找安全位置

(4)遍历全然部位置,得到结果

class Solution {
public:
vector<vector<string> > solveNQueens(int n) {
int *posArray = new int[n];
int count = 0;
vector< vector<string> > ret;
placeQueue(0, n, count, posArray, ret);
return ret;
} //检查棋盘安全性
bool checkSafe(int row, int *posArray){
for(int i=0; i < row; ++i){
int diff = abs(posArray[i] - posArray[row]);
if (diff == 0 || diff == row - i) {
return false;
}
}
return true;
} //放置皇后
void placeQueue(int row, int n, int &count, int *posArray, vector< vector<string> > &ret){
if(n == row){
count++;
vector<string> tmpRet;
for(int i = 0; i < row; i++){
string str(n, '.');
str[posArray[i]] = 'Q';
tmpRet.push_back(str);
}
ret.push_back(tmpRet);
return;
}
//从第一列開始试探
for(int col=0; col<n; ++col){
posArray[row] = col;
if(checkSafe(row, posArray)){
//若安全,放置下一个皇后
placeQueue(row+1, n, count, posArray, ret);
}
}
}
};

N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

仅仅需计算个数count即可,略微改动

class Solution {
public:
int totalNQueens(int n) {
int *posArray = new int[n];
int count = 0;
vector< vector<string> > ret;
placeQueue(0, n, count, posArray, ret);
return count;
} //检查棋盘安全性
bool checkSafe(int row, int *posArray){
for(int i=0; i < row; ++i){
int diff = abs(posArray[i] - posArray[row]);
if (diff == 0 || diff == row - i) {
return false;
}
}
return true;
} //放置皇后
void placeQueue(int row, int n, int &count, int *posArray, vector< vector<string> > &ret){
if(n == row){
count++;
return;
}
//从第一列開始试探
for(int col=0; col<n; ++col){
posArray[row] = col;
if(checkSafe(row, posArray)){
//若安全,放置下一个皇后
placeQueue(row+1, n, count, posArray, ret);
}
}
}
};

Generate Parentheses

刚做完N-QUEUE问题,受之影响,此问题也使用回溯法解决,代码看上去多了非常多

class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> vec;
int count = 0;
int *colArr = new int[2*n];
generate(2*n, count, 0, colArr, vec);
delete[] colArr;
return vec;
} //放置括弧
void generate(int n,int &count, int col, int *colArr, vector<string> &vec){
if(col == n){
++count;
string temp(n,'(');
for(int i = 0;i< n;++i){
if(colArr[i] == 1)
temp[i] = ')';
}
vec.push_back(temp);
return;
}
for(int i=0; i<2;++i){
colArr[col] = i;
if(checkSafe(col, colArr, n)){
//放置下一个括弧
generate(n, count, col+1, colArr, vec);
}
}
} //检查安全性
bool checkSafe(int col, int *colArr, int n){
int total = n/2;
if(colArr[0] == 1) return false;
int left = 0, right = 0;
for(int i = 0; i<=col; ++i){
if(colArr[i] == 0 )
++left;
else
++right;
}
if(right > left || left > total || right > total)
return false;
else
return true;
}
};

google了下,http://blog.csdn.net/pickless/article/details/9141935 代码简洁非常多,供參考

class Solution {
public:
vector<string> generateParenthesis(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<string> ans;
getAns(n, 0, 0, "", ans);
return ans;
} private:
void getAns(int n, int pos, int neg, string temp, vector<string> &ans) {
if (pos < neg) {
return;
}
if (pos + neg == 2 * n) {
if (pos == neg) {
ans.push_back(temp);
}
return;
}
getAns(n, pos + 1, neg, temp + '(', ans);
getAns(n, pos, neg + 1, temp + ')', ans);
}
};

N-Queens And N-Queens II [LeetCode] + Generate Parentheses[LeetCode] + 回溯法的更多相关文章

  1. 22&period; Generate Parentheses C&plus;&plus;回溯法

    把左右括号剩余的次数记录下来,传入回溯函数. 判断是否得到结果的条件就是剩余括号数是否都为零. 注意判断左括号是否剩余时,加上left>0的判断条件!否则会memory limited erro ...

  2. Generate Parentheses - LeetCode

    目录 题目链接 注意点 解法 小结 题目链接 Generate Parentheses - LeetCode 注意点 解法 解法一:递归.当left>right的时候返回(为了防止出现 )( ) ...

  3. LeetCode&colon; Generate Parentheses 解题报告

    Generate ParenthesesGiven n pairs of parentheses, write a function to generate all combinations of w ...

  4. &lbrack;LeetCode&rsqb;Generate Parentheses题解

    Generate Parentheses: Given n pairs of parentheses, write a function to generate all combinations of ...

  5. LeetCode刷题笔记-回溯法-括号生成

    题目描述: 给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合. 例如,给出 n = 3,生成结果为: [ "((()))", "( ...

  6. LeetCode刷题笔记-回溯法-分割回文串

    题目描述: 给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串. 返回 s 所有可能的分割方案. 示例: 输入: "aab"输出:[ ["aa", ...

  7. &lbrack;LeetCode&rsqb; Generate Parentheses 生成括号

    Given n pairs of parentheses, write a function to generate all combinations of well-formed parenthes ...

  8. Generate Parentheses leetcode java

    题目: Given n pairs of parentheses, write a function to generate all combinations of well-formed paren ...

  9. Generate Parentheses——LeetCode

    Given n pairs of parentheses, write a function to generate all combinations of well-formed parenthes ...

随机推荐

  1. 打开现有的pdf,并插入一个图片

    不说了,直接代码 T_ScanUploadData file = _IScanUploadDataAccessService.GetScanUploadData(id); byte[] filedat ...

  2. UI的一些方法(按钮和线)

    //设置按钮字体颜色 [self.determineBtn setTitleColor:[UIColor colorWithHexString:@"0xff9500"] forSt ...

  3. Android中的PopupWindow的使用

    PopupWindow 需要一个自定义的布局文件 列如:popupwindow.xml <?xml version="1.0" encoding="utf-8&qu ...

  4. BJFU 1440 fudq的ACM

    矩阵快速幂 #include<cstdio> #include<algorithm> using namespace std; ; const int INF =1e9; ; ...

  5. springboot新手使用guns开源框架心得

    一.导航 以guns的通知管理为例 l  通知管理的请求地址是localhost:8080/notice l  程序收到这样的请求就去找地址为notice的Controller l  通知控制器收到这 ...

  6. Python36 二进制文件读写问题

    在Python36中写如下代码: __author__ = '-------'#-*- coding: utf-8 -*-import struct fo = open("myfile.tx ...

  7. NUMA导致的Oracle性能问题

    背景简介: Oracle版本:11.2.0.4 OS 版本:OEL5.8 在一次Oracle的Dataguard正常switchover过程中,遇到了一个极其诡异的问题,一条主业务的SQL语句在新主库 ...

  8. zw版【转发&&num;183&semi;*nvp系列Delphi例程】HALCON MaxImage1

    zw版[转发·*nvp系列Delphi例程]HALCON MaxImage1 procedure TForm1.FormShow(Sender: TObject);begin Set8087CW($ ...

  9. ny14 会场安排问题

    会场安排问题 时间限制:3000 ms  |  内存限制:65535 KB 难度:4   描述 学校的小礼堂每天都会有许多活动,有时间这些活动的计划时间会发生冲突,需要选择出一些活动进行举办.小刘的工 ...

  10. PL&sol;SQL 02 声明变量 declare

    语法:identifier [CONSTANT] datatype [NOT NULL] [:= | DEFAULT expr] identifier:用于指定变量或常量的名称.CONSTANT:用于 ...