Часть 1: массивы и хеш-таблицы, куча, два указателя, интервалы, связанный список, двоичный поиск, метод скользящего окна, строки, жадные алгоритмы и динамическое программирование.
Эта статья будет полезна тем, кто готовится к ролям в разработке программного обеспечения, а также к ролям инженера по машинному обучению. В большинстве компаний нам придется пройти собеседование по кодированию с использованием структур данных и алгоритмов CS. Кроме того, в этой серии статей мы сначала рассмотрим темы в широком смысле, прежде чем вернуться к ним для более глубокого изучения. Лучше сначала получить представление обо всех типах проблем, таким образом, когда вы видите новую проблему, вы можете выяснить, какая структура данных и алгоритм подходят для решения проблемы.
1. Массивы и хеш-таблицы
Проблема¹: учитывая массив целых чисел nums (предположим, что положительное число) и целочисленную цель, вернуть индексы двух чисел так, чтобы они в сумме равнялись цели. Вы можете предположить, что каждый вход будет иметь ровно одно решение, и вы не можете использовать один и тот же элемент дважды. Вы можете вернуть ответ в любом порядке.
Пример: ввод: nums = [2,7,11,15], target = 26. Вывод: [2,3]
Решение:
Объяснение: Когда мы говорим о массивах, в Python это не что иное, как список. Во-первых, посмотрите на решение методом грубой силы - оно имеет 2 вложенных цикла for, которые повторяют все числа в массиве дважды, следовательно, наихудшая временная сложность составляет O (n²). Обратите внимание, что я даю более простое объяснение временной сложности, и каждый раз, когда у вас есть вложенные циклы for, вы можете с уверенностью предположить, что это не оптимальное решение, и вас отклонят, если вы предложите это решение только на собеседовании.
Ввод: nums = [2,7,11,15], target = 26.
Почему j начинается с i + 1? Мы избегаем избыточных вычислений, поскольку сложение является коммутативным для действительных чисел, а также нам не нужно добавлять одно и то же число дважды, как в каждой постановке задачи.
Во-вторых, посмотрите на функцию twoSumbetter - она использует только 1 для цикла, то есть выполняет итерацию по всем числам в массиве только один раз, поэтому временная сложность будет O (n). Это оптимальное решение, и мы бы предпочли его.
Итак, где же хеш-таблица?
Словарь, который мы используем в Python, - это то, что мы называем хеш-таблицей. Давайте рассмотрим пример:
Ввод: nums = [2,7,11,15], target = 26.
Идея состоит в том, чтобы отслеживать дополнение (текущее значение) с помощью словаря. Найдя дополнение в словаре, мы можем остановиться и вернуть ответ, то есть индексы. Для поиска ответа методом грубой силы потребовалось 6 шагов, но для этого метода потребовалось 4 шага. Если target = 9, то оба будут делать 2 шага для решения, но это не означает, что оба являются оптимальными решениями; нам нужно рассмотреть все возможные цели и в целом по какой из них нужно меньше всего шагов.
Чтобы понять словари и «final_dict [nums [i]] = i», попробуйте следующее:
A = {}
A [2] = 0
A [3] = 1
печать (A)
2. Куча
Согласно документации Python, «Кучи - это двоичные деревья, для которых каждый родительский узел имеет значение, меньшее или равное любому из его дочерних узлов».
Проблема²: Для данного массива вернуть k верхних наибольших значений в массиве.
Пример: array = [2,4,9,12,5,19] и k = 3. Выход = [9,12,19]
Решение²:
Мы можем легко решить эту проблему с помощью сортировки, верно? Оказывается, временная сложность функции sort (), используемой в Python, требует n * log (n) в наихудшем случае временной сложности (обратите внимание, что мы все равно не можем улучшить это). Алгоритм сортировки, используемый в Python, называется TimSort: https://en.wikipedia.org/wiki/Timsort.
Наша цель - сократить это время, и поэтому мы использовали кучу для решения проблемы, которая требует log (n) наихудшей временной сложности. Это то, что интервьюер ожидает от вас, чтобы выбрать правильную структуру данных, которая даст оптимальное решение. Если вы не понимаете сложность времени O (log (n)), проверьте эту страницу: https://hackernoon.com/what-does-the-time-complexity-o-log-n-actually-mean-45f94bb5bfbf
Объяснение: Итак, что именно происходит с нашей функцией: heap_topklargest? Давайте изменим наш код, добавив оператор печати:
Итак, вы видите, что heappush (heap, i) не добавляет следующее значение, а скорее вставляет новое значение для сохранения свойства кучи. Когда len (куча) впервые достигает 4, мы получаем heap = [2, 3, 4, 9], и мы используем heappop, и самое маленькое число удаляется. Также обратите внимание, что когда heap = [3,7,4,9]; heapop удаляет 3, но не возвращает [7,4,9], а вместо этого возвращает [4,7,9], потому что он обеспечивает сохранение свойства кучи (как указано выше: «Кучи - это двоичные деревья, для которых каждый родитель узел имеет значение, меньшее или равное любому из его дочерних элементов »).
3. Техника двух указателей.
В этом методе мы можем обрабатывать два элемента в цикле вместо одного.
Проблема⁴: возвести в квадрат каждое значение в отсортированном массиве и вернуть результат в отсортированном порядке.
Пример: array = [- 5, -4,1,2,3,4] Вывод = [1,4,9,16,16,25]
Решение⁴:
Пояснение: Почему так много циклов while? Первый цикл while должен проверить, есть ли у нас отрицательные числа в массиве, и если да, то нам нужно увеличить правый указатель. Второй цикл while вводится, только если left ≥0, и это произойдет, только если в массиве присутствуют отрицательные числа. Посмотрите на вывод ниже, где я использую операторы печати, чтобы узнать, что происходит:
В array1 мы вводим 1-й / 2-й / 3-й цикл while. 4-й цикл while не вводится как right = 7 = len (array). В array2 мы вводим только последний цикл while! Итак, если у нас есть только положительные числа, решить эту проблему несложно.
Вот еще одна проблема, которую нужно решить с помощью двух указателей: https://leetcode.com/problems/container-with-most-water/
4. Интервалы
Проблема: задан массив интервалов, где interval [i] = [start_i, end_i], объединить все перекрывающиеся интервалы и вернуть массив неперекрывающихся интервалов, которые покрывают все интервалы во входных данных.
Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]]
Решение: ⁵
Если мы удалим закомментированные операторы печати и перезапустим:
Первая итерация, интервалы [1] соответствуют [2,6]. Итак, start = 2 и end = 6. Мы также инициализировали Output = [interval [0]] = [[1,3]]. Поскольку условие if выполнено, Output [-1] [1] = max (end, lastEnd) = max (6,3) = 6. Таким образом, Output обновляется до [[1,6]]. Во второй итерации, если условие не выполняется, мы добавляем [8,10] к выводу и так далее.
5. Струны
Проблема: даны строка s и индексы целочисленного массива одинаковой длины. Строка s будет перемешана так, что символ в i-й позиции переместится в индексы [i] в перемешанной строке. Верните перетасованную строку.
Ввод: s = «codeleet», индексы = [4,5,6,7,0,2,1,3]
Вывод: «leetcode»
Если мы раскомментируем и проверим, то увидим, что произошло:
Сначала мы создали словарь, используя индексы и строку s. Наша цель - использовать индексы для возврата к исходной строке, поэтому мы сортируем этот словарь по элементам. Теперь мы почти закончили, но как извлечь буквы из всех кортежей? Простой способ - снова превратить его в словарь, а затем присоединить все значения.
Дополнительные сведения о строках Python см. В этой статье: https://towardsdatascience.com/41-questions-to-test-your-knowledge-of-python-strings-9eb473aa8fe8
В части 2 мы увидим связанный список, двоичный поиск, технику скользящего окна, жадные алгоритмы и динамическое программирование.
Использованная литература:
- Https://leetcode.com/problems/two-sum/
- Https://www.youtube.com/watch?v=3c-p4zWx5yU&list=UU25eIuHtWn8W6wstp0wDwlQ&index=2&ab_channel=BrennanFradelis
3. https://algodaily.com/lessons/using-the-two-pointer-technique
4. https://www.youtube.com/watch?v=0l2nePjDFuA&ab_channel=BrennanFradelis
5. https://www.youtube.com/watch?v=44H3cEC2fFM&ab_channel=NeetCode
