一个n个括号的序列由n个“(”和n个“)”组成。
一个有效的括号序列定义如下:
你可以找到一种重复擦除相邻的括号“()”,直到变成空的方法。
例如,“(())”是一个有效的括号,你可以擦除第2和第3个位置上的括号对“()”,然后它变成“()”,最终变为空。 “)(”不是有效的括号,当你擦除第2和第3个位置上的括号对后,它变成“)(”,你不能再擦除任何括号。
现在,我们有所有有效的n个括号序列。在字典序中查找第k个最小序列。
例如,这里是所有有效的3个括号序列按字典顺序排序:
((()))
(()())
(())()
()(())
()()()
来源:https://code.google.com/codejam/contest/4214486/dashboard#s=p3
注意:比赛已结束,解决方案可供下载。
我已经使用C ++ STL中提供的next_permutation()函数解决了小输入(k<10^6)的问题。但我无法为此构思子问题。我尝试使用卡特兰数解决此问题,但似乎没有成功。我不想参考解决方案,因为那对学习没有帮助。请帮助我确定一个子问题。
n/2
个位置可以放置它。因此,你有u(n) = n/2 * u(n-2)
。然后,你删除第一个“()”子字符串并得到一个n-2
有效序列。在这个子字符串中,第一个闭括号在哪里,你仍然有(n-2)/2
个选择!依此类推。 - Rerito