赣州网站建设哪家公司好,东莞什么平台好做,wordpress 导航 主题,网站建设费用计算依据创作目的#xff1a;为了方便自己后续复习重点#xff0c;以及养成写博客的习惯。
一、回溯算法
1、种类
排列、组合、分割、子集、棋盘问题
2、回溯步骤
#xff08;0#xff09;回溯抽象 回溯法解决的问题均可以抽象为树形结构#xff08;N叉树#xff09;
…创作目的为了方便自己后续复习重点以及养成写博客的习惯。
一、回溯算法
1、种类
排列、组合、分割、子集、棋盘问题
2、回溯步骤
0回溯抽象 回溯法解决的问题均可以抽象为树形结构N叉树
1回溯函数模板返回值以及参数 函数返回值一般为void回溯算的参数一般是先写逻辑然后需要什么参数就填什么参数。
2回溯函数终止条件
if(条件成立) {存放结果;return;
}
3回溯搜索的遍历过程 回溯法一般是在集合中递归搜索集合的大小构成了树的宽度递归的深度构成的树的深度。
3、与递归对比和效率
回溯与递归方法和步骤类似回溯是暴力查找效率不高。
二、组合
思路C解法参考了ledcode官方题解
lecode题目https://leetcode.cn/problems/combinations/ AC代码
int* temp;
int tempSize;int** ans;
int ansSize;void dfs(int cur, int n, int k) {// 剪枝temp 长度加上区间 [cur, n] 的长度小于 k不可能构造出长度为 k 的 tempif (tempSize (n - cur 1) k) {return;}// 记录合法的答案if (tempSize k) {int* tmp malloc(sizeof(int) * k);for (int i 0; i k; i) {tmp[i] temp[i];}ans[ansSize] tmp;return;}// 考虑选择当前位置temp[tempSize] cur;dfs(cur 1, n, k);tempSize--;// 考虑不选择当前位置dfs(cur 1, n, k);
}int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {temp malloc(sizeof(int) * k);ans malloc(sizeof(int*) * 200001);tempSize ansSize 0;dfs(1, n, k);*returnSize ansSize;*returnColumnSizes malloc(sizeof(int) * ansSize);for (int i 0; i ansSize; i) {(*returnColumnSizes)[i] k;}return ans;
}全篇后记 做起来有点蒙不是很能理解其中的奥妙希望通过后续的刷题能理清思路。
