郴州网站制作怎么做盗版小说网站吗

当前位置： 首页 > news >正文

郴州网站制作,怎么做盗版小说网站吗,百度搜索引擎介绍,12306网站开发人员回溯算法基础知识 一种效率不高的暴力搜索法。本质是穷举。有些问题能穷举出来就不错了。 回溯算法解决的问题有#xff1a; 组合问题#xff1a;N个数里面按一定规则找出k个数的集合切割问题#xff1a;一个字符串按一定规则有几种切割方式子集问题#xff1a;一个N个数…回溯算法基础知识 一种效率不高的暴力搜索法。本质是穷举。有些问题能穷举出来就不错了。 回溯算法解决的问题有 组合问题N个数里面按一定规则找出k个数的集合切割问题一个字符串按一定规则有几种切割方式子集问题一个N个数的集合里有多少符合条件的子集排列问题N个数按一定规则全排列有几种排列方式棋盘问题N皇后解数独等等 如何理解 回溯法解决的问题都可以抽象为树形结构是的我指的是所有回溯法的问题都可以抽象为树形结构 因为回溯法解决的都是在集合中递归查找子集集合的大小就构成了树的宽度递归的深度就构成了树的深度。 递归就要有终止条件所以必然是一棵高度有限的树N叉树。 回溯搜索的遍历过程 在上面我们提到了回溯法一般是在集合中递归搜索集合的大小构成了树的宽度递归的深度构成的树的深度。 如图 回溯算法模板 void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果} } 77.组合  题目77. 组合 - 力扣LeetCode 给定两个整数 n 和 k返回 1 … n 中所有可能的 k 个数的组合。 示例: 输入: n 4, k 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 递归里有for循环。 抽象成树形结构  然后就是经典的回溯三部曲 ·递归函数的参数和返回值 ·回溯终止条件 ·单层递归逻辑单层搜索过程 代码 class Solution {vectorvectorintresult;vectorintpath;private:void backtraking(int n,int k,int startIndex){if(path.size()k)//终止条件{result.push_back(path);//记录路径结果return;}//单层搜索过程for(int istartIndex;in;i){path.push_back(i);backtraking(n,k,i1);//递归搜索path.pop_back();//回溯撤销操作}} public:vectorvectorint combine(int n, int k) {backtraking(n,k,1);return result;} }; 这个和找二叉树路径总和那题还挺像的。 剪枝优化写法 来举一个例子n 4k 4的话那么第一层for循环的时候从元素2开始的遍历都没有意义了。 在第二层for循环从元素3开始的遍历都没有意义了。 这么说有点抽象如图所示 图中每一个节点图中为矩形就代表本层的一个for循环那么每一层的for循环从第二个数开始遍历的话都没有意义都是无效遍历。 所以可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。 如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了那么就没有必要搜索了。 优化过程 已经选择的元素个数path.size(); 还需要的元素个数为: k - path.size(); 在集合n中至多要从该起始位置 : n - (k - path.size()) 1开始遍历 为什么有个1呢因为包括起始位置我们要是一个左闭的集合。 举个例子n 4k 3 目前已经选取的元素为0path.size为0n - (k - 0) 1 即 4 - ( 3 - 0) 1 2。 从2开始搜索都是合理的可以是组合[2, 3, 4]。 所以优化之后的for循环是 for (int i startIndex; i n - (k - path.size()) 1; i) // i为本次搜索的起始位置 216.组合总和Ⅲ 题目216. 组合总和 III - 力扣LeetCode 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数并且每种组合中不存在重复的数字。 说明 所有数字都是正整数。解集不能包含重复的组合。 示例 1: 输入: k 3, n 7 输出: [[1,2,4]] 示例 2: 输入: k 3, n 9 输出: [[1,2,6], [1,3,5], [2,3,4]] 图思路 未剪枝版本 class Solution {private:vectorvectorintresult;vectorintpath;void backtraking(int k,int n,int sum,int startindex){if(path.size()k){if(sumn)result.push_back(path);return;//如果path.size() k 但sum ! targetSum 直接返回}for(int istartindex;i9;i){sumi;path.push_back(i);backtraking(k,n,sum,i1);//回溯操作发生于当第一个if条件满足后不管sum是否得到结果然后继续遍历所有情况sum-i;path.pop_back();}//这里注意我自己写的差别就是不需要if判断sum是否大等小于目标值的情况。} public:vectorvectorint combinationSum3(int k, int n) {result.clear();path.clear();backtraking(k,n,0,1);return result;} }; 在回溯算法中回溯操作的发生时机通常是在满足某种条件后或者在尝试所有可能性后。具体来说在组合求和问题中回溯操作的发生时机有两个主要情况 条件达成时的回溯 当当前路径 path 的长度达到了要求的 k即 path.size() k并且当前路径的和 sum 满足了要求例如 sum n此时会将当前路径 path 加入到结果集 result 中并进行回溯操作。 回溯操作包括将当前操作的影响从当前路径和当前状态中撤销以便尝试其他可能的路径组合。递归调用结束后的回溯 在递归调用中当完成了对当前数字的处理后通常是尝试加入当前数字并递归处理下一个数字会进行回溯操作。这里很重要在打日志时就可以看到回溯是如何进行的了 这种情况下回溯操作是为了确保在递归返回到当前层级时状态已经被恢复到递归前的状态从而可以尝试其他可能的数字组合。 在具体的实现中回溯操作通常包括以下步骤 ····加入当前选择将当前数字加入到路径 path 中并更新当前的和 sum。····递归处理递归调用下一层级处理下一个数字。····回溯在递归调用返回后撤销当前数字的选择将其从路径 path 中移除并恢复当前的和 sum 到递归前的状态。 回溯操作的发生时机是保证算法能够在所有可能的路径中搜索并且在满足条件或者确定无法满足条件时及时回溯以尝试其他可能的组合。 以本题为例子理解的回溯过程。 acm模式代码如图 #include iostream #include vectorusing namespace std;vectorvectorint result; vectorint path;void backtracking(int k, int n, int sum, int startindex) {if (sum n)return;if (path.size() k) {if (sum n) {result.push_back(path);cout 存入一条路径 endl;}return;}for (int i startindex; i 9; i) {sum i;path.push_back(i);cout 路径加入一个数 endl;backtracking(k, n, sum, i 1);// 回溯操作sum - i;path.pop_back();cout 撤销操作回溯到上一个状态寻找其他数字组合 endl;} }vectorvectorint combinationSum3(int k, int n) {result.clear();path.clear();cout 调用combinationSum3函数 endl;backtracking(k, n, 0, 1);return result; }int main() {int k, n;// 从标准输入读取数据while (cin k n) {result combinationSum3(k, n);// 输出结果for (const auto combination : result) {for (int num : combination) {cout num ;}cout endl;}}return 0; }日志如图 可以看出找到第一条路径后就开始剪枝操作了。  从这里开始有两条一模一样的撤销操作和加入数的操作。证明一个数字和它的所有组合已经遍历完了。将从第二个数字开始查找符合条件的组合。  如果有第二条路径的话 路径加入一个数 路径加入一个数 开始剪枝 撤销操作回溯到上一个状态寻找其他数字组合 路径加入一个数 开始剪枝 撤销操作回溯到上一个状态寻找其他数字组合 路径加入一个数 开始剪枝 撤销操作回溯到上一个状态寻找其他数字组合 路径加入一个数 开始剪枝 撤销操作回溯到上一个状态寻找其他数字组合 路径加入一个数 开始剪枝 撤销操作回溯到上一个状态寻找其他数字组合 路径加入一个数 开始剪枝 撤销操作回溯到上一个状态寻找其他数字组合 路径加入一个数 开始剪枝 撤销操作回溯到上一个状态寻找其他数字组合 撤销操作回溯到上一个状态寻找其他数字组合 路径加入一个数 路径加入一个数 开始剪枝 撤销操作回溯到上一个状态寻找其他数字组合 路径加入一个数 开始剪枝 撤销操作回溯到上一个状态寻找其他数字组合 路径加入一个数 开始剪枝 撤销操作回溯到上一个状态寻找其他数字组合 路径加入一个数 开始剪枝 撤销操作回溯到上一个状态寻找其他数字组合 路径加入一个数 开始剪枝 撤销操作回溯到上一个状态寻找其他数字组合 路径加入一个数 开始剪枝 撤销操作回溯到上一个状态寻找其他数字组合 撤销操作回溯到上一个状态寻找其他数字组合 路径加入一个数 路径加入一个数 开始剪枝 撤销操作回溯到上一个状态寻找其他数字组合 路径加入一个数 开始剪枝 撤销操作回溯到上一个状态寻找其他数字组合 路径加入一个数 开始剪枝 撤销操作回溯到上一个状态寻找其他数字组合 路径加入一个数 开始剪枝 撤销操作回溯到上一个状态寻找其他数字组合 路径加入一个数 开始剪枝 撤销操作回溯到上一个状态寻找其他数字组合 撤销操作回溯到上一个状态寻找其他数字组合 路径加入一个数 开始剪枝 撤销操作回溯到上一个状态寻找其他数字组合 路径加入一个数 开始剪枝 撤销操作回溯到上一个状态寻找其他数字组合 路径加入一个数 开始剪枝 撤销操作回溯到上一个状态寻找其他数字组合 路径加入一个数 开始剪枝 撤销操作回溯到上一个状态寻找其他数字组合 路径加入一个数 开始剪枝 撤销操作回溯到上一个状态寻找其他数字组合 1 3 剪枝情况 在递归函数开头剪枝好 if (sum targetSum) { // 剪枝操作return; } 17.电话号码的字母组合 题目17. 电话号码的字母组合 - 力扣LeetCode 给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。 给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 示例: 输入23输出[ad, ae, af, bd, be, bf, cd, ce, cf]. 说明尽管上面的答案是按字典序排列的但是你可以任意选择答案输出的顺序 思路 回溯的树形结构理解 深度是用户按键的digit长度如例子中就是2.递归函数有一个参数index。。这个index是记录遍历第几个数字了就是用来遍历digits的题目中给出数字字符串同时index也表示树的深度。 而横向遍历的宽度即for循环次数获取到的所有结果集。 代码 class Solution {private://键盘按键数字和字母的映射const string letterMap[10] {, // 0, // 1abc, // 2def, // 3ghi, // 4jkl, // 5mno, // 6pqrs, // 7tuv, // 8wxyz, // 9}; public:vectorstringresult;string s;void backtraking(const string digits,int index){if(indexdigits.size())//当 index 达到 digits.size() 时说明已经遍历完所有的数字将当前的组合 s 添加到 result 中然后返回。{result.push_back(s);return;}int digitdigits[index]-0;//string类型转intstring lettersletterMap[digit];for(int i0;iletters.size();i){s.push_back(letters[i]);backtraking(digits,index1);//探索下一层数字对应的字母了s.pop_back();//回溯在递归返回后通过 s.pop_back() 撤销之前的选择尝试其他字母组合。}}vectorstring letterCombinations(string digits) {result.clear();if(digits.size()0)return result;backtraking(digits,0);return result;} }; 我的疑惑index不会递增下去吗 回溯的执行过程和 index 的变化 以 digits 23 为例递归处理时的 index 变化如下 初始调用 backtracking(23, 0): index 0处理 digits[0] 2对应的字母是 abc。第一个递归调用选择 a调用 backtracking(23, 1)。 递归调用 backtracking(23, 1): index 1处理 digits[1] 3对应的字母是 def。第一个递归调用选择 d调用 backtracking(23, 2)。 递归调用 backtracking(23, 2) 此时 index 2已经达到了 digits.size()所以将当前组合 ad 加入结果 result 中并返回。这里 index 不再继续增加而是返回到上一层backtracking(23, 1)。 回溯到 backtracking(23, 1) 从组合 ad 中撤销 d并选择下一个字母 e继续递归调用 backtracking(23, 2)。 递归调用 backtracking(23, 2) 再次达到 index 2组合 ae 加入结果并返回到上一层。 继续回溯撤销 e选择 f重复上述过程将 af 加入结果。 完全处理完 a 后回到 backtracking(23, 0) 撤销 a选择 b重复上述过程处理 bd, be, bf。 最后处理 c得到 cd, ce, cf。 为什么 index 不会一直递增 每次递归调用时index 加 1是为了处理下一个数字对应的字母组合。当递归返回时index 会回到上一层并且回到上一层的状态后会尝试其他的可能性选择下一个字母然后再进行递归处理。每次递归到达终点即 index digits.size()时递归结束将当前的路径结果存入 result接着回溯撤销选择并返回上一层。 一些写法是把回溯的过程放在递归函数里了 如for循环变成了这样相应的递归参数多了个string s初始值是“” for (int i 0; i letters.size(); i) {getCombinations(digits, index 1, s letters[i]); 这里隐藏了回溯的写法。 要彻底理解回溯的过程可以自己打下日志逐行看下代码进行过程。