08 · FIFO

Очередь

Очередь нужна для BFS и обработки событий в порядке поступления.

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

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

Примитивы Go

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

Слайс + head

queue := []int{start}
for head := 0; head < len(queue); head++ {
    value := queue[head]
}

Индекс головы избегает дорогого сдвига элементов.

Кольцевой буфер

next := (tail + 1) % len(buffer)

Нужен для ограниченной очереди с переиспользованием памяти.

ПРАКТИКА

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

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

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

Среднее по уровням дерева

Размер очереди фиксирует текущий уровень.

O(n) time · O(width) space

solution.go

func averageOfLevels(root *TreeNode) []float64 {
    queue, out := []*TreeNode{root}, []float64{}
    for len(queue) > 0 {
        size, sum := len(queue), 0
        for i := 0; i < size; i++ {
            node := queue[0]; queue = queue[1:]; sum += node.Val
            if node.Left != nil { queue = append(queue, node.Left) }
            if node.Right != nil { queue = append(queue, node.Right) }
        }
        out = append(out, float64(sum)/float64(size))
    }
    return out
}

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

Острова через BFS

Каждую клетку добавляем в очередь один раз.

O(rows · cols) time · O(rows · cols) space

solution.go

func flood(grid [][]byte, sr, sc int) {
    queue := [][2]int{{sr, sc}}; grid[sr][sc] = '0'
    dirs := [][2]int{{1,0},{-1,0},{0,1},{0,-1}}
    for head := 0; head < len(queue); head++ {
        p := queue[head]
        for _, d := range dirs {
            r, c := p[0]+d[0], p[1]+d[1]
            if r >= 0 && r < len(grid) && c >= 0 && c < len(grid[0]) && grid[r][c] == '1' {
                grid[r][c] = '0'; queue = append(queue, [2]int{r,c})
            }
        }
    }
}

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

Последний камень

Приоритетная очередь каждый раз извлекает два максимальных веса.

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

solution.go

func lastStoneWeight(stones []int) int {
    h := MaxHeap(stones)
    heap.Init(&h)
    for h.Len() > 1 {
        first, second := heap.Pop(&h).(int), heap.Pop(&h).(int)
        if first != second { heap.Push(&h, first-second) }
    }
    if h.Len() == 0 { return 0 }
    return h[0]
}

ПЕРЕД КОДОМ

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

Отмечай вершину до enqueue
Обрабатывай уровень через size := len(queue)-head
Не используй append(queue[:0], queue[1:]...)