企业官网建设流程全解析

wordpress直接访问站点,电商网站建设流程,天津市住房和城乡建设厅官方网站,seo网站文章编辑软件递归回溯法 一、什么是回溯 回溯本质上属于深度优先搜索#xff08;DFS#xff09;#xff0c;运用到的思想是暴力枚举#xff0b;剪枝 从字面意思也很好理解#xff0c;他的步骤就是**枚举所有的可能#xff0c;边枚举边验证#xff0c;无效则回退**显然在一…递归回溯法一、什么是回溯回溯本质上属于深度优先搜索DFS运用到的思想是暴力枚举剪枝从字面意思也很好理解他的步骤就是**枚举所有的可能边枚举边验证无效则回退**显然在一些需要穷举所有可能的题就能用上。其中我们一般会定义一个char* path或int* path作为一次路径探索的容器即一次被探索构建完成满足问题条件的path代表一种完全可能满足条件的一种可能的答案// 通用回溯模板伪代码voidbacktrack(路径,选择列表,结果集){if(触发限制条件)return;// 剪枝if(满足终止条件){// 一次完整解决了问题的情况把路径加入结果集;return;}for(每个可选的选择 in 选择列表){// 基准问题每一步做选择把选择加入路径;backtrack(路径,选择列表,结果集);// 递归撤销选择把选择从路径中移除;// 回溯}}二、回溯的基本思路回溯的模板通常大差不差具体区别就是每一题的具体要求使得剪枝、穷举、组合的具体规则不尽相同因此理解每一个板块的核心思路很重要1.确定问题被解决的情况确定基准问题顾名思义这一部分的思路目标就是1. 确定什么情况算完成了一种可能的答案对应模板中第二个if情况和return2. 把整个问题拆分细解到最小最基层的每一步对应模板中的for循环部分例题给1到n的正整数取其中k个进行组合能有多少种不同的组合基准取1到n的其中一个数加入path中一次被解决的情况path内已填入元素的个数刚好等于k个例题每个数字可以代表多个字母如1可以是a、b或c给出一串数字其代表字母的所有可能基准针对一个数字取这个数字可代表的所有字母中的一个加入path中一次被解决的情况每个数字都取了一个对应字母加入了pathpath内字母的个数等于数字串长度2.确定底线/剪枝条件 or 限制探索步骤这一步就是弄明白在path探索的过程中当探索过并已加入了path的元素触犯了什么条件就会使这一次探索不再符合题目条件从而需要剪枝return或者在递归调用的时候让元素从新的start开始遍历避免重复例题给数字n生成n对“合法的”括号有多少种可能的组合底线约束方式1当前已生成的右括号数大于左括号数无法向左合法匹配底线约束方式2已生成的左括号数或者右括号数超过了n多于n对例题例题给1到n的正整数取其中k个进行组合不能重复取能有多少种不同的组合底线约束方式递归调用时让下一个数字的遍历探索从i1开始函数参数多一个startstart作为for循环i的起始也就是分成了两种类型的剪枝剪枝类型作用典型场景示例条件剪枝操作合法性剪枝终止「本身无效」的路径括号生成、组合总和括号生成右括号数 左括号数组合总和sum targetreturn重复性剪枝避免「重复生成」相同的路径组合、子集、全排列组合for 循环从 start 开始全排列used 数组标记已选元素传新参start其中传新参和return的操作都很明了易懂下面详细讲一下用used数组标记已使用元素的做法used数组的完整使用步骤初始化used数组在主函数中分配内存并初始化为 0未选状态长度等于数组长度int*used(int*)calloc(numsSize,sizeof(int));// calloc 自动初始化为 0等价于 malloc memset遍历中判断used状态剪枝在回溯的for循环中跳过已标记的元素for(inti0;inumsSize;i){if(used[i]1)continue;// 跳过已选元素核心剪枝// 选择元素 递归 回溯}选择元素时标记used将当前元素加入路径后标记used[i] 1used[i]1;// 标记为已选path[path_idx]nums[i];// 加入路径递归返回后撤销标记回溯核心递归返回后将used[i]恢复为 0让该元素可被后续路径选择backtrack(...);// 递归used[i]0;// 撤销标记回溯三、解题过程中的一些坑难点主要聚焦在由于组合问题带来的需要返回结果大小的要求力扣/** * Return an array of arrays of size *returnSize. * The sizes of the arrays are returned as *returnColumnSizes array. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). */int**xxxxxx(...,int*returnSize,int**returnColumnSizes){}参数名类型核心作用int** 返回值二维 int 数组存储所有最终结果如所有组合 / 排列 / 括号串int* returnSize一级指针输出参数返回「结果集的行数」即有多少个合法答案int** returnColumnSizes二级指针输出参数返回「每行结果的列数」即每个结果有多少个元素必须先为returnColumnSizes分配「和结果集行数上限匹配」的内存//main内intmax_size200000;// 结果集最大行数根据题目预估*returnColumnSizes(int*)malloc(max_size*sizeof(int));// 分配一维数组//自定义递归函数内的已完成分支内(*returnColumnSizes)[*answer_idx]k;//左式相当于(*returnColumnSizes)[*answer_idx][0]虽说是一个数组但其实只要一个数memcpy(目标, 源, 元素个数 *sizeof(元素类型))memcpy(answer[*answer_idx],path,k*sizeof(int));//重点在要有sizeof类型// 字符串类如括号生成memcpy(ans[idx], path, len * sizeof(char));主函数末尾必须将「实际生成的结果数」赋值给*returnSize*returnSizeanswer_idx;// answer_idx是回溯中统计的结果行数一般常规操作voidbacktravel(...,int**answer,int*answer_idx,int**returnColumnSizes,intpath_idx,int*path,intstart,...){if(完整条件){//完成填满answer[*answer_idx](int*)malloc(ok_size*sizeof(int));memcpy(answer[*answer_idx],path,ok_size*sizeof(int));(*returnColumnSizes)[*answer_idx]ok_size;//这个ok_size看题目来变动一般是等于path_idx(*answer_idx);return;//不要忘了这个}for(intistart;in;i){//基准的每一步path[path_idx]i;backtravel(...,answer,answer_idx,returnColumnSizes,path_idx1,path,i1,...);}}main(){int**answer(int**)malloc(max_size*sizeof(int*));//max_size根据题意调整int*path(int*)calloc(max_size,sizeof(int));*returnColumnSizes(int*)malloc(max_size*sizeof(int));intanswer_idx0;backtravel(...,answer_idx,...);free(path);*returnSizeanswer_idx;returnanswer;}四、例题题解这题只需穷举还不存在明显的剪枝constchar*numtoword[]{//定义数字对应字母集,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz,};//确定基准每一个数字的所有可能//for遍历解决每个数字的所有可能递归解决这个数字紧接着的下一个数字的所有可能//path是一个字符串代表一种完全可能每个数字都已对应着某一种字母的排列voidbacktrap(char*digits,char**answer,int*answer_idx,char*path,intpath_idx){if(digits[path_idx]\0){//这条路已经探索完整answer[*answer_idx](char*)malloc((strlen(path)1)*sizeof(char));strcpy(answer[*answer_idx],path);(*answer_idx);//作用于全体因为是下一条路了return;}//对于当前数字for遍历当前数字的所有可能intnumdigits[path_idx]-0;intpossible_lenstrlen(numtoword[num]);//这个数字对应的字母集的长度就是他所有可能的个数for(inti0;ipossible_len;i){//基准的最小步path[path_idx]numtoword[num][i];backtrap(digits,answer,answer_idx,path,path_idx1);//对于这个数字的这个字母他的下一个数字对应的字母又有许多可能}}char**letterCombinations(char*digits,int*returnSize){intdigits_lenstrlen(digits);intpossible_path_count0;int*pb_pacpossible_path_count;intanswer_max_size1;//最大的 可能的“组合” 的 个数for(inti0;idigits_len;i){intnumdigits[i]-0;answer_max_size*strlen(numtoword[num]);}char**answer(char**)malloc(answer_max_size*sizeof(char*));char*path(char*)malloc((digits_len1)*sizeof(char));//每条路即每个组合的字母数显然等于数字个数加一个给\0path[digits_len]\0;backtrap(digits,answer,pb_pac,path,0);//从第一个数字开始*returnSizepossible_path_count;free(path);returnanswer;}题解本题出现了剪枝voidbacktrap(char**answer,char*path,intpath_idx,int*answer_idx,inttotaltimes,intlessleft,intlessright){if(lessleft0||lessright0||lessrightlessleft)return;//剪枝if(path_idxtotaltimeslessleft0lessright0){//完成一条路answer[*answer_idx](char*)malloc((totaltimes1)*sizeof(char));strcpy(answer[*answer_idx],path);(*answer_idx);return;}if(lessleft0){path[path_idx](;backtrap(answer,path,path_idx1,answer_idx,totaltimes,lessleft-1,lessright);path[path_idx]\0;}if(lessright0path_idx!0){path[path_idx]);backtrap(answer,path,path_idx1,answer_idx,totaltimes,lessleft,lessright-1);path[path_idx]\0;}}char**generateParenthesis(intn,int*returnSize){inttotaltimesn*2;intmax_size2000;char**answer(char**)malloc(max_size*sizeof(char*));char*path(char*)calloc(totaltimes1,sizeof(char));intpath_idx0,answer_idx0;int*ans_idxanswer_idx;backtrap(answer,path,0,ans_idx,totaltimes,n,n);*returnSizeanswer_idx;free(path);returnanswer;}题解本题用到了used数组避免重复元素voidback(int*nums,intnumsSize,int*used,int*path,int**answer,int*answer_idx,intpath_idx,int**returnColumnSizes){if(path_idxnumsSize){answer[*answer_idx](int*)malloc(numsSize*sizeof(int));memcpy(answer[*answer_idx],path,numsSize*sizeof(int));(*returnColumnSizes)[*answer_idx]numsSize;(*answer_idx);return;}for(inti0;inumsSize;i){if(used[i]1)continue;used[i]1;path[path_idx]nums[i];back(nums,numsSize,used,path,answer,answer_idx,path_idx1,returnColumnSizes);used[i]0;}}int**permute(int*nums,intnumsSize,int*returnSize,int**returnColumnSizes){int**answer(int**)malloc(1000*sizeof(int*));int*path(int*)malloc(numsSize*sizeof(int));*returnColumnSizes(int*)malloc(1000*sizeof(int));int*used(int*)calloc(numsSize,sizeof(int));intanswer_idx0;back(nums,numsSize,used,path,answer,answer_idx,0,returnColumnSizes);*returnSizeanswer_idx;returnanswer;}题解本题用到了传新参start避免结果的重复如[2,2,3]和[2,3,2])voidbacktravel(int*candidates,intcandidatesSize,inttarget,int**returnColumnSizes,int*path,int**answer,int*answer_idx,intpath_idx,intsum,intstart){if(sumtarget)return;//剪枝if(sumtarget){//完成一条路answer[*answer_idx](int*)malloc(path_idx*sizeof(int));memcpy(answer[*answer_idx],path,path_idx*sizeof(int));(*returnColumnSizes)[*answer_idx]path_idx;(*answer_idx);return;}for(intistart;icandidatesSize;i){intnumcandidates[i];path[path_idx]num;backtravel(candidates,candidatesSize,target,returnColumnSizes,path,answer,answer_idx,path_idx1,sumnum,i);}}int**combinationSum(int*candidates,intcandidatesSize,inttarget,int*returnSize,int**returnColumnSizes){int**answer(int**)malloc(150*sizeof(int*));int*path(int*)calloc(100,sizeof(int));*returnColumnSizes(int*)malloc(150*sizeof(int));intanswer_idx0;backtravel(candidates,candidatesSize,target,returnColumnSizes,path,answer,answer_idx,0,0,0);*returnSizeanswer_idx;free(path);returnanswer;}