Реализовать reverse slice

Решение

Reverse slice in-place — это классическая задача на манипуляцию слайсами. Идея: использовать два указателя (two-pointer technique) для обмена элементов с концов.

Подход

1. Инициализируем два указателя: left = 0, right = len(s) - 1
2. Пока left < right:
   • Обмениваем элементы s[left] и s[right]
   • Продвигаем указатели: left++, right--
3. Когда указатели встречаются, слайс развёрнут

Реализация

func reverse(s []int) {
    left := 0
    right := len(s) - 1
    
    for left < right {
        // Обмениваем элементы
        s[left], s[right] = s[right], s[left]
        
        // Продвигаем указатели
        left++
        right--
    }
}

Пошаговый пример

Задача: развернуть [1, 2, 3, 4, 5]

Исходный слайс:
Индексы: 0  1  2  3  4
Элементы:[1, 2, 3, 4, 5]
left=0, right=4

Шаг 1: Обмен s[0] и s[4]
  s[0], s[4] = 5, 1
Результат: [5, 2, 3, 4, 1]
left=1, right=3

Шаг 2: Обмен s[1] и s[3]
  s[1], s[3] = 4, 2
Результат: [5, 4, 3, 2, 1]
left=2, right=2

Условие: left < right? 2 < 2? НЕТ
→ Цикл завершается

Финальный результат: [5, 4, 3, 2, 1]

Анализ сложности

• Временная сложность: O(n) — посещаем каждый элемент один раз (n/2 обменов)
• Пространственная сложность: O(1) — используем только два указателя, не создаём новый слайс

Полный код с примерами

package main

import "fmt"

func reverse(s []int) {
    left := 0
    right := len(s) - 1
    
    for left < right {
        s[left], s[right] = s[right], s[left]
        left++
        right--
    }
}

func main() {
    // Пример 1: нечётное количество элементов
    s1 := []int{1, 2, 3, 4, 5}
    reverse(s1)
    fmt.Println(s1)  // [5, 4, 3, 2, 1]
    
    // Пример 2: чётное количество элементов
    s2 := []int{1, 2, 3, 4}
    reverse(s2)
    fmt.Println(s2)  // [4, 3, 2, 1]
    
    // Пример 3: один элемент
    s3 := []int{42}
    reverse(s3)
    fmt.Println(s3)  // [42]
    
    // Пример 4: пустой слайс
    s4 := []int{}
    reverse(s4)
    fmt.Println(s4)  // []
    
    // Пример 5: два элемента
    s5 := []int{1, 2}
    reverse(s5)
    fmt.Println(s5)  // [2, 1]
}

Вариант с рекурсией

func reverseRecursive(s []int, left, right int) {
    if left >= right {
        return  // базовый случай
    }
    
    // Обмен
    s[left], s[right] = s[right], s[left]
    
    // Рекурсивный вызов
    reverseRecursive(s, left+1, right-1)
}

// Wrapper функция
func reverse(s []int) {
    reverseRecursive(s, 0, len(s)-1)
}

Минус рекурсии: может привести к stack overflow для больших слайсов, поэтому iterative подход предпочтительнее.

Реверс строк (generics в Go 1.18+)

Модернизированная версия с generics:

func reverse[T any](s []T) {
    left := 0
    right := len(s) - 1
    
    for left < right {
        s[left], s[right] = s[right], s[left]
        left++
        right--
    }
}

func main() {
    // Работает со слайсами любого типа
    ints := []int{1, 2, 3, 4, 5}
    reverse(ints)
    fmt.Println(ints)  // [5, 4, 3, 2, 1]
    
    strs := []string{"a", "b", "c"}
    reverse(strs)
    fmt.Println(strs)  // [c b a]
}

Реверс строк (string)

Для строк нужен другой подход (строки immutable):

func reverseString(s string) string {
    runes := []rune(s)  // конвертируем в слайс rune
    left := 0
    right := len(runes) - 1
    
    for left < right {
        runes[left], runes[right] = runes[right], runes[left]
        left++
        right--
    }
    
    return string(runes)  // конвертируем обратно в string
}

func main() {
    s := "hello"
    fmt.Println(reverseString(s))  // olleh
}

Особые случаи

1. Пустой слайс

reverse([]int{})  // ok, ничего не меняется

2. Один элемент

s := []int{42}
reverse(s)  // [42], left=0, right=0, условие 0 < 0 ложно

3. Два элемента

s := []int{1, 2}
reverse(s)  // [2, 1], обмен один раз, затем left=1, right=0

Сравнение подходов

Ключевые выводы

1. Two-pointer technique — стандартный подход для in-place операций
2. Условие left < right — избегает двойного обмена в центре
3. Go multi-assign (a, b = b, a) — удобен для обмена без temp переменной
4. O(1) extra space — достигается благодаря in-place модификации
5. Работает для любых типов — с использованием generics в Go 1.18+

Это фундаментальная техника, используемая во многих алгоритмах (quicksort, two-sum, и т.д.)