Задача на алгоритм для работы со связным списком в Python. Требуется удалить N-й узел с конца односвязного списка, сохранив структуру данных. Задача проверяет умение эффективно манипулировать связными списками с использованием алгоритма двух указателей (fast and slow), который решает проблему за один проход без дополнительной памяти.
Вариант решения задачи на Python с LeetCode
Категория: Алгоритмы.
Название задачи: Remove nth node from end of list.
Сложность: Средняя.
Статус решения: "Решено".
Условие задачи:
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Решение:
Python
# Определение узла связного списка
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
# Создаем фиктивный узел, чтобы упростить удаление первого элемента
dummy = ListNode(0)
dummy.next = head
# Инициализируем два указателя: fast и slow
fast = dummy
slow = dummy
# Перемещаем fast на n узлов вперед
for _ in range(n + 1):
fast = fast.next
# Перемещаем fast до конца списка, slow будет отставать на n узлов
while fast is not None:
slow = slow.next
fast = fast.next
# Удаляем n-й узел с конца
slow.next = slow.next.next
# Возвращаем новый head списка (исключая фиктивный узел)
return dummy.next
Объяснение кода
Фиктивный узел (dummy):
Используется для упрощения обработки случая, когда нужно удалить первый элемент списка.
dummy.next указывает на head списка.
Два указателя (fast и slow):
fast сначала перемещается на n + 1 шагов вперед, чтобы между fast и slow образовался разрыв в n узлов.
Затем оба указателя двигаются вместе, пока fast не достигнет конца списка.
В этот момент slow окажется перед узлом, который нужно удалить.
Удаление узла:
Когда slow находится перед n-м узлом с конца, мы просто перебрасываем ссылку slow.next через удаляемый узел (slow.next = slow.next.next).
Это исключает узел из списка.
Возврат результата:
Возвращаем dummy.next, так как head мог измениться (если удалялся первый элемент).
Пример работы:
head =
[1,2,3,4,5]
n =
2
Output
[1,2,3,5]
Expected
[1,2,3,5]
Мы рассмотрели пример решения, который был принят и засчитан платформой как правильный, но вы можете найти свой способ решения задачи, возможно лучше.
Источник решения: hdhai.com
Задача относится к алгоритмам и структуре данных. Надо найти все уникальные четверки целых чисел из заданного массива nums, сумма которых равна целевому значению target. Четверки должны состоять из элементов с различных индексов, а результат не должен содержать дубликатов. Задача требует эффективного поиска и обработки повторяющихся значений.
Вариант решения задачи на Python с LeetCode
Категория: Алгоритмы.
Название задачи: 4sum.
Сложность: Средняя.
Статус решения: "Решено".
Условие задачи:
Дан массив nums из n целых чисел. Верните массив всех уникальных четверок [nums[a], nums[b], nums[c], nums[d]], таких что:
0 <= a, b, c, d < n
Индексы a, b, c и d попарно различны.
Сумма nums[a] + nums[b] + nums[c] + nums[d] равна target.
Вы можете вернуть ответ в любом порядке.
Решение:
Python
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
res = [] # Здесь будем хранить результат — все уникальные четверки
nums.sort() # Сортируем массив для удобства работы с дубликатами и двухуказательным методом
n = len(nums)
for i in range(n): # Первый элемент четверки
# Пропускаем дубликаты для первого элемента
if i > 0 and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, n): # Второй элемент четверки
# Пропускаем дубликаты для второго элемента
if j > i + 1 and nums[j] == nums[j - 1]:
continue
# Двухуказательный метод для поиска оставшихся двух чисел
left = j + 1
right = n - 1
while left < right:
total = nums[i] + nums[j] + nums[left] + nums[right]
if total == target:
res.append([nums[i], nums[j], nums[left], nums[right]])
# Пропускаем дубликаты для left
while left < right and nums[left] == nums[left + 1]:
left += 1
# Пропускаем дубликаты для right
while left < right and nums[right] == nums[right - 1]:
right -= 1
# Переходим к следующей паре
left += 1
right -= 1
elif total < target:
left += 1 # Увеличиваем сумму, двигая left вправо
else:
right -= 1 # Уменьшаем сумму, двигая right влево
return res
Объяснение кода
Это расширение задачи Two Sum → Three Sum → Four Sum. Мы хотим найти все уникальные четверки чисел, сумма которых равна заданному target.
Сортировка:
Чтобы можно было легко убирать дубликаты и использовать двухуказательный метод.
Два внешних цикла:
i — первый элемент четверки.
j — второй элемент четверки.
После выбора этих двух элементов мы используем двухуказательный метод (left, right) для поиска оставшихся двух чисел.
Удаление дубликатов:
Проверяем, не повторяются ли значения предыдущих итераций для i и j.
Также пропускаем повторяющиеся left и right, если они уже были учтены.
Двухуказательный метод:
Если текущая сумма равна target — добавляем четверку в результат.
Если меньше — двигаем left вправо.
Если больше — двигаем right влево.
Сложность алгоритма
Временная сложность:
O(n^3) — из-за трёх вложенных циклов (i, j, и двухуказательный поиск).
Пространственная сложность:
O(1) дополнительной памяти (если игнорировать память под результат).
Мы рассмотрели пример решения, который был принят и засчитан платформой как правильный, но вы можете найти свой способ решения задачи, возможно лучше.
Источник решения: hdhai.com
Вариант решения задачи на Python с LeetCode
Категория: Алгоритмы.
Название задачи: Python LeetCode, Letter Combinations of a Phone Number.
Сложность: Средняя.
Статус решения: "Решено".
Задача относится к алгоритмическим задачам на комбинаторику и рекурсивный перебор (backtracking).
Условие задачи:
Дана строка, содержащая цифры от 2 до 9 включительно. Нужно вернуть все возможные буквенные комбинации, которые могут быть представлены этим числом, согласно стандартному сопоставлению цифр и букв на кнопках телефона. Ответ можно вернуть в любом порядке.
Решение:
Python
class Solution(object):
def letterCombinations(self, digits):
"""
Функция возвращает все возможные комбинации букв, соответствующие цифрам на телефонной клавиатуре.
:type digits: str - входная строка с цифрами от 2 до 9
:rtype: List[str] - список строк с комбинациями букв
"""
# Проверяем пустой ввод
if not digits:
return []
# Создаем словарь соответствия цифр буквам
digit_map = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
}
# Инициализируем список для хранения результатов
result = []
# Рекурсивная функция для генерации комбинаций
def backtrack(index, current_str):
"""
Вспомогательная функция для рекурсивного перебора комбинаций.
:param index: int - текущий индекс в строке digits
:param current_str: str - текущая формируемая строка
"""
# Если достигли конца цифр, добавляем комбинацию в результат
if index == len(digits):
result.append(current_str)
return
# Получаем текущую цифру и соответствующие ей буквы
current_digit = digits[index]
letters = digit_map[current_digit]
# Перебираем все буквы и рекурсивно вызываем функцию для следующей цифры
for letter in letters:
backtrack(index + 1, current_str + letter)
# Запускаем рекурсию с начальными параметрами
backtrack(0, "")
return result
Объяснение кода
Проверка ввода:
Сначала проверяем, не пустая ли строка digits. Если пустая - сразу возвращаем пустой список.
Словарь соответствий:
Создаем словарь digit_map, где каждой цифре от 2 до 9 соответствуют буквы, как на телефонной клавиатуре:
2: abc
3: def
4: ghi
5: jkl
6: mno
7: pqrs
8: tuv
9: wxyz
Рекурсивная функция backtrack:
Базовый случай:
Когда индекс достигает длины строки digits, текущая комбинация добавляется в результат.
Рекурсивный случай:
Для текущей цифры берем все соответствующие буквы и для каждой буквы рекурсивно вызываем функцию для следующей цифры, добавляя текущую букву к строке.
Запуск рекурсии:
Начинаем процесс с индекса 0 и пустой строки.
Возврат результата:
После завершения всех рекурсивных вызовов возвращаем накопленный результат.
Пример использования:
Python
sol = Solution()
print(sol.letterCombinations("23"))
# Вывод: ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
Особенности решения
Используется метод backtracking (возврат с проверкой)
Временная сложность:
O(3^N × 4^M), где N - количество цифр с 3 буквами, M - с 4 буквами
Пространственная сложность:
O(N) для хранения рекурсивного стека вызовов
Решение соответствует стилю задач LeetCode с использованием класса Solution и эффективно перебирает все возможные комбинации, используя рекурсию, является классическим подходом к подобным задачам на комбинаторику.
Мы рассмотрели пример решения, который был принят и засчитан платформой как правильный, но вы можете найти свой способ решения задачи, возможно лучше.
Источник решения: hdhai.com