Задача с собеседования в Zoho
Вы поднимаетесь по лестнице. Чтобы достичь вершины, нужно сделать n шагов.
Каждый раз вы можете подняться либо на 1, либо на 2 ступеньки.
Сколькими различными способами вы можете подняться на вершину?
Пример 1:
Input: n = 2
Output: 2
Explanation: Существует два способа подняться на вершину:
1. 1 шаг + 1 шаг
2. 2 шага
Пример 2:
Input: n = 3
Output: 3
Explanation: Существует три способа подняться на вершину:
1. 1 шаг + 1 шаг + 1 шаг
2. 1 шаг + 2 шага
3. 2 шага + 1 шаг
Ограничения:
1 <= n <= 45
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Задача помечена тегом "Dynamic Programming", оптимальным вариантом решения будет использование восходящего подхода с табуляцией, так мы избавимся от риска переполнения стека при глубокой рекурсии. Для оптимизации памяти до O(1) храним только две переменные (cur_step и prev_step) вместо dp массива.
Начинаем с базовых случаев (ступеньки 0 и 1), при которых ответ будет равен 1 способу => инициализируем наши две переменные значениями 1.
Запускаем цикл и поднимаемся вверх по лестнице со второй ступеньки, обновляя значения кол-ва способов подняться на предыдущую и текущую ступеньки, с каждой итерацией:
- текущая ступенька становится предыдущей;
- новая текущая ступенька равняется сумме способов подняться на две предыдущие ступеньки (по сути, классическая формула из задач о числах Фибоначчи: f(n) = f(n-1) + f(n-2)).
После окончания работы цикла выводим cur_step с последним вписанным в переменную значением.
Сложность
O(n) - по времени (так как делаем один проход по всем ступенькам)
O(1) - по памяти (так как храним только две переменные)
Код
class Solution:
def climbStairs(self, n: int) -> int:
if n == 0 or n == 1:
return 1
cur_step, prev_step = 1, 1
for _ in range(2, n + 1):
prev_step, cur_step = cur_step, prev_step + cur_step
return cur_step
@algoses
Вы поднимаетесь по лестнице. Чтобы достичь вершины, нужно сделать n шагов.
Каждый раз вы можете подняться либо на 1, либо на 2 ступеньки.
Сколькими различными способами вы можете подняться на вершину?
Пример 1:
Input: n = 2
Output: 2
Explanation: Существует два способа подняться на вершину:
1. 1 шаг + 1 шаг
2. 2 шага
Пример 2:
Input: n = 3
Output: 3
Explanation: Существует три способа подняться на вершину:
1. 1 шаг + 1 шаг + 1 шаг
2. 1 шаг + 2 шага
3. 2 шага + 1 шаг
Ограничения:
1 <= n <= 45
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Начинаем с базовых случаев (ступеньки 0 и 1), при которых ответ будет равен 1 способу => инициализируем наши две переменные значениями 1.
Запускаем цикл и поднимаемся вверх по лестнице со второй ступеньки, обновляя значения кол-ва способов подняться на предыдущую и текущую ступеньки, с каждой итерацией:
- текущая ступенька становится предыдущей;
- новая текущая ступенька равняется сумме способов подняться на две предыдущие ступеньки (по сути, классическая формула из задач о числах Фибоначчи: f(n) = f(n-1) + f(n-2)).
После окончания работы цикла выводим cur_step с последним вписанным в переменную значением.
Сложность
O(1) - по памяти (так как храним только две переменные)
Код
def climbStairs(self, n: int) -> int:
if n == 0 or n == 1:
return 1
cur_step, prev_step = 1, 1
for _ in range(2, n + 1):
prev_step, cur_step = cur_step, prev_step + cur_step
return cur_step
@algoses
👍6❤4😁1
Задача с собеседования в Zoho
Даны две строки: word1 и word2. Верните минимальное количество операций, требуемых для преобразования строки word1 в строку word2.
Вы можете выполнять следующие три операции над словом:
- вставить символ
- удалить символ
- заменить символ
Пример 1:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (заменить 'h' на 'r')
rorse -> rose (удалить 'r')
rose -> ros (удалить 'e')
Пример 2:
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (удалить 't')
inention -> enention (заменить 'i' на 'e')
enention -> exention (заменить 'n' на 'x')
exention -> exection (заменить 'n' на 'c')
exection -> execution (вставить 'u')
Ограничения:
0 <= word1.length, word2.length <= 500
word1 и word2 состоят из строчных английских букв
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Задача помечена тегом "Dynamic Programming" и является классическим примером задачи на вычисление "расстояния Левенштейна". Используем восходящее dp с табуляцией.
Сначала разберём базовое решение, а потом оптимизируем:
Заполняем таблицу размером (len(word1) + 1) × (len(word2) + 1), где dp[i][j] - минимальное кол-во операций, необходимое для превращения первых i символов word1 в первые j символов word2.
i и j - это кол-во символов, поэтому dp[0][j] соответствует пустой word1, dp[i][0] - пустой word2.
Базовый случай, когда одна из строк пустая:
word1 пустая: нужно вставить все символы word2 (j вставок);
word2 пустая: нужно удалить все символы word1 (i удалений).
Остальные ячейки заполняем, смотря на последние символы текущих префиксов (word1[i-1] и word2[j-1]):
Если символы совпадают, нам не нужно ничего с ними делать, копируем значение из левой верхней ячейки;
Если символы не совпадают, есть три варианта действий, выбираем минимальный по кол-ву операций:
1. Замена: dp[i-1][j-1] + 1 - заменяем последний символ word1 на последний символ word2;
2. Удаление: dp[i-1][j] + 1 - удаляем последний символ из word1;
3. Вставка: dp[i][j-1] + 1 - вставляем последний символ word2 в word1.
Оптимизируем:
Храним не всю таблицу, а две переменные: prev (предыдущая строка, на первом шаге - первая строка таблицы) и cur (текущая строка, вначале заполнена нулями).
Если длина word1 меньше длины word2, меняем строки местами: более короткая строка становится word2, внутренний цикл идёт по ней, оптимизируя память до O(min(m, n)).
Во внешнем цикле: проходим по всем символам word1:
- в начале каждой итерации устанавливаем первый эл-т текущей строки: cur[0] = i. Это соответствует случаю, когда word2 пустая, поэтому нужно удалить все i символов из word1.
Во внутреннем: проходим по word2:
- символы совпадают: копируем значение из левой верхней ячейки (prev[j-1]);
- не совпадают: берём минимум из трёх значений:
prev[j-1] - замена символа word1[i-1] на word2[j-1]; обе строки становятся короче на 1, в таблице dp это диагональ.
prev[j] - удаление символа word1[i-1]; word1 становится короче, word2 - той же длины, в таблице это верх.
cur[j-1] - вставка символа word2[j-1] в word1; word2 - короче, word1 - той же длины, в таблице это значение слева.
+ 1, так как любая операция требует одного действия.
После заполнения строки меняем местами prev и cur, текущая строка становится предыдущей для следующей итерации.
После завершения циклов prev содержит последнюю заполненную строку, а её последний эл-т является ответом.
Сложность
O(mn) - по времени (проходим по всем парам символов)
O(min(m, n)) - по памяти
Код
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
if len(word1) < len(word2):
word1, word2 = word2, word1
prev = list(range(len(word2) + 1))
cur = [0] * (len(word2) + 1)
for i in range(1, len(word1) + 1):
cur[0] = i
for j in range(1, len(word2) + 1):
if word1[i-1] == word2[j-1]:
cur[j] = prev[j-1]
else:
cur[j] = min(prev[j-1], prev[j], cur[j-1]) + 1
prev, cur = cur, prev
return prev[-1]
@algoses
Даны две строки: word1 и word2. Верните минимальное количество операций, требуемых для преобразования строки word1 в строку word2.
Вы можете выполнять следующие три операции над словом:
- вставить символ
- удалить символ
- заменить символ
Пример 1:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (заменить 'h' на 'r')
rorse -> rose (удалить 'r')
rose -> ros (удалить 'e')
Пример 2:
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (удалить 't')
inention -> enention (заменить 'i' на 'e')
enention -> exention (заменить 'n' на 'x')
exention -> exection (заменить 'n' на 'c')
exection -> execution (вставить 'u')
Ограничения:
0 <= word1.length, word2.length <= 500
word1 и word2 состоят из строчных английских букв
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Сначала разберём базовое решение, а потом оптимизируем:
Заполняем таблицу размером (len(word1) + 1) × (len(word2) + 1), где dp[i][j] - минимальное кол-во операций, необходимое для превращения первых i символов word1 в первые j символов word2.
i и j - это кол-во символов, поэтому dp[0][j] соответствует пустой word1, dp[i][0] - пустой word2.
Базовый случай, когда одна из строк пустая:
word1 пустая: нужно вставить все символы word2 (j вставок);
word2 пустая: нужно удалить все символы word1 (i удалений).
Остальные ячейки заполняем, смотря на последние символы текущих префиксов (word1[i-1] и word2[j-1]):
Если символы совпадают, нам не нужно ничего с ними делать, копируем значение из левой верхней ячейки;
Если символы не совпадают, есть три варианта действий, выбираем минимальный по кол-ву операций:
1. Замена: dp[i-1][j-1] + 1 - заменяем последний символ word1 на последний символ word2;
2. Удаление: dp[i-1][j] + 1 - удаляем последний символ из word1;
3. Вставка: dp[i][j-1] + 1 - вставляем последний символ word2 в word1.
Оптимизируем:
Храним не всю таблицу, а две переменные: prev (предыдущая строка, на первом шаге - первая строка таблицы) и cur (текущая строка, вначале заполнена нулями).
Если длина word1 меньше длины word2, меняем строки местами: более короткая строка становится word2, внутренний цикл идёт по ней, оптимизируя память до O(min(m, n)).
Во внешнем цикле: проходим по всем символам word1:
- в начале каждой итерации устанавливаем первый эл-т текущей строки: cur[0] = i. Это соответствует случаю, когда word2 пустая, поэтому нужно удалить все i символов из word1.
Во внутреннем: проходим по word2:
- символы совпадают: копируем значение из левой верхней ячейки (prev[j-1]);
- не совпадают: берём минимум из трёх значений:
prev[j-1] - замена символа word1[i-1] на word2[j-1]; обе строки становятся короче на 1, в таблице dp это диагональ.
prev[j] - удаление символа word1[i-1]; word1 становится короче, word2 - той же длины, в таблице это верх.
cur[j-1] - вставка символа word2[j-1] в word1; word2 - короче, word1 - той же длины, в таблице это значение слева.
+ 1, так как любая операция требует одного действия.
После заполнения строки меняем местами prev и cur, текущая строка становится предыдущей для следующей итерации.
После завершения циклов prev содержит последнюю заполненную строку, а её последний эл-т является ответом.
Сложность
O(min(m, n)) - по памяти
Код
def minDistance(self, word1: str, word2: str) -> int:
if len(word1) < len(word2):
word1, word2 = word2, word1
prev = list(range(len(word2) + 1))
cur = [0] * (len(word2) + 1)
for i in range(1, len(word1) + 1):
cur[0] = i
for j in range(1, len(word2) + 1):
if word1[i-1] == word2[j-1]:
cur[j] = prev[j-1]
else:
cur[j] = min(prev[j-1], prev[j], cur[j-1]) + 1
prev, cur = cur, prev
return prev[-1]
@algoses
❤6👍2
Задача с собеседования в Zoho
Дана строка s, разверните (изменив порядок на обратный) только все гласные в строке и верните полученную строку.
Гласными являются буквы 'a', 'e', 'i', 'o', и 'u'. Они могут быть как в нижнем, так и в верхнем регистре, а также встречаться более одного раза.
Пример 1:
Input: "IceCreAm"
Output: "AceCreIm"
Explanation:
Гласные в s: ['I', 'e', 'e', 'A']. После разворота гласных s превращается в "AceCreIm".
Пример 2:
Input: s = "leetcode"
Output: "leotcede"
Ограничения:
1 <= s.length <= 3 * 105
s состоит из печатных символов ASCII.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Будем использовать метод двух указателей:
left - индекс первого элемента в списке (после преобразования строки в список)
right - индекс последнего элемента
Гласные храним во множестве для быстрой проверки за O(1).
Пока left меньше right: идём по строке в двух направлениях, проверяя символы, на которые указывают left и right.
Если символ слева - не гласная: сдвигаем левый указатель;
Если символ справа - не гласная: сдвигаем правый указатель;
Если оба символа - гласные: меняем их местами и двигаем оба указателя.
Так проходим по всему списку, пока указатели не встретятся, и в конце возвращаем полученную строку.
Сложность
O(n) - по времени (так как проходим по списку один раз)
O(n) - по памяти (так как создаём список из символов строки)
Код
class Solution:
def reverseVowels(self, s: str) -> str:
s = list(s)
vowels = set("aeiouAEIOU")
left, right = 0, len(s) - 1
while left < right:
if s[left] not in vowels:
left += 1
elif s[right] not in vowels:
right -= 1
else:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
return "".join(s)
@algoses
Дана строка s, разверните (изменив порядок на обратный) только все гласные в строке и верните полученную строку.
Гласными являются буквы 'a', 'e', 'i', 'o', и 'u'. Они могут быть как в нижнем, так и в верхнем регистре, а также встречаться более одного раза.
Пример 1:
Input: "IceCreAm"
Output: "AceCreIm"
Explanation:
Гласные в s: ['I', 'e', 'e', 'A']. После разворота гласных s превращается в "AceCreIm".
Пример 2:
Input: s = "leetcode"
Output: "leotcede"
Ограничения:
1 <= s.length <= 3 * 105
s состоит из печатных символов ASCII.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
left - индекс первого элемента в списке (после преобразования строки в список)
right - индекс последнего элемента
Гласные храним во множестве для быстрой проверки за O(1).
Пока left меньше right: идём по строке в двух направлениях, проверяя символы, на которые указывают left и right.
Если символ слева - не гласная: сдвигаем левый указатель;
Если символ справа - не гласная: сдвигаем правый указатель;
Если оба символа - гласные: меняем их местами и двигаем оба указателя.
Так проходим по всему списку, пока указатели не встретятся, и в конце возвращаем полученную строку.
Сложность
O(n) - по памяти (так как создаём список из символов строки)
Код
def reverseVowels(self, s: str) -> str:
s = list(s)
vowels = set("aeiouAEIOU")
left, right = 0, len(s) - 1
while left < right:
if s[left] not in vowels:
left += 1
elif s[right] not in vowels:
right -= 1
else:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1
return "".join(s)
@algoses
🔥10❤3
HandbookShad.pdf
244.1 KB
Хэнбук по алгоритмам ШАД
Собрали и разобрали все задачи с собеседований в ШАД. Привели необходимую теорию и задачи для закрепления. Вам же осталось только сесть, разобраться и прорешать - и алгособес в кармане!
Еще больше подобных материалов на наших курсах в ШАД, залетаем в ШАД уже этим летом.
@postypashki_old
Собрали и разобрали все задачи с собеседований в ШАД. Привели необходимую теорию и задачи для закрепления. Вам же осталось только сесть, разобраться и прорешать - и алгособес в кармане!
Еще больше подобных материалов на наших курсах в ШАД, залетаем в ШАД уже этим летом.
@postypashki_old
🔥12❤5
Задача с собеседования в eBay
Дан целочисленный массив nums. Переместите все нули в его конец, сохранив при этом относительный порядок ненулевых элементов.
Обратите внимание, что необходимо сделать это in-place, без создания копии массива.
Пример 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
Пример 2:
Input: nums = [0]
Output: [0]
Ограничения:
1 <= nums.length <= 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Используем метод двух указателей, идём по массиву в одном направлении слева направо:
l - позиция, куда нужно поставить следующее ненулевое число
r - проходит по всем элементам массива
Проходим по массиву указателем r:
если r указывает на ненулевой элемент, меняем его местами с элементом на позиции l и двигаем левый указатель.
После завершения итерации с индексом r:
- все элементы до l будут ненулевыми;
- все элементы от l до r включительно - нули.
Вывод результата не требуется. Решение соблюдает принцип in-place (работаем с исходным массивом) и сохраняет порядок ненулевых элементов.
Сложность
O(n) - по времени (проходим по массиву один раз)
O(1) - по памяти (используем две переменные, изменяем только исходный массив)
Код
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
l = 0
for r in range(len(nums)):
if nums[r] != 0:
nums[l], nums[r] = nums[r], nums[l]
l += 1
@algoses
Дан целочисленный массив nums. Переместите все нули в его конец, сохранив при этом относительный порядок ненулевых элементов.
Обратите внимание, что необходимо сделать это in-place, без создания копии массива.
Пример 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
Пример 2:
Input: nums = [0]
Output: [0]
Ограничения:
1 <= nums.length <= 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
l - позиция, куда нужно поставить следующее ненулевое число
r - проходит по всем элементам массива
Проходим по массиву указателем r:
если r указывает на ненулевой элемент, меняем его местами с элементом на позиции l и двигаем левый указатель.
После завершения итерации с индексом r:
- все элементы до l будут ненулевыми;
- все элементы от l до r включительно - нули.
Вывод результата не требуется. Решение соблюдает принцип in-place (работаем с исходным массивом) и сохраняет порядок ненулевых элементов.
Сложность
O(n) - по времени (проходим по массиву один раз)
O(1) - по памяти (используем две переменные, изменяем только исходный массив)
Код
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
l = 0
for r in range(len(nums)):
if nums[r] != 0:
nums[l], nums[r] = nums[r], nums[l]
l += 1
@algoses
❤10🔥3
Хочешь в магистратуру, которая реально повлияет на твою карьеру?
Центральный университет проводит День открытых дверей ИТ-магистратуры 6 и 7 апреля, онлайн и офлайн в Москве!
Ты узнаешь:
— как и на какие программы можно поступить в 2026 году;
— как можно получить грант до 75%;
— как обучение приводит к работе мечты, а не просто диплому.
А также тебя ждут экскурсии по кампусу со студентами и ответы на все вопросы.
Регистрируйся и разберись, какое направление действительно тебе подходит
Центральный университет проводит День открытых дверей ИТ-магистратуры 6 и 7 апреля, онлайн и офлайн в Москве!
Ты узнаешь:
— как и на какие программы можно поступить в 2026 году;
— как можно получить грант до 75%;
— как обучение приводит к работе мечты, а не просто диплому.
А также тебя ждут экскурсии по кампусу со студентами и ответы на все вопросы.
Регистрируйся и разберись, какое направление действительно тебе подходит
❤2🔥1
Задача с собеседования в eBay
Дано целое положительное число n. Каждой цифре n присваивается знак в соответствии со следующими правилами:
- самой старшей цифре присваивается положительный знак;
- каждая следующая цифра имеет знак, противоположный знаку предыдущей цифры.
Верните сумму всех цифр с соответствующими знаками.
Пример 1:
Input: n = 521
Output: 4
Объяснение: (+5) + (-2) + (+1) = 4.
Пример 2:
Input: n = 111
Output: 1
Объяснение: (+1) + (-1) + (+1) = 1.
Пример 3:
Input: n = 886996
Output: 0
Объяснение: (+8) + (-8) + (+6) + (-9) + (+9) + (-6) = 0.
Ограничения:
1 <= n <= 10⁹
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Сначала разберём базовое решение:
Заводим переменные:
sign - знак текущей цифры, сначала равняется 1 (самая старшая цифра имеет положительный знак)
res - для накопления суммы цифр
Преобразуем n в строку, проходим по ней слева направо:
- присваиваем знак текущей цифре, умножая её на sign, и прибавляем к res;
- меняем sign на противоположный, умножая на -1.
Теперь оптимизируем решение, используя только математические операции без строки:
В цикле проходим по цифрам числа, от младших разрядов к старшим:
- остатком от деления получаем последнюю цифру. Обновляем сумму, вычитая из цифры предыдущий результат.
- переходим к следующему разряду, применяя целочисленное деление.
Формула гарантирует правильное присвоение знаков, так как вычитание предыдущего результата эквивалентно умножению всех накопленных цифр на -1.
К примеру, для n = 521:
res = 1 - 0 = 1
res = 2 - 1 = 1
res = 5 - (2 - 1) = 4
=> +5 - 2 + 1 = 4
Сложность
Базовое:
O(log n) - по времени (количество цифр в числе)
O(log n) - по памяти (храним строку)
Оптимизированное:
O(log n) - по времени
O(1) - по памяти (храним res)
Код
Базовое:
class Solution:
def alternateDigitSum(self, n: int) -> int:
n_str = str(n)
sign = 1
res = 0
for char in n_str:
res = res + int(char) * sign
sign *= -1
return res
Оптимизированное:
class Solution:
def alternateDigitSum(self, n: int) -> int:
res = 0
while n:
res = n % 10 - res
n //= 10
return res
@algoses
Дано целое положительное число n. Каждой цифре n присваивается знак в соответствии со следующими правилами:
- самой старшей цифре присваивается положительный знак;
- каждая следующая цифра имеет знак, противоположный знаку предыдущей цифры.
Верните сумму всех цифр с соответствующими знаками.
Пример 1:
Input: n = 521
Output: 4
Объяснение: (+5) + (-2) + (+1) = 4.
Пример 2:
Input: n = 111
Output: 1
Объяснение: (+1) + (-1) + (+1) = 1.
Пример 3:
Input: n = 886996
Output: 0
Объяснение: (+8) + (-8) + (+6) + (-9) + (+9) + (-6) = 0.
Ограничения:
1 <= n <= 10⁹
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Заводим переменные:
sign - знак текущей цифры, сначала равняется 1 (самая старшая цифра имеет положительный знак)
res - для накопления суммы цифр
Преобразуем n в строку, проходим по ней слева направо:
- присваиваем знак текущей цифре, умножая её на sign, и прибавляем к res;
- меняем sign на противоположный, умножая на -1.
Теперь оптимизируем решение, используя только математические операции без строки:
В цикле проходим по цифрам числа, от младших разрядов к старшим:
- остатком от деления получаем последнюю цифру. Обновляем сумму, вычитая из цифры предыдущий результат.
- переходим к следующему разряду, применяя целочисленное деление.
Формула гарантирует правильное присвоение знаков, так как вычитание предыдущего результата эквивалентно умножению всех накопленных цифр на -1.
К примеру, для n = 521:
res = 1 - 0 = 1
res = 2 - 1 = 1
res = 5 - (2 - 1) = 4
=> +5 - 2 + 1 = 4
Сложность
Базовое:
O(log n) - по времени (количество цифр в числе)
O(log n) - по памяти (храним строку)
Оптимизированное:
O(log n) - по времени
O(1) - по памяти (храним res)
Код
Базовое:
class Solution:
def alternateDigitSum(self, n: int) -> int:
n_str = str(n)
sign = 1
res = 0
for char in n_str:
res = res + int(char) * sign
sign *= -1
return res
Оптимизированное:
class Solution:
def alternateDigitSum(self, n: int) -> int:
res = 0
while n:
res = n % 10 - res
n //= 10
return res
@algoses
🤣25❤5
Задача с собеседования в Zopsmart
Дан массив nums, состоящий из n объектов, окрашенных в красный, белый и синий цвета. Отсортируйте их in-place так, чтобы объекты одного цвета оказались соседними, следуя порядку: красные, белые, синие.
Будем использовать целые числа 0, 1 и 2 для обозначения красного, белого и синего, соответственно.
Решите задачу без использования встроенной функции сортировки.
Follow up: можете ли вы реализовать однопроходный алгоритм, использующий только константную дополнительную память?
Пример 1:
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Пример 2:
Input: nums = [2,0,1]
Output: [0,1,2]
Ограничения:
n == nums.length
1 <= n <= 300
nums[i] is either 0, 1, or 2.
НАШ ЧАТ АЛГОРИТМИСТОВ
Сборник алгоритмический задач с собесов
Решение
Базовое решение: двухпроходный алгоритм с сортировкой подсчётом. При первом проходе - подсчитываем кол-во 0, 1 и 2. При втором - перезаписываем массив, помещая сначала все 0, затем все 1 и, наконец, все 2.
Сложность такого алгоритма: O(n) - по времени (проходим по массиву два раза) и O(1) - по памяти (храним только три переменные, перезаписываем массив in-place).
Однако, предлагаю реализовать решение с использованием однопроходного алгоритма (follow-up). Для этой задачи подойдёт алгоритм "Национальный флаг Нидерландов", использующийся для сортировки массива с тремя различными значениями за один проход.
Основная идея в разделении массива на три части (по типу цветовых границ на флаге) и использовании трёх указателей:
low (сначала равен нулю) - отслеживает границу, где должны заканчиваться 0;
mid (сначала равен нулю) - проходит по массиву слева направо;
high (сначала равен len(nums) - 1) - отслеживает границу, где должны начинаться 2.
Идём по массиву указателем mid, пока mid <=high:
Если текущий элемент равен 0: меняем его местами с элементом под индексом low и увеличиваем значения обоих указателей;
Если текущий элемент равен 1: оставляем его на месте и сдвигаем указатель mid вперёд;
Иначе, если текущий элемент равен 2: меняем его местами с элементом под индексом high и уменьшаем значение указателя high. Указатель mid не сдвигается, так как нужно проверить эл-т, который пришёл из правой части.
Сложность
O(n) - по времени
O(1) - по памяти
Код
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
low, mid = 0, 0
high = len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[mid], nums[low] = nums[low], nums[mid]
mid += 1
low += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
@algoses
Дан массив nums, состоящий из n объектов, окрашенных в красный, белый и синий цвета. Отсортируйте их in-place так, чтобы объекты одного цвета оказались соседними, следуя порядку: красные, белые, синие.
Будем использовать целые числа 0, 1 и 2 для обозначения красного, белого и синего, соответственно.
Решите задачу без использования встроенной функции сортировки.
Follow up: можете ли вы реализовать однопроходный алгоритм, использующий только константную дополнительную память?
Пример 1:
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Пример 2:
Input: nums = [2,0,1]
Output: [0,1,2]
Ограничения:
n == nums.length
1 <= n <= 300
nums[i] is either 0, 1, or 2.
НАШ ЧАТ АЛГОРИТМИСТОВ
Сборник алгоритмический задач с собесов
Решение
Сложность такого алгоритма: O(n) - по времени (проходим по массиву два раза) и O(1) - по памяти (храним только три переменные, перезаписываем массив in-place).
Однако, предлагаю реализовать решение с использованием однопроходного алгоритма (follow-up). Для этой задачи подойдёт алгоритм "Национальный флаг Нидерландов", использующийся для сортировки массива с тремя различными значениями за один проход.
Основная идея в разделении массива на три части (по типу цветовых границ на флаге) и использовании трёх указателей:
low (сначала равен нулю) - отслеживает границу, где должны заканчиваться 0;
mid (сначала равен нулю) - проходит по массиву слева направо;
high (сначала равен len(nums) - 1) - отслеживает границу, где должны начинаться 2.
Идём по массиву указателем mid, пока mid <=high:
Если текущий элемент равен 0: меняем его местами с элементом под индексом low и увеличиваем значения обоих указателей;
Если текущий элемент равен 1: оставляем его на месте и сдвигаем указатель mid вперёд;
Иначе, если текущий элемент равен 2: меняем его местами с элементом под индексом high и уменьшаем значение указателя high. Указатель mid не сдвигается, так как нужно проверить эл-т, который пришёл из правой части.
Сложность
O(1) - по памяти
Код
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
low, mid = 0, 0
high = len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[mid], nums[low] = nums[low], nums[mid]
mid += 1
low += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
@algoses
🔥11❤3😁1
В новом ролике обсудим изи темку, как получать офферы на 10 000$. Смотрим! Смотрим!
https://www.youtube.com/watch?v=ovYjaPpV6pw
https://www.youtube.com/watch?v=ovYjaPpV6pw
😁10❤1
Задача с собеседования в Zopsmart
Дана входная строка s. Переверните порядок слов в ней.
Слово определяется как последовательность символов, не являющихся пробелами. Слова в s будут разделены хотя бы одним пробелом.
Верните строку, содержащую слова в обратном порядке, объединённые одним пробелом.
Обратите внимание, что строка s может содержать начальные или конечные пробелы, или несколько пробелов между двумя словами. В возвращаемой строке должен быть только один пробел между словами. Не включайте каких-либо лишних пробелов.
Follow-up: если строковый тип данных - изменяемый в вашем языке, можете ли вы решить задачу in-place c O(1) дополнительной памяти?
Пример 1:
Input: s = "the sky is blue"
Output: "blue is sky the"
Пример 2:
Input: s = " hello world "
Output: "world hello"
Пример 3:
Input: s = "a good example"
Output: "example good a"
Ограничения:
1 <= s.length <= 10⁴
s содержит буквы английского алфавита (в нижнем и верхнем регистре), цифры и пробелы ' '.
s состоит хотя бы из одного слова.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Так как в питоне строки неизменяемы, мы не можем реализовать решение in-place с O(1) дополнительной памяти.
Преобразуем строку в список строк методом split(), автоматически удаляя лишние пробелы - O(n).
Используем два указателя:
left - индекс первого слова в списке
right - индекс последнего слова
Пока left меньше right:
- меняем местами элементы под индексом left с элементами под индексом right;
- сдвигаем указатели навстречу друг другу.
В конце объединяем слова списка в строку через один пробел и возвращаем её.
Делитесь решением на вашем языке с O(1) дополнительной памяти в комментариях!
Сложность
O(n) - по времени (сплит и обход списка строк)
O(n) - по памяти (храним список строк)
Код
class Solution:
def reverseWords(self, s: str) -> str:
words = s.split()
left, right = 0, len(words) - 1
while left < right:
words[left], words[right] = words[right], words[left]
left += 1
right -= 1
return " ".join(words)
@algoses
Дана входная строка s. Переверните порядок слов в ней.
Слово определяется как последовательность символов, не являющихся пробелами. Слова в s будут разделены хотя бы одним пробелом.
Верните строку, содержащую слова в обратном порядке, объединённые одним пробелом.
Обратите внимание, что строка s может содержать начальные или конечные пробелы, или несколько пробелов между двумя словами. В возвращаемой строке должен быть только один пробел между словами. Не включайте каких-либо лишних пробелов.
Follow-up: если строковый тип данных - изменяемый в вашем языке, можете ли вы решить задачу in-place c O(1) дополнительной памяти?
Пример 1:
Input: s = "the sky is blue"
Output: "blue is sky the"
Пример 2:
Input: s = " hello world "
Output: "world hello"
Пример 3:
Input: s = "a good example"
Output: "example good a"
Ограничения:
1 <= s.length <= 10⁴
s содержит буквы английского алфавита (в нижнем и верхнем регистре), цифры и пробелы ' '.
s состоит хотя бы из одного слова.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Преобразуем строку в список строк методом split(), автоматически удаляя лишние пробелы - O(n).
Используем два указателя:
left - индекс первого слова в списке
right - индекс последнего слова
Пока left меньше right:
- меняем местами элементы под индексом left с элементами под индексом right;
- сдвигаем указатели навстречу друг другу.
В конце объединяем слова списка в строку через один пробел и возвращаем её.
Делитесь решением на вашем языке с O(1) дополнительной памяти в комментариях!
Сложность
O(n) - по памяти (храним список строк)
Код
def reverseWords(self, s: str) -> str:
words = s.split()
left, right = 0, len(words) - 1
while left < right:
words[left], words[right] = words[right], words[left]
left += 1
right -= 1
return " ".join(words)
@algoses
❤5👍4
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
Завтра закончится отбора на стажировку в Т-банк
Если хотите летом выйти на стажировку с высокой зарплатой и опытом работы в bigteche, то подаваться нужно уже сейчас. На наших соответсвующих курсах уже выложен разбор математики и программирования, а на интенсиве по алгоритмам выложен разбор программирования.
📌 Специально к закрытию отбора
Скидка 35% на эти курсы с разборами до 28 апреля включительно.
Также на курсах будет доступно:
📌 Для записи на курс напишите менеджеру
Если хотите летом выйти на стажировку с высокой зарплатой и опытом работы в bigteche, то подаваться нужно уже сейчас. На наших соответсвующих курсах уже выложен разбор математики и программирования, а на интенсиве по алгоритмам выложен разбор программирования.
Скидка 35% на эти курсы с разборами до 28 апреля включительно.
Также на курсах будет доступно:
➡️ разборы контеста Яндекса, Летних школ Яндекса➡️ Сочные пет проекты в портфолио➡️ Огромный банк технических вопросов➡️ Записи реальных собесов и интервью➡️ Помощь с резюме и легендой
Please open Telegram to view this post
VIEW IN TELEGRAM
❤4
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
На наших соответсвующих курсах уже выложен разбор математики и программирования, а на интенсиве по алгоритмам выложен разбор программирования. На все последние 7 часов 35% скидки в честь конца отбора. Все подробности у администратора.
И не сомневаемся, это одна из лучших опций для получения первого опыта в индустрии: можно совмещать с учебой, загрузка от 20 часов в неделю, после нее легко залететь в штат и да, вам даже будут платить за нее! Для участия нужно просто заполнить анкету и решить отбор до 28 апреля. Задания на этот раз несложные (чекаем вот тут), но больше задач, где можно запросто ошибиться, специально сделали такие задачи, чтобы chatgpt путался с условиями и выдавал неправильные ответы и тех, кто спишет эти ответы, просто забанят в системе Т-банка. При этом из-за учебы подается меньше народу, все жесткие ботари заняты учебой, а значит у простых работяг куда больше шансов получить оффер! У топов собесы начнутся в мае, а у работяг в конце июня, когда сессия уже закончилась и есть силы и время, чтобы к ним подготовиться, еще не закончились.
Проходной на собес везде разный и зависит от популярности специальности и кол-во выделенных мест, региона. Где-то проход 350, а где-то 600 за контест. Далее отбор идет по анкете. Командам и HR очень важна ваша мотивация и погруженность в специальность. Будет обидно набрать полный балл за контест, но не заполнить анкету (подробный совет тоже даем участникам наших курсов). Общие советы такие: пишем про курсы, которые проходили и не проходили, фокусируем внимание на курсах от Т-банка. Только помните, что на собесе нужно будет не запутаться в этих выдумках. Обязательно пишем про олимпиадный опыт, даже школьный, от олимпиадников все просто сходят с ума. Пишем образование. Про свои стартапы и телеграмм каналы советую писать осторожно: это может отпугнуть. Подумают, что после года работы в штате вы уйдете строить свой мега успешный бизнес, а работодатель хочет, чтобы вы росли и развивались внутри компании и стали приносить пользу именной ей.
Сразу создаем второй телеграмм канал для работы и учебы с настоящим именем и фамилией, без тупых статусов и аниме на аватаре. Это серьезно очень раздражает рекрутеров. Также с этого аккаунта не пишем никому и некуда никакую неоднозначную ерунду, которая может стать народным достоянием и вас скомпрометировать. Работодателю важно, чтобы вы разделяли корпоративные ценности. Касаемо составления анкеты и резюме более подробно рассказывал в ролике, обязательно посмотрите.
Раньше большинство собесов было похоже на смотрины: команда рассказывала про себя, а вы про себя. Спрашивали мотивацию, бизнес кейс и может немного теории, задачи давали только на какого-нибудь риск аналитика. Сейчас все по-другому: контест не катает только ленивый, поэтому собесе почти всегда дают задачи. На аналитику и мл могут спросить матешу, скл, питон, а на разработчика и мл простенькие алгоритмы. Некоторые из этих заданий можно чекнуть тут, и тут, и тут, и тут, а если вы хотите разбор всех тасков с собесов - бегом на наши курсы.
Более подробно обо всем этом можно посмотреть в видео. Главное помните, что шанс выиграть в этой игре > 90% (по крайней мере, в прошлом году именно таким был процент взятых на стажировку среди наших учеников), если знать правила игры. Серьезно, прошлым летом выпускница нашего курса по аналитике прошла отбор и стала стажером-аналитиком едва закончив 11-ый класс.
@postypashki_old
Please open Telegram to view this post
VIEW IN TELEGRAM
😁3❤1
Forwarded from Поступашки - ШАД, Стажировки и Магистратура
Товарищи, заполняем анкеты если ещё не сделали и приступаем к онлайн-тестированию. Время до 3 мая.
Если сомневаешься, стоит ли пробовать поступать в этом году, то пробуй сейчас. Те, кто откладывают поступление на следующий год, откладывают и дальше. Сейчас лучший момент, чтобы задуматься о своем будущем.
Специально в честь отбора открываем дополнительные места на интенсиве к ШАД с разбором первого этапа. Все участники получают:
Сегодня и завтра на интенсивы скидка 35%
Количество мест ограничено!
Please open Telegram to view this post
VIEW IN TELEGRAM
❤1
Задача с собеседования в Zopsmart
Даны строки s и t длиной m и n, соответственно. Верните минимальную подстроку (подстроку окна) строки s такую, что каждый символ из строки t (включая повторяющиеся) содержится в этом окне. Если такой подстроки не существует, верните пустую строку "".
Тестовые данные составлены таким образом, чтобы ответ был уникальным.
Follow up: можете ли вы найти алгоритм, работающий за O(m + n) по времени?
Пример 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Объяснение: Подстрока минимального окна "BANC" включает символы 'A', 'B' и 'C' из строки t.
Пример 2:
Input: s = "a", t = "a"
Output: "a"
Объяснение: Вся строка s является минимальным окном.
Пример 3:
Input: s = "a", t = "aa"
Output: ""
Объяснение: Обе 'a' из строки t должны быть включены в окно. Поскольку самое большое окно s имеет только одну 'a', возвращаем пустую строку.
Ограничения:
m == s.length
n == t.length
1 <= m, n <= 10⁵
s и t состоят из английских букв верхнего и нижнего регистра.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Используем алгоритм "скользящего окна" с двумя указателями и хэш-таблицу.
Расширяем окно правым указателем, пока не набираем все необходимые символы. Когда окно становится валидным, пробуем сжать его левым указателем, избавляясь от лишних символов, пока окно не перестанет удовлетворять условиям.
Создаём два словаря:
freqT - хранит частоту символов строки t, не изменяется;
freqWindow - хранит частоту символов текущего окна, изменяется при движении указателей.
Заполняем словарь freqT:
- С помощью метода get(ch, 0) возвращаем текущую частоту символа, либо 0, если символ ещё не встречался. Увеличиваем счётчик символа на 1.
Переменные:
need - кол-во уникальных символов в t, которые нужно набрать;
have - кол-во уникальных символов, которые уже есть в текущем окне.
res - индексы минимального найденного окна;
resLen - длина минимального окна (float("inf"), чтобы записать первое валидное окно в кач-ве минимального).
Расширяем окно, проходя по строке s указателем r:
- Добавляем каждый новый символ в словарь freqWindow и увеличиваем его частоту на 1;
- Если текущий символ находится в freqT и после добавления его частота в freqWindow равна требуемой в freqT: увеличиваем have.
Сжимаем окно, пока текущее окно содержит все необходимые символы:
- Сравниваем длину окна с длиной найденного ранее (resLen). Если текущее окно короче: сохраняем его индексы в res и обновляем resLen;
- Так как будем сдвигать левый указатель: текущий символ под его индексом покинет окно - уменьшаем счётчик этого символа в freqWindow на 1;
- Проверяем, осталось ли окно валидным:
если s[l] есть в freqT и кол-во символа в freqWindow меньше, чем необходимо (freqT), значит, мы потеряли один из требуемых уникальных символов - уменьшаем have на 1;
- Сдвигаем левый указатель вправо.
Если have становится меньше need, цикл завершается, мы возвращаемся к расширению окна правым указателем.
Возвращаем срез по сохранённым индексам минимального найденного окна.
Сложность
O(m + n) - по времени (l и r двигаются только вправо и ограничены длиной s - O(m), заполнение freqT по строке t - O(n))
O(1) - по памяти (фиксированное кол-во букв алфавита)
Код
class Solution:
def minWindow(self, s: str, t: str) -> str:
if len(s) < len(t):
return ""
freqT, freqWindow = {}, {}
for ch in t:
freqT[ch] = 1 + freqT.get(ch, 0)
need, have = len(freqT), 0
res, resLen = [-1, -1], float("inf")
l = 0
for r in range(len(s)):
ch = s[r]
freqWindow[ch] = 1 + freqWindow.get(ch, 0)
if ch in freqT and freqWindow[ch] == freqT[ch]:
have += 1
while have == need:
if (r - l + 1) < resLen:
res = [l, r]
resLen = (r - l + 1)
freqWindow[s[l]] -= 1
if s[l] in freqT and freqWindow[s[l]] < freqT[s[l]]:
have -= 1
l += 1
l, r = res
return s[l:r+1] if resLen != float("inf") else ""
@algoses
Даны строки s и t длиной m и n, соответственно. Верните минимальную подстроку (подстроку окна) строки s такую, что каждый символ из строки t (включая повторяющиеся) содержится в этом окне. Если такой подстроки не существует, верните пустую строку "".
Тестовые данные составлены таким образом, чтобы ответ был уникальным.
Follow up: можете ли вы найти алгоритм, работающий за O(m + n) по времени?
Пример 1:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Объяснение: Подстрока минимального окна "BANC" включает символы 'A', 'B' и 'C' из строки t.
Пример 2:
Input: s = "a", t = "a"
Output: "a"
Объяснение: Вся строка s является минимальным окном.
Пример 3:
Input: s = "a", t = "aa"
Output: ""
Объяснение: Обе 'a' из строки t должны быть включены в окно. Поскольку самое большое окно s имеет только одну 'a', возвращаем пустую строку.
Ограничения:
m == s.length
n == t.length
1 <= m, n <= 10⁵
s и t состоят из английских букв верхнего и нижнего регистра.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Расширяем окно правым указателем, пока не набираем все необходимые символы. Когда окно становится валидным, пробуем сжать его левым указателем, избавляясь от лишних символов, пока окно не перестанет удовлетворять условиям.
Создаём два словаря:
freqT - хранит частоту символов строки t, не изменяется;
freqWindow - хранит частоту символов текущего окна, изменяется при движении указателей.
Заполняем словарь freqT:
- С помощью метода get(ch, 0) возвращаем текущую частоту символа, либо 0, если символ ещё не встречался. Увеличиваем счётчик символа на 1.
Переменные:
need - кол-во уникальных символов в t, которые нужно набрать;
have - кол-во уникальных символов, которые уже есть в текущем окне.
res - индексы минимального найденного окна;
resLen - длина минимального окна (float("inf"), чтобы записать первое валидное окно в кач-ве минимального).
Расширяем окно, проходя по строке s указателем r:
- Добавляем каждый новый символ в словарь freqWindow и увеличиваем его частоту на 1;
- Если текущий символ находится в freqT и после добавления его частота в freqWindow равна требуемой в freqT: увеличиваем have.
Сжимаем окно, пока текущее окно содержит все необходимые символы:
- Сравниваем длину окна с длиной найденного ранее (resLen). Если текущее окно короче: сохраняем его индексы в res и обновляем resLen;
- Так как будем сдвигать левый указатель: текущий символ под его индексом покинет окно - уменьшаем счётчик этого символа в freqWindow на 1;
- Проверяем, осталось ли окно валидным:
если s[l] есть в freqT и кол-во символа в freqWindow меньше, чем необходимо (freqT), значит, мы потеряли один из требуемых уникальных символов - уменьшаем have на 1;
- Сдвигаем левый указатель вправо.
Если have становится меньше need, цикл завершается, мы возвращаемся к расширению окна правым указателем.
Возвращаем срез по сохранённым индексам минимального найденного окна.
Сложность
O(1) - по памяти (фиксированное кол-во букв алфавита)
Код
def minWindow(self, s: str, t: str) -> str:
if len(s) < len(t):
return ""
freqT, freqWindow = {}, {}
for ch in t:
freqT[ch] = 1 + freqT.get(ch, 0)
need, have = len(freqT), 0
res, resLen = [-1, -1], float("inf")
l = 0
for r in range(len(s)):
ch = s[r]
freqWindow[ch] = 1 + freqWindow.get(ch, 0)
if ch in freqT and freqWindow[ch] == freqT[ch]:
have += 1
while have == need:
if (r - l + 1) < resLen:
res = [l, r]
resLen = (r - l + 1)
freqWindow[s[l]] -= 1
if s[l] in freqT and freqWindow[s[l]] < freqT[s[l]]:
have -= 1
l += 1
l, r = res
return s[l:r+1] if resLen != float("inf") else ""
@algoses
❤8🔥1
Задача с собеседования в Zopsmart
Дана голова односвязного списка. Разверните список и верните его.
Follow-up: связный список можно развернуть как итеративно, так и рекурсивно. Могли бы вы реализовать оба способа?
Пример 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Пример 2:
Input: head = [1,2]
Output: [2,1]
Пример 3:
Input: head = []
Output: []
Ограничения:
Количество узлов в списке находится в диапазоне [0, 5000].
-5000 <= Node.val <= 5000
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
В односвязном списке каждый узел хранит данные и ссылку на следующий элемент (или None, если узел последний).
Чтобы развернуть список, нужно изменить указатели всех узлов на противоположные.
Итеративно:
reversed_head - голова развёрнутого списка (сначала None, так как развёрнутый список пуст).
head - узел, с которым работаем (текущий обрабатываемый узел исходного списка).
head.next - указатель текущего узла, его направление будем менять.
Идём до конца исходного списка, на каждой итерации обрабатывая head:
- сохраняем узел, следующий за head, в переменную next_node, чтобы не потерять остаток списка после разрыва связи между узлами;
- операция разворота: указатель текущего узла теперь указывает на голову развёрнутой части;
- обновляем голову развёрнутой части: теперь она начинается с текущего узла;
- переходим к сохраненному остатку исходного списка.
В конце возвращаем голову развёрнутого списка.
Сложность:
O(n) - по времени (проходим по списку один раз)
O(1) - по памяти (храним три указателя, разворачиваем ссылки на месте)
Код:
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
reversed_head = None
while head:
next_node = head.next
head.next = reversed_head
reversed_head = head
head = next_node
return reversed_head
Рекурсивно:
Сначала уходим в конец списка, достигая базового случая, а потом идём в обратном порядке, переворачивая указатели.
Базовый случай:
если исходный список пуст или следующий узел отсутствует. Последний узел становится головой развёрнутого списка, рекурсия останавливается.
Рекурсивный случай:
вызываем функцию для остатка исходного списка и получаем reversed_head - последний узел исходного списка, ставший головой (ссылка на него не меняется во время работы алгоритма).
После достижения базового случая поднимаемся по стеку вызовов:
- меняем указатель у узла, следующего за head, на head. Теперь они ссылаются друг на друга;
- разрываем старую связь между узлами: head указывает на None и становится последним узлом в развёрнутой части;
- возвращаем голову развёрнутого списка.
Сложность:
O(n) - по времени (кол-во вызовов равно длине списка)
O(n) - по памяти (рекурсия линейная)
Код:
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next :
return head
reversed_head = self.reverseList( head.next )
head.next.next = head
head.next = None
return reversed_head
@algoses
Дана голова односвязного списка. Разверните список и верните его.
Follow-up: связный список можно развернуть как итеративно, так и рекурсивно. Могли бы вы реализовать оба способа?
Пример 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Пример 2:
Input: head = [1,2]
Output: [2,1]
Пример 3:
Input: head = []
Output: []
Ограничения:
Количество узлов в списке находится в диапазоне [0, 5000].
-5000 <= Node.val <= 5000
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Чтобы развернуть список, нужно изменить указатели всех узлов на противоположные.
Итеративно:
head - узел, с которым работаем (текущий обрабатываемый узел исходного списка).
Идём до конца исходного списка, на каждой итерации обрабатывая head:
- сохраняем узел, следующий за head, в переменную next_node, чтобы не потерять остаток списка после разрыва связи между узлами;
- операция разворота: указатель текущего узла теперь указывает на голову развёрнутой части;
- обновляем голову развёрнутой части: теперь она начинается с текущего узла;
- переходим к сохраненному остатку исходного списка.
В конце возвращаем голову развёрнутого списка.
Сложность:
O(n) - по времени (проходим по списку один раз)
O(1) - по памяти (храним три указателя, разворачиваем ссылки на месте)
Код:
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
reversed_head = None
while head:
next_node =
reversed_head = head
head = next_node
return reversed_head
Рекурсивно:
Базовый случай:
если исходный список пуст или следующий узел отсутствует. Последний узел становится головой развёрнутого списка, рекурсия останавливается.
Рекурсивный случай:
вызываем функцию для остатка исходного списка и получаем reversed_head - последний узел исходного списка, ставший головой (ссылка на него не меняется во время работы алгоритма).
После достижения базового случая поднимаемся по стеку вызовов:
- меняем указатель у узла, следующего за head, на head. Теперь они ссылаются друг на друга;
- разрываем старую связь между узлами: head указывает на None и становится последним узлом в развёрнутой части;
- возвращаем голову развёрнутого списка.
Сложность:
O(n) - по времени (кол-во вызовов равно длине списка)
O(n) - по памяти (рекурсия линейная)
Код:
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not
return head
reversed_head = self.reverseList(
return reversed_head
@algoses
🔥8❤3