Задача: Длина последнего слова

Для заданной строки s, состоящей из слов и пробелов, вернуть длину последнего слова в строке. Примечание: слово — это максимальная подстрока, состоящая только из символов без пробелов.

Пример
Ввод: s = " Привет Мир "
Вывод: 3
Объяснение: Последнее слово "Мир" содержит 3 буквы.

Ответ 👈

#algorithms

Грокаем алгоритмы

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

Книга написана достаточно простым языком, да еще и с картинками. Если вы читаете англоязычные ответы на stackoverflow, то и книга вам будет по силам.

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

P.S. Книгу на обоих языках скинул в комменты.

#algorithms

Задача: Лучшее время для покупки и продажи акций

Дан массив prices, где prices[i] — цена акции на i-й день.

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

Напишите функцию, которая возвращает максимальную прибыль, которую можно получить от сделки. Если прибыль получить нельзя, вернуть 0.

Пример 1:
Ввод: prices = [7,1,5,3,6,4]
Вывод: 5
Объяснение: Обратите внимание, что покупка во 2й день и продажа в 1й день не возможны, потому что вы должны купить перед продажей.

Пример 2:
Ввод: prices = [7,6,4,3,1]
Вывод: 0

Пример 3:
Ввод: prices = [7,3,5,1,10,4]
Вывод: 9

Пишите свои версии в комментариях.

Ответ с объяснением 👈

#algorithms

Задача: Идентичность деревьев

Даны корни двух бинарных деревьев P и Q, напишите функцию, чтобы проверить, являются ли деревья одинаковыми.

Два бинарных дерева считаются одинаковыми, если они структурно идентичны, а узлы имеют одинаковое значение.

P.S. В телеге проблематично оформить наглядный пример деревьев с картинками. Кому нужны картинки – переходите к статье с ответом. Раздел до "Решения" не содержит спойлеров.

Пример 1:
Ввод: p = [1,2,3], q = [1,2,3]
Вывод: true

Пример 2:
Ввод: p = [1,2], q = [1,null,2]
Вывод: false

Пример 3:
Ввод: p = [1,2,1], q = [1,1,2]
Вывод: false

Пишите свои версии в комментариях.

Ответ с объяснением 👈

#algorithms

Избегание мыслительной нагрузки

Частно встречаю "короткие" и "простые" решения под задачками с алгоритмами. Типа использование split, reverse, join для переворота строки или сравнение объектов через JSON.strigify/parse.

Знание подобных практик, безусловно, обязательно, вот только мыслить алгоритмически они не особо помогают. При решении алгоритмов нужно прокачивать скилл понимая и решения алгоритмов, а не пытаться вспомнить все методы языка. В идеале, обходиться минимальным набором: объявление переменных, условия и циклы. А все вот эти map, filter, split и т.д. оставить для решения рутинных прикладных задач на реальных проектах.

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

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

P.S. вот тут оставлял книгу по алгоритмам, а по тэгу #algorithms можно найти решение задач с leetcode с пояснениями

Задача: Преобразование отсортированного массива в двоичное дерево поиска

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

Дан целочисленный массив nums, элементы которого отсортированы по возрастанию. Преобразуйте его в сбалансированное по высоте двоичное дерево поиска (АВЛ-дерево).

АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.

P.S. В телеге проблематично оформить наглядный пример деревьев с картинками. Кому нужны картинки – переходите к статье с ответом. Раздел до "Решения" не содержит спойлеров.

Пример 1:
Ввод: nums = [-10,-3,0,5,9]
Вывод: [0,-3,9,-10,null,5]
Объяснение: [0,-10,5,null,-3,null,9] тоже подходит

Пример 2:
Ввод: nums = [1,3]
Вывод: [3,1]
Объяснение: [1,null,3] и [3,1] тоже АВЛ деревья.

Пишите свои версии в комментариях.

Ответ с объяснением 👈

#algorithms

Задача: Самый повторяющийся элемент в массиве

Дан массив nums размера n, верните самый большой элемент.

Большой элемент – это элемент, который встречается более [n/2] раз. Можете считать, что большой элемент всегда существует в массиве.

Задание со звездочкой: Решите задачу за линейное время и используйте только O(1) памяти.

Первое решение, которое приходит на ум, довольно тривиальное: взять объект или Map, пройтись циклом по массиву и записать количество каждого элемента, а потом пройтись циклом по этому объекту и найти элемент с максимальным значением. Решение рабочее, но может оказаться прожорливым на больших данных: память – O(N), время – O(N + M), где M – количество уникальных символов. В статье решение для условия со звездочкой.

Пример 1:
Ввод: nums = [3,2,3]
Вывод: 3

Пример 2:
Ввод: nums = [2,2,1,1,1,2,2]
Вывод: 2

Пишите свои версии в комментариях.

Ответ с объяснением 👈

#algorithms

Задача: Объединение отсортированных массивов

Даны два целочисленных массива nums1 и nums2, отсортированных в возрастающем порядке, и два целых числа m и n, представляющие количество элементов в nums1 и nums2, соответственно.

Объедините nums1 и nums2 в один массив, отсортированный в возрастающем порядке.

Функция не должна ничего возвращать, вместо этого нужно мутировать массив nums1. Для этого, nums1 имеет длину m + n, где первые m элементов обозначают те, которые должны быть объединены, а последние n элементов установлены в 0 и должны быть проигнорированы. nums2 имеет длину n.

Задача со звездочкой: Сможете придумать алгоритм, который работает за время O(m + n)?

Пример 1:
Ввод: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Вывод: [1,2,2,3,5,6]
Объяснение: Массивы, которые мы объединяем – [1,2,3] и [2,5,6].
Результат объединения –[1,2,2,3,5,6].

Пример 2:
Ввод: nums1 = [1], m = 1, nums2 = [], n = 0
Вывод: [1]
Объяснение: Массивы, которые мы объединяем – [1] и [].
Результат объединения – [1].

Пример 3:
Ввод: nums1 = [0], m = 0, nums2 = [1], n = 1
Вывод: [1]
Объяснение: Массивы, которые мы объединяем – [] и [1].
Результат объединения – [1].
Обратите внимание, что, так как m = 0, в nums1 нет элементов. 0 здесь только для того, чтобы гарантировать, что результат слияния может поместиться в nums1.

Пишите свои версии в комментариях.

Ответ с объяснением 👈

#algorithms
@js_is_easy

Задача: Количество лазерных лучей в банке

Задачи с данными, которые можно визуализировать, а не просто абстрактные массивы решать интереснее. Это одна из них.

В банке активировали защитную систему. Дан двумерный массив bank, представляющий план банка, где 0 означает пустую ячейку, а 1 – ячейку с защитным устройством.

Между двумя устройствами проходит один лазерный луч, если выполняются оба условия:

- Два устройства находятся на двух разных строках: r1 и r2, где r1 < r2.
- Для каждой строки i, где r1 < i < r2, в i-й строке нет устройств безопасности (т.е. луч всегда идет к устройствам на ближайшей строке).

Каждый луч независим, то есть один луч не мешает другим и не соединяется с ними.

Верните общее количество лазерных лучей в банке.

Пример:
Ввод: ["011001","000000","010100","001000"]
Вывод: 8
Объяснение: Между каждой из следующих пар устройств проходит луч. Всего получается 8 лучей:
* bank[0][1] -- bank[2][1]
* bank[0][1] -- bank[2][3]
* bank[0][2] -- bank[2][1]
* bank[0][2] -- bank[2][3]
* bank[0][5] -- bank[2][1]
* bank[0][5] -- bank[2][3]
* bank[2][1] -- bank[3][2]
* bank[2][3] -- bank[3][2]
Обратите внимание, что между устройствами на 0-й и 3-й строках нет лучей, потому что на 2-й строке есть устройства безопасности, что нарушает второе условие.

Больше примеров и ответ с разбором: https://telegra.ph/Kolichestvo-lazernyh-luchej-v-banke-07-12

#algorithms

@js_is_easy