Статьи по тегу leetcode на hdhAI.com

Условие задачи:
Даны головы двух отсортированных связных списков 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

Решение задачи #20. Python LeetCode, Valid Parentheses

Задача на проверку корректности скобочных последовательностей в 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

Источник решения: hdhai.com

Решение задачи #19. Python LeetCode, Remove nth node from end of list

Задача на алгоритм для работы со связным списком в 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

Вперед >>