Задача на работу со связными списками и указателями.
Вариант решения задачи на Python с LeetCode
Категория: Алгоритмы.
Название задачи: Merge two sorted lists.
Сложность: Легкая.
Статус решения: "Решено".
Условие задачи:
Даны головы двух отсортированных связных списков list1 и list2. Объедините эти два списка в один отсортированный список. Новый список должен быть составлен путем соединения узлов исходных списков (без создания новых узлов). Верните голову объединенного связного списка.
Примечания:
Оба списка list1 и list2 уже отсортированы в порядке неубывания. Нельзя создавать новые узлы, нужно только переставлять указатели next существующих узлов.
Решение:
Python
# Определение узла связного списка
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val # Значение узла
self.next = next # Ссылка на следующий узел
class Solution(object):
def mergeTwoLists(self, list1, list2):
"""
Объединяет два отсортированных связных списка в один отсортированный список.
Аргументы:
list1: Голова первого связного списка
list2: Голова второго связного списка
Возвращает:
Голову объединенного отсортированного связного списка
"""
# Создаем фиктивный узел для упрощения кода
dummy = ListNode(-1)
# Указатель для построения нового списка
current = dummy
# Пока в обоих списках есть элементы
while list1 is not None and list2 is not None:
# Сравниваем значения текущих узлов
if list1.val <= list2.val:
current.next = list1 # Добавляем узел из list1
list1 = list1.next # Перемещаем указатель list1
else:
current.next = list2 # Добавляем узел из list2
list2 = list2.next # Перемещаем указатель list2
current = current.next # Перемещаем указатель current
# Добавляем оставшиеся элементы из list1 или list2
if list1 is not None:
current.next = list1
else:
current.next = list2
# Возвращаем голову нового списка (пропускаем фиктивный узел)
return dummy.next
Мы рассмотрели пример решения, который был принят и засчитан платформой LeetCode как правильный, но вы можете найти свой способ решения задачи, возможно лучше.
Источник решения: hdhai.com
Задача на проверку корректности скобочных последовательностей в Python. Это классическая алгоритмическая задача на использование стека, часто встречающаяся на собеседованиях в IT-компаниях.
Вариант решения задачи на Python с LeetCode
Категория: Алгоритмы.
Название задачи: Valid Parentheses.
Сложность: Легкая.
Статус решения: "Решено".
Условие задачи:
Дана строка s, состоящая только из символов '(', ')', '{', '}', '[' и ']'. Определите, является ли входная строка допустимой.
Входная строка считается допустимой, если:
Каждая открывающая скобка должна быть закрыта скобкой того же типа.
Например, () — допустимо, (] — нет.
Скобки должны закрываться в правильном порядке.
Например, ({}) — допустимо, ({)} — нет.
Каждая закрывающая скобка должна иметь соответствующую открывающую скобку того же типа.
Например, ()[]{} — допустимо, (] — нет.
Решение:
Python
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
# Создаем словарь для соответствия открывающих и закрывающих скобок
brackets_map = {')': '(', '}': '{', ']': '['}
# Создаем стек для хранения открывающих скобок
stack = []
# Проходим по каждому символу в строке
for char in s:
# Если символ - закрывающая скобка
if char in brackets_map:
# Извлекаем последнюю открывающую скобку из стека
# Если стек пуст, используем заглушку
top_element = stack.pop() if stack else '#'
# Проверяем соответствие скобок
if brackets_map[char] != top_element:
return False
else:
# Если символ - открывающая скобка, добавляем в стек
stack.append(char)
# Строка валидна, если стек пуст в конце
return not stack
Мы рассмотрели пример решения, который был принят и засчитан платформой LeetCode как правильный, но вы можете найти свой способ решения задачи, возможно лучше.
Источник решения: hdhai.com
Задача на алгоритм для работы со связным списком в 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