wordpress主题网站,seo自学,wordpress 从新安装,手游app平台排行榜#回溯算法理论基础
能解决的问题#xff1a;
组合问题#xff1a;N个数里面按一定规则找出k个数的集合切割问题#xff1a;一个字符串按一定规则有几种切割方式子集问题#xff1a;一个N个数的集合里有多少符合条件的子集排列问题#xff1a;N个数按一定规则全排列…#回溯算法理论基础
能解决的问题
组合问题N个数里面按一定规则找出k个数的集合切割问题一个字符串按一定规则有几种切割方式子集问题一个N个数的集合里有多少符合条件的子集排列问题N个数按一定规则全排列有几种排列方式棋盘问题N皇后解数独等等 第77题. 组合
力扣题目链接(opens new window)
给定两个整数 n 和 k返回 1 ... n 中所有可能的 k 个数的组合。
示例: 输入: n 4, k 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],
注意
1、对于是递归回溯问题用树图来考虑问题使用基本结构 同时也要积极分析如何剪枝
2、路径类问题的标准套路 在函数外开辟path 和 ans 一层空间 ansint**malloc一层空间二层空间还没开辟 终止条件 if一条路径完成了 把path放入ans数组 先开辟ans的二层空间ans【i】int*malloc 放入path的过程需要用循环一个个放入直接path的话后面会随path修改而修改 递归体填充path
3、报错分析
遇见heap堆错误找malloc相关的遇见stack栈报错找函数内数组是否越界
4、returnsize 和 return column
*returnsize 在函数调用中无需且指向个数而非下标
column的赋值过程*column是正常数组先为*column开辟空间*column【第几个returnsize】ans【第几个】有多少个二层元素 分析 代码
void bf(int *path,int n,int start,int k,int *pathlength,int **ans,int *returnSize){if(*pathlength k-1){//路径类问题的标准输出ans[(*returnSize)](int *)malloc(sizeof(int)*k);for (int i0;ik;i){ans[*returnSize][i]path[i];}return;}for(int istart;in-(k-*pathlength-2);i){//遍历各个树//剪枝如果后面全放进去也达不到k个个数那么就不考虑了path[(*pathlength)]i;bf(path,n,i1,k,pathlength,ans,returnSize);(*pathlength)--;//回溯 步骤}
}int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {int **ans(int **)malloc(sizeof(int *)*200001);*returnSize-1;int pathlength-1;//考虑路径用到pathpathlengthint *path(int *)malloc(sizeof(int )*k);bf(path,n,1, k, pathlength,ans,returnSize);//returnsize不需要(*returnSize);//returnsize指向数组的实际大小*returnColumnSizes(int*)malloc(sizeof(int )*(*returnSize));//column的意义for(int i0;i(*returnSize);i){(*returnColumnSizes)[i]k;}return ans;
} 216.组合总和III
力扣题目链接(opens new window)
找出所有相加之和为 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] void bp(int **ans,int *size,int *path,int *p,int k,int n,int start,int sum){if(sumn) return;//剪枝if(sumn *pk){ans[*size](int *)malloc(sizeof(int)*k);for (int i0;ik;i){ans[*size][i]path[i];}(*size);return;//不要忘记写return}else if(*pk){//另外一种终止情况return;}for(int istart;i9;i){path[(*p)]i;bp(ans, size, path, p, k, n, i1, sumi);//i1而不是start1(*p)--;}
}int** combinationSum3(int k, int n, int* returnSize, int** returnColumnSizes) {int **ans(int **)malloc(sizeof(int *)*500);int size0;int *path(int *)malloc(sizeof(int)*k);int p0;bp(ans, size,path, p, k, n, 1, 0);*returnSizesize;*returnColumnSizes(int *)malloc(sizeof(int)*(size));for (int i0;isize;i){(*returnColumnSizes)[i]k;//要加括号}return ans;} 17.电话号码的字母组合
力扣题目链接(opens new window)
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 char phoneMap[11][5] {\0, \0, abc\0, def\0, ghi\0, jkl\0, mno\0, pqrs\0, tuv\0, wxyz\0};void bp(char**ans,int *size,char *path,int *p,int len,char* digits,int d){if(*plen){ans[*size] (char*)malloc(sizeof(char)*(len1));for(int i0;ilen;i){ans[*size][i]path[i];printf(%c,path[i]);} ans[*size][len]\0;printf(\n);(*size);return;}int number digits[d]-0;char * nowdphoneMap[number];int dlenstrlen(nowd);for(int i0;idlen;i){char newnowd[i];path[(*p)]new;bp(ans, size, path,p, len, digits,d1);(*p)--;}}char** letterCombinations(char* digits, int* returnSize) {int lenstrlen(digits);char**ans(char**)malloc(sizeof(char*)*pow(4,len));int size0;if (len0) {*returnSize0;return ans;}char *path(char*)malloc(sizeof(char)*(len1));int p0;bp(ans,size, path, p, len, digits, 0);*returnSizesize;return ans;}
