每周一道算法题(十八)
2017-07-16 本文已影响470人
CrazySteven
本周题目难度级别"Medium"，没错，比较难。。。
题目：就是给你一个数字n，让你输出n个左右括号"()"的排列组合。
思路：给一个n，则有n个左括号和n个右括号，排列组合用到了递归，把所有的组合列出来你就会发现两个原则，一是所有的组合都是从左括号开始，并且都是从1个左括号、2个左括号。。。一直到n个左括号；二是每个右括号的前面都会有一个左括号对应，例如第6个右括号前一定有大于等于6个的左括号与之对应。思路其实不难，关键是实现难，下面来看看代码(从英文注释下方开始看)：
void generate(char** result,int* size,int l,int r,char* tmp,int index){
//当左括号和右括号都用完的时候停止
if(l==0 && r==0){
//设置结束位
tmp[index]=0;
result[*size]=(char*)malloc(sizeof(char)*index);
//复制
strcpy(result[*size],tmp);
(*size)++;
return;
}
//左括号的个数大于0（原则一）
if(l>0){
//对应位置设为左括号
tmp[index]='(';
//递归
generate(result,size,l-1,r,tmp,index+1);
}
//右括号的个数大于0,并且左括号的个数小于右括号的个数（原则二）
if(r>0 && l<r){
tmp[index]=')';
//递归
generate(result,size,l,r-1,tmp,index+1);
}
}
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
char** generateParenthesis(int n, int* returnSize) {
char** result;
//存放一种组合
char* tmp=(char*)malloc(sizeof(char)*(n*2+1));
//l是左括号的个数，r是右括号的个数
int l=n,r=n;
//无法确定有多少种组合，就写的大一点
result =(char**)malloc(sizeof(char*)*1000000);
*returnSize=0;
//最后的0是从对应的位置，因为这是从第一个开始，所以是0
generate(result,returnSize,l,r,tmp,0);
return result;
}
