上海网站设计价,什么站做咨询网站好,网站建设下拉导航栏,个人兴趣图片集网站建设目录
框架#xff1a;排列/组合/子集
元素无重不可复选
全排列
子集
组合#xff1a;[1, n] 中的 k 个数
分割成回文串
元素无重不可复选#xff1a;排序#xff0c;多条值相同的只遍历第一条
子集/组合
先进行排序#xff0c;让相同的元素靠在一起#xff0c;如…目录
框架排列/组合/子集
元素无重不可复选
全排列
子集
组合[1, n] 中的 k 个数
分割成回文串
元素无重不可复选排序多条值相同的只遍历第一条
子集/组合
先进行排序让相同的元素靠在一起如果发现 nums[i] nums[i-1]则跳过
排列
元素无重可复选
子集/组合sumtarget
排列去除 used 剪枝
N皇后 如果不能成功那么返回的时候我们就还要把这个位置还原。这就是回溯算法也是试探算法。
解决一个回溯问题实际上就是一个决策树的遍历过程。
1、路径已选择。
2、选择列表可选择。
3、结束条件无选择。
框架排列/组合/子集
result []
function backtrack(路径, 选择列表):if 满足结束条件:result.add(路径)result.push([...path])或者result.push(path.slice())//path还会改变所以不能传引用地址returnfor 选择 in 选择列表:做选择pushbacktrack(路径, 选择列表)撤销选择pop数组有一定的剪枝不用判断是否use
const backtrack (start) {// 回溯算法标准框架for (let i start; i nums.length; i) {// 做选择track.push(nums[i]);// 回溯遍历下一层节点backtrack(i 1);// 撤销选择track.pop();}};backtrack(0);
图
function backtrack(nums, used, track, res) {for (let i 0; i nums.length; i) {if (used[i]) {continue;}track.push(nums[i]);used[i] true;backtrack(nums, used, track, res);track.pop();used[i] false;}
}全排列中
做选择/撤销选择 可用if(path.includes(item)) continue;代替
元素无重不可复选
全排列 key
path.length string.lengthpath.includes(item)
const _permute string {const res [];const backtrace path {if(path.length string.length){res.push(path);return;}for(const item of string) {if(path.includes(item)) continue;backtrace(path item);}};backtrace();return res;
}
子集
输入一个无重复元素的数组 nums其中每个元素最多使用一次请你返回 nums 的所有子集
比如输入 nums [1,2,3]算法应该返回如下子集
[ [],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3] ]/*** param {number[]} nums* return {number[][]}*/
var subsets function(nums) {// 用于存储结果const res [];// 用于记录回溯路径const track [];/*** 回溯算法的核心函数用于遍历子集问题的回溯树* param {number} start - 控制树枝的遍历避免产生重复子集*/const backtrack (start) {// 前序遍历位置每个节点的值都是一个子集res.push([...track]);// 回溯算法标准框架for (let i start; i nums.length; i) {// 做选择track.push(nums[i]);// 回溯遍历下一层节点backtrack(i 1);// 撤销选择track.pop();}};backtrack(0);return res;
};
组合[1, n] 中的 k 个数
返回范围 [1, n] 中所有可能的 k 个数的组合剪枝
let result []
let path []
var combine function(n, k) {result []combineHelper(n, k, 1)return result
};
const combineHelper (n, k, startIndex) {if (path.length k) {result.push([...path])return}for (let i startIndex; i n - (k - path.length) 1; i) {path.push(i)combineHelper(n, k, i 1)path.pop()}
}
分割成回文串
组合问题选取一个a之后在bcdef中再去选取第二个选取b之后在cdef中再选取第三个.....。切割问题切割一个a之后在bcdef中再去切割第二段切割b之后在cdef中再切割第三段.....。 /*** param {string} s* return {string[][]}*/
const isPalindrome (s, l, r) {for (let i l, j r; i j; i, j--) {if(s[i] ! s[j]) return false;}return true;
}var partition function(s) {const res [], path [], len s.length;backtracking(0);return res;function backtracking(startIndex) {if(startIndex len) {res.push(Array.from(path));return;}for(let i startIndex; i len; i) {if(!isPalindrome(s, startIndex, i)) continue;path.push(s.slice(startIndex, i 1));backtracking(i 1);path.pop();}}
};
元素无重不可复选排序多条值相同的只遍历第一条
子集/组合
nums [1,2,2]你应该输出
[ [],[1],[2],[1,2],[2,2],[1,2,2] ]
如果一个节点有多条值相同的树枝相邻则只遍历第一条剩下的都剪掉不要去遍历
先进行排序让相同的元素靠在一起如果发现 nums[i] nums[i-1]则跳过
排列
// 注意javascript 代码由 chatGPT 根据我的 java 代码翻译旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试仅供参考如有疑惑可以参照我写的 java 代码对比查看。/*** param {number[]} nums* return {number[][]}*/var permuteUnique function(nums) {let res [];let track [];let used new Array(nums.length).fill(false);// 先排序让相同的元素靠在一起nums.sort((a, b) a - b);backtrack(nums, used, track, res);return res;
};/*** param {number[]} nums* param {boolean[]} used* param {number[]} track* param {number[][]} res*/
function backtrack(nums, used, track, res) {if (track.length nums.length) {res.push(track.slice());return;}for (let i 0; i nums.length; i) {if (used[i]) {continue;}// 新添加的剪枝逻辑固定相同的元素在排列中的相对位置if (i 0 nums[i] nums[i - 1] !used[i - 1]) {continue;}track.push(nums[i]);used[i] true;backtrack(nums, used, track, res);track.pop();used[i] false;}
}元素无重可复选
子集/组合sumtarget
想让每个元素被重复使用我只要把 i 1 改成 i 即可
给之前的回溯树添加了一条树枝在遍历这棵树的过程中一个元素可以被无限次使用 这棵回溯树会永远生长下去所以我们的递归函数需要设置合适的 base case 以结束算法即路径和大于 target 时就没必要再遍历下去了
排列去除 used 剪枝
N皇后 在 n * n 的棋盘上要摆 n 个皇后 要求任何两个皇后不同行不同列也不在同一条斜线上 求给一个整数 n 返回 n 皇后的摆法数。
要求空间复杂度 O(1) 时间复杂度O(n!)
要确定皇后的位置其实就是确定列的位置因为行已经固定了进一步讲也就是如何摆放 数组arr [0,1,2,3,...,n-1]如果没有【不在同一条斜线上】要求这题其实只是单纯的全排列问题在全排列的基础上根据N皇后的问题去除一些结果 arr n个皇后的列位置 res n皇后排列结果 ruler 记录对应的列位置是否已经占用也是是否有皇后如果有那么设为1没有设为0 setPos 哈希集合标记正斜线从左上到右下位置如果在相同正斜线上坐标(x,y)满足 y-x 都相同(y1 - x1)应该等于(y2 - x2)。 setCon 哈希集合标记反正斜线从y右上到左下位置如果在相同反斜线上坐标(x,y)满足 xy 都相同(x1 y1)应该等于(x2 y2)。 是否在同一斜线上其实就是这两个点的所形成的斜线的斜率是否为±1。点P(a,b) 点Q(c,d) 1斜率为1 (d-b)/(c-a) 1横纵坐标之差相等 2斜率为-1 (d-b)/(c-a) -1 等式两边恒等变形 ab c d 横纵坐标之和相等
/**** param n int整型 the n* return int整型*/
function Nqueen(n) {let res []; //二维数组存放每行Q的列坐标let isQ new Array(n).fill(0); //记录该列是否有Qlet setPos new Set(); //标记正对角线let setCon new Set(); // 标记反对角线//给当前row找一个colconst backTrace (row, path) {if (path.length n) {res.push(path);return;}for (let col 0; col n; col) {if (isQ[col] 0 !setPos.has(row - col) !setCon.has(row col)) {path.push(col);isQ[col] 1;setPos.add(row - col);setCon.add(row col);backTrace(row 1, path);path.pop();isQ[col] 0;setPos.delete(row - col);setCon.delete(row col);}}};backTrace(0, []);return res.length;
}
module.exports {Nqueen: Nqueen,
};动态规划的暴力求解阶段就是回溯算法。只是有的问题具有重叠子问题性质可以用 dp table 或者备忘录优化将递归树大幅剪枝这就变成了动态规划。
