Google Codejam APAC测试练习轮：括号顺序 [英] Google codejam APAC Test practice round: Parentheses Order

问题描述

我花了一天的时间解决这个问题，并且不能

I spent one day solving this problem and couldn't find a solution to pass the large dataset.

问题

n个括号序列由n（

An n parentheses sequence consists of n "("s and n ")"s.

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

Now, we have all valid n parentheses sequences. Find the k-th smallest sequence in lexicographical order.

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

For example, here are all valid 3 parentheses sequences in lexicographical order:

((()))

(()())

(())()

()(())

()()()

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

Given n and k, write an algorithm to give the k-th smallest sequence in lexicographical order.

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

推荐答案

可以通过使用动态编程

• 让 dp [n] [m] =如果我们有可以创建的有效括号数n 中括号， m 中括号。


• 基本情况：
  
  dp [0] [a] = 1（a> = 0）


• 使用基本情况填充矩阵：
  
  dp [n] [m] = dp [n-1] [m] +（n



• Let dp[n][m] = number of valid parentheses that can be created if we have n open brackets and m close brackets.
• Base case:
  dp[0][a] = 1 (a >=0)
• Fill in the matrix using the base case:
  dp[n][m] = dp[n - 1][m] + (n < m ? dp[n][m - 1]:0 );

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

Then, we can slowly build the kth parentheses.

• 以 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

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

Notice that open bracket is less than close bracket in lexicographical order, so we always try to add open bracket first.

这篇关于Google Codejam APAC测试练习轮：括号顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！