LeetCode51. N皇后

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

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

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

在建立算法之前，我们来考虑两个有用的细节。

•     一行只可能有一个皇后且一列也只可能有一个皇后。这意味着没有必要再棋盘上考虑所有的方格。只需要按列循环即可。
•     对于所有的主对角线有 行号 + 列号 = 常数，对于所有的次对角线有 行号 - 列号 = 常数。这可以让我们标记已经在攻击范围下的对角线并且检查一个方格 (行号, 列号) 是否处在攻击位置。

class Solution {
public:vector<vector<string>> res; vector<vector<string>> solveNQueens(int n) {vector<string> board(n, string(n, '.'));dfs(board, 0);return res;}void dfs(vector<string>& board, int row){if(row == board.size()){                   //边界条件res.push_back(board);return;}int length = board[row].size();for(int col = 0; col < length; col++){if(!isValid(board, row, col)){        //不满足8皇后条件continue;}board[row][col] = 'Q';                //回溯模板dfs(board, row + 1);board[row][col] = '.';}}bool isValid(vector<string>& board, int row, int col){int length = board.size();//检查同列for(int i = 0; i < row; i++){if(board[i][col] == 'Q'){return false;}}//检查右上for(int i = row - 1, j = col + 1; i >= 0 && j < length; i--, j++){if(board[i][j] == 'Q'){return false;}}//检查左上for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){if(board[i][j] == 'Q'){return false;}}return true;}
};

LeetCode93. 复原IP地址

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。

示例:输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

dfs深度搜索思路，数值>255非法，以零开头长度大于等于2非法；不同于常规回溯思路，同层只用最多遍历3个数字，依次查看是否满足数值要求；各段的数值状态也是分段存储的，互不干涉，使用vector<string> path来存储；

class Solution {
public:bool isValid(string ip){                   //判断ip地址是否有效int val = stoi(ip);if (val > 255)    return false;        //值不能超过255if (ip.size() >= 2 && ip[0] == '0')    return false;//以0开头的除非数字是0本身，否则也是非法return true;}void dfs(string& s, int pos, vector<string> &path, vector<string>& res){//首先判断剩余的位数，是不是还能满足要求//比如25525511135，若2.5.5.25511135显然不满足，//这可以预判4组，每组最多3位数字int maxLen = (4 - path.size()) * 3;if (s.size() - pos > maxLen)    return;if (path.size() == 4 && pos == s.size()) {string str = "";for (int i = 0; i < 4; i++) {     //字符串拼接转换成地址str += path[i];if (i != 3)    str += ".";}res.push_back(str);return;}//回溯算法的典型模式，循环递归for (int i = pos; i < s.size() && i <= pos + 2; i++) {//同层最多遍历3个数字string ip = s.substr(pos, i - pos + 1);    //子串分割if (!isValid(ip))    continue;path.push_back(ip);dfs(s, i + 1, path, res);path.pop_back();}}vector<string> restoreIpAddresses(string s) {vector<string> res;if (s.size() == 0 || s.size() < 4)    return res;vector<string> path;//存储从根开始的到叶子节点的满足条件的路径//因为最多3位数字一组，所以同一层横向循环时尝试最多3个位的长度dfs(s, 0, path, res);return res;}
};

LeetCode22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

括号是成对出现的，如果左括号数量不大于 n，我们可以放一个左括号；如果右括号数量小于左括号的数量，我们可以放一个右括号，当左右括号都用完时，得到答案，当左括号个数比右括号多时结束匹配，剩下需要用递归形式在tmp字符串上分别增加左右括号。

class Solution {
public:vector<string> res;void dfs(int left, int right, string tmp) {if (left == 0 && right == 0) {res.push_back(tmp);return ;}if (left > right || left < 0 || right < 0)  //左括号用的比右括号少return ;dfs(left - 1, right, tmp + '(');dfs(left, right - 1, tmp + ')');}vector<string> generateParenthesis(int n) {if(n == 0)  return res;string tmp;dfs(n, n, tmp);return res;}
};

LeetCode301. 删除无效的括号

删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。说明: 输入可能包含了除 ( 和 ) 以外的字符。

示例 1:输入: "()())()"
输出: ["()()()", "(())()"]示例 2:输入: "(a)())()"
输出: ["(a)()()", "(a())()"]示例 3:输入: ")("
输出: [""]

思路：

• 1、删除括号使得字符串有效，其实是可以知道有多少非法的左括号和右括号的，遍历一把就可以计算得到
• 2、那就在原始字符串上面进行删除操作，遍历删除的字符位置[0, s.size()-1], 对应字符为左右括号时，分别递归
• 3、当前删除位置需要传递给下一次迭代，因为每次其实删除一个字符后，字符串长度是减少1的，而删除的位置正好是下一次迭代中开始删除的首位。
• 4、有个优化点，就是在循环删除的时候，如果下一个字符和上一次回溯结束后的字符一样时，不需要再重复处理
• 5、左右括号删除满足条件时，检查字符串s是否有效

class Solution {
public:vector<string> res;vector<string> removeInvalidParentheses(string s) {//DFS算法int left = 0;int right = 0;for(char str : s){            //统计多余的左右括号if(str == '('){left++;}else if(str == ')'){if(left > 0)    left--;else    right++;}else continue;}// 深度优先遍历，寻找题解，left与right为不合法的左括号个数和右括号个数dfs(s, 0, left, right);return res;}void dfs(string s, int start, int left, int right){if(left == 0 && right == 0){if(isValid(s)){res.push_back(s);}return;}for(int i = start; i < s.size(); i++){if(i - 1 >= start && s[i] == s[i - 1])   continue;                    if(left > 0 && s[i] == '('){        //左括号多余且该括号为左括号dfs(s.substr(0, i) + s.substr(i + 1), i, left - 1, right);//将字符串进行左右分割去遍历，找出多余的括号}if(right > 0 && s[i] == ')'){       //右括号多余且该括号为右括号dfs(s.substr(0, i) + s.substr(i + 1), i, left, right - 1);}}}bool isValid(string s) {                    //利用栈进行括号匹配stack<char> st;for(int i = 0; i < s.size(); i++){if(s[i] == '(')st.push(s[i]);  else if(s[i] == ')') {if(st.empty())  return false; if( st.top() == '(')st.pop();else    return false;}else continue;}if(st.empty()) return true;else    return false;}
};

此题还试着用了BFS去解决，方法如下：

class Solution {
public://BFS算法vector<string> removeInvalidParentheses(string s) {       vector<string> res;unordered_set<string> visited{{s}};queue<string> q{{s}};bool flag = false;while (!q.empty()) {string tmp = q.front();q.pop();if (isValid(tmp)) {res.push_back(tmp);flag = true;}if(flag) continue;for (int i = 0; i < tmp.size(); i++) {if (tmp[i] != '(' && tmp[i] != ')') continue;               //过滤非括号内容string str = tmp.substr(0, i) + tmp.substr(i + 1);          //对字符串进行切割if (!visited.count(str)) {                                  //将去除一个符号的字符串入队q.push(str);visited.insert(str);}}}return res;}
}