Компания ByteDance должна быть той, которая уделяет алгоритмам наибольшее внимание среди всех компаний, которые набирают осенью.Каждое собеседование в основном заставит вас рвать алгоритм руками.Сегодня в этой статье записано несколько алгоритмов, которые задавали в то время. вопросы, и для каждого вопроса алгоритма IподробныйдалОптимальным решением, сцена интервью того времени воспроизведена ниже. После прочтения вы что-то приобретете
1. Пробный нож Mavericks: эффективные кронштейны
В большинстве случаев интервьюер задаст вопрос, который не очень сложен, но не слишком радуйтесь, потому что этот вопрос часто может быть расширен до более сложных вопросов, или вопрос, который выглядит простым, но дает оптимальное решение. нелегко. Вопрос в этом
Учитывая строку, содержащую только '(', ')', проверьте, действительна ли строка. Примечание. Пустые строки являются допустимыми строками.
示例 1:
输入: "(())"
输出: true
实例 2：
输入: "())("
输出: false
Первый раз увидела этот вопрос, зашла, настолько он простой и стабильный (потому что меня просто отругал интервьюер, когда я был на стороне)Квест Драконавопросы DP, которые относятся к сложному уровню в leeetcdoe).
На самом деле, литкод вопроса 20 этого вопросаупрощенная версия, относящийся к легкому уровню
Так что я не колеблясь использовалкучаПриходите решать, я думаю, 99% будет решено с помощью стека, верно? Здесь я кратко расскажу о следующем процессе, шаги следующие:
1. В процессе обхода строки при встрече "(" пусть она помещается в стек, а при встрече ")" оценивается, есть ли "(" в следующем стеке:
（1）、如果有，则把处于栈顶的 "(" 弹出，相当于和 ")" 进行匹配，然后继续往后遍历字符串
（2）、如果没有，则匹配失败。相当于字符串的最前面出现了 ")"，显然这是不合理的。
2. По завершению обхода строки определить, пуст ли стек, если пуст, то строка валидна, иначе невалидна.
Для того, чтобы принять во вниманиенуб, Я должен был нарисовать для вас картинку, чтобы продемонстрировать, я слишком добросовестный.
Код выглядит следующим образом (Java, но его можно понять и без изучения Java)
public static boolean isValid(String s){
if(s == null || s.length() < 1)
return true;
int n = s.length();// 字符串长度
// 创建一个栈来装字符
Stack<Character> stack = new Stack<>();
// 遍历字符串
for(int i = 0; i < n; i++){
// 获取字符串的第 i 个字符
char c = s.charAt(i);
if(c == '('){
stack.push(c);
}else{
if(stack.isEmpty())
return false;
else
stack.pop();
}
}
// 判断是否为空
if(stack.isEmpty())
return true;
return false;
}
2. Оптимизация
Затем интервьюер сказал, что пространственная сложность моего вопроса равна O(n),Могу ли я оптимизировать его?
Честно говоря, если вы ответили на 20-й вопрос литкода, ваш мозг может ориентироваться, и не обязательно, потому что этот вопрос является оптимальным решением для работы со стеком. Однако этот вопрос является упрощенной версией.На самом деле сложность пространства может быть оптимизирована до O (1).Вы можете подумать об этом.
Поскольку мы сохраняем все **одинаковые символы**"(" в стеке, мы фактически можем использовать переменную для замены стека. Эта переменная записывает количество "(" и добавляет 1 к переменной "(" . переменная ")" уменьшается на 1, а пустой стек эквивалентен значению переменной 0.
В то время я не знал, почему, поэтому я сразу же использовал этот метод, поэтому я изменил код за одну минуту следующим образом:
public static boolean isValid(String s){
if(s == null || s.length() < 1)
return true;
int n = s.length();// 字符串长度
// 用来记录遇到的 "(" 的个数
int sum = 0;
// 遍历字符串
for(int i = 0; i < n; i++){
// 获取字符串的第 i 个字符
char c = s.charAt(i);
if(c == '('){
sum++;
}else{
if(sum == 0)
return false;
else
sum--;
}
}
return sum == 0 ? true : false;
}
В этом случае временная сложность равна O(n), а пространственная сложность — O(1).
В-третьих, самая длинная эффективная скобка
Затем интервьюер продолжал усложнять этот вопрос, и вопрос был изменен на следующий:
Учитывая строку, содержащую только '(' и ')', найдите длину самой длинной подстроки, содержащей допустимые круглые скобки.
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
На самом деле, этот вопрос является исходным вопросом leetcode, вопрос 32, сложность сложная.
Поскольку я уже задавал этот вопрос раньше, я слегка улыбнулся, сделал вид, что думаю с серьезным выражением лица, а затем сразу же дал идею.закон о насилиииз.
1. Закон о насилии
Закон насилия на самом деле очень прост, то есть первый символкак первый символ самой длинной допустимой скобкичтобы пройти по строке, затем пройти по строке со вторым символом в качестве первого символа самой длинной допустимой скобки, затем пройти по строке с третьим символом...
Например, s = "( ) ) ( ( ) )".
Возьмите первый символ в качестве первого символа, тогда max = 2 (третий символ ')' не будет совпадать) Используйте второй символ в качестве первого символа, тогда max = 0 (это ')' в начале, очевидно, ничего не совпадает) Возьмите третий символ в качестве первого символа, тогда max = 0 Возьмите четвертый символ в качестве первого символа, тогда max = 4 ..... Временная сложность этого подхода составляет O (n ^ 2), а пространственная сложность - O (1).
В основном тот же вопрос, что и выше, просто выполните n обходов.
Тогда интервьюер спросил, можно ли его оптимизировать?
Я давно знал, что буду просить оптимизацию.Я уже сам этим вопросом занимался, поэтому сделал вид, что думаю об этом, и сразу дал оптимизацию.
2. Оптимизация
Мы по-прежнему используем стек для выполнения оптимизированной версии этого вопроса, но при добавлении в стек вместо помещения "(" в стек мы помещаем в стек индекс "(". Шаги следующие:
1. Сначала положите в стек -1. (А почему? Вы узнаете, когда увидите это позже) 2. Для каждого встретившегося '(' мы конвертируем егоиндексположить в стек. 3. Для каждого встречающегося ')' мы извлекаем элемент из вершины стека и помещаем текущий элементиндексПодстрочный индекс с всплывающим элементомсделать ошибку, предполагаемыйДлина текущей допустимой строки скобок.
Таким образом, мы продолжаем вычислять длину допустимых подстрок и, наконец, возвращаем длину самой длинной допустимой подстроки.
не могу читать? Все в порядке, я возьму пример и нарисую несколько графиков, таких как s = "( ) ) ( ( ) )", и использую переменную max для хранения размера самой длинной действительной строки, я представляет нижний индекс текущая строка
0. Инициализация: max = 0, i = 0. -1 помещается в стек
1. i = 0, s[i] = '(', индекс i = 0 помещается в стек
2. i = 1, s[i] = ')', вытолкнуть стек, i - верхний элемент стека = 1 - (-1) = 2, в этот момент max = 2
Не могу понять? Все в порядке, посмотрите на код, чтобы углубить свое понимание, код выглядит следующим образом:
public int longestValidParentheses(String s) {
int max = 0;
Stack<Integer> stack = new Stack<>();
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
//下标入栈
stack.push(i);
} else {
// 出栈
stack.pop();
// 看栈顶是否为空，为空的话就不能作差了
if (stack.empty()) {
stack.push(i);
} else {
// i - 栈顶，获得档期有效括号长度
max = Math.max(max, i - stack.peek());
}
}
}
return maxans;
}
Временная сложность этого подхода составляет O (n), а пространственная сложность — O (n). Очень хорошо подумать об использовании стека для решения этой проблемы.
4. Последний удар
Я подумал, что это нормально, что я могу дать это решение. Интервьюер должен изменить вопрос. Затем интервьюер снова сказал:Можно ли его еще оптимизировать?. В этот момент я теряюсь в догадках....
Большие ребята, прочитавшие статью, могут подумать, можно ли ее оптимизировать в пространстве, ведь оптимизировать во времени невозможно.
Подумав об этом некоторое время, использовать стек невозможно.Решение оптимизации должно быть похоже на вопрос выше, заменяя стек рядом переменных, и тогда я придумал его следующим образом:
На самом деле, эту проблему все еще можно оптимизировать, используя переменные вместо стеков, как указано выше, но на этот раз нам нужны две переменные, мы предполагаем, что переменные левые и правые.
В процессе обхода строки слева направо мы используем левую для записи количества '(' и правую для записи количества ')'. И в процессе обхода:
1. Если левый == правый, очевидно, что правый ')' в этот раз обязательно будет совпадать. Таким образом, текущая эффективная длина скобки равна 2 * справа. Затем обновите макс.
2. Если лево
** Когда мы закончим обход строки, получим ли мы максимальную длину допустимых круглых скобок? ** Вы можете подумать об этом
Ответ - нет, нам все еще нужносправа налевоПройдите расчеты.
Зачем?
Поскольку '(' и ')' на самом деле эквивалентны, почему мы не можем выполнить вычисление в обратном порядке? Так что не игнорируйте это.
Окончательный код выглядит следующим образом:
public int longestValidParentheses(String s) {
if(s == null || s.length() < 1)
return 0;
int left = 0, right = 0, max = 0;
// 从左到右
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
if (left == right) {
max = Math.max(max, 2 * right);
} else if(right > left){
left = right = 0;
}
}
left = right = 0;
// 从右到左
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == '(') {
left++;
} else {
right++;
}
if (left == right) {
max = Math.max(max, 2 * left);
} else if (left > right) {
left = right = 0;
}
}
return max;
}
Временная сложность этого подхода составляет O(n), а пространственная сложность — O(1).
Суммировать
Во время выступления последний метод все еще относительно трудно придумать.Из этого интервью также видно, что не смотреть на вопрос очень просто, некоторые вопросы очень просто сделать, но если вы хотите использоватьОптимальным решениемКак это сделать, индекс сложности сразу же повышается. .
Если вы потом не поймете, то советую прочитать несколько раз.Частота этого вопроса по-прежнему довольно высока, в основном потому, что есть много методов, которые можно сделать, и эффективность каждого метода разная, но я должен дам вам вот.напоминание, то есть когда вы обычно делаете проблему, вы должны искать оптимальное решение, а не только ac, и вы должны смотреть на решения других людей.
Есть урожай? Я надеюсь, что старые айроны придут к комбо из трех ударов и покажут больше людей, чтобы увидеть эту статью.
1,как, чтобы больше людей могли увидеть эту статью
2. Обратите внимание на оригинальный публичный аккаунт WeChat»Играйте в программирование красиво』, чтобы закрепить базовые компьютерные знания (компьютерная сеть + операционная система + база данных + Linux) и алгоритмы, недавно открыл публичный аккаунт WeChat "Играйте в программирование красиво』, вы можете обратить внимание на тех, кто заинтересован, и сосредоточиться на объяснении связанных с алгоритмами статей, хи-хи. Закулисный ответ"электронная книга』Подарить вам подарочный набор избранных электронных книг, в том числеКачественные электронные книги для всех навыков