首页 > 试题广场 >

括号生成

[编程题]括号生成
  • 热度指数：70717 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。
例如，给出n=3，解集为：
"((()))", "(()())", "(())()", "()()()", "()(())"

数据范围：
要求：空间复杂度 O(n)，时间复杂度 O(2^n)
示例1

输入

1

输出

["()"]
示例2

输入

2

输出

["(())","()()"]
算法知识视频讲解
查看答案及解析
添加回答
C
一个优雅的程序猿头像 一个优雅的程序猿
土算法 
int cmp(const void *a, const void *b) {
    int i=0;
    while(i<strlen(*(char**)a)) {
        if((*(char**)a)[i] > (*(char**)b)[i])
            return 1;
        else if((*(char**)a)[i] < (*(char**)b)[i])
            return -1;
        else
            i++;
    }
    return 0;
}
    
char** generateParenthesis(int n, int* returnSize ) {
    char **proRes, **res, **lastres;
    int lastreturnSize, proResreturnSize;
    int i, j;
    proRes = (char**)malloc(pow(2,14));
    for(i=0; i<pow(2,14); i++) 
        proRes[i] = (char*)malloc(n*2+1);
    if(n==0)
        *returnSize = 0;
    strcpy(proRes[0], "()");
    *returnSize = 1;
    if(n==1) 
        return proRes;

    lastres = generateParenthesis(n-1, &lastreturnSize);
    for(i=0, proResreturnSize=0; i<lastreturnSize; i++) {
        for(j=0; j<strlen(lastres[i])+1; j++) {
            if(j==0) {
                strcpy(proRes[proResreturnSize], "()");
                strcat(proRes[proResreturnSize++], lastres[i]);
            }
            else if(lastres[i][j-1]=='(' && lastres[i][j]==')') {
                strncpy(proRes[proResreturnSize], lastres[i], j);
                proRes[proResreturnSize][j] = 0;
                strcat(proRes[proResreturnSize], "()");
                strcat(proRes[proResreturnSize++], lastres[i]+j);
            }
            else if(lastres[i][j-1]==')' && lastres[i][j]=='(' && strncmp(lastres[i]+j-2, "()", 2)!=0) {
                strncpy(proRes[proResreturnSize], lastres[i], j);
                proRes[proResreturnSize][j] = 0;
                strcat(proRes[proResreturnSize], "()");
                strcat(proRes[proResreturnSize++], lastres[i]+j);
            }
            else if(lastres[i][j-1]=='(' && lastres[i][j]=='(') {
                {
                    int m=0,n=0;
                    strncpy(proRes[proResreturnSize], lastres[i], j);
                    proRes[proResreturnSize][j] = 0;
                    strcat(proRes[proResreturnSize], "(");
                    while (1) {
                        if(lastres[i][j+n]=='(') {
                            m++;
                            n++;
                            strcat(proRes[proResreturnSize], "(");
                        }
                        else if(lastres[i][j+n]==')') {
                            m--;
                            n++;
                            strcat(proRes[proResreturnSize], ")");
                        }
                        else
                            break;
                        if(m==0) 
                            break;
                    }
                    strcat(proRes[proResreturnSize], ")");
                    strcat(proRes[proResreturnSize++], lastres[i]+j+n);
                }

                if(strncmp(lastres[i]+j-2, "()", 2)!=0) {
                    strncpy(proRes[proResreturnSize], lastres[i], j);
                    proRes[proResreturnSize][j] = 0;
                    strcat(proRes[proResreturnSize], "()");
                    strcat(proRes[proResreturnSize++], lastres[i]+j);
                }
            }
        }
    }
    
    qsort(proRes, proResreturnSize, sizeof(char*), cmp);
    res = (char**)malloc(proResreturnSize*sizeof(char*));
    res[0] = (char*)malloc(n*2+1);
    strcpy(res[0], proRes[0]);
    *returnSize=1;
    for(i=1; i<proResreturnSize; i++) {
        if(strcmp(res[*returnSize-1], proRes[i])!=0) {
            res[*returnSize] = (char*)malloc((n*2+1));
            strcpy(res[*returnSize], proRes[i]);
            (*returnSize)++;
        }
    }
    return res;
}


发表于 2024-03-23 17:20:49 回复(0)
C
我是小安哥头像 我是小安哥

void DFS(int left,int right, char **ret, char *str, int n,int *returnSize)
{
    if(left == n && right == n)
    {//DFS终止条件，左括号和右括号都用了n个
        ret[(*returnSize)] = malloc(sizeof(char)*2*n);
        strncpy(ret[(*returnSize)], str,2*n);
        (*returnSize)++;
        return;
    }
    if(left <n)//左括号没用完
    {
        str[left+right] = '(';
        DFS(left+1,right,ret,str,n,returnSize);
    }
    if(right < n && right <left)//右括号没有用完，右面括号用的次数比左半边括号用的次数少，不能等于
    {
        str[left+right] = ')';
         DFS(left,right+1,ret,str,n,returnSize);
    }

}

char** generateParenthesis(int n, int* returnSize ) {
    //全排列想的是回溯算法
    char **ret =(char**)malloc(sizeof(char*)*2000);
    *returnSize = 0;
    char *str = (char*)malloc(sizeof(char) *2*n);

    DFS(0,0,ret,str,n,returnSize);//初始化left,right表示用了多少次
    return ret;
}
发表于 2023-06-04 09:58:01 回复(0)
C
笑个不停头像 笑个不停
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
 
void generate(int left,int right,int size,char* str,int n, int* returnSize,char** result)
//left代表左括号数量，right代表右括号数量，str代表储存几组有效组合，returnsize表示返回数量
{
    if (size == 2 * n) //n对括号
    { // 当前字符串的长度已达2n，将该字符串加入到结果中
        result[(*returnSize)] = (char*)calloc((2 * n + 1), sizeof(char));
        strcpy(result[(*returnSize)++], str);
        return;
    }
    // 如果左括号数量不大于 n，可以放一个左括号
    if (left < n)
    {
        str[size] = '(';
        generate(left + 1, right, size + 1, str, n,  returnSize, result);
    }
    // 如果右括号数量小于左括号的数量，可以放一个右括号
    if (right < left)
    {
        str[size] = ')';
        generate(left , right+1, size + 1, str, n, returnSize, result);
    }
}
 
 
char ** generateParenthesis(int n, int* returnSize)
{
    char *str = (char*)calloc((2 * n + 1), sizeof(char));//用于存放每一种括号组合
    char **result = (char**)malloc(sizeof(char*) * 1430); //结果数组
    // 卡特兰数: 1, 2, 5, 14, 42, 132, 429, 1430，题目中最多生成1430组
    *returnSize = 0;
    generate(0, 0, 0, str, n, returnSize, result);
    return result;
}
发表于 2023-03-25 22:54:20 回复(0)
提交观点

问题信息

递归
难度：
3条回答 21777浏览

热门推荐

通过挑战的用户

查看代码

相关试题

括号生成

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号