Google Codejam APAC测试练习轮：括号顺序

小编典典

Google Codejam APAC测试练习轮：括号顺序

algorithm

我花了一天的时间解决这个问题，却找不到通过大型数据集的解决方案。

问题

n个括号序列由n个“（” s和n“）”组成。

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

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

((()))

(()())

(())()

()(())

()()()

给定n和k，编写一种算法，以字典顺序给出第k个最小序列。

对于大数据集：1 ≤ n ≤ 100和1 ≤ k ≤ 10^18

阅读 265

2020-07-28

共1个答案

小编典典

通过使用动态编程* 可以解决此问题 *

令dp[n][m]=如果我们n有方括号和m方括号，则可以创建的有效括号数。
基本情况：
dp[0][a] = 1 (a >=0)
使用基本情况填写矩阵：
dp[n][m] = dp[n - 1][m] + (n < m ? dp[n][m - 1]:0 );

然后，我们可以慢慢建立第k个括号。

以 a = n右方括号 和 b = n右方括号 开头，当前结果为空

while(k is not 0):
 If number dp[a][b] >= k: 
        If (dp[a - 1][b] >= k) is true:
           * Append an open bracket '(' to the current result
           * Decrease a 
        Else:
           //k is the number of previous smaller lexicographical parentheses
           * Adjust value of k: `k -= dp[a -1][b]`,
           * Append a close bracket ')' 
           * Decrease b
 Else k is invalid

请注意，按字典顺序，左括号小于右括号，因此我们总是尝试首先添加左括号。

2020-07-28