java - 关于字符串中的括号

Question

在一次采访中，我被要求解决以下问题。

给定一个字符串，计算其中括号对的数量。例如字符串为s = "()()"，则有3对:

s[0], s[1]
s[0], s[3]
s[2], s[3]

我写了下面的代码:

int count(char* s) {
  int left = 0;
  int pair = 0;
  for (int i = 0; i < strlen(s); i++) {
    char c = s[i];
    if (c == '(') {
      left++;
    } else if (c == ')') {
      pair += left;
    }
  }
  return pair;
}

接着又出现了一个问题:

给定长度 L 和计数 N，用 strlen(s) == L 和 count(s) == N 确定字符串 s (count 是我上面写的函数；s 应该只包含括号)。例如L为4，N为3，则字符串为“()()”。

我发现，在例子中，s也可以是“((()”或“()))”。最好打印所有符合要求的字符串。

谁能解决第二个问题？谢谢。如果您编写java或c/c++代码来解决问题，那就太好了。

Answer 1

生成具有正确计数的正确长度的字符串是一项数学练习。

先让k是 N 的平方根的底部.将生成 k<sup>2</sup> 的最短字符串字符串的长度为 2k .看起来像 (...()...) .

将生成 k<sup>2</sup>+k 的最短字符串字符串的长度为 2k+1 .您只需附加一个 )到前一个字符串。对于 N在 k<sup>2</sup> 之间和 k<sup>2</sup>+k你只需滑动最左边的)超过(的正确数量括号。

将生成 k<sup>2</sup>+2k 的最短字符串字符串的长度为 2k+2 .您只需附加另一个 )到前一个字符串。对于 N在 k<sup>2</sup>+k 之间和 k<sup>2</sup>+2k你只需滑动最左边的)超过(的正确数量括号。

如果N大于 k<sup>2</sup>+2k那你就没有计算平方根的下限。 :-)

如果L比这个长度短，则无解。如果L大于此长度，那么您只需编写此解决方案并附加正确的 ( 编号即可到最后。

---

找到解决方案数量的正确方法是使用动态规划。你为所有长度的东西建立了一个表i ，有多少解j用 m 打开括号总对。 (如果需要，有标准方法可以将此动态规划解决方案转换为列出解决方案的方式。但列表通常会很长。)