4

一个 n 括号序列由 n 个“(”s 和 n 个“)”s 组成。

一个有效的括号序列定义如下：

您可以找到一种方法来重复擦除相邻的一对括号“（）”，直到它变空。

例如，"(())" 是一个有效的括号，你可以删除第 2 和第 3 个位置的对，它变成 "()"，然后你可以把它留空。")()(" 不是一个有效的括号，在你擦除第 2 和第 3 位置的对后，它变成了 ")(" 并且你不能再擦除了。

现在，我们有了所有有效的 n 个括号序列。按字典顺序查找第 k 个最小的序列。

例如，以下是按字典顺序排列的所有有效的 3 个括号序列：

((()))
(()())
(())()
()(())
()()()

来源：https ://code.google.com/codejam/contest/4214486/dashboard#s=p3

注意：比赛现已结束，解决方案可供下载。

我已经通过使用 C++ STL 中可用的 next_permutation()解决了小输入（ k < 10 6 ）的问题。我无法为此制定一个子问题。我试图通过使用加泰罗尼亚语的号码来解决这个问题，但似乎没有取得任何成功。我不想看到解决方案，因为它对学习没有帮助。请帮助我确定一个子问题。

4

2 回答 2

2

让N表示序列的长度（即 2 n）。

关键是能够计算长度为N的有效序列的数量。

如果你有一个函数countValid ( N , depth ) 你可以解决原来的问题如下：

  1. 如果depth < 0 这是不可能的（负深度意味着无效序列）

  2. 如果k < countValid ( N -1, depth +1) append (（因为寻找的序列位于剩余搜索空间的前半部分）

  3. 否则追加)（因为寻找的序列位于总搜索空间的后半部分）

  4. 如果您在上面选择，则从 1 继续更新N -1 和深度+1 (，或者如果您在上面选择深度-1 )。

countValid ( N , depth ) 可以通过使用标准 DP 矩阵M的动态规划来实现，其中两个参数作为索引：

  • 基本情况，M [0,0] = 1，因为存在一个有效的 0 长度序列（空序列）

  • 对于第一列中的所有其他值M [0, 1... N ] 为 0。

  • 对于M [ N , depth ] 你只需加起来

    • 打开后的有效序列数：M [ N -1, depth -1]，和
    • 关闭后的有效序列数：M [ N -1, depth +1]

    即：M [ N , depth ] = M [ N -1, depth -1] + M [ N -1, depth +1]

于 2014-10-18T07:18:55.760 回答
0

我知道这是一个老话题，但有些人可能会回到这个话题。我很难实施 aioobe 的解决方案，因为我认为它错过了一步：

3.1) 如果选择“)”，则 k = k - countValid(N-1, depth+1)

直觉上推理是这样的。如果您选择减小深度，则您要查找的序列位于搜索空间的第二部分，该部分在 (N, depth) 处划分。如果我们保持 k 相同，它会在路径上的某个点大于所有剩余的解决方案数量，并且我们的遍历不再起作用。我们需要减去我们排除的解决方案的数量，以便遍历矩阵以产生所需的结果。

如果您的矩阵 D 包含每个 (N,depth) 的有效序列数，则这是一些用于查找第 k 个元素的 java 代码：

// get k-th element
int N = 2*n;
int d = 0;
String str = new String("");
while (N>0 && d >= 0) {
  // invalid elements (out of bounds or 0)
  if (d+1 > n || D[N-1][d+1] == 0) {
    str += ")"; d--;
  } else if (d-1 < 0 || D[N-1][d-1] == 0) {
    str += "("; d++;
  } else {
    if (k <= D[N-1][d+1]) {
      // first part of search-space
      str += "("; d++;
    } else {
      // second part of search-space
      str += ")";
      k -= D[N-1][d+1]; // substract number of excluded solutions
      d--;
    }
  }
  N--;
}

// For valid strings k should be 1
if (k != 1) str = "Doesn't Exist!";
于 2015-10-06T08:54:44.687 回答