wordpress能做流量站吗,哈尔滨寸金网站建设价格,网站建设方案模板高校,网络平台建站【ps】本篇有 9 道 leetcode OJ。 目录
一、算法简介
二、相关例题
1#xff09;全排列
.1- 题目解析
.2- 代码编写
2#xff09;子集
.1- 题目解析
.2- 代码编写
3#xff09;找出所有子集的异或总和再求和
.1- 题目解析
.2- 代码编写
4#xff09;全排列 II… 【ps】本篇有 9 道 leetcode OJ。 目录
一、算法简介
二、相关例题
1全排列
.1- 题目解析
.2- 代码编写
2子集
.1- 题目解析
.2- 代码编写
3找出所有子集的异或总和再求和
.1- 题目解析
.2- 代码编写
4全排列 II
.1- 题目解析
.2- 代码编写
5电话号码的字母组合
.1- 题目解析
.2- 代码编写
6括号生成
.1- 题目解析
.2- 代码编写
7组合
.1- 题目解析
.2- 代码编写
8目标和
.1- 题目解析
.2- 代码编写
9组合总和
.1- 题目解析
.2- 代码编写 一、算法简介 回溯算法是一种经典的递归算法通常⽤于解决组合问题、排列问题和搜索问题等。 回溯算法的基本思想从一个初始状态开始按照⼀定的规则向前搜索当搜索到某个状态无法前进时回退到前一个状态再按照其他的规则搜索。回溯算法在搜索过程中维护一个状态树通过遍历状态树来实现对所有可能解的搜索。 回溯算法的核心思想“试错”即在搜索过程中不断地做出选择如果选择正确则继续向前搜索否则回退到上一个状态重新做出选择。回溯算法通常用于解决具有多个解且每个解都需要搜索才能找到的问题。
// 回溯算法的模板
void dfs(vectorint path, vectorint choice, ...)
{// 满⾜结束条件if (/* 满⾜结束条件 */){// 将路径添加到结果集中res.push_back(path);return;}// 遍历所有选择for (int i 0; i choices.size(); i){// 做出选择path.push_back(choices[i]);// 做出当前选择后继续搜索dfs(path, choices);// 撤销选择path.pop_back();}
} 其中 path 表示当前已经做出的选择 choices 表示当前可以做的选择。在回溯算法中我们需要做出选择然后递归地调用回溯函数。如果满足结束条件则将当前路径添加到结果集中。 否则我们需要撤销选择回到上一个状态然后继续搜索其他的选择。回溯算法的时间复杂度通常较高因为它需要遍历所有可能的解。但是回溯算法的空间复杂度较低因为它只需要维护一个状态树。在实际应用中回溯算法通常需要通过剪枝等方法进行优化以减少搜索的次数从而提高算法的效率。 回溯算法是一种非常重要的算法可以解决许多组合问题、排列问题和搜索问题等。回溯算法的核心思想是搜索状态树通过遍历状态树来实现对所有可能解的搜索。回溯算法的模板非常简单但是实现起来需要注意一些细节比如何做出选择、如何撤销选择等。 二、相关例题
1全排列
46. 全排列 .1- 题目解析 全排列的过程其实可以画成一棵决策树而找出全排列的结果其实就是对这棵决策树进行 DFS。 DFS 的思路是循环模仿遍历树的结点到叶子结点就返回不是就进入循环。 在下面 for 循环里要考虑这个位置要填哪个数。根据题目要求我们肯定不能填已经填过的数因此很容易想到的一个处理手段就是定义一个标记数组来标记已经填过的数那么在填这个数的时候我们遍历题目给定的所有数如果这个数没有被标记过我们就尝试填入并将其标记继续尝试填下一个位置。而回溯的时候要撤销这一个位置填的数以及标记并继续尝试其他没被标记过的数。 .2- 代码编写
class Solution {vectorvectorint ret;vectorint path;bool check[7];
public:vectorvectorint permute(vectorint nums) {dfs(nums);return ret;}void dfs(vectorint nums){if(path.size()nums.size()){ret.push_back(path);return ;}for(int i0;inums.size();i)//枚举每一个在排列开头的数{if(check[i]false){//记录结果并遍历下一层path.push_back(nums[i]);check[i]true;dfs(nums);//回到这一层再恢复现场path.pop_back();check[i]false;}}}
}; 2子集
78. 子集 .1- 题目解析 本题有两种解法。 第一种与上一道题类似根据某一个元素选或不选将所有的子集穷举出来然后统计结果即可。 第二种解法则是根据子集中有多少个元素来将所有的子集穷举出来。 .2- 代码编写
//解法一
class Solution {vectorvectorint ret;vectorint path;
public:vectorvectorint subsets(vectorint nums) {dfs(nums,0);return ret;}void dfs(vectorint nums,int i){if(inums.size()){ret.push_back(path);return;}//不选dfs(nums,i1);//选path.push_back(nums[i]);//记录结果dfs(nums,i1);path.pop_back();//恢复现场}
};
//解法二
class Solution {vectorvectorint ret;vectorint path;
public:vectorvectorint subsets(vectorint nums) {dfs(nums,0);return ret;}void dfs(vectorint nums,int pos){ret.push_back(path);//每次进到下一层都是新结果都要记录for(int ipos;inums.size();i)//枚举下一层{path.push_back(nums[i]);//记录结果dfs(nums,i1); //进入下一层path.pop_back(); //回到当前层恢复现场}}
}; 3找出所有子集的异或总和再求和
1863. 找出所有子集的异或总和再求和 .1- 题目解析 这道题只需要在上一道的基础上稍微改变统计结果的方式即可。 .2- 代码编写
class Solution {int sum;int path;
public:int subsetXORSum(vectorint nums) {dfs(nums,0);return sum;}void dfs(vectorint nums,int pos){sumpath;for(int ipos;inums.size();i){path^nums[i];dfs(nums,i1);path^nums[i];}}
}; 4全排列 II
47. 全排列 II .1- 题目解析 我们可以直接在上文《全排列》的基础上用 set 对结果去重。 或者在上文《全排列》的基础上加入剪枝操作。由于题目不要求返回的排列顺序因此我们可以对初始状态排序将所有相同的元素放在各自相邻的位置方便之后操作。 .2- 代码编写
//解法一set去重
class Solution {setvectorint ret;vectorint path;bool cheak[8] {false};
public:vectorvectorint permuteUnique(vectorint nums) {dfs(nums);vectorvectorint tmp(ret.begin(), ret.end());return tmp;}void dfs(vectorint nums){if(nums.size() path.size()){// if(find(ret.begin(), ret.end(), path) ret.end())// ret.push_back(path);ret.insert(path);return;}for(int i 0; i nums.size(); i){if(cheak[i] false) // 如果没有用过{path.push_back(nums[i]);cheak[i] true;dfs(nums); // 此时路径已经加上一个了在让其进入递归path.pop_back(); // 回溯恢复现场递归往回走了cheak[i] false;}}}
};
//解法二剪枝关心不合法的分支
class Solution {vectorint path;vectorvectorint ret;bool check[9];
public:vectorvectorint permuteUnique(vectorint nums) {sort(nums.begin(),nums.end());dfs(nums);return ret;}void dfs(vectorint nums){if(path.size()nums.size()){ret.push_back(path);return;}for(int i0;inums.size();i){if(check[i]true|| (i!0 nums[i]nums[i-1] check[i-1]false)){continue;}path.push_back(nums[i]);check[i]true;dfs(nums);path.pop_back();check[i]false;}}
};
//解法三剪枝关心合法的分支
//解法二剪枝
class Solution {vectorint path;vectorvectorint ret;bool check[9];
public:vectorvectorint permuteUnique(vectorint nums) {sort(nums.begin(),nums.end());dfs(nums);return ret;}void dfs(vectorint nums){if(path.size()nums.size()){ret.push_back(path);return;}for(int i0;inums.size();i){if(check[i]false (i0 || nums[i]!nums[i-1] || check[i-1]true))//剪枝{path.push_back(nums[i]);check[i]true;dfs(nums);path.pop_back();check[i]false;}}}
}; 5电话号码的字母组合
17. 电话号码的字母组合 .1- 题目解析 每一个数字都对应了一串字符我们可以由此用一个哈希表建立数字和字符之间的映射以便通过数字找到相应的字符。 而其他过程同上文中的题目通过画决策树 DFS 来解决。 .2- 代码编写
class Solution {string hash[10]{,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};vectorstring ret;string path;
public:vectorstring letterCombinations(string digits) {if(digits.size()0)return ret;dfs(digits,0);return ret;}void dfs(string digits,int pos){if(posdigits.size()){ret.push_back(path);return;}for(auto ch:hash[digits[pos]-0]){path.push_back(ch);dfs(digits,pos1);path.pop_back();}}
}; 6括号生成
22. 括号生成 .1- 题目解析 .2- 代码编写
class Solution {int left,right,n;string path;vectorstring ret;
public:vectorstring generateParenthesis(int _n) {n_n;dfs();return ret;}void dfs(){if(rightn){ret.push_back(path);return ;}if(leftn){path.push_back(();left;dfs();path.pop_back();left--;}if(rightleft){path.push_back());right;dfs();path.pop_back();right--;}}
}; 7组合
77. 组合 .1- 题目解析 本题是上一道题的变形画决策树穷举出所有情况即可。 .2- 代码编写
class Solution {vectorint path;vectorvectorint ret;int n,k;
public:vectorvectorint combine(int _n, int _k) {n_n,k_k;dfs(1);return ret;}void dfs(int start){if(path.size()k){ret.push_back(path);return;}for(int istart;in;i){path.push_back(i);dfs(i1);path.pop_back();}}
}; 8目标和
494. 目标和 .1- 题目解析 .2- 代码编写
class Solution {
int ret,aim;
public:int findTargetSumWays(vectorint nums, int target) {aimtarget;dfs(nums,0,0);//参数原始数组、当前下标位置、决策树某一条路径之和return ret;}void dfs(vectorint nums,int pos,int path){if(posnums.size()){if(pathaim)ret;//统计结果return;}dfs(nums,pos1,pathnums[pos]);//穷举加dfs(nums,pos1,path-nums[pos]);//穷举减}
}; 9组合总和
39. 组合总和 .1- 题目解析 .2- 代码编写
//解法一枚举每个值之和
class Solution {int aim;vectorint path;vectorvectorint ret;
public:vectorvectorint combinationSum(vectorint nums, int target) {aimtarget;dfs(nums,0,0);return ret;}void dfs(vectorint nums,int pos,int sum){if(sumaim){ret.push_back(path);return;}if(sumaim || posnums.size())return;//回溯for(int ipos;inums.size();i){path.push_back(nums[i]);dfs(nums,i,sumnums[i]);path.pop_back();}}
};
//解法二枚举每个值的个数
class Solution {int aim;vectorint path;vectorvectorint ret;
public:vectorvectorint combinationSum(vectorint nums, int target) {aimtarget;dfs(nums,0,0);return ret;}void dfs(vectorint nums,int pos,int sum){if(sumaim){ret.push_back(path);return;}if(sumaim || posnums.size())return;//回溯for(int k0;k*nums[pos]aim;k) //枚举个数{if(k)path.push_back(nums[pos]);dfs(nums,pos1,sumk*nums[pos]);}for(int k1;k*nums[pos]aim;k){path.pop_back();}}
};
