Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
Ссылка на сайт
трудность
Medium
описывать
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Учитывая n пар круглых скобок, вернуть все различные допустимые строки этих круглых скобок.
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
отвечать
Эта задача очень интересная, и решений много.Это все еще старое правило.Начнем с самого простого способа.
Давайте кратко проанализируем проблему. Пара скобок n означает, что длина строки равна 2n. Мы можем использовать перестановку и комбинацию, чтобы вычислить, что количество всех комбинаций имеет в общей сложности
своего рода. Если вы сделаете математику, вы узнаете, что это число очень велико, а это означает, что даже если мы знаем ответ с самого начала, для прохождения ответа потребуется много времени, поэтому временная сложность этого вопроса не должна быть очень высоким.
Насилие
Самый простой способ, который я могу придумать, это, конечно, насилие. Не смотрите свысока на этот простой алгоритм. Часто вдохновение черпается из насилия. Однако эту тему о насилии написать непросто, потому что будет ощущение, что нет возможности начать.Мы знаем, что требуется насилие, но не умеем быть жестоким. Нет простых элементов, которые можно прямо перечислить в этом вопросе, надо свернуть за угол.
Как его повернуть, собственно, ответ я только что сказал. Имеется n пар скобок, что означает, что всего символов 2n. Мы можем перечислить, где размещаются n '(', а остальное, естественно, ')'. Вроде разумно, но есть проблема, то есть нет возможности напрямую реализовать эту идею через цикл. На самом деле это превратилось в проблему поиска, мы хотим искать все возможности, которые можно поместить в скобки.
Если вы можете перейти от метода грубой силы к проблеме поиска, то вы очень близки к написанию кода. Если нет, то предлагаю вам уделить время изучению темы поисковых алгоритмов.
Для задачи поиска это уже очень просто, пространство, которое мы ищем, понятно, 2n позиций, содержание поиска, для каждой позиции мы можем поставить '(' или ')'. Тогда код выходит естественным образом:
def dfs(pos, left, right, n, ret, cur_str):
"""
pos: 当前枚举的位置
left: 已经放置的左括号的数量
right: 已经放置的右括号的数量
n: 括号的数量
ret: 放置答案的数组
cur_str: 当前的字符串
"""
if pos == 2*n:
ret.append(cur_str)
return
if left < n:
dfs(pos+1, left+1, right, n, ret, cur_str+'(')
if right < n:
dfs(pos+1, left, right+1, n, ret, cur_str+')')
Эта программа не закончилась после обхода и выполнения.Нам также нужно судить, являются ли сгенерированные скобки допустимыми, то есть скобки должны совпадать. Мы можем использовать стек, чтобы определить, могут ли скобки совпадать. Например, когда мы встречаем левую скобку, мы помещаем ее в стек, а когда мы встречаем правую скобку, мы оцениваем вершину стека. стек является левой скобкой, затем левая скобка наверху стека извлекается из стека, в противном случае она помещается в стек Наконец, проверьте, пуст ли стек. Этот алгоритм, конечно, не сложен в реализации, но если хорошенько подумать, то обнаружится, что нет необходимости использовать стек, потому что если мы встречаем закрывающую скобку, то вершина стека не является левой скобкой, тогда он должен быть непревзойденным в конце. Поскольку открывающая скобка, которая появляется позже, не может соответствовать закрывающей скобке, которая стоит перед ней, это так называемаянеотслеживаемыйВот и все. 【Собачья голова】
оптимизация
Давайте подумаем над вопросом: что происходит, когда закрывающая скобка не встречается с открывающей скобкой? Есть только один случай, то есть количество закрывающих скобок в данный момент превышает количество открывающих скобок, то есть мы обходим строку Если количество закрывающих скобок превышает количество открывающих скобок в середине, это означает, что строка незаконно. Вроде бы и не проблема, да, но есть проблема, почему бы нам не судить при перечислении, если количество левых скобок равно закрывающей скобке, то закрывающие скобки нам не помешают, так мы можем гарантировать поиск Должна ли это быть корректная строка?
Если вы можете представить себе этот слой, ваше понимание поиска довольно хорошее. Давайте посмотрим на измененный код:
def dfs(pos, left, right, n, ret, cur_str):
"""
pos: 当前枚举的位置
left: 已经放置的左括号的数量
right: 已经放置的右括号的数量
n: 括号的数量
ret: 放置答案的数组
cur_str: 当前的字符串
"""
if pos == 2*n:
ret.append(cur_str)
return
if left < n:
dfs(pos+1, left+1, right, n, ret, cur_str+'(')
if right < n and right < left:
dfs(pos+1, left, right+1, n, ret, cur_str+')')
Большая часть кода остается прежней, просто добавляется условие право
структура
Вышеупомянутая схема имеет доход в официальном LeetCode, а также является относительно традиционным решением.Способ, который будет представлен ниже, является моим оригинальным, и лично мне он кажется более интересным, поэтому я поделюсь им с вами.
В предыдущей статье мы представили метод «разделяй и властвуй», Суть метода «разделяй и властвуй» состоит в том, чтобы разложить, казалось бы, неразрешимую большую проблему на более мелкие проблемы, которые легче решить, и, наконец, решить ее. В этой задаче решение, когда мы напрямую находим n, сложнее, и нет возможности получить его напрямую.Можем ли мы также попытаться использовать метод «разделяй и властвуй» для ее решения?
Посмотрим на данные, когда n=1, это очень просто, результат (), есть только этот. А когда n=2? Существует два вида, а именно (()) и ()(), когда n=3? Существует 5 типов: ((())), ()(()), ()()(), (()()), (())(). Есть ли в этом какие-то правила?
Мы используем решение (n) для представления решения, соответствующего n, тогда мы можем написать формулу, соответствующую решению (n):
Приведенная выше формула немного похожа на уравнение перехода состояния динамического программирования, хотя это не совсем то же самое, но, вероятно, то же самое. То есть мы можем собрать текущий ответ с ответами меньше размера ответа. Например, ответ при n=3 равен конкатенации ответа при n=2 и ответа при n=1.
Например: решение(1) + решение(2) может получить: ()()() и ()(()), решение(2) + решение(1) может получить ()()() и (() ) ( ). Но есть еще один ответ, который нельзя получить конкатенацией (solution(2)). То есть, оберните слой скобок вокруг ответа решения (2). Тогда почему бы не рассмотреть ответ решения (1), заключенный в два слоя круглых скобок? Ответ прост, потому что решение (2) уже включает такой случай, поэтому нам нужно рассмотреть только один уровень вниз.
Но это еще не все, еще есть небольшая проблема, полученный таким образом ответ может быть дублирован, поэтому нам нужно провести дедупликацию, мы можем сделать это очень легко с помощью set, давайте посмотрим код вместе:
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
solutionMap = {}
# 记录下n=0和1时的答案
solutionMap[0] = set([""])
solutionMap[1] = set(["()"])
# 遍历小于n的所有长度
for i in range(2, n+1):
cur = set()
# 遍历小于n的所有长度
for j in range(1, i):
# 构造答案
ans1 = solutionMap[j]
ans2 = solutionMap[i-j]
for s in ans1:
for t in ans2:
cur.add(s + t)
# 构造 ( solution(n-1) )这种答案
for s in solutionMap[i-1]:
cur.add("(" + s + ")")
solutionMap[i] = cur
return list(solutionMap[n])
В C++ эти два метода примерно одинаково эффективны, но в Python сконструированный метод работает быстрее. По сравнению с методом поиска, метод поиска заключается в поиске ответа, не зная ответа, а метод построения заключается в том, чтобы знать, как выглядит ответ, и производить ответ в соответствии с определенными правилами. Можно сказать, что есть два разных способа мышления, поэтому мне очень нравится этот вопрос.
Код этого вопроса не длинный, но идея очень интересная, надеюсь вам понравится.
На сегодняшней статье все.Если вы чувствуете, что что-то приобрели, пожалуйста, отсканируйте код и обратите внимание.Ваши усилия очень важны для меня.