小编dav*_*ave的帖子

任何人都可以帮我解决这个问题吗？我会输入问题,然后给出一些我的想法/替代解决方案.

所以问题就在于,给出一个这样的括号:

[[]]

我们希望为每个括号分配一个组号(组1或组2).一个有效的赋值意味着,如果你只看第一组中的括号,它会形成一个有效的,平衡的括号字符串(这就像[] [[]]之类的东西,而不是像[] [] []那样的东西.同样的对于第二组是正确的.组不必是连续的.我们想要计算将这些括号分成两组的方法.

在[[]]上面的示例字符串上,答案是6,这里是枚举:(1 =组1,2 =组2)

  [[]]
1.1111
2.2222
3.1221
4.2112
5.1212
6.2121

该安排不必包括所有组(如安排1.和2.)

思考

一个明显的暴力解决方案,最多可以使用32个括号,相当快速,是一个32位整数,表示哪个括号是单个组的一部分.或者我们可以使用数组.运行时间是O(2 ^ N)(我想),这太慢了？

通过查看问题,我认为您给出的原始括号字符串必须预先平衡,否则无法选择一个子集,使第1组和第2组平衡.

我还注意到你可以分开组件 - 字符串"[]"有2个排列,所以字符串"[] []"有4个排列.(您可以在每个组件中找到方法的数量并将它们相乘).

我对如何将这些想法纳入算法感到困惑.我写了蛮力程序,我检查了字符串"[]","[[]]","[[[]]]"和"[[[[]]]]",我不是真的看一个模式.

从将这些字符串插入我的暴力程序,我得到:

"[]" = 2
"[[]]" = 6
"[[]]" = 20
"[[[[]]]]" = 70

码:

char buf[1000];
int N;
bool isValid(int mask)
{
    int lv = 0;
    for (int i = 0; i < N; i++)
    {
        if (mask & (1 << i))
        {
            if (buf[i] == '(')
            {
                lv++;
            }
            else
            { …