每周一道算法题(十八)

本周题目难度级别"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;  
}

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!