Аварийный алгоритм передней части переднего конца: общий алгоритм и совершенство

внешний интерфейс алгоритм

введение

Бутылка снова здесь, она здесь с фронтенд-алгоритмом👏👏👏

Собеседования на крупных фабриках становятся все сложнее, а требования к алгоритмам — все больше и больше. Когда интервьюер задает алгоритмический вопрос, точный ответ может значительно повысить благосклонность интервьюера. Эта серия посвящена созданию набора алгоритмов. для передней части.

Прошлый замечательный цикл статей:

Резюме трех групповых вопросов по обмену кистями:

Название (название будет выпущено только в «Лагере обучения продвинутому алгоритму», где каждое утро в 9:00):

Массив статей:

Связанный список:

Строковые статьи:

Стек статей:

Этот раздел представляет собой подведение итогов и обзор четвертой недели, давайте приступим к делу! 👇👇👇

1. Baidu: реализовать функцию для определения того, является ли ввод строкой-палиндромом.

1. Решение 1. Используйте API

function isPlalindrome(input) {
  if (typeof input !== 'string') return false;
  return input.split('').reverse().join('') === input;
}

2. Решение 2. Не используйте API

function isPlalindrome(input) {
  if (typeof input !== 'string') return false;
  let i = 0, j = input.length - 1
  while(i < j) {
      if(input.charAt(i) !== input.charAt(j)) return false
      i ++
      j --
  }
  return true
}

3. Больше решений

смотрите подробностиBaidu: реализовать функцию для определения того, является ли ввод строкой-палиндромом.

2. Byte & Leetcode3: самая длинная подстрока без повторяющихся символов.

1. Темы

Дана строка, пожалуйста, найдите ту, которая не содержит повторяющихся символовсамая длинная подстрока длина.

Пример 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

Пример 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

Пример 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

2. Решение

Решение 1. Сохраните массив

Идеи решения проблемы:Используйте массив для поддержки скользящего окна

Пройдите по строке, чтобы определить, находится ли символ в массиве скользящего окна.

  • Отсутствиеpushв массив
  • Затем удалите тот же символ и символ перед тем же символом в массиве скользящего окна, а затем удалите текущий символpushв массив
  • потомmaxОбновление длины текущей самой длинной подстроки

После обхода возвращайтесьmaxТолько что

Рисунок для понимания:

Код:

var lengthOfLongestSubstring = function(s) {
    let arr = [], max = 0
    for(let i = 0; i < s.length; i++) {
        let index = arr.indexOf(s[i])
        if(index !== -1) {
            arr.splice(0, index+1);
        }
        arr.push(s.charAt(i))
        max = Math.max(arr.length, max) 
    }
    return max
};

Временная сложность: O(n2), вarr.indexOf()Временная сложность O(n) ,arr.splice(0, index+1)Временная сложность также O (n)

Космическая сложность: O (n)

Решение 2. Сохраняйте подписки

Идеи решения проблемы:Используйте индексы для поддержки скользящих окон

Код:

var lengthOfLongestSubstring = function(s) {
    let index = 0, max = 0
    for(let i = 0, j = 0; j < s.length; j++) {
        index = s.substring(i, j).indexOf(s[j]) 
        if(index !== -1) { 
            i = i + index + 1 
        } 
        max = Math.max(max, j - i + 1) 
    }
    return max
};

Временная сложность: O(n2)

Космическая сложность: O(n)

Решение 3. Оптимизированная карта

Идеи решения проблемы:

использоватьmapдля хранения символов, которые были пройдены до сих пор,keyэто персонаж,valueиндекс

использоватьiчтобы отметить начало подстроки без повторения подстрок,jИндекс текущий обход символ

Пройдитесь по строке, чтобы определить, находится ли текущий символ уже вmapсуществует в подстроке, если она существует, обновить подстроку без дубликатов и начать индексациюiэто следующая позиция того же символа, на этот раз отiприбытьjдля последней неповторяющейся подстроки обновитеmax, поместите текущий символ и индекс вmapсередина

Наконец, вернитесьmaxТолько что

Код:

var lengthOfLongestSubstring = function(s) {
    let map = new Map(), max = 0
    for(let i = 0, j = 0; j < s.length; j++) {
        if(map.has(s[j])) {
            i = Math.max(map.get(s[j]) + 1, i)
        }
        max = Math.max(max, j - i + 1)
        map.set(s[j], j)
    }
    return max
};

Временная сложность: O(n)

Космическая сложность: O(n)

3. Больше решений

смотрите подробностиbytes & Leetcode3: самая длинная подстрока без повторяющихся символов

3. Статья: Комплексная интерпретация структуры стека

1. Стек структуры данных

Стек — это упорядоченная коллекция, работающая по принципу «последним пришел — первым обслужен» (LIFO/Last In First Out) и имеет следующую структуру:

Код

function Stack() {
  let items = []
  this.push = function(e) { 
    items.push(e) 
  }
  this.pop = function() { 
    return items.pop() 
  }
  this.isEmpty = function() { 
    return items.length === 0 
  }
  this.size = function() { 
    return items.length 
  }
  this.clear = function() { 
    items = [] 
  }
}

Поиск: поиск с вершины стека, временная сложность O(n)

Вставка или удаление: временная сложность нажатия и извлечения стека составляет O (1)

2. Интервью: стек вызовов

Стек вызовов – это структура данных, которую JavaScript использует для управления контекстом выполнения функции. Он записывает, где выполняется текущая функция и какая функция выполняется. Если мы выполняем функцию, контекст выполнения создается для функции и помещается на вершину стека. Если мы возвращаемся из функции, извлекать ее контекст выполнения из вершины стека. Также можно сказать, что стек вызовов — это стек, используемый для управления этим контекстом выполнения, или стек контекста выполнения (стек выполнения).

3. Интервью: пространство стека и пространство кучи

В JavaScript существует три основных типа пространства памяти:

  • Кодовое пространство: в основном используется для хранения исполняемого кода.
  • Пространство стека: пространство для хранения стека вызовов — это пространство стека.
  • куча пространства

Кодовое пространство в основном используется для хранения исполняемого кода. Пространство стека и пространство кучи в основном используются для хранения данных. Далее мы в основном вводим пространство стека и пространство кучи.

Когда контекст выполнения выполняется в стеке вызовов, контекст и связанное с ним пространство данных должны быть удалены. сборщик мусора (нового поколения) С основным сборщиком мусора (старого поколения) для сбора.

4. Детали

Подробнее см.Расширенный алгоритм внешнего интерфейса 5: всесторонне интерпретировать структуру стека, используемую во внешнем интерфейсе (+ вопросы по чистке кода)

4. Byte & leetcode155: минимальный стек (стек, содержащий функцию getMin)

1. Темы

спроектировать опоруpush,pop,topоперации и может получить стек с наименьшим элементом за постоянное время.

  • push(x)- Поместить элемент x в стек.
  • pop()—— Удалить элемент в верхней части стека.
  • top()—— Получить верхний элемент стека.
  • getMin()- Получить наименьший элемент в стеке.

Пример:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

2. Решение

Стек с наименьшим элементом извлекается за постоянное время, т.е. только гарантируетgetMinВременная сложность O (1)

var MinStack = function() {
    this.items = []
    this.min = null
};

// 进栈
MinStack.prototype.push = function(x) {
    if(!this.items.length) this.min = x 
    this.min = Math.min(x, this.min)
    this.items.push(x) 
};

// 出栈
MinStack.prototype.pop = function() {
    let num = this.items.pop() 
    this.min = Math.min(...this.items)
    return num
};

// 获取栈顶元素
MinStack.prototype.top = function() {
    if(!this.items.length) return null
    return this.items[this.items.length -1] 
};

// 检索栈中的最小元素
MinStack.prototype.getMin = function() {
    return this.min
};

Временная сложность: O(1) для нажатия, O(n) для извлечения, O(1) для получения верхнего элемента стека, O(1) для получения наименьшего элемента

Космическая сложность: O(n)

3. Больше решений

смотрите подробностиbytes&leetcode155: минимальный стек (стек, содержащий функцию getMin)

5. Графика Tencent и leetcode20: Допустимые скобки

1. Темы

Учитывая только включить'(',')','{','}','[',']'Строка, чтобы определить, является ли строка допустимой.

Действительная строка должна удовлетворять:

  • Открывающие скобки должны быть закрыты закрывающими скобками того же типа.
  • Левые скобки должны быть закрыты в правильном порядке.

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

Пример 1:

输入: "()"
输出: true

Пример 2:

输入: "()[]{}"
输出: true

Пример 3:

输入: "(]"
输出: false

Пример 4:

输入: "([)]"
输出: false

Пример 5:

输入: "{[]}"
输出: true

2. Решение: использовать структуру стека

Идеи решения проблемы:Вставьте символы в строку в стек по очереди и пройдитесь по символам, чтобы судить по очереди:

  • Сначала определите, является ли элемент{,(,[, прямо в стек
  • В противном случае персонаж},),]Один из вариантов, если строка действительна, элемент должен соответствовать вершине стека, например, элемент в стеке имеет({, если элемент, который продолжает движение,), то текущая последовательность элементов({)Невозможно быть действительным, поэтому, если он не соответствует верхнему элементу стека в это время, он вернется напрямую.false, строка недействительна

Когда обход завершен, все совпадающие символы были сопоставлены и выскочили из стека. Если стек в это время пуст, строка действительна. Если стек не пуст, это означает, что в строке есть несовпадающие символы. , а строка недействительна.

Рисунок для понимания:

Код:

var isValid = function(s) {
    let map = {
        '{': '}',
        '(': ')',
        '[': ']'
    }
    let stack = []
    for(let i = 0; i < s.length ; i++) {
        if(map[s[i]]) {
            stack.push(s[i])
        } else if(s[i] !== map[stack.pop()]){
            return false
        }
    }
    return stack.length === 0
};

Временная сложность: O(n)

Космическая сложность: O(n)

3. Больше решений

смотрите подробностиГрафика Tencent&leetcode20: Допустимые скобки

6. leetcode1047: удалить все соседние дубликаты в строке.

1. Темы

дать строку, состоящую из строчных буквS,Дублирование операции удаленияДве соседние и одинаковые буквы выбираются и удаляются.

Повторяйте операцию дедупликации на S до тех пор, пока его больше нельзя будет удалить.

Возвращает окончательную строку после выполнения всех операций дедупликации. Ответ гарантированно будет уникальным.

Пример:

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

намекать:

  1. <= S.length <= 20000
  2. SСостоит только из строчных английских букв.

2. Решение: используйте стек

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

Этапы решения проблемы:Пройдите по строке, извлеките символ заголовка стека и определите, согласуется ли текущий символ с символом заголовка стека.

  • Несовместимо, символ заголовка помещается в стек, а текущий символ помещается в стек.
  • Консистентные, то есть символ заголовка стека совпадает с текущим символом, и их не нужно запихивать в стек, просто сразу перейти к следующему обходу

После завершения обхода вернуть строку в стек

Код:

var removeDuplicates = function(S) {
    let stack = []
    for(c of S) {
        let prev = stack.pop()
        if(prev !== c) {
            stack.push(prev)
            stack.push(c)
        }
    }
    return stack.join('')
};

Временная сложность: O(n)

Космическая сложность: O(n)

3. Больше решений

смотрите подробностиleetcode1047: удалить все соседние дубликаты в строке

7. Присоединиться к первой фазе тренировочного лагеря по фронтенд-алгоритму можно бесплатно.

Создайте полную структуру данных и систему алгоритмов от 0 до 1!

Здесь мистер Боттл не только представляет алгоритм, но и объединяет алгоритм с различными полями интерфейса, включая браузеры, HTTP, V8, React, исходный код Vue и т. д.

Здесь вы можете изучать большой вопрос по заводскому алгоритму (Ali, Tencent, Baidu, Byte и т. д.) или литкод каждый день, а мистер Бутылка ответит на него на следующий день!

Отсканируйте код, чтобы присоединиться. Если количество человек в группе достигло линии, подпишитесь на общедоступную учетную запись «Front-end Bottle Gentleman» и ответьте «алгоритм» для автоматического присоединения.

⬆️Отсканируйте код, чтобы подписаться на официальный аккаунт «Front-end Bottle King», и ответьте на «Алгоритм», чтобы автоматически присоединиться к 👍👍👍

Категории