C# · 12月 20, 2021

LeetCode 22. 括号生成 Generate Parentheses(C语言)

题目描述:

给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。

例如,给出 n = 3,生成结果为:

[

“((()))”,

“(()())”,

“(())()”,

“()(())”,

“()()()”

]

题目解答:

方法1:回溯算法

for循环+递归。记录当前用的左括号数目bef及未成对的左括号数目single,根据这两个数字可以计算出当前用了多少个字符。另外如果当前没有未成对的左括号,则需要先放置左括号。有未成对的左括号时,这个位置可以放置左括号,也可以放置右括号,但需要更新记录的数目。

注意优先级问题,++的优先级高于*。运行时间0ms,代码如下。

/**

* Return an array of size *returnSize.

* Note: The returned array must be malloced,assume caller calls free().

*/

void backTrack(char*** result,int* size,char* before,int bef,int n,int single) {

int i = 0,j = 0;

j = (bef – single) * 2 + single;

if(bef == n) {

for(j; j < 2 * n; j++)

before[j] = ‘)’;

(*size)++;

*result = (char**)realloc(*result,*size * sizeof(char*));

result[0][*size – 1] = (char*)malloc((n * 2 + 1) * sizeof(char));

memcpy(result[0][*size – 1],before,(n * 2 + 1) * sizeof(char));

return;

}

if(single == 0) {

before[j] = ‘(‘;

backTrack(result,size,1 + bef,n,1);

}

else {

before[j] = ‘(‘;

backTrack(result,1 + single);

before[j] = ‘)’;

backTrack(result,bef,single – 1);

}

}

char** generateParenthesis(int n,int* returnSize) {

char** result = NULL;

char* before = (char*)malloc((n * 2 + 1) * sizeof(char));

before[2 * n] = ”;

backTrack(&result,returnSize,0);

return result;

}

方法2:迭代法

参考最快的,需要理解下。

/**

* 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 = NULL;

char* temp = (char*)malloc((n * 2 + 1) * sizeof(char));

temp[2 * n] = ”;

int index = 0;

int remain1 = n,remain2 = n;

while(true) {

while(remain1 > 0) {

temp[index++] = ‘(‘;

remain1–;

}

while(remain2 > 0) {

temp[index++] = ‘)’;

remain2–;

}

(*returnSize)++;

result = (char**)realloc(result,*returnSize * sizeof(char*));

result[*returnSize – 1] = (char*)malloc((n * 2 + 1) * sizeof(char));

memcpy(result[*returnSize – 1],temp,(n * 2 + 1) * sizeof(char));

while(temp[index – 1] == ‘)’ || remain1 > remain2 – 2) {

if(temp[index – 1] == ‘)’)

remain2++;

else

remain1++;

index–;

if(index < 0)

return result;

}

temp[index – 1] = ‘)’;

remain1++;

remain2–;

}

return result;

}

或者自顶向下:

f(0): “”

f(1): “(“f(0)”)”

f(2): “(“f(0)”)”f(1),“(“f(1)”)”

f(3): “(“f(0)”)”f(2),”(“f(1)”)”f(1),“(“f(2)”)”

So f(n) = “(“f(0)”)”f(n-1),”(“f(1)”)”f(n-2) “(“f(2)”)”f(n-3) … “(“f(i)”)“f(n-1-i) … “(f(n-1)”)”

发现不能是这样组合:

f(n) = f(1)f(n-1),f(2)f(n-2) f(3)f(n-3) … f(1+i)f(n-1-i) … “(f(n-1)”)”

这样有重复的结果

该方法参考:

https://leetcode.com/problems/generate-parentheses/discuss/10127/An-iterative-method