05 · ДВУМЕРНЫЕ ДАННЫЕ

Матрицы

Матрица в Go — слайс слайсов; размеры строк могут различаться.

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

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

Примитивы Go

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

Создание

grid := make([][]int, rows)
for r := range grid {
    grid[r] = make([]int, cols)
}

Каждую строку нужно выделять отдельно.

Направления

dirs := [][2]int{
    {-1, 0}, {1, 0}, {0, -1}, {0, 1},
}

Пары смещений упрощают обход соседей.

ПРАКТИКА

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

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

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

Спиральный обход

Сжимаем четыре границы.

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

solution.go

func spiralOrder(a [][]int) []int {
    top, bottom, left, right := 0, len(a)-1, 0, len(a[0])-1
    out := []int{}
    for top <= bottom && left <= right {
        for c := left; c <= right; c++ { out = append(out, a[top][c]) }; top++
        for r := top; r <= bottom; r++ { out = append(out, a[r][right]) }; right--
        if top <= bottom { for c := right; c >= left; c-- { out = append(out, a[bottom][c]) }; bottom-- }
        if left <= right { for r := bottom; r >= top; r-- { out = append(out, a[r][left]) }; left++ }
    }
    return out
}

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

Обнуление строк и столбцов

Первую строку и колонку используем как маркеры.

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

solution.go

func setZeroes(a [][]int) {
    firstCol := false
    for r := range a {
        if a[r][0] == 0 { firstCol = true }
        for c := 1; c < len(a[0]); c++ {
            if a[r][c] == 0 { a[r][0], a[0][c] = 0, 0 }
        }
    }
    for r := len(a)-1; r >= 0; r-- {
        for c := 1; c < len(a[0]); c++ {
            if a[r][0] == 0 || a[0][c] == 0 { a[r][c] = 0 }
        }
        if firstCol { a[r][0] = 0 }
    }
}

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

Транспонирование

Строки исходной матрицы становятся колонками результата.

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

solution.go

func transpose(a [][]int) [][]int {
    out := make([][]int, len(a[0]))
    for c := range out {
        out[c] = make([]int, len(a))
        for r := range a { out[c][r] = a[r][c] }
    }
    return out
}

ПЕРЕД КОДОМ

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

Проверь пустую матрицу
Не перепутай rows и cols
Отмечай посещённое до добавления в очередь