Как определить максимальную глубину вложенности скобок

Русские Блоги

【LeetCode】 1111. Максимальная глубина вложения двух допустимых строк в круглых скобках

• Автор: Сюэ Мин Чжу отрицательный
• id： fuxuemingzhu
• личный блог:http://fuxuemingzhu.cn/

оглавление

Титульный адрес: https://leetcode-cn.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/

Название Описание

Допустимые символы скобокСтроковое определение: для каждой левой круглой скобки можно найти соответствующую правую скобку, и наоборот. Подробности см. В разделе «Допустимые строки в скобках» в конце заголовка.

Глубина вложенности Определение: количество уровней вложенности допустимых строк в скобках, глубина (A) представляет собой глубину вложения допустимой строки в скобках A. Подробнее см. В разделе «Глубина вложения» в конце заголовка.

Дайте вам последовательность «допустимой строки в квадратных скобках», разделите ее на две непересекающиеся допустимые строки в квадратных скобках, A и B, и минимизируйте глубину этих двух строк.

• Непересекающиеся: каждый seq[i] Он может быть назначен только одному из A и B и не может принадлежать одновременно A и B.
• Элементы в A или B могут быть прерывистыми в исходной строке.
• A.length + B.length = seq.length
• max(depth(A), depth(B)) Наименьшее возможное значение.

В схеме разбиения используется длина seq.length Массив ответов answer Указывает, что правила кодирования следующие:

• answer[i] = 0 ， seq[i] Отдай А.
• answer[i] = 1 ， seq[i] Отдай Б.
  Если существует несколько ответов, соответствующих требованиям, просто верните любой из них.

1. 1 <= text.size <= 10000

Допустимая строка в скобках:

Точно так же мы можем определить глубину вложенности (S) любой допустимой скобочной строки s:

Все сообщили, что не могут понять тему, поэтому сегодня тема была пересмотрена, и последняя тема будет объяснена ниже.

Объяснение темы

В названии объясняются «допустимая строка скобок» и «глубина вложенности», я думаю, все могут понять. Главное, что не понятны «правила разделения» и «возврат результатов».

Разъяснение правил разделения

Зная, что ввод является «допустимой строкой в ​​скобках», теперь ввод «разделен на две непересекающиеся допустимые строки в скобках». Фактически, входная строка делится на две допустимые скобки A и B.

«Непересекающийся» в названии немного излишне, например, давать двум детям конфеты ��, но уж точно не конфеты �� двум детям одновременно. Заголовок называет этот метод распределения «непересекающимся».

Объяснение результата возврата

Возвращаемый результат — это массив, который требует только 0 или 1, и каждый из них отмечен ( Или ) Должен быть отнесен к A или B.

Если символ разделен на A, вывод, соответствующий символу, равен 0; если он разделен на B, вывод, соответствующий символу, равен 1.

Метод решения проблемы

Заголовок требует, чтобы минимальная глубина была разделена на две допустимые строки скобок, поэтому необходимо только сделать глубину каждой допустимой строки скобок как можно меньшей, то есть глубина самой большой вложенности скобок A и B должна быть самой низкой. Поэтому мы хотим, чтобы глубина скобок этих двух строк была как можно более равномерной.

Перемещайте строку слева направо, вам нужно знать сумму A и B, сложенных вместеНезавершенная левая скобкаЧисло, пусть этиНезавершенная левая скобкаПопытайтесь разделить между A и B поровну.

Итак, дело в том, что A и B основаны на общемНезавершенная левая скобкаПросто по очереди требуйте новую открывающую скобку.

1. Обнаружена открывающая скобка, еслиНезавершенная левая скобкаЕсли число нечетное, поставьте новую левую скобку на A, еслиНезавершенная левая скобкаЕсли число четное, дайте B новую открывающую скобку. И увеличит количество незавершенных левых скобок на одну;
2. Когда вы встречаетесь с правой круглой скобкой, какая правая скобка принадлежит A или B? Это согласуется с присвоением последней левой круглой скобки A или B. И это уменьшит количество незавершенных левых круглых скобок на одну;

Взгляните на пример темы:

Вход разделен на две строки, красную A и синюю B. После этого деления глубина красного равна 1, а глубина синего также равна 1. Как показано на рисунке ниже.

Вход разделен на две строки, красную A и синюю B. После этого деления глубина красного цвета равна 1, а глубина синего также равна 1. Результатом вопроса является только один из результатов, и следующие два подразделения могут пройти тест вопроса. Как показано ниже.

Согласно приведенному выше анализу, нам не нужно использовать структуру стека, просто запишитеТекущее количество незавершенных левых скобокВы знаете, кому следует назначить A и B.

Комментарии к коду очень подробны, я думаю, вы это понимаете.

Код C ++ выглядит следующим образом.

Добро пожаловать, чтобы следоватьБлог Нин Сюэминчжу, Leetcode выдает более 800 вопросов, и каждый из них подробно объясняет написание!

Найдите максимальную глубину вложенных скобок в строке R-кода

У меня проблема с завершением этого кода R. Нам дается строка со скобками, как показано ниже «(((X)) (((Y))))» Нам нужно найти максимальную глубину сбалансированной скобки, например 4 в примере выше. Так как «Y» заключено в 4 сбалансированные круглые скобки.

Если круглые скобки не сбалансированы, верните -1 Мой код выглядит так:

Но когда я вызываю функцию def («(A ((B)))»), ответ должен быть 2. Но каждый раз он показывает 0, даже когда круглые скобки неуравновешены. Я не уверен, правильный ли код или где ошибка. Я пытаюсь выучить R, так что будьте терпеливы. Спасибо

2 ответа

Если x <- «( ((X)) (((Y))) )» , удалить все скобки и разделить на символы .

А затем максимальная вложенность — это наибольшая совокупная сумма +1 (для ( ) и -1 (для ) ) .

Если круглые скобки неуравновешены, то sum(ifelse(y==»(«, 1, -1))) не будет равно нулю.

Вот три решения. Все они векторизованы, т.е. вход x может быть вектором символов, и все они правильно обрабатывают случай отсутствия скобок.

1) strapply / proto strapply в пакетах gsubfn соответствует регулярному выражению, заданному в качестве второго аргумента, запускающего функцию fun в прото-объекте p , который также должен передается в strapply . Функция pre в p инициализирует вычисление для каждого компонента ввода x . Прото-объект можно использовать для сохранения памяти о прошлых совпадениях (здесь lev — уровень вложенности), позволяя производить подсчет. Мы добавляем произвольный символ здесь «X» к каждой строке, чтобы всегда было хотя бы одно совпадение. Если бы мы знали, что вводимых строк символов нулевой длины нет, это можно было бы опустить. sapply использует Max , который берет максимум из возвращенных глубин или возвращает -1, если баланс отсутствует.

2) Уменьшить . Это базовое решение. Он использует Max из (1).

3) strapply / list . Другой возможностью является извлечение скобок и возврат с +1 или -1 для ( и ) , используя strapply со списком замены. Затем запустите cumsum и Max (сверху) над этим.

Нахождение глубины вложенности массивов Python

Нужно найти глубину вложенности массива. Моя реализация:

На одном из тестов ошибка:

Но запятые стоят не там, чтобы получить вложенность 3.

По скобкам ориентируйтесь. Так должно быть понятнее

Сколько видите отступов для тройки?

Ну, и решение может быть проще:

Гораздо легче как мне кажется просто посчитать максимальное количество скобочек подряд.

Можно заменить ( и ) на [ и ] если требуется искать массив, но на сайте работает именно вариант с ( и )

Дизайн сайта / логотип © 2023 Stack Exchange Inc; пользовательские материалы лицензированы в соответствии с CC BY-SA . rev 2023.3.11.43304

Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.

Как определить максимальную глубину вложенности скобок

Вход разделен на две строки, красную A и синюю B. После этого деления глубина красного равна 1, а глубина синего также равна 1. Как показано на рисунке ниже.

Вход разделен на две строки, красную A и синюю B. После этого деления глубина красного цвета равна 1, а глубина синего также равна 1. Результатом вопроса является только один из результатов, и следующие два подразделения могут пройти тест вопроса. Как показано ниже.