深度/广度优先搜索¶
生成有效括号的集合¶
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
来源: LeetCode第22题
经典递归解法，观察发现
1、某一次递归终止时需要将当前字符存入数组
2、 字符任取一个位置左侧必 左括号>=右括号
3、每次递归除了需要传当前字符还需要记情当前左右括号数
var generateParenthesis = function (n) {
let res = [];
// cur :当前字符 left：当前字符左括号 right:当前字符右括号
const help = (cur, left, right) => {
if (cur.length === 2 * n) {
res.push(cur);
return;
}
if (left < n) {
help(cur + "(", left + 1, right)
}
if (right < left) {
help(cur + ")", left, right + 1);
}
};
help("", 0, 0);
return res;
};
var generateParenthesis = function (total) {
let list = []
function generate(left, right, n, s) {
// 终止条件：如果左右括弧都用完则结束
if (left === n && right === n) {
list.push(s)
return
}
// 如果左括弧未用完则继续增加左括弧
if (left < n) {
generate(left + 1, right, n, s + "(")
}
// 如果右括弧少于左括弧则继续增加右括弧
if (left > right) {
generate(left, right + 1, n, s + ")")
}
}
generate(0, 0, total, "")
return list
}
N 皇后问题¶
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例:
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
来源: LeetCode第51题
/**
* @param {number} n
* @return {string[][]}
*/
var solveNQueens = function(n) {
let position = [];
let res = [];
let isValid = (index, depth) => {
for(let i = 0; i < depth; i++) {
if(position[i] === index) return false;
if(i + position[i] === index + depth || i - position[i] === depth - index) return false;
}
return true;
};
let generateString = (arr) => {
let res = [];
for(let i = 0; i < n; i++) {
let str = "";
for(let j = 0; j < n; j++) {
if(j === arr[i]) str += "Q";
else str += ".";
}
res.push(str);
}
return res;
};
let traverse = (depth) => {
if(depth === n) {
res.push(generateString(position));
return;
}
for(let i = 0; i < n; i++) {
if(isValid(i, depth)) {
position[depth] = i;
traverse(depth + 1);
}
}
}
traverse(0);
return res;
};
高赞回答
/**
* @param {number} n
* @return {string[][]}
*/
var solveNQueens = function (n) {
let result = [];
backStart(0, [], n, result);
return result;
};
function backStart(k, arr, n, result) {
if (k >= n) {
let ar = [];
arr.forEach(e => {
// 转换为需要的格式
let str = '..............................';
str=str.substring(0,n);
str = `${str.substring(0, e)}Q${str.substring(e + 1)}`
ar.push(str);
})
result.push(ar);
} else {
for (let i = 0; i < n; i++) {
arr[k] = i;
if (isBack(k, arr)) {
backStart(k + 1, arr, n, result)
}
}
}
}
function isBack(k, arr) {
for (let i = 0; i < k; i++) {
if (k - i == Math.abs(arr[i] - arr[k]) || arr[k] == arr[i]) {
return false;
}
}
return true;
}
作者：uzi0
链接：https://leetcode-cn.com/problems/n-queens/solution/nhuang-hou-fei-hui-shuo-zheng-xiang-si-lu-jie-fa-c/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
思路二
var solveNQueens = function(n) {
let res = []
dfs(n, [], res)
return res
}
/**
* 递归计算 N 皇后的解
* @param {number} n
* @param {number[]} tmp 长度为 n 的数组，tmp[i] 代表第 i 行的皇后放置的位置
* @param {string[]} res
*/
function dfs(n, tmp, res) {
// 如果 tmp 长度为 n，代表所有皇后放置完毕
if (tmp.length === n) {
// 把这种解记录下来
res.push(
tmp.map(i => {
let strArr = Array(n).fill('.')
strArr.splice(i, 1, 'Q')
return strArr.join('')
})
)
return
}
// 每次有 n 个选择，该次放置在第几列
for (let j = 0; j < n; j++) {
// 如果当前列满足条件
if (isValid(tmp, j)) {
// 记录当前选择
tmp.push(j)
// 继续下一次的递归
dfs(n, tmp, res)
// 撤销当前选择
tmp.pop()
}
}
}
function isValid(tmp, j) {
let i = tmp.length
for (let x = 0; x < i; x++) {
let y = tmp[x]
if (y === j || x - y === i - j || x + y === i + j) {
return false
}
}
return true
}
作者：_tank_
链接：https://leetcode-cn.com/problems/n-queens/solution/jian-ji-de-javascript-dfs-ti-jie-dai-zhu-shi-by-_t/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复原IP地址¶
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
示例:
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
来源:LeetCode第93题
解题思路¶
思路一 DFS¶
递归，DFS的思路，去掉不符合的情况，每次从字符串开始位置截掉长度为 1，2，3之后剩下的子串，用于递归。
注意 0开头，
/**
* @param {string} s
* @return {string[]}
*/
var restoreIpAddresses = function(s) {
let result = [];
function helper(s, last, segments){
if(segments == 3){
if(s.length <= 3 && parseInt(s.slice(0,3)) <= 255){
if(s.length >= 2 && s.charAt(0) == "0"){
return
}
let item = last.concat(s)
result.push(item);
return
}
}
if(segments < 3){
let item = last.concat(s.slice(0,1)).concat(".");
helper(s.slice(1), item, segments+1)
if(s.charAt(0) != "0"){
item = last.concat(s.slice(0,2)).concat(".")
helper(s.slice(2), item, segments+1)
if(parseInt(s.slice(0,3)) <= 255){
item = last.concat(s.slice(0,3)).concat(".")
helper(s.slice(3), item, segments+1);
}
}
}
}
helper(s, "", 0);
return result;
};
思路二：回溯实现¶
var restoreIpAddresses = function (s) {
if (s.length > 12) return []
let result = []
fn(s, [], result)
return result
};
递归遍历
- 递归结束条件：当判断到最后一段时，如果合法直接加入到结果集
- 递归体：每一段长度可以为1、2、3，所以每次都有三种可能
function fn(remain, temp, result) {
if (temp.length === 3) {
regular(remain) && result.push([...temp, remain].join('.'))
return
}
for (let i = 1; i < 4; i++) {
regular(remain.substr(0, i)) && fn(remain.substr(i), [...temp, remain.substr(0, i)], result)
}
}
是否合法需要满足以下条件：
- 大于等于0；
- 小于等于255
- 如果是一位可以为0，如果超过一位，不能以0开头
/**
* @desc 用来判断每一段是否合法
* @param {string} s
* @return {boolean}
*/
function regular(s) {
if (!s.length) return false
return 0 <= +s && +s <= 255 && (s.length > 1 ? !!+s[0] : true)
}