17 · РЕКУРСИЯ

Разделяй и властвуй

Раздели задачу на независимые части, реши их и объедини результаты.

2 Go-примитива3 примераInterview 150

СНАЧАЛА ИНСТРУМЕНТЫ

Примитивы Go

Минимальный синтаксис, который понадобится в решении.

Срезы

left := nums[:mid]
right := nums[mid:]

Срезы не копируют данные; это полезно, пока части только читаются.

Рекурсия

if small(input) { return base(input) }
return combine(solve(left), solve(right))

Обязательно формулируй уменьшающийся размер задачи.

ПРАКТИКА

Примеры решений

Три идиоматичных решения на Go с оценкой времени и памяти.

ПРИМЕР РЕШЕНИЯ

Сортировка списка

Делим fast/slow и сливаем отсортированные половины.

O(n log n) time · O(log n) stack

solution.go

func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil { return head }
    slow, fast := head, head.Next
    for fast != nil && fast.Next != nil { slow, fast = slow.Next, fast.Next.Next }
    right := slow.Next; slow.Next = nil
    return mergeLists(sortList(head), sortList(right))
}

ПРИМЕР РЕШЕНИЯ

Построение BST

Середина сортированного массива становится корнем.

O(n) time · O(log n) stack

solution.go

func sortedArrayToBST(nums []int) *TreeNode {
    if len(nums) == 0 { return nil }
    mid := len(nums)/2
    return &TreeNode{
        Val: nums[mid],
        Left: sortedArrayToBST(nums[:mid]),
        Right: sortedArrayToBST(nums[mid+1:]),
    }
}

ПРИМЕР РЕШЕНИЯ

Быстрая степень

Результат для половины степени используется дважды.

O(log n) time · O(log n) space

solution.go

func power(x float64, n int) float64 {
    if n == 0 { return 1 }
    half := power(x, n/2)
    if n%2 == 0 { return half*half }
    return half*half*x
}

ПЕРЕД КОДОМ

Чек-лист рассуждения

Части независимы?
Какова стоимость combine
Можно ли переиспользовать буфер