Задача с собеседования в eBay
Коко любит есть бананы. Имеется n куч бананов, где i-я куча содержит piles[i] бананов. Охранники ушли и вернутся через h часов.
Коко может выбрать скорость поедания бананов в час (равняется k). Каждый час она выбирает какую-либо кучу и съедает k бананов из неё. Если в выбранной куче меньше k бананов, она съедает их все и в течение этого часа больше не ест.
Коко любит есть медленно, но хочет успеть съесть все бананы до возвращения охранников.
Верните минимальное целое число k, при котором Коко сможет съесть все бананы в течение h часов.
Пример 1:
Input: piles = [3,6,7,11], h = 8
Output: 4
Пример 2:
Input: piles = [30,11,23,4,20], h = 5
Output: 30
Пример 3:
Input: piles = [30,11,23,4,20], h = 6
Output: 23
Ограничения:
1 <= piles.length <= 10⁴
piles.length <= h <= 10⁹
1 <= piles[i] <= 10⁹
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Используем бинарный поиск, а точнее бинарный поиск по ответу: если Коко успеет съесть все бананы при некоторой скорости k, значит, она сможет их съесть и при любой скорости больше k (свойство монотонности). Таким образом, можно отбросить половину диапазона поиска.
В отличие от классического бинпоиска здесь не требуется сортировка входных данных, так как искать результат будем не в массиве piles, а в уже упорядоченном диапазоне скоростей (левую границу определим как 1, а правую - как max(piles)). Порядок самих куч не влияет на сумму часов.
- Определяем исходный диапазон поиска: l = 1 (минимальная возможная скорость), r = max(piles) (кол-во бананов в самой большой куче, так как в любом случае нельзя съесть кучу быстрее, чем за час);
- Задаём условие для перехода в левую или правую половину: в цикле бинарного поиска вычисляем среднюю скорость.
Проходим по всем кучам и считаем кол-во часов, за которые Коко съест все бананы при текущем гипотетическом значении k: hours += (p + k - 1) // k
Формула вычисления часов работает следующим образом:
к примеру, Коко успевает съесть за час все бананы из кучи, кроме 1. На этот 1 банан в любом случае нужен 1 дополнительный час, в течение которого Коко съест только его, не начиная новую кучу. То есть нам требуется округление вверх (целочисленное деление в питоне по умолчанию округляет вниз).
Нужно добавить такое кол-во бананов, чтобы и получить необходимый дополнительный час при наличии остатка, и корректно обработать числа без остатка. Значение, которое сработает в любом из двух случаев - это прибавка k - 1 (максимальное значение, не создающее дополнительные часы, когда у нас нет остатка).
Предположим, p = 11, а k = 5. При простом делении p // k получили бы 2, и один банан остался бы без учёта при подсчёте часов. Но если пользуемся формулой (11 + 5 -1) // 5, получаем 3 часа, которые потребуются, чтобы съесть 11 бананов со скоростью 5 бананов/час.
А если бы в другой куче было 15 бананов, которые делятся на 5 без остатка, формула тоже сработала бы: (15 + 5 - 1) // 5 = 3 (всё те же 3 часа, так как целочисленное деление просто отбросит остаток 4);
- Сдвигаем границы поиска:
Если Коко успевает съесть все бананы: запоминаем k как текущего кандидата, обновляя res, и сдвигаем правую границу поиска влево (пытаемся найти ещё меньшую скорость);
Если не успевает: сдвигаем левую границу вправо, так как нужно искать среди больших скоростей;
Возвращаем минимальную возможную скорость, при которой Коко сможет съесть все бананы, уложившись в h часов.
Сложность
O(n log m) - по времени (где n - кол-во куч бананов, а m - максимальное кол-во бананов в куче)
O(1) - по памяти (храним только переменные, не создавая дополнительных структур данных)
Код
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
l, r = 1, max(piles)
res = r
while l <= r:
k = (l + r) // 2
hours = 0
for p in piles:
hours += (p + k - 1) // k
if hours <= h:
res = min(res, k)
r = k - 1
else:
l = k + 1
return res
@algoses
Коко любит есть бананы. Имеется n куч бананов, где i-я куча содержит piles[i] бананов. Охранники ушли и вернутся через h часов.
Коко может выбрать скорость поедания бананов в час (равняется k). Каждый час она выбирает какую-либо кучу и съедает k бананов из неё. Если в выбранной куче меньше k бананов, она съедает их все и в течение этого часа больше не ест.
Коко любит есть медленно, но хочет успеть съесть все бананы до возвращения охранников.
Верните минимальное целое число k, при котором Коко сможет съесть все бананы в течение h часов.
Пример 1:
Input: piles = [3,6,7,11], h = 8
Output: 4
Пример 2:
Input: piles = [30,11,23,4,20], h = 5
Output: 30
Пример 3:
Input: piles = [30,11,23,4,20], h = 6
Output: 23
Ограничения:
1 <= piles.length <= 10⁴
piles.length <= h <= 10⁹
1 <= piles[i] <= 10⁹
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
В отличие от классического бинпоиска здесь не требуется сортировка входных данных, так как искать результат будем не в массиве piles, а в уже упорядоченном диапазоне скоростей (левую границу определим как 1, а правую - как max(piles)). Порядок самих куч не влияет на сумму часов.
- Определяем исходный диапазон поиска: l = 1 (минимальная возможная скорость), r = max(piles) (кол-во бананов в самой большой куче, так как в любом случае нельзя съесть кучу быстрее, чем за час);
- Задаём условие для перехода в левую или правую половину: в цикле бинарного поиска вычисляем среднюю скорость.
Проходим по всем кучам и считаем кол-во часов, за которые Коко съест все бананы при текущем гипотетическом значении k: hours += (p + k - 1) // k
Формула вычисления часов работает следующим образом:
к примеру, Коко успевает съесть за час все бананы из кучи, кроме 1. На этот 1 банан в любом случае нужен 1 дополнительный час, в течение которого Коко съест только его, не начиная новую кучу. То есть нам требуется округление вверх (целочисленное деление в питоне по умолчанию округляет вниз).
Нужно добавить такое кол-во бананов, чтобы и получить необходимый дополнительный час при наличии остатка, и корректно обработать числа без остатка. Значение, которое сработает в любом из двух случаев - это прибавка k - 1 (максимальное значение, не создающее дополнительные часы, когда у нас нет остатка).
Предположим, p = 11, а k = 5. При простом делении p // k получили бы 2, и один банан остался бы без учёта при подсчёте часов. Но если пользуемся формулой (11 + 5 -1) // 5, получаем 3 часа, которые потребуются, чтобы съесть 11 бананов со скоростью 5 бананов/час.
А если бы в другой куче было 15 бананов, которые делятся на 5 без остатка, формула тоже сработала бы: (15 + 5 - 1) // 5 = 3 (всё те же 3 часа, так как целочисленное деление просто отбросит остаток 4);
- Сдвигаем границы поиска:
Если Коко успевает съесть все бананы: запоминаем k как текущего кандидата, обновляя res, и сдвигаем правую границу поиска влево (пытаемся найти ещё меньшую скорость);
Если не успевает: сдвигаем левую границу вправо, так как нужно искать среди больших скоростей;
Возвращаем минимальную возможную скорость, при которой Коко сможет съесть все бананы, уложившись в h часов.
Сложность
O(1) - по памяти (храним только переменные, не создавая дополнительных структур данных)
Код
def minEatingSpeed(self, piles: List[int], h: int) -> int:
l, r = 1, max(piles)
res = r
while l <= r:
k = (l + r) // 2
hours = 0
for p in piles:
hours += (p + k - 1) // k
if hours <= h:
res = min(res, k)
r = k - 1
else:
l = k + 1
return res
@algoses
❤8
Задача с собеседования в Zynga
Дан массив целых чисел asteroids, представляющий астероиды, расположенные в ряд. Индексы элементов массива соответствуют их относительному положению в пространстве.
Для каждого астероида абсолютное значение (модуль) определяет его размер, а знак - направление движения (положительный означает движение вправо, отрицательный - влево). Все астероиды движутся с одинаковой скоростью.
Определите состояние астероидов после всех столкновений. Если два астероида встречаются, взрывается меньший из них. Если их размеры равны, взрываются оба. Два астероида, движущиеся в одном направлении, никогда не встретятся.
Пример 1:
Input: asteroids = [5,10,-5]
Output: [5,10]
Объяснение: 10 и -5 сталкиваются, в результате остаётся 10. 5 и 10 никогда не столкнутся.
Пример 2:
Input: asteroids = [8,-8]
Output: []
Объяснение: 8 и -8 сталкиваются, взрывая друг друга.
Пример 3:
Input: asteroids = [10,2,-5]
Output: [10]
Объяснение: 2 и -5 сталкиваются, в результате остаётся -5. 10 и -5 сталкиваются, остаётся 10.
Пример 4:
Input: asteroids = [3,5,-6,2,-1,4]
Output: [-6,2,4]
Объяснение: Астероид -6 взрывает астероиды 5 и 3, затем продолжает двигаться влево. С другой стороны, астероид 2 взрывает астероид -1 и продолжает двигаться вправо, не сталкиваясь с астероидом 4.
Ограничения:
2 <= asteroids.length <= 10⁴
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Столкновение происходит между соседними астероидами (они могут не быть соседями в изначальном массиве, а стать ими после взрывов), летящими в разные стороны (с противоположными знаками). И только в том случае, когда астероид, летящий вправо, находится левее астероида, летящего влево. Иначе астероиды просто разлетятся в разные стороны и никогда не столкнутся. Так произойдёт, например, при asteroids = [-1, -2, 1, 2]. Однако при [1, -1, 2, -2], они взорвут друг друга, и стек окажется пуст.
- Используем стек для хранения астероидов, которые ещё не столкнулись или пережили столкновение. Стек удобен тем, что позволяет проверять верхний астероид (последний добавленный) на столкновение с левым. Верхний - ближайший справа к левому, при его взрыве левый продолжит движение и проверит следующий (добавленный раньше) астероид в стеке, который автоматически станет новым ближайшим.
- Симулируем движение:
В цикле while (while позволяет проверять левый астероид на столкновение с несколькими правыми подряд) имитируем столкновение: стек должен быть не пуст, текущий астероид должен лететь влево, а верхний астероид в стеке - лететь вправо:
Чтобы определить, какой взорвётся, высчитываем разницу между их размерами посредством суммирования. Так как мы зашли в цикл while, текущий a всегда отрицательный, а stack[-1] - положительный, знак diff покажет, какой астероид больше:
- если diff отрицательный - левый больше => правый взрывается => удаляем его из стека => левый остаётся и продолжает цикл while, проверяя следующий астероид в стеке;
- если diff положительный - правый больше => левый взрывается, правый остаётся в стеке => обнуляем значение левого, цикл while завершается, так как условие a < 0 больше не выполняется;
- если значение diff равно нулю - размеры равны => оба взрываются => обнуляем левый и удаляем правый из стека, цикл завершается.
- Если после столкновений текущий астероид не равен 0, значит, он выжил. Добавляем его в стек.
Сложность
O(n) - по времени (проходим по массиву 1 раз, каждый астероид может быть добавлен в стек или удалён из него не более 1 раза)
O(n) - по памяти (в худшем случае храним в стеке все элементы массива)
Код
class Solution:
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
stack = []
for a in asteroids:
while stack and a < 0 < stack[-1]:
diff = a + stack[-1]
if diff < 0:
stack.pop()
elif diff > 0:
a = 0
else:
a = 0
stack.pop()
if a:
stack.append(a)
return stack
@algoses
Дан массив целых чисел asteroids, представляющий астероиды, расположенные в ряд. Индексы элементов массива соответствуют их относительному положению в пространстве.
Для каждого астероида абсолютное значение (модуль) определяет его размер, а знак - направление движения (положительный означает движение вправо, отрицательный - влево). Все астероиды движутся с одинаковой скоростью.
Определите состояние астероидов после всех столкновений. Если два астероида встречаются, взрывается меньший из них. Если их размеры равны, взрываются оба. Два астероида, движущиеся в одном направлении, никогда не встретятся.
Пример 1:
Input: asteroids = [5,10,-5]
Output: [5,10]
Объяснение: 10 и -5 сталкиваются, в результате остаётся 10. 5 и 10 никогда не столкнутся.
Пример 2:
Input: asteroids = [8,-8]
Output: []
Объяснение: 8 и -8 сталкиваются, взрывая друг друга.
Пример 3:
Input: asteroids = [10,2,-5]
Output: [10]
Объяснение: 2 и -5 сталкиваются, в результате остаётся -5. 10 и -5 сталкиваются, остаётся 10.
Пример 4:
Input: asteroids = [3,5,-6,2,-1,4]
Output: [-6,2,4]
Объяснение: Астероид -6 взрывает астероиды 5 и 3, затем продолжает двигаться влево. С другой стороны, астероид 2 взрывает астероид -1 и продолжает двигаться вправо, не сталкиваясь с астероидом 4.
Ограничения:
2 <= asteroids.length <= 10⁴
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
- Используем стек для хранения астероидов, которые ещё не столкнулись или пережили столкновение. Стек удобен тем, что позволяет проверять верхний астероид (последний добавленный) на столкновение с левым. Верхний - ближайший справа к левому, при его взрыве левый продолжит движение и проверит следующий (добавленный раньше) астероид в стеке, который автоматически станет новым ближайшим.
- Симулируем движение:
В цикле while (while позволяет проверять левый астероид на столкновение с несколькими правыми подряд) имитируем столкновение: стек должен быть не пуст, текущий астероид должен лететь влево, а верхний астероид в стеке - лететь вправо:
Чтобы определить, какой взорвётся, высчитываем разницу между их размерами посредством суммирования. Так как мы зашли в цикл while, текущий a всегда отрицательный, а stack[-1] - положительный, знак diff покажет, какой астероид больше:
- если diff отрицательный - левый больше => правый взрывается => удаляем его из стека => левый остаётся и продолжает цикл while, проверяя следующий астероид в стеке;
- если diff положительный - правый больше => левый взрывается, правый остаётся в стеке => обнуляем значение левого, цикл while завершается, так как условие a < 0 больше не выполняется;
- если значение diff равно нулю - размеры равны => оба взрываются => обнуляем левый и удаляем правый из стека, цикл завершается.
- Если после столкновений текущий астероид не равен 0, значит, он выжил. Добавляем его в стек.
Сложность
O(n) - по памяти (в худшем случае храним в стеке все элементы массива)
Код
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
stack = []
for a in asteroids:
while stack and a < 0 < stack[-1]:
diff = a + stack[-1]
if diff < 0:
stack.pop()
elif diff > 0:
a = 0
else:
a = 0
stack.pop()
if a:
stack.append(a)
return stack
@algoses
❤7🔥4
Задача с собеседования в eBay
Даны строка s и словарь из строк wordDict.
Верните true, если s можно разбить на последовательность из одного или нескольких слов из словаря, разделённых пробелами.
Обратите внимание: одно и то же слово в словаре может использоваться при разбиении многократно.
Пример 1:
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Вернётся true, так как строку "leetcode" можно разбить как "leet code".
Пример 2:
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Вернётся true, так как строку "applepenapple" можно разбить как "apple pen apple" (слово из словаря может использоваться повторно).
Пример 3:
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
Ограничения:
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s и wordDict[i] состоят только из строчных английских букв.
Все строки в wordDict уникальные.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Задача помечена тегом "Dynamic Programming": есть оптимальная подструктура и перекрывающиеся подзадачи. Если знаем, что хвост строки после некоторой позиции можно разбить на слова из словаря, то, чтобы расширить это разбиение влево, достаточно найти слово, заканчивающееся на этой позиции. Один и тот же срез строки может проверяться несколько раз - кэшируя ответ для каждой позиции, избежим повторных вычислений.
Используем итеративный dp:
Превращаем список wordDict во множество wordSet для ускорения поиска за O(L), где L - длина слова.
Создаём таблицу, где dp[i] = True, если суффикс s[i:] можно разбить. Размер: (n+1), где n - длина s (+1, чтобы учесть позицию после последнего символа и убедиться, что строка разбита полностью). По умолчанию заполняем False, так как ещё ничего не нашли.
Базовый случай: dp[n] = True. Пустой остаток корректен, цепочка слов доходит до конца s.
Суть алгоритма: перебираем позиции в s, проверяя срезы на присутствие в wordSet и возможность их "стыковки" с уже разобранными срезами в правой части.
Заполняем таблицу:
i - позиция начала потенциального слова; идёт по s справа налево.
j - конец потенциального слова, которое начинается в i; идёт вправо от i.
s[i:j+1] - текущий проверяемый срез.
В начале внутреннего цикла: i = j, с каждой следующей итерацией j увеличивается на 1, а длина подстроки растёт, пока не достигнет maxLength (длина самого длинного слова в словаре) или конца строки.
За проверку валидности среза отвечают два условия:
if dp[j+1] - разбивается ли остаток строки справа от текущего среза. Движемся справа налево, поэтому это значение уже вычислено.
Это условие не позволяет попасть в тупик, если слово есть в словаре, но не стыкуется корректно с хвостом (например, в строке "catsandog" на какой-то итерации найдём срез "and", но он не будет стыковаться с остатком строки, так как в словаре нет слова "og");
if s[i:j+1] in wordSet - наличие слова в словаре.
Порядок условий важен за счёт оптимизации "коротким замыканием": если остаток строки справа не разбивается корректно - новый срез не создаётся, а хэш не вычисляется.
Если оба условия удовлетворяются: dp[i] = True, цикл прерывается, так как нам достаточно найти один подходящий путь.
Возвращаем dp[0] - ответ для всей строки s[0:].
Сложность
O(N * L^2 + M * L) - время:
M * L - создание wordSet;
N * L^2 - N итераций во внешнем цикле (N - длина s) и до L итераций (ограничен maxLength) во внутреннем цикле:
внутри: создание среза s[i:j+1] за O(L) и вычисление хэша для поиска в wordSet за O(L) => O(L^2).
O(N + M * L) - память (дп массив и хэш-множество M слов длиной до L)
Код
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
wordSet = set(wordDict)
n = len(s)
maxLength = max(len(w) for w in wordDict)
dp = [False] * (n+1)
dp[n] = True
for i in range(n-1, -1, -1):
for j in range(i, min(i+maxLength, n)):
if dp[j+1] and s[i:j+1] in wordSet:
dp[i] = True
break
return dp[0]
@algoses
Даны строка s и словарь из строк wordDict.
Верните true, если s можно разбить на последовательность из одного или нескольких слов из словаря, разделённых пробелами.
Обратите внимание: одно и то же слово в словаре может использоваться при разбиении многократно.
Пример 1:
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Вернётся true, так как строку "leetcode" можно разбить как "leet code".
Пример 2:
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Вернётся true, так как строку "applepenapple" можно разбить как "apple pen apple" (слово из словаря может использоваться повторно).
Пример 3:
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
Ограничения:
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s и wordDict[i] состоят только из строчных английских букв.
Все строки в wordDict уникальные.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Используем итеративный dp:
Превращаем список wordDict во множество wordSet для ускорения поиска за O(L), где L - длина слова.
Создаём таблицу, где dp[i] = True, если суффикс s[i:] можно разбить. Размер: (n+1), где n - длина s (+1, чтобы учесть позицию после последнего символа и убедиться, что строка разбита полностью). По умолчанию заполняем False, так как ещё ничего не нашли.
Базовый случай: dp[n] = True. Пустой остаток корректен, цепочка слов доходит до конца s.
Суть алгоритма: перебираем позиции в s, проверяя срезы на присутствие в wordSet и возможность их "стыковки" с уже разобранными срезами в правой части.
Заполняем таблицу:
i - позиция начала потенциального слова; идёт по s справа налево.
j - конец потенциального слова, которое начинается в i; идёт вправо от i.
s[i:j+1] - текущий проверяемый срез.
В начале внутреннего цикла: i = j, с каждой следующей итерацией j увеличивается на 1, а длина подстроки растёт, пока не достигнет maxLength (длина самого длинного слова в словаре) или конца строки.
За проверку валидности среза отвечают два условия:
if dp[j+1] - разбивается ли остаток строки справа от текущего среза. Движемся справа налево, поэтому это значение уже вычислено.
Это условие не позволяет попасть в тупик, если слово есть в словаре, но не стыкуется корректно с хвостом (например, в строке "catsandog" на какой-то итерации найдём срез "and", но он не будет стыковаться с остатком строки, так как в словаре нет слова "og");
if s[i:j+1] in wordSet - наличие слова в словаре.
Порядок условий важен за счёт оптимизации "коротким замыканием": если остаток строки справа не разбивается корректно - новый срез не создаётся, а хэш не вычисляется.
Если оба условия удовлетворяются: dp[i] = True, цикл прерывается, так как нам достаточно найти один подходящий путь.
Возвращаем dp[0] - ответ для всей строки s[0:].
Сложность
M * L - создание wordSet;
N * L^2 - N итераций во внешнем цикле (N - длина s) и до L итераций (ограничен maxLength) во внутреннем цикле:
внутри: создание среза s[i:j+1] за O(L) и вычисление хэша для поиска в wordSet за O(L) => O(L^2).
O(N + M * L) - память (дп массив и хэш-множество M слов длиной до L)
Код
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
wordSet = set(wordDict)
n = len(s)
maxLength = max(len(w) for w in wordDict)
dp = [False] * (n+1)
dp[n] = True
for i in range(n-1, -1, -1):
for j in range(i, min(i+maxLength, n)):
if dp[j+1] and s[i:j+1] in wordSet:
dp[i] = True
break
return dp[0]
@algoses
❤4🔥2
Задача с собеседования в eBay
Дан массив целых чисел nums, сдвиньте его вправо на k шагов, где k - неотрицательное число.
Follow up:
- Постарайтесь придумать, как можно больше решений. Существует, по крайней мере, три разных способа решения этой задачи;
- Можно ли решить задачу in-place, используя O(1) дополнительной памяти?
Пример 1:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
сдвиг на один шаг вправо: [7, 1, 2, 3, 4, 5, 6]
сдвиг на два шага вправо: [6, 7, 1, 2, 3, 4, 5]
сдвиг на три шага вправо: [5, 6, 7, 1, 2, 3, 4]
Пример 2:
Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
сдвиг на один шаг вправо: [99, -1, -100, 3]
сдвиг на два шага вправо: [3, 99, -1, -100]
Ограничения:
1 <= nums.length <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1
0 <= k <= 10⁵
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Разберём один из способов решения этой задачи in-place - тройной разворот + метод двух указателей:
Заметим, что массив nums как бы состоит из двух частей. Первая часть - числа, которые стоят в начале, но должны переместиться в конец, вторая часть - числа, которые находятся в конце, но должны уйти в начало.
Алгоритм решения заключается в трёх разворотах.
Перед началом разворотов выполняем k = k % len(nums) - это гарантирует корректный ответ, если k больше или равен длине массива. Так как сдвиг на len(nums) шагов оставляет массив неизменным, отбрасываем "полные круги" и выполняем только эффективные сдвиги - остаток от деления k на длину массива.
Для визуализации рассмотрим работу алгоритма на примере 1:
1. Переворачиваем первую часть: от нулевого индекса до len(nums) - k - 1 (так как кол-во эл-тов, которые должны переместиться в начало, равно k).
[1,2,3,4,5,6,7] -> [4,3,2,1,5,6,7]
2. Переворачиваем вторую часть: от len(nums) - k до последнего эл-та массива.
[4,3,2,1,5,6,7] -> [4,3,2,1,7,6,5]
3. И теперь переворачиваем весь массив целиком, чтобы разместить числа в правильном порядке.
[4,3,2,1,7,6,5] -> [5,6,7,1,2,3,4]
Чтобы избежать дублирования кода, создаём отдельный метод для реверсирования эл-тов через метод двух указателей:
Пока l < r:
- меняем местами число под индексом l с числом под индексом r;
- двигаем левый указатель вправо, а правый указатель - влево.
Этот метод отрабатывает в каждом из трёх разворотов.
Делитесь вашим вариантом решения в комментариях!
Сложность
O(n) - время (где n - длина массива)
O(1) - память (изменяем исходный массив без создания дополнительной структуры данных (in-place), используем две переменные: l и r)
Код
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
k = k % len(nums)
self.reverse(nums, 0, len(nums) - k - 1)
self.reverse(nums, len(nums) - k, len(nums) - 1)
self.reverse(nums, 0, len(nums) - 1)
def reverse(self, nums: List[int], l: int, r: int) -> None:
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 1
@algoses
Дан массив целых чисел nums, сдвиньте его вправо на k шагов, где k - неотрицательное число.
Follow up:
- Постарайтесь придумать, как можно больше решений. Существует, по крайней мере, три разных способа решения этой задачи;
- Можно ли решить задачу in-place, используя O(1) дополнительной памяти?
Пример 1:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
сдвиг на один шаг вправо: [7, 1, 2, 3, 4, 5, 6]
сдвиг на два шага вправо: [6, 7, 1, 2, 3, 4, 5]
сдвиг на три шага вправо: [5, 6, 7, 1, 2, 3, 4]
Пример 2:
Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
сдвиг на один шаг вправо: [99, -1, -100, 3]
сдвиг на два шага вправо: [3, 99, -1, -100]
Ограничения:
1 <= nums.length <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1
0 <= k <= 10⁵
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Заметим, что массив nums как бы состоит из двух частей. Первая часть - числа, которые стоят в начале, но должны переместиться в конец, вторая часть - числа, которые находятся в конце, но должны уйти в начало.
Алгоритм решения заключается в трёх разворотах.
Перед началом разворотов выполняем k = k % len(nums) - это гарантирует корректный ответ, если k больше или равен длине массива. Так как сдвиг на len(nums) шагов оставляет массив неизменным, отбрасываем "полные круги" и выполняем только эффективные сдвиги - остаток от деления k на длину массива.
Для визуализации рассмотрим работу алгоритма на примере 1:
1. Переворачиваем первую часть: от нулевого индекса до len(nums) - k - 1 (так как кол-во эл-тов, которые должны переместиться в начало, равно k).
[1,2,3,4,5,6,7] -> [4,3,2,1,5,6,7]
2. Переворачиваем вторую часть: от len(nums) - k до последнего эл-та массива.
[4,3,2,1,5,6,7] -> [4,3,2,1,7,6,5]
3. И теперь переворачиваем весь массив целиком, чтобы разместить числа в правильном порядке.
[4,3,2,1,7,6,5] -> [5,6,7,1,2,3,4]
Чтобы избежать дублирования кода, создаём отдельный метод для реверсирования эл-тов через метод двух указателей:
Пока l < r:
- меняем местами число под индексом l с числом под индексом r;
- двигаем левый указатель вправо, а правый указатель - влево.
Этот метод отрабатывает в каждом из трёх разворотов.
Сложность
O(1) - память (изменяем исходный массив без создания дополнительной структуры данных (in-place), используем две переменные: l и r)
Код
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
k = k % len(nums)
self.reverse(nums, 0, len(nums) - k - 1)
self.reverse(nums, len(nums) - k, len(nums) - 1)
self.reverse(nums, 0, len(nums) - 1)
def reverse(self, nums: List[int], l: int, r: int) -> None:
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 1
@algoses
🔥7❤1
В новом ролике обсудим современное рабство: стоит ли идти в айти галеры ради первого опыта работы на примере Астона! Осторожно, факты вас шокируют! Смотрим! Смотрим!
https://www.youtube.com/watch?v=y7QwkvxSzbc
https://www.youtube.com/watch?v=y7QwkvxSzbc
YouTube
Айти галеры: изи опыт или рабство? На примере Астон
Что такое Астон и почему его называют «галерой»? Как попасть в IT, подписав кабальный договор, и почему здесь сеньор будет получать зарплату джуна? Разбираем на реальном примере, как работает эта схема и какой ценой получается бесценный опыт в айти, а главное…
🔥3
Задача с собеседования в eBay
Дан массив nums, состоящий из различных целых чисел. Верните все возможные перестановки этого массива. Вы можете вернуть ответ в любом порядке.
Пример 1:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Пример 2:
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Пример 3:
Input: nums = [1]
Output: [[1]]
Ограничения:
1 <= nums.length <= 6
-10 <= nums[i] <= 10
Все числа в nums уникальны.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Так как необходимо вернуть все возможные перестановки элементов массива, используем backtracking - алгоритм поиска с возвратом.
Суть алгоритма: на каждом шаге добавляем элемент и строим полную правильную перестановку, после её сохранения последовательно возвращаемся по стеку вызовов до последней точки выбора и исследуем другие ветки из этой точки.
Создаём два списка:
res - для хранения найденных корректных перестановок;
permutation - временный список для "собирания" текущей перестановки.
Чтобы оптимизировать отслеживание уже использованных эл-тов, создаём множество used (проверка наличия эл-та за O(1) вместо O(n) при поиске по списку).
Запускаем рекурсивную функцию backtrack():
Базовый случай: если длина текущей перестановки достигла n (длина массива nums), значит: мы использовали все эл-ты -> перестановка готова -> сохраняем копию текущей перестановки в res (копия нужна, чтобы последующие изменения не затронули уже сохранённый ответ) и завершаем текущий вызов рекурсии, откатываясь назад.
Рекурсивное ветвление: перебираем все возможные эл-ты, которые можно добавить следующими.
Для каждого допустимого выбора (эл-та, которого ещё нет в текущей перестановке):
- добавляем значение в used ("помечаем" эл-т как использованный) и permutation (добавляет эл-т в текущую перестановку);
- вызываем рекурсию для выбора следующего значения;
- удаляем последнее добавленное значение из permutation (для возврата к развилке и исследованию другой ветки перестановки) и used (для возможности использования эл-та в других ветках).
Функция завершается, когда полностью исследовано дерево возможных перестановок.
Для этой задачи существует альтернативное решение через перестановки элементов в исходном массиве (in-place swapping). Делитесь им в комментариях!
Сложность
O(n*n!) - по времени (так как существует n! перестановок для массива размера n, каждая из них копируется в список за O(n))
O(n) - по памяти (стек рекурсии глубиной n, множество used размера n и список permutation размера n)
Код
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
res, permutation = [], []
used = set()
def backtrack():
if len(permutation) == n:
res.append(permutation[:])
return
for i in nums:
if i not in used:
used.add(i)
permutation.append(i)
backtrack()
permutation.pop()
used.remove(i)
backtrack()
return res
@algoses
Дан массив nums, состоящий из различных целых чисел. Верните все возможные перестановки этого массива. Вы можете вернуть ответ в любом порядке.
Пример 1:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Пример 2:
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Пример 3:
Input: nums = [1]
Output: [[1]]
Ограничения:
1 <= nums.length <= 6
-10 <= nums[i] <= 10
Все числа в nums уникальны.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Суть алгоритма: на каждом шаге добавляем элемент и строим полную правильную перестановку, после её сохранения последовательно возвращаемся по стеку вызовов до последней точки выбора и исследуем другие ветки из этой точки.
Создаём два списка:
res - для хранения найденных корректных перестановок;
permutation - временный список для "собирания" текущей перестановки.
Чтобы оптимизировать отслеживание уже использованных эл-тов, создаём множество used (проверка наличия эл-та за O(1) вместо O(n) при поиске по списку).
Запускаем рекурсивную функцию backtrack():
Базовый случай: если длина текущей перестановки достигла n (длина массива nums), значит: мы использовали все эл-ты -> перестановка готова -> сохраняем копию текущей перестановки в res (копия нужна, чтобы последующие изменения не затронули уже сохранённый ответ) и завершаем текущий вызов рекурсии, откатываясь назад.
Рекурсивное ветвление: перебираем все возможные эл-ты, которые можно добавить следующими.
Для каждого допустимого выбора (эл-та, которого ещё нет в текущей перестановке):
- добавляем значение в used ("помечаем" эл-т как использованный) и permutation (добавляет эл-т в текущую перестановку);
- вызываем рекурсию для выбора следующего значения;
- удаляем последнее добавленное значение из permutation (для возврата к развилке и исследованию другой ветки перестановки) и used (для возможности использования эл-та в других ветках).
Функция завершается, когда полностью исследовано дерево возможных перестановок.
Для этой задачи существует альтернативное решение через перестановки элементов в исходном массиве (in-place swapping). Делитесь им в комментариях!
Сложность
O(n) - по памяти (стек рекурсии глубиной n, множество used размера n и список permutation размера n)
Код
def permute(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
res, permutation = [], []
used = set()
def backtrack():
if len(permutation) == n:
res.append(permutation[:])
return
for i in nums:
if i not in used:
used.add(i)
permutation.append(i)
backtrack()
permutation.pop()
used.remove(i)
backtrack()
return res
@algoses
🔥2🤔1
Задача с собеседования в Josh Technology Group
Дан массив целых чисел temperatures, представляющий ежедневные значения температуры. Верните массив answer, где answer[i] - это количество дней, которое нужно подождать после i-ого, чтобы наступил день с более высокой температурой. Если нет будущего дня, для которого это возможно, вместо этого сохраните answer[i] == 0.
Пример 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Пример 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Пример 3:
Input: temperatures = [30,60,90]
Output: [1,1,0]
Ограничения:
1 <= temperatures.length <= 10⁵
30 <= temperatures[i] <= 100
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
При наивном решении мы бы итерировались по массиву для каждого дня в поисках более тёплого c асимптотикой O(n²).
Но мы видим паттерн - поиск ближайшего большего/меньшего эл-та, поэтому используем монотонный стек (стек, элементы которого хранятся в строго возрастающем или строго убывающем порядке).
В данном случае стек будет монотонно убывающим. При добавлении нового эл-та алгоритм будет сравнивать его с вершиной стека:
- Пока текущий эл-т больше верхнего эл-та стека (stack[-1][0]): достаём верхний элемент, вычисляем ответ для него (через разницу между индексами текущего эл-та и эл-та из стека) и удаляем эл-т из стека.
Кладём текущий эл-т в стек.
Разберём более подробно:
Создаём:
- стек для хранения пар (температура, индекс) в монотонно убывающем порядке;
- массив answer длиной n, равной длине входящего массива. Заполняем его нулями.
Итерируемся по массиву температур:
Пока стек не пуст и в нём есть дни холоднее текущего:
- достаём значение и индекс более холодного дня, удаляя его из стека;
- вычисляем разницу между индексом текущего дня и индексом более холодного дня - таким образом, узнаем кол-во дней, которые должны пройти между ними. Записываем разницу в массив answer по индексу более холодного дня (answer[stack_i]).
После выхода из цикла while или непопадания в него: добавляем текущий день в стек для последующего сравнения с другими значениями.
В конце возвращаем заполненный массив answer.
Сложность
O(n) - по времени (каждый эл-т добавляется в стек только 1 раз и может быть удалён только 1 раз)
O(n) - по памяти (в худшем случае в стек придётся добавить все элементы входного массива длиной n)
Код
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
stack = []
answer = [0] * n
for i, temp in enumerate(temperatures):
while stack and stack[-1][0] < temp:
stack_temp, stack_i = stack.pop()
answer[stack_i] = i - stack_i
stack.append((temp, i))
return answer
@algoses
Дан массив целых чисел temperatures, представляющий ежедневные значения температуры. Верните массив answer, где answer[i] - это количество дней, которое нужно подождать после i-ого, чтобы наступил день с более высокой температурой. Если нет будущего дня, для которого это возможно, вместо этого сохраните answer[i] == 0.
Пример 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Пример 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Пример 3:
Input: temperatures = [30,60,90]
Output: [1,1,0]
Ограничения:
1 <= temperatures.length <= 10⁵
30 <= temperatures[i] <= 100
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Но мы видим паттерн - поиск ближайшего большего/меньшего эл-та, поэтому используем монотонный стек (стек, элементы которого хранятся в строго возрастающем или строго убывающем порядке).
В данном случае стек будет монотонно убывающим. При добавлении нового эл-та алгоритм будет сравнивать его с вершиной стека:
- Пока текущий эл-т больше верхнего эл-та стека (stack[-1][0]): достаём верхний элемент, вычисляем ответ для него (через разницу между индексами текущего эл-та и эл-та из стека) и удаляем эл-т из стека.
Кладём текущий эл-т в стек.
Разберём более подробно:
Создаём:
- стек для хранения пар (температура, индекс) в монотонно убывающем порядке;
- массив answer длиной n, равной длине входящего массива. Заполняем его нулями.
Итерируемся по массиву температур:
Пока стек не пуст и в нём есть дни холоднее текущего:
- достаём значение и индекс более холодного дня, удаляя его из стека;
- вычисляем разницу между индексом текущего дня и индексом более холодного дня - таким образом, узнаем кол-во дней, которые должны пройти между ними. Записываем разницу в массив answer по индексу более холодного дня (answer[stack_i]).
После выхода из цикла while или непопадания в него: добавляем текущий день в стек для последующего сравнения с другими значениями.
В конце возвращаем заполненный массив answer.
Сложность
O(n) - по памяти (в худшем случае в стек придётся добавить все элементы входного массива длиной n)
Код
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
stack = []
answer = [0] * n
for i, temp in enumerate(temperatures):
while stack and stack[-1][0] < temp:
stack_temp, stack_i = stack.pop()
answer[stack_i] = i - stack_i
stack.append((temp, i))
return answer
@algoses
❤6🔥6
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
Хотите учить алгоритмы, но не знаете Python?
Товарищи, алгоритмы сами по себе не самые простые. А если параллельно с решением задачи приходится гуглить, как написать цикл for, подготовка превращается в отдельный вид страдания😔
Поэтому запускаем бесплатный открытый курс «Python для алгоритмов».
С 14 по 19 июля разберём базу Python, которая нужна именно для решения алгоритмических задач.
Почему Python? Именно его чаще всего выбирают для решения задач на алгоритмических собеседованиях и технических отборах. У языка простой синтаксис, поэтому на собесе можно сосредоточиться на решении задачи, а не на борьбе с кодом.
За 6 дней разберём условия, циклы, функции, строки и основные структуры данных. Научимся читать код, работать с вводом и выводом и переводить уже придуманное решение задачи на Python.
Задача курса — построить фундамент, с которым вы сможете полноценно начать изучать алгоритмы и структуры данных.
Курс подойдёт, если вы:
➡️ никогда раньше не программировали
➡️ когда-то учили Python, но забыли базовый синтаксис
➡️ планируете проходить отборы на стажировки, в ШАД, Академию аналитиков Авито и другие школы
🏆А самых сильных участников ждёт отдельный бонус. Лучшим подарим полный курс по алгоритмам
📌 Ссылка на курс в нашем боте - @Postupashkianalitycsbot
Первые материалы уже выложены!
Товарищи, алгоритмы сами по себе не самые простые. А если параллельно с решением задачи приходится гуглить, как написать цикл for, подготовка превращается в отдельный вид страдания
Поэтому запускаем бесплатный открытый курс «Python для алгоритмов».
С 14 по 19 июля разберём базу Python, которая нужна именно для решения алгоритмических задач.
Почему Python? Именно его чаще всего выбирают для решения задач на алгоритмических собеседованиях и технических отборах. У языка простой синтаксис, поэтому на собесе можно сосредоточиться на решении задачи, а не на борьбе с кодом.
За 6 дней разберём условия, циклы, функции, строки и основные структуры данных. Научимся читать код, работать с вводом и выводом и переводить уже придуманное решение задачи на Python.
Задача курса — построить фундамент, с которым вы сможете полноценно начать изучать алгоритмы и структуры данных.
Курс подойдёт, если вы:
🏆А самых сильных участников ждёт отдельный бонус. Лучшим подарим полный курс по алгоритмам
Первые материалы уже выложены!
Please open Telegram to view this post
VIEW IN TELEGRAM
Please open Telegram to view this post
VIEW IN TELEGRAM
❤2
Товарищи, Поступашкам нужны контент мейкеры. Если вы творческая личность, интересующейся бэкендом, дата сайнс, аналитикой, алгоритмами и так далее, вам нравится писать посты/ придумывать идеи для контента, то обязательно пишите @vice22821. Оплата сдельная, ориентировочно за один пост от 2 тыс до 15 тыс рублей.
Обязательно делитесь с ребятами, которым это может быть интересно.
Обязательно делитесь с ребятами, которым это может быть интересно.
❤1
Задача с собеседования в Josh Technology Group
Дан целочисленный массив nums, индексированный с нуля, длины n и целое число target. Верните количество пар (i, j), где 0 <= i < j < n и nums[i] + nums[j] < target.
Пример 1:
Input: nums = [-1,1,2,3,1], target = 2
Output: 3
Explanation: Существует 3 пары индексов, удовлетворяющих условию:
- (0, 1), так как 0 < 1 и nums[0] + nums[1] = 0 < target
- (0, 2), так как 0 < 2 и nums[0] + nums[2] = 1 < target
- (0, 4), так как 0 < 4 и nums[0] + nums[4] = 0 < target
Обратите внимание, что пара (0, 3) не учитывается, так как сумма nums[0] и nums[3] не является строго меньшей target.
Пример 2:
Input: nums = [-6,2,5,-2,-7,-1,3], target = -2
Output: 10
Explanation: Существует 10 пар индексов, удовлетворяющих условию:
- (0, 1), так как 0 < 1 и nums[0] + nums[1] = -4 < target
- (0, 3), так как 0 < 3 и nums[0] + nums[3] = -8 < target
- (0, 4), так как 0 < 4 и nums[0] + nums[4] = -13 < target
- (0, 5), так как 0 < 5 и nums[0] + nums[5] = -7 < target
- (0, 6), так как 0 < 6 и nums[0] + nums[6] = -3 < target
- (1, 4), так как 1 < 4 и nums[1] + nums[4] = -5 < target
- (3, 4), так как 3 < 4 и nums[3] + nums[4] = -9 < target
- (3, 5), так как 3 < 5 и nums[3] + nums[5] = -3 < target
- (4, 5), так как 4 < 5 и nums[4] + nums[5] = -8 < target
- (4, 6), так как 4 < 6 и nums[4] + nums[6] = -4 < target
Ограничения:
1 <= nums.length == n <= 50
-50 <= nums[i], target <= 50
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
При наивном решении мы бы проходили по вложенному циклу за O(n²).
Но в данном случае заметим, что для удовлетворения условию nums[i] + nums[j] < target важны не позиции эл-в в массиве, а только их значения => мы можем отсортировать массив в восходящем порядке, и для каждого текущего nums[i] все подходящие nums[j] будут идти подряд от начала до некоторого индекса (образовывать префикс), так как если nums[i] + nums[j] < target, то nums[i] + nums[k] < target для любого k < j.
Логично использовать алгоритм двух указателей и двигать указатели навстречу друг другу, проверяя сумму nums[left] и nums[right]. К count (счетчик пар) добавляется не одна пара, а целая группа пар (count += right - left), так как nums[left] - самый маленький текущий эл-т, и, если его сумма с самым большим текущим эл-м (nums[right]) меньше target => сумма nums[left] и любого эл-та между left и right будет также меньше target.
Переменные:
left - индекс первого эл-та в массиве;
right - индекс последнего эл-та;
count - счётчик пар, удовлетворяющих условию.
Пока left меньше right, проходим по массиву, сужая окно между указателями:
Сравниваем сумму текущей пары эл-в с target:
Если меньше:
- добавляем к count значение right - left. Таким образом, все пары с текущим left учтены;
- сдвигаем left вправо.
Если сумма больше или равна target:
- сдвигаем right влево.
В конце возвращаем count.
Сложность
O(n log n) - по времени (сортируем массив, где n - кол-во элементов в массиве; обход двумя указателями - за O(n), так как проходимся по каждому элементу единожды)
O(n) - по памяти (для сортировки на питоне)
Код
class Solution:
def countPairs(self, nums: List[int], target: int) -> int:
nums.sort()
count = 0
left = 0
right = len(nums) - 1
while left < right:
if nums[left] + nums[right] < target:
count += right - left
left += 1
else:
right -= 1
return count
@algoses
Дан целочисленный массив nums, индексированный с нуля, длины n и целое число target. Верните количество пар (i, j), где 0 <= i < j < n и nums[i] + nums[j] < target.
Пример 1:
Input: nums = [-1,1,2,3,1], target = 2
Output: 3
Explanation: Существует 3 пары индексов, удовлетворяющих условию:
- (0, 1), так как 0 < 1 и nums[0] + nums[1] = 0 < target
- (0, 2), так как 0 < 2 и nums[0] + nums[2] = 1 < target
- (0, 4), так как 0 < 4 и nums[0] + nums[4] = 0 < target
Обратите внимание, что пара (0, 3) не учитывается, так как сумма nums[0] и nums[3] не является строго меньшей target.
Пример 2:
Input: nums = [-6,2,5,-2,-7,-1,3], target = -2
Output: 10
Explanation: Существует 10 пар индексов, удовлетворяющих условию:
- (0, 1), так как 0 < 1 и nums[0] + nums[1] = -4 < target
- (0, 3), так как 0 < 3 и nums[0] + nums[3] = -8 < target
- (0, 4), так как 0 < 4 и nums[0] + nums[4] = -13 < target
- (0, 5), так как 0 < 5 и nums[0] + nums[5] = -7 < target
- (0, 6), так как 0 < 6 и nums[0] + nums[6] = -3 < target
- (1, 4), так как 1 < 4 и nums[1] + nums[4] = -5 < target
- (3, 4), так как 3 < 4 и nums[3] + nums[4] = -9 < target
- (3, 5), так как 3 < 5 и nums[3] + nums[5] = -3 < target
- (4, 5), так как 4 < 5 и nums[4] + nums[5] = -8 < target
- (4, 6), так как 4 < 6 и nums[4] + nums[6] = -4 < target
Ограничения:
1 <= nums.length == n <= 50
-50 <= nums[i], target <= 50
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Но в данном случае заметим, что для удовлетворения условию nums[i] + nums[j] < target важны не позиции эл-в в массиве, а только их значения => мы можем отсортировать массив в восходящем порядке, и для каждого текущего nums[i] все подходящие nums[j] будут идти подряд от начала до некоторого индекса (образовывать префикс), так как если nums[i] + nums[j] < target, то nums[i] + nums[k] < target для любого k < j.
Логично использовать алгоритм двух указателей и двигать указатели навстречу друг другу, проверяя сумму nums[left] и nums[right]. К count (счетчик пар) добавляется не одна пара, а целая группа пар (count += right - left), так как nums[left] - самый маленький текущий эл-т, и, если его сумма с самым большим текущим эл-м (nums[right]) меньше target => сумма nums[left] и любого эл-та между left и right будет также меньше target.
Переменные:
left - индекс первого эл-та в массиве;
right - индекс последнего эл-та;
count - счётчик пар, удовлетворяющих условию.
Пока left меньше right, проходим по массиву, сужая окно между указателями:
Сравниваем сумму текущей пары эл-в с target:
Если меньше:
- добавляем к count значение right - left. Таким образом, все пары с текущим left учтены;
- сдвигаем left вправо.
Если сумма больше или равна target:
- сдвигаем right влево.
В конце возвращаем count.
Сложность
O(n) - по памяти (для сортировки на питоне)
Код
def countPairs(self, nums: List[int], target: int) -> int:
nums.sort()
count = 0
left = 0
right = len(nums) - 1
while left < right:
if nums[left] + nums[right] < target:
count += right - left
left += 1
else:
right -= 1
return count
@algoses
❤4
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
Товарищи, мы обновили линейку СТАРТ и открываем новый набор! 🚀
Мы переработали программы: обновили темы, добавили новые кейсы и вопросы с реальных собеседований, усилили практику и запустили полноценный карьерный блок.
Если раньше упор был только на технические навыки, то теперь на курсе вы также научитесь:
— составлять сильное резюме;
— презентовать свой опыт, даже если коммерческой работы не было;
— искать вакансии и понимать, куда лучше откликаться;
— проходить HR-этапы и уверенно чувствовать себя на всех интервью.
Открываем набор сразу на 4 направления:
- Аналитика
- Алгоритмы
- Backend
- Машинное обучение
📎 Кому подойдет СТАРТ?
Тем, кто:
— готовится к первой работе и хочет получить системную базу;
— уже проходит собеседования, но чувствует пробелы;
— хочет попробовать направление на практике, прежде чем идти глубже;
— хочет за лето прокачаться и выйти на рынок уже с готовым портфолио.
Что будет на курсах?
➡️ Аналитика
Освоим SQL, продуктовые метрики, дашборды и A/B-тесты. В качестве пет-проекта пройдете полный цикл АВ тестирования — от запроса в БД до презентации результатов. Именно так работает аналитик.
➡️ Алгоритмы
Разберем всё, что действительно спрашивают на технических интервью: структуры данных, графы, динамическое программирование, деревья, теория чисел и многое другое. Закроем фундамент для алгособеседований и контестов.
➡️ Backend
Изучим архитектуру приложений, базы данных, Docker, gRPC и современные подходы к разработке. Итоговый пет-проект — полноценный сервис аналитики и прогнозирования цен криптовалют.
➡️ Machine Learning
Метрики качества, классические алгоритмы, бустинг, нейронные сети и Transformer. Пет-проект — система кредитного скоринга. Без искусственных задач вроде «обучи свою LLM», только то, с чем реально сталкивается ML-инженер в начале карьеры.
Участникам курса также доступны:
Курс длится 6 недель. Программа построена так, чтобы успевать осваивать теорию, выполнять домашние задания и постепенно делать пет-проект без перегруза. Все это время рядом преподаватель и куратор, которые помогают разобраться со сложными темами и отвечают на вопросы.
🔊 Подробную программу и стоимость курсов смотрите на сайте
Действует гарантия: прошел курс, выполнил все рекомендации, но не получил оффер — вернем деньги
📌 Для вопросов и записи на курс напишите менеджеру
Мы переработали программы: обновили темы, добавили новые кейсы и вопросы с реальных собеседований, усилили практику и запустили полноценный карьерный блок.
Если раньше упор был только на технические навыки, то теперь на курсе вы также научитесь:
— составлять сильное резюме;
— презентовать свой опыт, даже если коммерческой работы не было;
— искать вакансии и понимать, куда лучше откликаться;
— проходить HR-этапы и уверенно чувствовать себя на всех интервью.
Открываем набор сразу на 4 направления:
- Аналитика
- Алгоритмы
- Backend
- Машинное обучение
Тем, кто:
— готовится к первой работе и хочет получить системную базу;
— уже проходит собеседования, но чувствует пробелы;
— хочет попробовать направление на практике, прежде чем идти глубже;
— хочет за лето прокачаться и выйти на рынок уже с готовым портфолио.
Что будет на курсах?
Освоим SQL, продуктовые метрики, дашборды и A/B-тесты. В качестве пет-проекта пройдете полный цикл АВ тестирования — от запроса в БД до презентации результатов. Именно так работает аналитик.
Разберем всё, что действительно спрашивают на технических интервью: структуры данных, графы, динамическое программирование, деревья, теория чисел и многое другое. Закроем фундамент для алгособеседований и контестов.
Изучим архитектуру приложений, базы данных, Docker, gRPC и современные подходы к разработке. Итоговый пет-проект — полноценный сервис аналитики и прогнозирования цен криптовалют.
Метрики качества, классические алгоритмы, бустинг, нейронные сети и Transformer. Пет-проект — система кредитного скоринга. Без искусственных задач вроде «обучи свою LLM», только то, с чем реально сталкивается ML-инженер в начале карьеры.
Участникам курса также доступны:
🔵 разбор контеста донабора Т-банк, стажировки в Яндекс, Авито буткемп DS (DS только на мл старт);🔵 mock-собеседования с обратной связью;🔵 закрытый банк вопросов с реальных интервью Яндекса, Т-Банка, Ozon, WB, Авито и других компаний;🔵 банк тестовых заданий и задач из бигтеха;🔵 реферальную рекомендацию в бигтех после успешной защиты пет-проекта.
Курс длится 6 недель. Программа построена так, чтобы успевать осваивать теорию, выполнять домашние задания и постепенно делать пет-проект без перегруза. Все это время рядом преподаватель и куратор, которые помогают разобраться со сложными темами и отвечают на вопросы.
Дополнительные скидки:
-500 ₽, если учились уже у нас на других курсах
-500 ₽, если берете с другом
Действует гарантия: прошел курс, выполнил все рекомендации, но не получил оффер — вернем деньги
Please open Telegram to view this post
VIEW IN TELEGRAM
❤1
Задача с собеседования в Blinkit
Дан целочисленный массив nums. Найдите подмассив с наибольшей суммой и верните эту сумму.
Follow up: если вы нашли решение с асимптотикой O(n), попробуйте реализовать ещё одно, используя метод "разделяй и властвуй".
Пример 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: Подмассив [4,-1,2,1] имеет наибольшую сумму, равную 6.
Пример 2:
Input: nums = [1]
Output: 1
Explanation: Подмассив [1] имеет наибольшую сумму, равную 1.
Пример 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: Подмассив [5,4,-1,7,8] имеет наибольшую сумму, равную 23.
Ограничения:
1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение за O(n):
Классический алгоритм для этой задачи - алгоритм Кадана, где для каждого эл-та решаем:
- продлить эл-том текущий подмассив или начать новый подмассив с этого эл-та.
- параллельно обновляем глобальный максимум, если сумма текущего подмассива больше.
Разберём подробнее:
max_sum - глобальный максимум; инициализируем, как float("-inf"), гарантируя, что первый эл-т массива обновит максимум;
cur_sum - текущая сумма подмассива; инициализируем, как 0 (пустой префикс).
Проходим по массиву:
- формула, обновляющая cur_sum, выбирает: начать новый подмассив с текущего эл-та или продлить существующий. Если накопленная сумма отрицательна, значит, любой подмассив, начинающийся до текущего эл-та и идущий дальше, будет иметь сумму меньше, чем если бы он начинался с текущего эл-та => выгодно начать новый подмассив;
- обновляем глобальный максимум, выбирая максимальное значение среди max_sum и cur_sum.
Сложность
O(n) - по времени (проходим по массиву один раз)
O(1) - по памяти (храним две переменные)
Код
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
max_sum = float("-inf")
cur_sum = 0
for num in nums:
cur_sum = max(num, cur_sum + num)
max_sum = max(max_sum, cur_sum)
return max_sum
Подход "разделяй и властвуй":
Идея: делим массив пополам. Подмассив с наибольшей суммой попадает в один из трёх случаев:
- находится в левой половине;
- в правой половине;
- пересекает середину (начинается в левой половине и заканчивается в правой).
Рекурсивная функция принимает границы текущего подмассива [left, right], при первом вызове - весь массив:
База: если left == right - подмассив из одного эл-та, возвращаем его.
Рекурсивное ветвление:
1. Находим середину mid;
2. Рекурсивно ищем максимум в левой [left, mid] и правой половине [mid + 1, right];
3. Ищем максимум, пересекающий mid:
- идём влево от mid до left, накапливая текущую сумму; ищем cross_left - максимальный суффикс левой половины.
- идём от mid+1 вправо до right, накапливая текущую сумму; ищем cross_right - максимальный префикс правой половины.
- вычисляем cross_max, как сумму cross_left и cross_right.
4. Находим максимум среди left_max, right_max и cross_max.
Сложность:
O(n log n) - по времени (T(N) = 2T(N/2) + O(N) = O(N log N), где 2T(N/2) - рекурсивные вызовы для левой и правой половин и O(N) - проход от left до right для вычисления cross_max)
O(log n) - по памяти (глубина стека рекурсии)
Код:
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
def divide_and_conquer(left: int, right: int) -> int:
if left == right:
return nums[left]
mid = (left + right) // 2
left_max = divide_and_conquer(left, mid)
right_max = divide_and_conquer(mid + 1, right)
cross_left = float("-inf")
cur_sum = 0
for i in range(mid, left - 1, -1):
cur_sum += nums[i]
cross_left = max(cross_left, cur_sum)
cross_right = float("-inf")
cur_sum = 0
for i in range(mid + 1, right + 1):
cur_sum += nums[i]
cross_right = max(cross_right, cur_sum)
cross_max = cross_left + cross_right
return max(left_max, cross_max, right_max)
return divide_and_conquer(0, len(nums) - 1)
@algoses
Дан целочисленный массив nums. Найдите подмассив с наибольшей суммой и верните эту сумму.
Follow up: если вы нашли решение с асимптотикой O(n), попробуйте реализовать ещё одно, используя метод "разделяй и властвуй".
Пример 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: Подмассив [4,-1,2,1] имеет наибольшую сумму, равную 6.
Пример 2:
Input: nums = [1]
Output: 1
Explanation: Подмассив [1] имеет наибольшую сумму, равную 1.
Пример 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: Подмассив [5,4,-1,7,8] имеет наибольшую сумму, равную 23.
Ограничения:
1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение за O(n):
- продлить эл-том текущий подмассив или начать новый подмассив с этого эл-та.
- параллельно обновляем глобальный максимум, если сумма текущего подмассива больше.
Разберём подробнее:
max_sum - глобальный максимум; инициализируем, как float("-inf"), гарантируя, что первый эл-т массива обновит максимум;
cur_sum - текущая сумма подмассива; инициализируем, как 0 (пустой префикс).
Проходим по массиву:
- формула, обновляющая cur_sum, выбирает: начать новый подмассив с текущего эл-та или продлить существующий. Если накопленная сумма отрицательна, значит, любой подмассив, начинающийся до текущего эл-та и идущий дальше, будет иметь сумму меньше, чем если бы он начинался с текущего эл-та => выгодно начать новый подмассив;
- обновляем глобальный максимум, выбирая максимальное значение среди max_sum и cur_sum.
Сложность
O(1) - по памяти (храним две переменные)
Код
def maxSubArray(self, nums: List[int]) -> int:
max_sum = float("-inf")
cur_sum = 0
for num in nums:
cur_sum = max(num, cur_sum + num)
max_sum = max(max_sum, cur_sum)
return max_sum
Подход "разделяй и властвуй":
- находится в левой половине;
- в правой половине;
- пересекает середину (начинается в левой половине и заканчивается в правой).
Рекурсивная функция принимает границы текущего подмассива [left, right], при первом вызове - весь массив:
База: если left == right - подмассив из одного эл-та, возвращаем его.
Рекурсивное ветвление:
1. Находим середину mid;
2. Рекурсивно ищем максимум в левой [left, mid] и правой половине [mid + 1, right];
3. Ищем максимум, пересекающий mid:
- идём влево от mid до left, накапливая текущую сумму; ищем cross_left - максимальный суффикс левой половины.
- идём от mid+1 вправо до right, накапливая текущую сумму; ищем cross_right - максимальный префикс правой половины.
- вычисляем cross_max, как сумму cross_left и cross_right.
4. Находим максимум среди left_max, right_max и cross_max.
Сложность:
O(log n) - по памяти (глубина стека рекурсии)
Код:
def maxSubArray(self, nums: List[int]) -> int:
def divide_and_conquer(left: int, right: int) -> int:
if left == right:
return nums[left]
mid = (left + right) // 2
left_max = divide_and_conquer(left, mid)
right_max = divide_and_conquer(mid + 1, right)
cross_left = float("-inf")
cur_sum = 0
for i in range(mid, left - 1, -1):
cur_sum += nums[i]
cross_left = max(cross_left, cur_sum)
cross_right = float("-inf")
cur_sum = 0
for i in range(mid + 1, right + 1):
cur_sum += nums[i]
cross_right = max(cross_right, cur_sum)
cross_max = cross_left + cross_right
return max(left_max, cross_max, right_max)
return divide_and_conquer(0, len(nums) - 1)
@algoses
❤2
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
Скоро начнутся отборы на осенние стажировки. Самое время обсудить на какие программы обратить свое внимание в первую очередь и как гарантировано пройти отбор! Смотрим! Смотрим!
https://www.youtube.com/watch?v=8QxduqUBn3g
https://www.youtube.com/watch?v=8QxduqUBn3g
YouTube
Топ 6 стажировок в Айти!
Хочешь попасть в топовые IT-компании, но не знаешь, с чего начать? В этом видео разбираю 6 самых крупных стажировок в России — без воды, по полочкам и с конкретными цифрами!
⚡️ Что внутри:
1️⃣ Яндекс — самая масштабная стажировка, набор круглый год, но есть…
⚡️ Что внутри:
1️⃣ Яндекс — самая масштабная стажировка, набор круглый год, но есть…
🔥2
Задача с собеседования в TCS
Дан целочисленный массив nums, передвиньте все чётные числа в начало массива, а за ними — все нечётные.
Верните любой массив, удовлетворяющий этому условию.
Пример 1:
Input: nums = [3,1,2,4]
Output: [2,4,3,1]
Explanation: результаты [4,2,3,1], [2,4,1,3] и [4,2,1,3] также были бы приняты.
Пример 2:
Input: nums = [0]
Output: [0]
Ограничения:
1 <= nums.length <= 5000
0 <= nums[i] <= 5000
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Используем метод двух указателей, движущихся в одном направлении (в этом случае сохранится относительный порядок чётных чисел в массиве):
left - индекс, указывающий, куда нужно записать следующее чётное число;
right - указатель, который проходит по массиву и последовательно проверяет каждый эл-т на чётность.
Вначале оба указателя указывают на первый эл-т.
Проходим указателем right по массиву nums:
- если число чётное: меняем его местами с числом на позиции left;
- сдвигаем указатель left вправо.
В конце возвращаем изменённый массив nums.
Сложность
O(n) - по времени (проходим по массиву длиной n)
O(1) - по памяти (храним две переменные, меняем эл-ты in-place)
Код
class Solution:
def sortArrayByParity(self, nums: List[int]) -> List[int]:
left = 0
for right in range(len(nums)):
if nums[right] % 2 == 0:
nums[left], nums[right] = nums[right], nums[left]
left += 1
return nums
@algoses
Дан целочисленный массив nums, передвиньте все чётные числа в начало массива, а за ними — все нечётные.
Верните любой массив, удовлетворяющий этому условию.
Пример 1:
Input: nums = [3,1,2,4]
Output: [2,4,3,1]
Explanation: результаты [4,2,3,1], [2,4,1,3] и [4,2,1,3] также были бы приняты.
Пример 2:
Input: nums = [0]
Output: [0]
Ограничения:
1 <= nums.length <= 5000
0 <= nums[i] <= 5000
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
left - индекс, указывающий, куда нужно записать следующее чётное число;
right - указатель, который проходит по массиву и последовательно проверяет каждый эл-т на чётность.
Вначале оба указателя указывают на первый эл-т.
Проходим указателем right по массиву nums:
- если число чётное: меняем его местами с числом на позиции left;
- сдвигаем указатель left вправо.
В конце возвращаем изменённый массив nums.
Сложность
O(1) - по памяти (храним две переменные, меняем эл-ты in-place)
Код
def sortArrayByParity(self, nums: List[int]) -> List[int]:
left = 0
for right in range(len(nums)):
if nums[right] % 2 == 0:
nums[left], nums[right] = nums[right], nums[left]
left += 1
return nums
@algoses
🔥6❤2🤔1
Выкладываем задания Т-Академии и Т-Интенсива
Товарищи, прямо сейчас Т-Банк набирает участников на программы по аналитике и разработке. Задания уже выложены здесь.
Мы разберём вступительные испытания на карьерных курсах — выбирайте направление и смотрите, какой курс поможет подготовиться:
⭐️ Т-Академия
— Разработка ПО: программирование
Разбор экзамена будет на «Бэкенд Старт» и «Алгоритмы Старт»
Дедлайн: 31 июля
— Продуктовая аналитика: математика и SQL
Разбор экзамена будет на «Аналитика Старт»
Дедлайн: 31 июля
⭐️ Т-Интенсив
— Риск-аналитика: математика и программирование
Разбор экзамена будет на «ML Старт»
Дедлайн: 26 июля
— Бизнес-аналитика: математика, SQL и аналитический кейс
Разбор экзамена будет на «Аналитика Старт»
Дедлайн: 8 августа
Программы дают возможность поработать над реальными задачами со специалистами Т-Банка, а финалисты могут получить фаст-трек на стажировку или джуновскую позицию. Но сначала нужно пройти отбор. Делимся мини-гайдом с неочевидными нюансами, которые помогут повысить шансы на поступление.
Подписаться: @algoses
Товарищи, прямо сейчас Т-Банк набирает участников на программы по аналитике и разработке. Задания уже выложены здесь.
Мы разберём вступительные испытания на карьерных курсах — выбирайте направление и смотрите, какой курс поможет подготовиться:
— Разработка ПО: программирование
Разбор экзамена будет на «Бэкенд Старт» и «Алгоритмы Старт»
Дедлайн: 31 июля
— Продуктовая аналитика: математика и SQL
Разбор экзамена будет на «Аналитика Старт»
Дедлайн: 31 июля
— Риск-аналитика: математика и программирование
Разбор экзамена будет на «ML Старт»
Дедлайн: 26 июля
— Бизнес-аналитика: математика, SQL и аналитический кейс
Разбор экзамена будет на «Аналитика Старт»
Дедлайн: 8 августа
Программы дают возможность поработать над реальными задачами со специалистами Т-Банка, а финалисты могут получить фаст-трек на стажировку или джуновскую позицию. Но сначала нужно пройти отбор. Делимся мини-гайдом с неочевидными нюансами, которые помогут повысить шансы на поступление.
Подписаться: @algoses
Please open Telegram to view this post
VIEW IN TELEGRAM
❤3👍1
Товарищи, Поступашкам нужны контент мейкеры по ДС-МЛ. Если вы творческая личность, вам нравится писать посты/ придумывать идеи для контента, то обязательно пишите @vice22821. Оплата сдельная, ориентировочно за один пост от 2 тыс до 15 тыс рублей.
Обязательно делитесь с ребятами, которым это может быть интересно.
Обязательно делитесь с ребятами, которым это может быть интересно.
Для тех кто хочет прокачаться в DS
Качественные материалы и подборки бывают не только на нашем канале! Для тех, кто хочет разобраться во всех этих бустингах, пресижн и реколл, советую заглянуть в канал @asisakov_channel и прочитать тот самый роудмап по вкатыванию в Data Science.
Автор канала Александр руководит командой внедрения AI-агентов в Яндекс Лавке🛒 , а в свободное время в блоге пишет про ML, агентов, софты и свою жизнь
Что рекомендую почитать на канале:
1. Грандиозная подборка по собесам
2. Как заботать SQL?
3. Как понять теорвер?
4. Как упороться в статистику?
5. Как заботать математику для Data Science?
Ну и вишенка на канале - есть задачи и мемы, так что всё в лучших традициях авторского блога. Подписывайся, чтобы не потерять @asisakov_channel
Качественные материалы и подборки бывают не только на нашем канале! Для тех, кто хочет разобраться во всех этих бустингах, пресижн и реколл, советую заглянуть в канал @asisakov_channel и прочитать тот самый роудмап по вкатыванию в Data Science.
Автор канала Александр руководит командой внедрения AI-агентов в Яндекс Лавке
Что рекомендую почитать на канале:
1. Грандиозная подборка по собесам
2. Как заботать SQL?
3. Как понять теорвер?
4. Как упороться в статистику?
5. Как заботать математику для Data Science?
Ну и вишенка на канале - есть задачи и мемы, так что всё в лучших традициях авторского блога. Подписывайся, чтобы не потерять @asisakov_channel
Please open Telegram to view this post
VIEW IN TELEGRAM
❤1
Задача с собеседования в TCS
Дан целочисленный массив nums. Изначально вы находитесь на первом индексе массива, а каждый элемент массива представляет максимальную длину прыжка из этой позиции. Верните true, если вы можете достичь последнего индекса, или false в противном случае.
Пример 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Прыгаем на 1 шаг с индекса 0 на 1, а затем — на 3 шага к последнему индексу.
Пример 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: Вы всегда будете оказываться на индексе 3. Максимальная длина прыжка равно 0, из-за чего добраться до последнего индекса невозможно.
Ограничения:
1 <= nums.length <= 10⁴
0 <= nums[i] <= 10⁵
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Используем жадный алгоритм: максимальная достижимая позиция является локальным оптимумом; нам не нужно выбирать, на сколько позиций стоит прыгнуть, а только знать - какой самый дальний индекс можем достичь на текущей итерации.
max_reach - самый дальний индекс, до которого можем допрыгнуть; инициализируем, как 0, так как начинаем с индекса 0.
Проходим по массиву nums (i - индекс, на который хотим прыгнуть на текущей итерации):
- Если i больше значения max_reach: мы застряли и не можем достичь проверяемой позиции -> достичь конца массива невозможно, возвращаем False;
- Иначе, если можем достичь индекса i: из текущей позиции можно прыгнуть на nums[i] шагов, то есть возможно достичь индекса (i + nums[i]). Сравниваем прошлый максимум доступной нам дальности с новым, обновляя max_reach.
Если удалось пройти от начала до конца массива, возвращаем True.
Сложность
O(n) - по времени (один раз проходим по массиву длиной n)
O(1) - по памяти (храним только одну переменную max_reach)
Код
class Solution:
def canJump(self, nums: List[int]) -> bool:
max_reach = 0
for i in range(len(nums)):
if i > max_reach:
return False
max_reach = max(max_reach, i + nums[i])
return True
@algoses
Дан целочисленный массив nums. Изначально вы находитесь на первом индексе массива, а каждый элемент массива представляет максимальную длину прыжка из этой позиции. Верните true, если вы можете достичь последнего индекса, или false в противном случае.
Пример 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Прыгаем на 1 шаг с индекса 0 на 1, а затем — на 3 шага к последнему индексу.
Пример 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: Вы всегда будете оказываться на индексе 3. Максимальная длина прыжка равно 0, из-за чего добраться до последнего индекса невозможно.
Ограничения:
1 <= nums.length <= 10⁴
0 <= nums[i] <= 10⁵
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
max_reach - самый дальний индекс, до которого можем допрыгнуть; инициализируем, как 0, так как начинаем с индекса 0.
Проходим по массиву nums (i - индекс, на который хотим прыгнуть на текущей итерации):
- Если i больше значения max_reach: мы застряли и не можем достичь проверяемой позиции -> достичь конца массива невозможно, возвращаем False;
- Иначе, если можем достичь индекса i: из текущей позиции можно прыгнуть на nums[i] шагов, то есть возможно достичь индекса (i + nums[i]). Сравниваем прошлый максимум доступной нам дальности с новым, обновляя max_reach.
Если удалось пройти от начала до конца массива, возвращаем True.
Сложность
O(1) - по памяти (храним только одну переменную max_reach)
Код
def canJump(self, nums: List[int]) -> bool:
max_reach = 0
for i in range(len(nums)):
if i > max_reach:
return False
max_reach = max(max_reach, i + nums[i])
return True
@algoses
🔥6👍1