网页设计基础入门_中企动力济南分公司_大型seo公司_产品推广方式都有哪些

一、回溯算法思想：

• 本质是穷举，当发现不满足求解条件是，就回溯返回，尝试别的路径
• 重要的是找到嵌套逻辑和终止条件。

二、回溯算法模板：

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}

• 回溯算法要素：
  • 回溯（嵌套）逻辑和参数
  • 回溯终止条件和存放结果方式
  • 回溯搜索的循环体

三、leetcode

• 77. 组合 https://leetcode.cn/problems/combinations/
  • 题目描述：返回范围 [1, n] 中所有可能的 k 个数的组合
  • 题解思路：
    • 当求解1个数的所有组合时，我们可以使用1层for循环
    • 当求解2个数的所有组合时，我们可以使用2层for循环
    • 当求解k个数的所有组合时，我们可以使用k层for循环
    • for循环嵌套结束条件：当循环超过k层时，保存结果并返回。
• 39. 组合总数 https://leetcode.cn/problems/combination-sum/

  • 题目描述：找给定数组can中元素满足数字和为target的不同组合（可重复）

  • 解题思路：

    • 首先确定回溯逻辑和参数：function backTrack(nums, sum, j)
      • nums是用来存储满足条件组合的数组，nums[i]代表的是这个组合包含can[i]的个数
      • sum是组合目前的数组和
      • j是代表目前正在搜索can的j位
    • 接下来确定终止条件和存放结果方式
      • 终止条件1：当sum===target要输出结果，将nums数组转化为题目要求的组合形式然后添加到结果数组中
      • sum>targrt怎么办？通过在循环体中控制，只会sum<=target
      • 终止条件2：当j>=can.length时要return
    • 确定回溯循环体逻辑
      • 搜索当前can[j]可能的个数i，i范围为i<=(target-sum)/can[j])
      • 需要注意的是，因为每个数组最后代表一种组合方式，所以要对数组进行处理，控制数组的第j位nums[i]代表的是这个组合包含can[i]的个数

  • 最后JavaScript代码：

    var combinationSum = function (can, target) {let ans = [];   //定义保存结果的数组function backTrack(nums, sum, j) {// console.log(nums,sum,j)if (sum === target) {        //保存结果的逻辑及终止条件1let arr = [];for (let i = 0; i < nums.length; i++) {for (let j = 0; j < nums[i]; j++) {arr.push(can[i]);}}ans.push(arr);return;}if (j >= can.length) return;   //终止条件2for (let i = 0; i <= (target - sum) / can[j]; i++) {   //can[j]的个数为i时，循环体nums.push(i);backTrack(nums, sum + i * can[j], j + 1);nums.pop();         //保证下次循环时nums的长度符合要求}}backTrack([], 0, 0);   //调用函数return ans;   //返回最后结果
    };
    

• 78. 子集 https://leetcode.cn/problems/subsets/description/
  • 题目描述：返回数组的所有子集
  • 解题思路1：77.组合的进阶版，在77中仅需输出k个数的组合，而此题需输出0-n个数的所有组合。77中元素是连续的，在这道题中，数组的下标也是连续的，可以借用下标去使用77中的逻辑。
  • JavaScript代码

    var subsets = function(nums) {let ans=[];let n=nums.length;function backtrack(arr,m){   //arr为下标形式表示的子集if(arr.length===m){let array=arr.map(a=>nums[a]);ans.push(array);return;}for(let i=(arr[arr.length-1]+1)|0;i<=n-m+arr.length;i++){arr.push(i);backtrack(arr,m);arr.pop();}}for(let i=0;i<=n;i++){backtrack([],i);}return ans;};
    

• 22. 括号生成 https://leetcode.cn/problems/generate-parentheses/description/
  • 题目描述：生成n对括号所有的有效组合
  • 解题思路1：在回溯的同时满足有效的规则，所谓有效的规则就是
    • 左括号的个数>=右括号的个数
    • 左括号的个数<=n
  • JavaScript代码

    var generateParenthesis = function(n) {let ans=[];let arr=[];const backtrack=(a,b)=>{if(a==n&&b==n){ans.push(arr.join(''));return;}if(a>n||b>n)returnif(a<n){arr.push('(');backtrack(a+1,b);arr.pop();}if(b<a){arr.push(')');backtrack(a,b+1);arr.pop();}}backtrack(0,0);return ans; 
    };
    

• 51. N皇后 https://leetcode.cn/problems/n-queens/description/
  • 题目描述：在n*n的棋盘上放n个皇后，要求不能在同一行、同一列、同一45度斜线，求解所有组合。
  • 解题思路1：首先要理解清楚摆放规则，然后转化为代码
    • 摆放规则就是当我们在讨论第n行的皇后位置时，不能与之前每一行的皇后处于同一列或者45度角的位置。如果存在这样的位置，那么继续递归。
    • 终止/输出条件：当遍历完棋盘且有N个皇后时，保存结果，并且return
  • JavaScript代码：

    var solveNQueens = function (n) {let ans = [];let arr = [];const backtrack = (a) => {   //代表第a行时的情况// console.log(a,arr)if (a === n) {let array = Array(n).fill(0).map(a=>Array(n).fill('.'));for (let i of arr) {array[i[0]][i[1]]='Q';}let tem=array.map(a=>a.join(''));ans.push(tem);return;}if (a > n) returnfor (let i = 0; i < n; i++) {if (arr.length == 0) {arr.push([0, i]);backtrack(a + 1);arr.pop();} else {let sig = 0;for (let j = 0; j < arr.length; j++) {if (i === arr[j][1] || i === (arr[j][1] + a-arr[j][0] )|| i === (arr[j][1] - a+arr[j][0])) {// console.log(arr)sig = 1;}}if (sig === 0) {arr.push([a, i]);backtrack(a + 1);arr.pop();}}}}backtrack(0);return ans;
    };
    

  • 缺点：由于每次都要遍历棋盘的前几行，复杂度比较高。
  • 52. N皇后2和此题基本一致，更简单了，输出只需要输出组合数量。
• 131. 分割回文串 https://leetcode.cn/problems/palindrome-partitioning/description/
  • 题目描述：返回s所有的回文子串分割方案
  • 解题思路：先利用动态规划将以第i个元素开头的回文串全部找到，然后再利用回溯进行组合输出
  • JavaScript代码：

    var partition = function (s) {let n = s.length;const mark = Array(n).fill(0).map(a => Array(n).fill(false));  //动态规划标记矩阵const ans=[];const arr=Array(n).fill(0).map(a=>[]);   //将动态规划的结果保存在arr中const tem=[];   //临时矩阵，保存每次的结果/**动态规划来寻找所有的回文串 */for (let i = 0; i < n; i++) {mark[i][i] = true;arr[i].push(i);}for (let i = 0; i < n; i++) {if (i + 1 < n && s[i] === s[i + 1]) {mark[i][i+1]=true;arr[i].push(i+1);let a = 1;while (i - a >= 0 && i + a + 1 < n && mark[i - a + 1][i + a] === true) {if (s[i - a] === s[i + a + 1]) {mark[i - a][i + a + 1] = true;arr[i-a].push(i+a+1);}a++;}}let a = 1;while (i - a >= 0 && i + a < n && mark[i - a + 1][i + a - 1] === true) {if (s[i - a] === s[i + a]) {mark[i - a][i + a] = true;arr[i-a].push(i+a);}a++;}}// console.log(arr)/**将各个回文串按照不同的组合进行回溯输出 */const backtrack=(a)=>{if(a>=n){    //当需要递归的元素位数超过或等于n时，保存结果并回溯回去。ans.push(tem.slice());  return;}for(let i of arr[a]){tem.push(s.slice(a,i+1));   //将[a,i+1)范围的字符串加入tembacktrack(i+1);            //然后从i+1继续递归tem.pop();}}backtrack(0);return ans;
    };