1、// 给定一个 没有重复 数字的序列,返回其所有可能的全排列。 回溯
var permute = function(nums) {
let res = [];
let track = [];
backTrack(nums, track, res);
return res;
};
let backTrack = (nums, track, res) => {
if (track.length === nums.length) {
res.push([].concat(track));
return;
}
for (let i = 0; i < nums.length; i++) {
if (track.includes(nums[i])){
continue;
}
track.push(nums[i]);
backTrack(nums, track, res);
track.pop();
}
}
2、// n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
// 给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。
// 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。
var solveNQueens = function(n) {
let res = [];
let queueRes = Array.from(new Array(n), () => {return new Array(n).fill('.')});
backTrack(res, 0, queueRes);
return res;
};
let backTrack = (res, row, queueRes) => {
let n = queueRes.length;
if (row === n) {
let arr = queueRes.map(item => {
return item.join('');
})
res.push(arr);
return;
}
for (let clo = 0; clo < n; clo++) {
if (isValide(queueRes, row, clo)) {
continue;
}
queueRes[row][clo] = 'Q';
backTrack(res, row + 1, queueRes);
queueRes[row][clo] = '.';
}
}
let isValide = (queueRes, row, clo) => {
let n = queueRes.length;
for (let i = 0; i < n; i++) { // 列检查
if (queueRes[i][clo] === 'Q') {
return true;
}
}
for (let i = row - 1, j = clo + 1; i >= 0 && j < n; i--, j++ ) { // 右上
if (queueRes[i][j] === 'Q') {
return true;
}
}
for (let i = row - 1, j = clo - 1; i >= 0 && j >= 0; i--, j--) {
if (queueRes[i][j] === 'Q') {
return true;
}
}
return false;
}
solveNQueens(4);
3、// . 串联所有单词的子串
var findSubstring = function(s, words) {
let res = [];
let len = words[0].length;
let wordNum = words.length;
let totalLen = len * wordNum;
for (let i = 0; i <= s.length - totalLen; i++) {
let arr = [...words];
let allStr = s.substring(i);
dfs(arr, i, allStr);
}
function dfs(arr, start, allStr) {
if (!arr.length) {
res.push(start);
}
let str = allStr.substring(0, len);
let index = arr.findIndex(item => item === str);
if (index > -1) {
arr.splice(index, 1);
dfs(arr, start, allStr.substring(len));
}
}
console.log(res)
return res;
};
let b = "barfoothefoobarman", words = ["foo","bar"];
// let b ="wordgoodgoodgoodbestword",words = ["word","good","best","good"];
findSubstring(b,words);
网友评论