01 · ОСНОВЫ

Массивы и строки

Слайсы, строки и техника изменения данных на месте — база почти каждой задачи.

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

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

Примитивы Go

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

Слайс

nums := []int{1, 2, 3}
nums = append(nums, 4)
part := nums[1:3]

len и cap работают за O(1); append иногда перевыделяет массив.

Строки

bytes := []byte("hello")
runes := []rune("привет")
var b strings.Builder

byte — для ASCII, rune — для Unicode, Builder — для сборки.

Копия

clone := append([]int(nil), nums...)
// или
clone = slices.Clone(nums)

Обычный subslice разделяет память с исходным слайсом.

ПРАКТИКА

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

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

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

Удаление дублей

Держим границу уникальной части массива.

O(n) time · O(1) space

solution.go

func removeDuplicates(nums []int) int {
    write := 0
    for _, n := range nums {
        if write == 0 || nums[write-1] != n {
            nums[write] = n
            write++
        }
    }
    return write
}

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

Общий префикс

Постепенно укорачиваем первый элемент.

O(n · m) time · O(1) space

solution.go

func longestCommonPrefix(words []string) string {
    prefix := words[0]
    for _, word := range words[1:] {
        for !strings.HasPrefix(word, prefix) {
            prefix = prefix[:len(prefix)-1]
        }
    }
    return prefix
}

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

Разворот слов

Разбиваем строку по пробелам и собираем слова в обратном порядке.

O(n) time · O(n) space

solution.go

func reverseWords(s string) string {
    words := strings.Fields(s)
    for left, right := 0, len(words)-1; left < right; left, right = left+1, right-1 {
        words[left], words[right] = words[right], words[left]
    }
    return strings.Join(words, " ")
}

ПЕРЕД КОДОМ

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

Уточни: ASCII или Unicode
Следи за границами полуинтервала [l, r)
Проверь, можно ли менять входной массив