LeetCode-中等-22-括号生成(C)

图床换了个新的,以前的虽然不错,但是上传后会模糊。

这道题还是很费脑子的,我得去加点水。

使用realloc在LeetCode上会增大内存消耗,就很气。

题目

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

示例:

输入:n = 3
输出:[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

已知需要生成出包含n组括号的二维数组,获得所有可能结果后,使用returnSize返回大小,下面简写rSize。

这n组括号中,我们研究左括号的排放位置。

在获得左括号位置时,引入一个存放括号的,大小为n的数组,称为parenthesisPosition,下面简写pPos,

在第i个数组位置,存放第i个左括号的位置,例如下面这个n=4的括号组合中:
((()))(),pPos的内容为0,1,2,6,为了方便研究,我们不以0开头,而以1开头,即nPos的内容为1,2,3,7,
表示这组括号中的第1/2/3/7个位置是左括号。

那么,对于n=2的所有括号组合,可以列出:

1 2
1 3 |

而对于n=3的所有括号组合,有:

1 2 3
1 2 4
1 2 5 |
1 3 4
1 3 5 |

n=4:

1 2 3 4
1 2 3 5
1 2 3 6
1 2 3 7 |
1 2 4 5
1 2 4 6
1 2 4 7 |
1 2 5 6
1 2 5 7 |

1 3 4 5
1 3 4 6
1 3 4 7 |
1 3 5 6
1 3 5 7 |

将所有末尾增长到最大值的情况用 | 标出,
可以看出,第i个左括号的位置不能超过 2 * i -1。

还可以看出,当n=2时,rSize=2,
n=3时,rSize=3+2,
n=4时,rSize=4+3+2+3+2,
那么这有什么用呢?
n=5时,rSize=5+4+3+2+4+3+2+3+2吗?
不,不会,这只会误导我,他唯一的作用就是让我误以为我解出来了。
我没有找到除遍历外更方便的计算方式,因为把第n=5列出来太麻烦了,不好找规律,而如果我解出来了,我除了优化外没有需要新的计算方式的理由了。

上段略过,如果我们将括号的位置当作进制数,第i个括号一旦到 2*i-1,就将第i-1位置进位,
但同时,还需要注意,在十进制中,12579的进位是12580,
而在这里,12579的进位是13456。

看起来不好处理,但实际上,只需要两个循环即可,
但在此之前,我们需要每次循环前,都将第n位的值加1,这样表示下一个括号组合,例如:
上一轮循环后,组合为1 2 4,那么这一次为1 2 5,
如果上一轮为1 2 5,那么这一轮为 1 2 6(此时组合错误,在后面的循环中处理)

在开始下面两个循环前,此时的组合为1 2 5,
末尾自增,变为1 2 6。

第一个循环,从第n位向第2位(因为第1位最大值为1),
比较当前值是否等于 2*i,即 pPos[i-1] = 2*i;(这里的i从1开始,而数组下标从0开始)
如果相等,则将第i-1的值加1,例如:
本次循环是1 2 6,此时循环在第3位,6=2*3,那么第2位值加1,变为1 3 6,之后循环在第2位,3 != 2*2,不处理。

在上一个循环中,我们已将1 2 6改为了1 3 6,在本轮循环中,只需要将错误的值修正即可,
第二轮循环,由第2位向第n位,
一个方便的修正方式,也是方便遍历方式,是:
若第 i 位的位置: pPos[i-1] == 2*i,则将其改为第i-1位+1后的值,那么上次循环产生的1 3 6,就会变成1 3 4。

经过一次末尾自增以及一组翻转的遍历循环后,1 2 5 变成了 1 3 4,符合条件。
试试更复杂的值:1 2 5 7 9,
末尾自增后:1 2 5 7 10
第一轮循环:
1 2 5 8 10
1 2 6 8 10
1 3 6 8 10
第二轮循环
1 3 4 8 10
1 3 4 5 10
1 3 4 5 6
此时,1 2 5 7 9变为了1 3 4 5 6。

这种进位可以正常使用,那么他能正常自增吗?
1 3 4 5 6:
经过末尾自增:1 3 4 5 7
一组翻转的循环条件均不满足,无需修改。
再次末尾自增:1 3 4 5 8
再次末尾自增:1 3 4 5 9
再次末尾自增:1 3 4 5 10
此时第一轮循环中:
1 3 4 6 10
第一轮循环结束,第二轮循环:
1 3 4 6 7
则,1 3 4 5 9转为了1 3 4 6 7,正常增长。

这样,在值增长为1 3 5 7 9时终止循环即可。

适合搭配realloc函数使用,根据增长大小,按需分配空间。

代码

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

char ** generateParenthesis(int n, int* returnSize){
    int i, i2;
    char **parenthesisReturnArray = NULL;
    *returnSize = 0;
    int *parenthesisPosition = (int*)malloc(sizeof(int) * (n+1));   // 括号位置存放数组
    for(i=0;    i<n;    i++){   // 将初始位置数组置为12345...表示左括号存放位置
        parenthesisPosition[i] = i+1;
    }
    parenthesisPosition[n-1] = n-1; // 数组第n位置为n-1,因为后面每次循环都会把它加1,第一次的时候回多出一次。
    

    for(i=1;    ;  i++){
        for(i2=0;   parenthesisPosition[i2]==(i2+1)*2-1 && i2<n;   i2++);
        if(i2==n) break;    // 如果发现上一组括号存在的位置为13579...则表明已经遍历完全。
        
        parenthesisPosition[n-1] += 1;
        *returnSize += 1;
        parenthesisReturnArray = (char**)realloc(parenthesisReturnArray, sizeof(char*)*(*returnSize));
        *(parenthesisReturnArray + i-1) = (char*)malloc(sizeof(char) * (2*n+1));

        for(i2=n;   i2>1;   i2--){  
            if(parenthesisPosition[i2-1] == 2*i2){
                parenthesisPosition[i2-2]++;
            }
        }
        for(i2=2;   i2<=n;  i2++){
            if(parenthesisPosition[i2-1] == 2*i2){
                parenthesisPosition[i2-1] = parenthesisPosition[i2-2] + 1;
            }
        }

		int i3; // 根据前两个循环设置各位置括号
        for(i2=1, i3=0;   i2<=2*n;    i2++){
            if(i2 == parenthesisPosition[i3])   {
                parenthesisReturnArray[i-1][i2-1] = '(';
                i3++;
            }
            else parenthesisReturnArray[i-1][i2-1] = ')';
        }
        parenthesisReturnArray[i-1][2*n] = '\0';
    }

    return parenthesisReturnArray;
}

You may also like...

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注