Задача: 142. Linked List Cycle II
Сложность: medium

Дана голова связного списка. Верните узел, с которого начинается цикл. Если цикла нет, верните null.

Цикл в связном списке существует, если есть такой узел в списке, до которого можно добраться снова, последовательно следуя по указателю next. Внутренне переменная pos используется для обозначения индекса узла, к которому подключен указатель next последнего узла (индексация с нуля). Она равна -1, если цикла нет. Обратите внимание, что pos не передается в качестве параметра.

Не модифицируйте связный список.

Пример:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

👨‍💻 Алгоритм:

1⃣Инициализация и начало обхода:
Инициализируйте узел указателем на голову связного списка и создайте пустое множество nodes_seen для отслеживания посещенных узлов.
Начните обход со связного списка, перемещая узел на один шаг за раз.

2⃣Проверка на наличие узла в множестве:
Для каждого посещенного узла проверьте, содержится ли он уже в множестве nodes_seen.
Если узел найден в множестве, это означает, что был найден цикл. Верните текущий узел как точку входа в цикл.

3⃣Добавление узла в множество или завершение обхода:
Если узел не найден в nodes_seen, добавьте его в множество и перейдите к следующему узлу.
Если узел становится равным null (конец списка), верните null. В списке нет цикла, так как в случае наличия цикла вы бы застряли в петле и не достигли бы конца списка.

😎 Решение:

type ListNode struct {
    Val  int
    Next *ListNode
}

func detectCycle(head *ListNode) *ListNode {
    nodesSeen := make(map[*ListNode]bool)
    node := head
    for node != nil {
        if _, ok := nodesSeen[node]; ok {
            return node
        } else {
            nodesSeen[node] = true
            node = node.Next
        }
    }
    return nil
}

Ставь 👍 и забирай 📚 Базу знаний

"Ты че, дурак?" – базовая реакция сеньора на тех, кто покупает IT курсы

Дело в том, что онлайн школы создают инкубаторных айтишников, которые в реальных условиях попросту зависнут.

Трушные ребята учатся на жизненных каналах для айтишников. Вот топ-5 от тимлида из Сбера:

⚙️ Технолоджия – для тех, кто хочет быть в курсе новостей в айти

🧠 Ai-чница – способы превратить нейросети в заработок $$$

💻 ИИ тебя заменит! – тенденции айти рынка в связке с нейросетями

4️⃣ Войти в IT – тонны бесплатного обучения для прогеров

😄 IT индус – сборник айти мемов

Задача: 1325. Delete Leaves With a Given Value
Сложность: medium

Дано корневое дерево root и целое число target. Удалите все листовые узлы со значением target.

Обратите внимание, что после удаления листового узла со значением target, если его родительский узел становится листовым узлом и имеет значение target, он также должен быть удален (необходимо продолжать делать это, пока это возможно).

Пример:

Input: root = [1,2,3,2,null,2,4], target = 2
Output: [1,null,3,null,4]
Explanation: Leaf nodes in green with value (target = 2) are removed (Picture in left). 
After removing, new nodes become leaf nodes with value (target = 2) (Picture in center).

👨‍💻 Алгоритм:

1⃣Базовый случай: Если root равен null, верните null, чтобы обработать условия пустого дерева или прохождения за пределы листовых узлов.

2⃣Рекурсивный обход: Выполните обход в постфиксном порядке, чтобы гарантировать обработку всех потомков перед текущим узлом (root):
— Рекурсивно вызовите removeLeafNodes для левого дочернего узла root и обновите левый дочерний узел возвращаемым значением.
— Аналогично, рекурсивно вызовите removeLeafNodes для правого дочернего узла root и обновите правый дочерний узел возвращаемым значением.

3⃣Оценка узла:
— Проверьте, является ли текущий узел root листовым узлом и совпадает ли его значение с target. Если оба условия выполнены, верните null, чтобы эффективно удалить узел, не присоединяя его к родителю.
— Если узел не является листом или не совпадает с target, верните сам root.

😎 Решение

func removeLeafNodes(root *TreeNode, target int) *TreeNode {
    if root == nil {
        return nil
    }

    root.Left = removeLeafNodes(root.Left, target)
    root.Right = removeLeafNodes(root.Right, target)

    if root.Left == nil && root.Right == nil && root.Val == target {
        return nil
    }
    return root
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 126. Word Ladder II
Сложность: hard

Дано beginWord, endWord и wordList. Нужно найти все кратчайшие последовательности преобразования beginWord -> s1 -> s2 -> ... -> sk, где:

- Каждое слово отличается от предыдущего ровно одной буквой.
- Каждое слово есть в wordList.
- Последнее слово sk совпадает с endWord.

Пример:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]  
Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]  

👨‍💻 Алгоритм:

1⃣Добавляем wordList в wordSet для быстрого поиска.

2⃣Запускаем BFS, строим adjList — список смежности, где храним связи между словами.

3⃣Используем backtracking, чтобы восстановить пути от endWord к beginWord.

😎 Решение:

func findLadders(beginWord, endWord string, wordList []string) [][]string {
    adjList := make(map[string][]string)
    wordSet := make(map[string]bool)
    for _, word := range wordList {
        wordSet[word] = true
    }

    bfs(beginWord, wordSet, adjList)
    var currPath []string
    var shortestPaths [][]string
    currPath = append(currPath, endWord)
    backtrack(endWord, beginWord, &currPath, &shortestPaths, adjList)
    return shortestPaths
}

func findNeighbors(word string, wordSet map[string]bool) []string {
    var neighbors []string
    charList := []rune(word)
    for i := range charList {
        oldChar := charList[i]
        for c := 'a'; c <= 'z'; c++ {
            if c != oldChar {
                charList[i] = c
                newWord := string(charList)
                if wordSet[newWord] {
                    neighbors = append(neighbors, newWord)
                }
            }
        }
        charList[i] = oldChar
    }
    return neighbors
}

func backtrack(source, destination string, currPath *[]string, shortestPaths *[][]string, adjList map[string][]string) {
    if source == destination {
        pathCopy := make([]string, len(*currPath))
        copy(pathCopy, *currPath)
        reverse(pathCopy)
        *shortestPaths = append(*shortestPaths, pathCopy)
        return
    }
    for _, neighbor := range adjList[source] {
        *currPath = append(*currPath, neighbor)
        backtrack(neighbor, destination, currPath, shortestPaths, adjList)
        *currPath = (*currPath)[:len(*currPath)-1]
    }
}

func bfs(beginWord string, wordSet map[string]bool, adjList map[string][]string) {
    queue := []string{beginWord}
    visited := make(map[string]bool)
    visited[beginWord] = true

    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]
        neighbors := findNeighbors(current, wordSet)
        for _, neighbor := range neighbors {
            if !visited[neighbor] {
                visited[neighbor] = true
                queue = append(queue, neighbor)
                adjList[neighbor] = append(adjList[neighbor], current)
            }
        }
    }
}

func reverse(slice []string) {
    for i, j := 0, len(slice)-1; i < j; i, j = i+1, j-1 {
        slice[i], slice[j] = slice[j], slice[i]
    }
}

Ставь 👍 и забирай 📚 Базу знаний