Алгоритмы - Связанные списки | Деревья

Этот код реализует функцию isPalindrome, которая проверяет, является ли связанный список палиндромом (читается одинаково слева направо и справа налево).

Алгоритм решения

1. Проверка базовых случаев:
   • Если список пустой или содержит только один элемент, возвращаем true
2. Нахождение середины списка:
   • Используется техника "быстрого и медленного" указателей
3. Разворот второй половины списка:
   • Используется вспомогательная функция reverseList
4. Сравнение первой и развернутой второй половины:
   • Проходим по обеим половинам, сравнивая значения узлов

• Временная сложность: O(n)
  • Где n - количество узлов в списке
  • Алгоритм проходит по списку дважды: один раз для нахождения середины и разворота, второй раз для сравнения
• Пространственная сложность: O(1)
  • Используется постоянное количество дополнительной памяти, независимо от размера входного списка

type ListNode struct {
	Val  int
	Next *ListNode
}

func isPalindrome(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return true
	}

	// Находим середину списка
	slow, fast := head, head
	for fast.Next != nil && fast.Next.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}

	// Разворачиваем вторую половину списка
	secondHalf := reverseList(slow.Next)

	// Сравниваем первую и вторую половины
	firstHalf := head
	for secondHalf != nil {
		if firstHalf.Val != secondHalf.Val {
			return false
		}
		firstHalf = firstHalf.Next
		secondHalf = secondHalf.Next
	}

	return true
}

// reverseList разворачивает связанный список
func reverseList(head *ListNode) *ListNode {
	var prev *ListNode
	current := head
	for current != nil {
		nextTemp := current.Next
		current.Next = prev
		prev = current
		current = nextTemp
	}
	return prev
}
                                        

Код реализует функцию isSymmetric, которая проверяет, является ли заданное бинарное дерево симметричным. Дерево считается симметричным, если левое и правое поддеревья являются зеркальными отражениями друг друга.

Алгоритм решения

1. Определение структуры узла дерева:
   • Структура TreeNode содержит значение узла и указатели на левого и правого потомков
2. Функция isSymmetric:
   • Проверяет корневой узел на nil
   • Вызывает вспомогательную функцию isMirror для левого и правого поддеревьев
3. Функция isMirror:
   • Рекурсивно сравнивает левое и правое поддеревья
   • Проверяет три условия:
     1. Оба узла nil (симметричны)
     2. Только один узел nil (не симметричны)
     3. Значения узлов равны и их поддеревья симметричны

• Временная сложность: O(n)
  • Где n - количество узлов в дереве
  • Каждый узел посещается ровно один раз
• Пространственная сложность: O(h)
  • Где h - высота дерева
  • В худшем случае (несбалансированное дерево) может достигать O(n)
  • Обусловлена рекурсивными вызовами на стеке

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// isSymmetric проверяет, является ли бинарное дерево симметричным
func isSymmetric(root *TreeNode) bool {
	if root == nil {
		return true
	}
	return isMirror(root.Left, root.Right)
}

// isMirror рекурсивно проверяет, являются ли два поддерева зеркальными отражениями друг друга
func isMirror(left, right *TreeNode) bool {
	// Если оба узла nil, они симметричны
	if left == nil && right == nil {
		return true
	}
	// Если только один из узлов nil, они не симметричны
	if left == nil || right == nil {
		return false
	}
	// Проверяем, равны ли значения узлов и симметричны ли их поддеревья
	return (left.Val == right.Val) &&
		isMirror(left.Left, right.Right) &&
		isMirror(left.Right, right.Left)
}
                                        

Функция addTwoNumbers складывает два числа, представленных в виде связанных списков, где каждый узел содержит одну цифру, а цифры расположены в обратном порядке.

Алгоритм решения

1. Инициализация:
   • Создание фиктивного узла для результирующего списка
   • Инициализация переменной для переноса
2. Итерация по спискам:
   • Суммирование соответствующих цифр из обоих списков и переноса
   • Вычисление новой цифры результата и нового значения переноса
   • Создание нового узла в результирующем списке
   • Переход к следующим узлам входных списков
3. Продолжение итерации, пока есть цифры в любом из списков или есть перенос
4. Возврат результирующего списка (без фиктивного начального узла)

• Временная сложность: O(max(n, m))
  • n и m - длины входных списков
  • Один проход по более длинному из двух списков
• Пространственная сложность: O(max(n, m))
  • Создание нового списка для хранения результата
  • Длина результата может быть максимум на один узел больше, чем длина более длинного входного списка

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	dummy := &ListNode{0, nil}
	current := dummy
	carry := 0

	for l1 != nil || l2 != nil || carry != 0 {
		sum := carry
		if l1 != nil {
			sum += l1.Val
			l1 = l1.Next
		}
		if l2 != nil {
			sum += l2.Val
			l2 = l2.Next
		}
		carry = sum / 10
		current.Next = &ListNode{sum % 10, nil}
		current = current.Next
	}

	return dummy.Next
}

type ListNode struct {
	Val  int
	Next *ListNode
}
                                        

Функция mergeKLists объединяет K отсортированных связанных списков в один отсортированный список. Для эффективного решения используется структура данных "куча" (heap).

Алгоритм решения

1. Определение структуры данных:
   • ListNode для представления узлов связанного списка
   • MinHeap как срез указателей на ListNode
2. Реализация интерфейса heap для MinHeap:
   • Методы Len, Less, Swap, Push, Pop
3. Алгоритм объединения:
   • Инициализация кучи и добавление первых узлов каждого списка
   • Итеративное извлечение наименьшего элемента из кучи
   • Добавление извлеченного элемента в результирующий список
   • Добавление следующего узла из того же списка в кучу, если он существует

• Временная сложность: O(N log K)
  • N - общее количество узлов во всех списках
  • K - количество списков
  • log K - сложность операций с кучей размера K
• Пространственная сложность: O(K)
  • K - размер кучи, которая содержит по одному узлу из каждого списка

type ListNode struct {
	Val  int
	Next *ListNode
}

type MinHeap []*ListNode

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(*ListNode))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func mergeKLists(lists []*ListNode) *ListNode {
	h := &MinHeap{}
	heap.Init(h)

	// Добавляем первый узел каждого списка в кучу
	for _, list := range lists {
		if list != nil {
			heap.Push(h, list)
		}
	}

	dummy := &ListNode{}
	current := dummy

	// Извлекаем наименьший элемент из кучи и добавляем его в результирующий список
	for h.Len() > 0 {
		smallest := heap.Pop(h).(*ListNode)
		current.Next = smallest
		current = current.Next

		if smallest.Next != nil {
			heap.Push(h, smallest.Next)
		}
	}

	return dummy.Next
}
                                        

Функция mergeTwoLists объединяет два отсортированных связанных списка в один отсортированный список. Она использует рекурсивный подход для решения задачи.

Алгоритм решения

1. Проверка базовых случаев:
   • Если первый список пуст, возвращаем второй список
   • Если второй список пуст, возвращаем первый список
2. Сравнение значений текущих узлов обоих списков:
   • Если значение узла первого списка меньше или равно значению узла второго списка:
     • Рекурсивно вызываем функцию для следующего узла первого списка и всего второго списка
     • Присоединяем результат к текущему узлу первого списка
   • Иначе:
     • Рекурсивно вызываем функцию для всего первого списка и следующего узла второго списка
     • Присоединяем результат к текущему узлу второго списка
3. Возвращаем узел с меньшим значением

• Временная сложность: O(n + m)
  • n - длина первого списка
  • m - длина второго списка
  • Каждый узел обрабатывается ровно один раз
• Пространственная сложность: O(n + m)
  • В худшем случае (при несбалансированном рекурсивном дереве вызовов) может достигать O(n + m)
  • Это связано с глубиной рекурсии, которая может быть равна сумме длин списков

type ListNode struct {
	Val  int
	Next *ListNode
}

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	if list1 == nil {
		return list2
	}
	if list2 == nil {
		return list1
	}

	if list1.Val <= list2.Val {
		list1.Next = mergeTwoLists(list1.Next, list2)
		return list1
	} else {
		list2.Next = mergeTwoLists(list1, list2.Next)
		return list2
	}
}
                                        

Функция removeNthFromEnd удаляет N-й узел с конца односвязного списка.

Алгоритм решения

1. Создание фиктивного узла (dummy node):
   • Упрощает обработку случая удаления первого элемента
2. Использование двух указателей:
   • first: продвигается на N+1 узлов вперед
   • second: остается в начале
3. Продвижение указателей:
   • Оба указателя двигаются вперед, пока first не достигнет конца списка
4. Удаление узла:
   • second указывает на узел перед удаляемым
   • Перенаправление указателя Next для удаления нужного узла

• Временная сложность: O(L)
  • L - длина списка
  • Один проход по списку
• Пространственная сложность: O(1)
  • Использование только нескольких дополнительных указателей
  • Не зависит от размера входного списка

type ListNode struct {
	Val  int
	Next *ListNode
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	// Создаем фиктивный узел, чтобы упростить обработку случая удаления первого элемента
	dummy := &ListNode{Next: head}

	// Инициализируем два указателя
	first := dummy
	second := dummy

	// Продвигаем первый указатель на n узлов вперед
	for i := 0; i <= n; i++ {
		first = first.Next
	}

	// Двигаем оба указателя, пока первый не достигнет конца
	for first != nil {
		first = first.Next
		second = second.Next
	}

	// Удаляем n-ый узел с конца
	second.Next = second.Next.Next

	return dummy.Next
}
                                        

Функция reverseList разворачивает односвязный список, изменяя направление всех указателей.

Алгоритм решения

1. Проверка на пустой список:
   • Если список пуст, возвращаем nil
2. Инициализация указателей:
   • prev: изначально null
   • current: указывает на голову списка
3. Итерация по списку:
   • Сохранение следующего узла во временной переменной
   • Изменение указателя текущего узла на предыдущий
   • Перемещение указателей prev и current вперед
4. Возврат нового начала списка (бывший последний элемент)

• Временная сложность: O(n)
  • n - количество узлов в списке
  • Один проход по всем элементам списка
• Пространственная сложность: O(1)
  • Использование фиксированного количества дополнительных переменных
  • Не зависит от размера входного списка

type ListNode struct {
    Val  int
    Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
    // Проверка на пустой список
    if head == nil {
        return nil
    }

    var prev *ListNode
    current := head

    for current != nil {
        nextTemp := current.Next
        current.Next = prev
        prev = current
        current = nextTemp
    }

    return prev
}
                                        

Код реализует две основные функции:

• serialize: преобразует бинарное дерево поиска в строку
• deserialize: восстанавливает бинарное дерево поиска из строки

Алгоритм решения

Сериализация:

1. Использует обход дерева в глубину (DFS) в порядке предварительного обхода (preorder)
2. Преобразует значения узлов в строки
3. Соединяет значения запятыми

• Временная сложность: O(n), где n - количество узлов в дереве
• Пространственная сложность: O(n) для хранения результирующей строки

Десериализация:

1. Разбивает входную строку на массив значений
2. Использует рекурсивную функцию для восстановления дерева
3. Применяет свойство BST для определения границ значений при построении

• Временная сложность: O(n), где n - количество узлов в дереве
• Пространственная сложность: O(n) для хранения массива значений и рекурсивного стека

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

type Codec struct{}

func Constructor() Codec {
    return Codec{}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
    if root == nil {
        return ""
    }
    var result []string
    var dfs func(*TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        result = append(result, strconv.Itoa(node.Val))
        dfs(node.Left)
        dfs(node.Right)
    }
    dfs(root)
    return strings.Join(result, ",")
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
    if data == "" {
        return nil
    }
    values := strings.Split(data, ",")
    var index int
    var build func(min, max int) *TreeNode
    build = func(min, max int) *TreeNode {
        if index >= len(values) {
            return nil
        }
        val, _ := strconv.Atoi(values[index])
        if val < min || val > max {
            return nil
        }
        index++
        node := &TreeNode{Val: val}
        node.Left = build(min, val-1)
        node.Right = build(val+1, max)
        return node
    }
    return build(math.MinInt, math.MaxInt)
}
                                        

Функция isValidBST проверяет, является ли заданное бинарное дерево корректным бинарным деревом поиска (BST).

Алгоритм решения

1. Использует рекурсивный подход для обхода дерева
2. Для каждого узла проверяет, находится ли его значение в допустимом диапазоне
3. Рекурсивно проверяет левое и правое поддеревья, обновляя границы допустимого диапазона

Детали реализации:

• Функция isValidBST инициирует проверку с максимально возможным диапазоном значений
• Функция validateBST выполняет рекурсивную проверку:
  • Проверяет, не является ли узел пустым (базовый случай)
  • Проверяет, находится ли значение узла в допустимом диапазоне
  • Рекурсивно проверяет левое и правое поддеревья с обновленными границами

• Временная сложность: O(n), где n - количество узлов в дереве
  • Каждый узел посещается ровно один раз
• Пространственная сложность: O(h), где h - высота дерева
  • В худшем случае (несбалансированное дерево) может достигать O(n)
  • В среднем случае для сбалансированного дерева будет O(log n)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func isValidBST(root *TreeNode) bool {
    return validateBST(root, math.MinInt64, math.MaxInt64)
}

func validateBST(node *TreeNode, min, max int) bool {
    if node == nil {
        return true
    }

    if node.Val <= min || node.Val >= max {
        return false
    }

    return validateBST(node.Left, min, node.Val) && validateBST(node.Right, node.Val, max)
}
                                        

Дано бинарное дерево, где каждая вершина содержит букву от 'a' до 'z'. Необходимо найти две вершины, поддеревья которых содержат одинаковый набор букв, и сумма вершин в этих поддеревьях максимальна.

Алгоритм решения

1. Выполняем обход дерева в глубину (DFS).
2. Для каждой вершины:
   • Рекурсивно обрабатываем левое и правое поддерево.
   • Объединяем информацию о буквах из левого и правого поддерева.
   • Добавляем букву текущей вершины.
   • Создаем уникальный ключ, представляющий набор букв в поддереве.
   • Сохраняем сумму вершин для данного ключа.
   • Если найден одинаковый набор букв, обновляем результат при необходимости.
3. Возвращаем результат с максимальной суммой и одной из вершин.

• Временная сложность: O(N), где N - количество вершин в дереве. Каждая вершина обрабатывается один раз.
• Пространственная сложность: O(N), в худшем случае, когда все вершины имеют уникальные наборы букв в своих поддеревьях.

// Node представляет узел в бинарном дереве
type Node struct {
    Value byte  // Значение узла (буква от 'a' до 'z')
    Left  *Node // Левый дочерний узел
    Right *Node // Правый дочерний узел
}

// Result хранит результат поиска максимально равных узлов
type Result struct {
    MaxSum   int   // Максимальная сумма вершин в поддеревьях
    MaxNode1 *Node // Первый узел с максимальной суммой
    MaxNode2 *Node // Второй узел с максимальной суммой (не используется в текущей реализации)
}

// findMaxEqualNodes находит две равные вершины с максимальной суммой вершин в их поддеревьях
func findMaxEqualNodes(root *Node) Result {
    result := Result{}
    letterCounts := make(map[string][]int) // Карта для хранения сумм вершин для каждого уникального набора букв

    var dfs func(*Node) (int, map[byte]int)
    dfs = func(node *Node) (int, map[byte]int) {
        if node == nil {
            return 0, make(map[byte]int)
        }

        // Рекурсивно обходим левое и правое поддерево
        leftSum, leftLetters := dfs(node.Left)
        rightSum, rightLetters := dfs(node.Right)

        // Вычисляем сумму вершин в текущем поддереве
        sum := leftSum + rightSum + 1

        // Объединяем буквы из левого и правого поддеревьев
        letters := make(map[byte]int)
        for k, v := range leftLetters {
            letters[k] += v
        }
        for k, v := range rightLetters {
            letters[k] += v
        }
        letters[node.Value]++ // Добавляем текущую букву

        // Создаем ключ из набора букв
        key := mapToString(letters)
        letterCounts[key] = append(letterCounts[key], sum)

        // Проверяем, есть ли равные поддеревья с большей суммой
        if len(letterCounts[key]) >= 2 {
            maxSum := letterCounts[key][len(letterCounts[key])-1] + letterCounts[key][len(letterCounts[key])-2]
            if maxSum > result.MaxSum {
                result.MaxSum = maxSum
                result.MaxNode1 = node
                // Здесь мы не можем точно определить второй узел, но это не требуется по условию задачи
            }
        }

        return sum, letters
    }

    dfs(root)
    return result
}

// mapToString преобразует карту букв и их количества в строковое представление
func mapToString(m map[byte]int) string {
    result := ""
    for i := byte('a'); i <= 'z'; i++ {
        if count, exists := m[i]; exists {
            result += fmt.Sprintf("%c%d", i, count)
        }
    }
    return result
}
                                        

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

Алгоритм решения

1. Определяем структуру TreeNode для представления узла бинарного дерева.
2. Реализуем функцию diameterOfBinaryTree, которая находит диаметр дерева:
   • Инициализируем переменную diameter для хранения максимального диаметра.
   • Определяем вложенную функцию dfs для поиска в глубину.
3. Функция dfs выполняет следующие действия:
   • Если узел nil, возвращаем 0.
   • Рекурсивно вызываем dfs для левого и правого поддеревьев.
   • Обновляем diameter, если сумма высот левого и правого поддеревьев больше текущего диаметра.
   • Возвращаем максимальную высоту текущего поддерева + 1.
4. Вызываем dfs для корня дерева.
5. Возвращаем найденный диаметр.

• Временная сложность: O(n), где n - количество узлов в дереве. Алгоритм посещает каждый узел ровно один раз.
• Пространственная сложность: O(h), где h - высота дерева. Это обусловлено рекурсивными вызовами на стеке. В худшем случае (для несбалансированного дерева) может достигать O(n).

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

// diameterOfBinaryTree находит диаметр бинарного дерева
func diameterOfBinaryTree(root *TreeNode) int {
    diameter := 0

    // dfs выполняет поиск в глубину и возвращает высоту поддерева
    var dfs func(*TreeNode) int
    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }

        leftHeight := dfs(node.Left)
        rightHeight := dfs(node.Right)

        // Обновляем диаметр, если текущий путь длиннее
        diameter = max(diameter, leftHeight+rightHeight)

        // Возвращаем высоту текущего поддерева
        return max(leftHeight, rightHeight) + 1
    }

    dfs(root)
    return diameter
}