Эта статья была включена в мою серию Github «Algorithm Illustrated»:GitHub.com/VIP камень/Али…
Вопрос, о котором я хочу поговорить сегодня, является реальным вопросом письменного теста bilibili в этом году, а также классическим вопросом интервью о стеке.
После изучения предыдущей статьи, я думаю, многие друзья ее видели,Далее я напишу серию статей на тему "Алгоритмические диаграммы"., в середине может быть разбросано небольшое количество статей других типов, но «алгоритмы и структуры данных» будут в центре внимания моей статьи в этом году.
Когда я буду писать эту серию алгоритмов, я обращу внимание на две проблемы:
- Алгоритмы идей решения проблем гарантируют, что все смогут понять, поэтому я подумаю объяснить форму изображений, которая более интуитивно понятна и понятна.;
- После введения точки знаний будет много упражнений для закрепления изученного, Например, когда я закончу говорить о структуре «стека», я задам серию классических вопросов для интервью о «стеке».
Ключом к обучению алгоритмов является овладение идеей решения проблем.Пока идея верна, написание кода является лишь вопросом времени.
Давайте сначала рассмотрим предыдущий контент о «стеке»:
- «Анимационная демонстрация: два метода реализации стекирования рук! 》
- «JDK на самом деле реализует стек именно так? 》
- "Две реализации реверсирования связанных списков, последняя побеждает 100% пользователей! 》
- Алгоритмическая диаграмма: как найти минимальное значение в стеке? 》
Итак, далее мы входим в официальный контент сегодняшнего дня...
тема
Учитывая только включить'(',')','{','}','[',']'Строка , чтобы определить, является ли строка допустимой.
Действительная строка должна удовлетворять:
- Открывающие скобки должны быть закрыты закрывающими скобками того же типа.
- Левые скобки должны быть закрыты в правильном порядке.
- Обратите внимание, что пустые строки считаются допустимыми строками.
Пример 1:
Вход: "()" вывод: правда
Пример 2:
Вход: "()[]{}" вывод: правда
Пример 3:
Вход: "(]" вывод: ложь
Пример 4:
Вход: "([)]" вывод: ложь
Пример 5:
Вход: "{[]}" вывод: правда
Адрес LeetCode:Lee TCO's-talent.com/problems/VA…
Идеи решения проблем
Цель этого вопроса – проверить симметрию скобок. Например, такая строка, как "([{}])", является правильной и должна возвращать значение true, а такая строка, как "([{})]", неверна. . , который должен возвращать false.
Как видно из вышеприведенного заголовка, круглые скобки делятся на три категории: круглые скобки, квадратные скобки и фигурные скобки, затемМы можем использовать функцию стека «первым пришел — последним вышел», чтобы сначала поместить в стек все левые скобки («(», «[», «{»), а затем, когда встретится правая скобка, сделать это соответствует элементу наверху стека, например, при обнаружении ")", если вершина стека "(", это означает, что совпадение выполнено успешно, верхний элемент стека извлекается из стека, а процесс зацикливания строк продолжается.Если есть ошибка в совпадении, false будет возвращено напрямую.
Допустимо ли предположить, что мы хотим сопоставить строку "(([]))"? Тогда поток выполнения такой.
Когда левая скобка встречается первой, она сначала помещается в стек:
Далее идет левая скобка, и продолжаем толкать стек:
Затем снова левая скобка и продолжайте нажать стек:
Далее идет правая круглая скобка, соответствующая верхнему элементу стека. «[]» — пара допустимых круглых скобок. Верхний элемент стека успешно сопоставляется и извлекается из стека:
Далее идет правая круглая скобка, которая соответствует верхнему элементу стека. "()" — это пара допустимых круглых скобок, и верхний элемент стека успешно сопоставляется и извлекается из стека:
Далее идет правая круглая скобка, которая соответствует верхнему элементу стека. "()" — это пара допустимых круглых скобок, и верхний элемент стека успешно сопоставляется и извлекается из стека:
Когда строковый цикл заканчивается и стек пуст, это доказывает, что круглые скобки строки допустимы, и окончательный результат показан на следующем рисунке:
Затем мы будем использовать код для реализации всего процесса...
код реализации один
public boolean isValid(String s) {
int slen = s.length(); // 括号的长度
if (slen % 2 == 1) { // 括号不是成对出现直接返回 false
return false;
}
// 把所有对比的括号存入 map，对比时用
Map<Character, Character> map = new HashMap<>();
map.put(')', '(');
map.put('}', '{');
map.put(']', '[');
// 定义栈，用于存取括号（辅助比较）
Stack<Character> stack = new Stack<>();
for (int i = 0; i < slen; i++) { // 循环所有字符
char c = s.charAt(i);
if (map.containsKey(c)) { // 为右边的括号，如 ')'、'}' 等
if (stack.isEmpty() || stack.peek() != map.get(c)) { // 栈为空或括号不匹配
return false;
}
stack.pop(); // 是一对括号，执行出栈（消除左右括号）
} else { // 左边括号，直接入栈
stack.push(c);
}
}
return stack.isEmpty();
}
Давайте отправим код в LeetCode, и результат выполнения будет следующим:
Анализ кода
приведенного выше кодаmapНабор — это правило сопоставления, используемое для определения круглых скобок. Например, совпадающее значение, соответствующее «)», — это «(», совпадающее значение «]» — это «[» и т. д., а затем мы переходим к циклу строки для проверки, и столкнуться с левой скобкой.Поместить прямо в стек, найти правую скобку, чтобы она соответствовала верхнему элементу стека, дождаться конца всего строкового цикла, если стек пуст, скобки строка является законной.
Анализ сложности
Временная сложность: O(n), обход всей строки один раз. Пространственная сложность: O(n).
Второй код реализации
В дополнение к стеку мы также можем использовать JavareplaceМетод реализован, мы можем зациклить фигурные скобки в строке, например циклы "()" или "[]" или "{}" заменяют их, и, наконец, если строка пуста после завершения выполнения. Legal, конкретный код реализации выглядит следующим образом:
public boolean isValid(String s) {
int len;
do {
len = s.length();
// 消除成双成对的符号
s = s.replace("()", "").replace("[]", "").
replace("{}", "");
} while (len != s.length()); // 不能再进行替换了，replace 方法没有替换任何字符
return s.length() == 0;
}
Давайте отправим код в LeetCode, и результат выполнения будет следующим:
Судя по текущим результатам, разница в эффективности выполнения между ними по-прежнему очевидна:
Суммировать
В этой статье мы говорили о реальном письменном тестовом вопросе билибили, который также является классическим вопросом интервью о стеке.Мы можем использовать характеристики стека (первым пришел, последним ушел), чтобы вставить все левые скобки в стек, и пусть он соответствует верхнему элементу стека, когда встречается правая круглая скобка.Чтобы соответствовать, когда строковый цикл заканчивается и стек пуст, круглые скобки этой строки являются допустимыми. Конечно, в самом интервью мы также можем использовать Java.replaceметод как гарантированная реализация, потому чтоreplaceРеализация метода относительно проще, но производительность не так хороша.
Благосостояние в конце статьи: Поиск общедоступной учетной записи «Китайское сообщество Java», чтобы отправить «интервью», чтобы получить последние материалы интервью.