// Здесь реализован односвязный список в таком случае родительский элемент ссылается на дочерний,
// зная родительский элемент мы можем получить дочерний, но зная дочерний не можем получить родительский
// не обойдя весь список сначала.
 
package linkedlist
 
import (
    "fmt"
)
 
// compile-time проверка что LinkedList реализует List
// Это хитрый трюк Go — присваивание в _ (blank identifier)
// которое компилятор проверяет но не выполняет в runtime.
// компилятор видит присваивание и проверяет что правая часть
// реализует интерфейс левой части. Если какой-то метод не реализован — ошибка компиляции
var _ List[struct{}] = (*LinkedList[struct{}])(nil)
 
// List — интерфейс односвязного списка
type List[T comparable] interface {
    // PushFront добавляет элемент в начало списка — O(1)
    PushFront(val T)
 
    // PushBack добавляет элемент в конец списка — O(n)
    PushBack(val T)
 
    // PopFront удаляет и возвращает первый элемент — O(1)
    // Возвращает false если список пуст
    PopFront() (T, bool)
 
    // PopBack удаляет и возвращает последний элемент — O(n)
    // Возвращает false если список пуст
    PopBack() (T, bool)
 
    // PeekFront возвращает первый элемент без удаления — O(1)
    PeekFront() (T, bool)
 
    // PeekBack возвращает последний элемент без удаления — O(n)
    PeekBack() (T, bool)
 
    // Insert вставляет элемент по индексу — O(n)
    Insert(index int, val T) error
 
    // Remove удаляет элемент по индексу — O(n)
    Remove(index int) (T, error)
 
    // Len возвращает количество элементов — O(1)
    Len() int
 
    // Contains проверяет наличие элемента — O(n)
    Contains(val T) bool
 
    // ToSlice возвращает все элементы в виде среза — O(n)
    ToSlice() []T
}
 
// Node — элемент односвязного списка
type Node[T comparable] struct {
    // Значение для хранения
    val T
    // Ссылка на последующий элемент
    next *Node[T]
}
 
// LinkedList — односвязный список
type LinkedList[T comparable] struct {
    // Ссылка на головной элемент
    head *Node[T]
    // Ссылка на хвостовой элемент
    tail *Node[T]
    // Длинна списка
    len int
}
 
// Вставляем значение в начало списка
func (l *LinkedList[T]) PushFront(val T) {
 
    // Инициируем новый элемент списка
    node := Node[T]{
        val: val,
    }
 
    // Ошибок мы не предполагаем поэтому счетчик увеличиваем сразу
    l.len++
 
    // Если список пустой
    if l.head == nil {
 
        // Устанавливаем в head ссылку на инициированный элемент
        l.head = &node
 
        // Устанавливаем в tail ссылку на инициированный элемент
        l.tail = &node
 
        // Закончили упражнение
        return
    }
 
    // Если код дошел до сюда список не пуст
    // Полю next нового элемента присваиваем ссылку на текущий элемент head
    node.next = l.head
 
    // Заменяем элемент head новым элементом
    l.head = &node
}
 
// Вставляем значение в конец списка
func (l *LinkedList[T]) PushBack(val T) {
 
    // Увеличиваем счетчик элементов
    l.len++
 
    // Инициируем новый элемент списка
    node := Node[T]{
        val: val,
    }
 
    // Если список пустой
    if l.head == nil {
 
        // Устанавливаем в head ссылку на инициированный элемент
        l.head = &node
 
        // Устанавливаем в tail ссылку на инициированный элемент
        l.tail = &node
 
        // Закончили упражнение
        return
    }
 
    // Значению поля next хвостового элемента присваиваем ссылку на новый элемент
    l.tail.next = &node
 
    // Значению поля tail списка присваиваем ссылку на новый хвостовой элемент
    l.tail = &node
 
}
 
// Извлекаем значение головного элемента
func (l *LinkedList[T]) PopFront() (T, bool) {
 
    // Если список пуст возвращаем Т, false
    if l.head == nil {
        var zero T
        return zero, false
    }
 
    // Если код дошел сюда то список не пуст
    value := l.head.val
 
    // Уменьшаем счетчик элементов
    l.len--
 
    // Если это был крайний элемент
    if l.head.next == nil {
        // В head устанавливаем ссылку на nil
        l.head = nil
        // В tail устанавливаем ссылку на nil
        l.tail = nil
    } else { // В этом случае есть еще элементы
        // Меняем ссылку головного элемента списка на ссылку на следующий элемент
        l.head = l.head.next
    }
 
    // Возвращаем значение и true
    return value, true
}
 
// Извлекаем значение хвостового элемента
func (l *LinkedList[T]) PopBack() (T, bool) {
    // Если список пуст возвращаем Т, false
    if l.head == nil {
        var zero T
        return zero, false
    }
 
    // Если код дошел сюда то список не пуст
    value := l.tail.val
 
    // Уменьшаем счетчик элементов
    l.len--
 
    // Если в списке один элемент
    if l.head.next == nil {
        // Удаляем головной элемент
        l.head = nil
        // Удаляем хвостовой элемент
        l.tail = nil
        // Возвращаем значение и true
        return value, true
    }
 
    // Тут надо перебрать весь список чтобы получить адрес предпоследнего элемента
    // ересь конечно, но оставлю этот метод
 
    // currentNode содержит текущий элемент при обходе
    // начинаем с головного элемента
    currentNode := l.head
 
    // обходим список пока у следующего за текущим элементом поле next не окажется пустым
    for currentNode.next.next != nil {
        // Присваиваем текущему элементу обхода следующий элемент
        currentNode = currentNode.next
    }
 
    // Когда цикл будет пройден до конца currentNode будет содержать предпоследний элемент,
    // Удаляем в нем ссылку на последний элемент
    currentNode.next = nil
 
    // Присваиваем его хвостовому элементу
    l.tail = currentNode
 
    // Возвращаем значение и true
    return value, true
}
 
// PeekFront возвращает значение головного элемента не извлекая его
func (l *LinkedList[T]) PeekFront() (T, bool) {
 
    // Если список пуст возвращаем Т, false
    if l.head == nil {
        var zero T
        return zero, false
    }
 
    // Возвращаем значение головного элемента
    return l.head.val, true
}
 
// PeekBack возвращает значение хвостового элемента не извлекая его
func (l *LinkedList[T]) PeekBack() (T, bool) {
 
    // Если список пуст возвращаем Т, false
    if l.head == nil {
        var zero T
        return zero, false
    }
 
    // Возвращаем значение хвостового элемента
    return l.tail.val, true
}
 
// Insert вставляет значение на определенный индекс списка
func (l *LinkedList[T]) Insert(index int, val T) error {
 
    // Проверяем что индекс вписывается в диапазон существующих значений
    if index < 0 || index > l.len {
        return ErrIndexOutOfRange
    }
 
    // Если индекс 0 пользуемся методом PushFront
    if index == 0 {
        l.PushFront(val)
        return nil
    }
 
    // если индекс равен длине списка то используем PushBack
    if index == l.len {
        l.PushBack(val)
        return nil
    }
 
    // Если код дошел до сюда то индекс внутри списка
    // Получаем предыдущий элемент
    currentNode := l.nodeAt(index - 1)
 
    // Создаем новый элемент
    newNode := Node[T]{
        val:  val,
        next: currentNode.next, // тут ссылка на элемент который нашли при обходе
    }
 
    // Меняем ссылку
    currentNode.next = &newNode
 
    // Увеличиваем счетчик
    l.len++
 
    // Возвращаем nil
    return nil
}
 
// Remove удаляет элемент из списка
func (l *LinkedList[T]) Remove(index int) (T, error) {
 
    // Проверяем корректность индекса
    if index < 0 || index >= l.len {
        var zero T
        return zero, ErrIndexOutOfRange
    }
 
    // При индексе 0 выполняем PopFront
    if index == 0 {
        val, _ := l.PopFront()
        return val, nil
    }
 
    // При хвостовом индексе удаляем PopBack
    if index == l.len-1 {
        val, _ := l.PopBack()
        return val, nil
    }
 
    // В списке больше одного элемента, индекс в середине
    prevNode := l.nodeAt(index - 1)
    val := prevNode.next.val
    prevNode.next = prevNode.next.next
    l.len--
    return val, nil
}
 
// nodeAt возвращает узел по индексу
func (l *LinkedList[T]) nodeAt(index int) *Node[T] {
    currentNode := l.head
    for i := 0; i < index; i++ {
        currentNode = currentNode.next
    }
    return currentNode
}
 
// Len возвращает длину списка
func (l *LinkedList[T]) Len() int {
    return l.len
}
 
func (l *LinkedList[T]) Contains(val T) bool {
    if l.len == 0 {
        return false
    }
    for currentNode := l.head; currentNode != nil; currentNode = currentNode.next {
        if currentNode.val == val {
            return true
        }
    }
    return false
}
 
func (l *LinkedList[T]) ToSlice() []T {
 
    slice := make([]T, 0, l.len)
 
    for currentNode := l.head; currentNode != nil; currentNode = currentNode.next {
        slice = append(slice, currentNode.val)
    }
 
    return slice
}
 
// sentinel error-ы
var (
    ErrEmptyList       = fmt.Errorf("linkedlist: list is empty")
    ErrIndexOutOfRange = fmt.Errorf("linkedlist: index out of range")
)

package linkedlist
 
import (
    "testing"
 
    "github.com/stretchr/testify/assert"
)
 
func TestPushFrontAndToSlice(t *testing.T) {
    l := &LinkedList[int]{}
    l.PushFront(3)
    l.PushFront(2)
    l.PushFront(1)
    assert.Equal(t, []int{1, 2, 3}, l.ToSlice())
}
 
func TestPushBack(t *testing.T) {
    l := &LinkedList[int]{}
    l.PushBack(1)
    l.PushBack(2)
    l.PushBack(3)
    assert.Equal(t, []int{1, 2, 3}, l.ToSlice())
}
 
func TestPopFront(t *testing.T) {
    l := &LinkedList[int]{}
    l.PushBack(1)
    l.PushBack(2)
    l.PushBack(3)
 
    val, ok := l.PopFront()
    assert.True(t, ok)
    assert.Equal(t, 1, val)
    assert.Equal(t, []int{2, 3}, l.ToSlice())
}
 
func TestPopFrontEmpty(t *testing.T) {
    l := &LinkedList[int]{}
    _, ok := l.PopFront()
    assert.False(t, ok)
}
 
func TestPopBack(t *testing.T) {
    l := &LinkedList[int]{}
    l.PushBack(1)
    l.PushBack(2)
    l.PushBack(3)
 
    val, ok := l.PopBack()
    assert.True(t, ok)
    assert.Equal(t, 3, val)
    assert.Equal(t, []int{1, 2}, l.ToSlice())
}
 
func TestPopBackEmpty(t *testing.T) {
    l := &LinkedList[int]{}
    _, ok := l.PopBack()
    assert.False(t, ok)
}
 
func TestPeekFront(t *testing.T) {
    l := &LinkedList[int]{}
    l.PushBack(1)
    l.PushBack(2)
 
    val, ok := l.PeekFront()
    assert.True(t, ok)
    assert.Equal(t, 1, val)
    assert.Equal(t, 2, l.Len()) // peek не удаляет
}
 
func TestPeekBack(t *testing.T) {
    l := &LinkedList[int]{}
    l.PushBack(1)
    l.PushBack(2)
 
    val, ok := l.PeekBack()
    assert.True(t, ok)
    assert.Equal(t, 2, val)
    assert.Equal(t, 2, l.Len()) // peek не удаляет
}
 
func TestInsert(t *testing.T) {
    l := &LinkedList[int]{}
    l.PushBack(1)
    l.PushBack(3)
 
    err := l.Insert(1, 2) // [1, 2, 3]
    assert.NoError(t, err)
    assert.Equal(t, []int{1, 2, 3}, l.ToSlice())
}
 
func TestInsertAtHead(t *testing.T) {
    l := &LinkedList[int]{}
    l.PushBack(2)
    l.PushBack(3)
 
    err := l.Insert(0, 1) // [1, 2, 3]
    assert.NoError(t, err)
    assert.Equal(t, []int{1, 2, 3}, l.ToSlice())
}
 
func TestInsertAtTail(t *testing.T) {
    l := &LinkedList[int]{}
    l.PushBack(1)
    l.PushBack(2)
 
    err := l.Insert(2, 3) // [1, 2, 3]
    assert.NoError(t, err)
    assert.Equal(t, []int{1, 2, 3}, l.ToSlice())
}
 
func TestInsertOutOfRange(t *testing.T) {
    l := &LinkedList[int]{}
    l.PushBack(1)
 
    err := l.Insert(5, 99)
    assert.ErrorIs(t, err, ErrIndexOutOfRange)
}
 
func TestRemove(t *testing.T) {
    l := &LinkedList[int]{}
    l.PushBack(1)
    l.PushBack(2)
    l.PushBack(3)
 
    val, err := l.Remove(1) // удаляем 2
    assert.NoError(t, err)
    assert.Equal(t, 2, val)
    assert.Equal(t, []int{1, 3}, l.ToSlice())
}
 
func TestRemoveHead(t *testing.T) {
    l := &LinkedList[int]{}
    l.PushBack(1)
    l.PushBack(2)
 
    val, err := l.Remove(0)
    assert.NoError(t, err)
    assert.Equal(t, 1, val)
    assert.Equal(t, []int{2}, l.ToSlice())
}
 
func TestRemoveOutOfRange(t *testing.T) {
    l := &LinkedList[int]{}
    l.PushBack(1)
 
    _, err := l.Remove(5)
    assert.ErrorIs(t, err, ErrIndexOutOfRange)
}
 
func TestLen(t *testing.T) {
    l := &LinkedList[int]{}
    assert.Equal(t, 0, l.Len())
    l.PushBack(1)
    l.PushBack(2)
    assert.Equal(t, 2, l.Len())
    l.PopFront()
    assert.Equal(t, 1, l.Len())
}
 
func TestContains(t *testing.T) {
    l := &LinkedList[int]{}
    l.PushBack(1)
    l.PushBack(2)
    l.PushBack(3)
 
    assert.True(t, l.Contains(2))
    assert.False(t, l.Contains(99))
}
 
func TestToSliceEmpty(t *testing.T) {
    l := &LinkedList[int]{}
    assert.Equal(t, []int{}, l.ToSlice())
}

package binaryHeap
 
import "errors"
 
var ErrEmptyHeap = errors.New("heap is empty")
 
// Интерфейс двоичной кучи
type BinaryHeap interface {
    Push(n int)
    Pop() (int, error)
    Peek() (int, error)
    Len() int
    IsEmpty() bool
}
 
// binaryHeap структура двоичной кучи
type binaryHeap struct {
    data []int
}
 
// NewBinaryHeap возвращает новый экземпляр структуры BinaryHeap
func NewBinaryHeap() BinaryHeap {
    return &binaryHeap{
        data: make([]int, 0, 16),
    }
}
 
// Push добавляет элемент в двоичную кучу
func (h *binaryHeap) Push(n int) {
 
    // Добавляем в конец массива элемент
    h.data = append(h.data, n)
 
    // Фиксируем индекс элемента для просеивания вверх
    currentIndex := len(h.data) - 1
 
    // Цикл к корню кучи
    for currentIndex > 0 {
 
        // Находим индекс родительского элемента
        parentIndex := (currentIndex - 1) / 2
 
        // Если родительский элемент больше
        if h.data[parentIndex] > h.data[currentIndex] {
 
            // Меняем местами с текущим
            h.data[parentIndex], h.data[currentIndex] = h.data[currentIndex], h.data[parentIndex]
 
            // Изменяем индекс текущего элемента на индекс родительского элемента
            currentIndex = parentIndex
        } else { // Если родительский элемент не больше
            break // прерываем цикл
        }
    }
}
 
// Pop извлекает корневой элемент из бинарной кучи
func (h *binaryHeap) Pop() (int, error) {
 
    // Если куча пуста возвращаем 0 и ошибку
    if len(h.data) == 0 {
        return 0, ErrEmptyHeap
    }
 
    // Забираем элемент для возврата
    returnValue := h.data[0]
 
    // На его место вставляем крайний элемент
    h.data[0] = h.data[len(h.data)-1]
 
    // Обрезаем слайс
    h.data = h.data[:len(h.data)-1]
 
    // Устанавливаем 0 как индекс просматриваемого элемента
    currentIndex := 0
 
    // Просеиваем вниз
    for {
        leftChildIndex := 2*currentIndex + 1
        if leftChildIndex >= len(h.data) {
            break
        }
        rightChildIndex := 2*currentIndex + 2
 
        // выбираем наименьшего ребёнка
        smallestIndex := leftChildIndex
        if rightChildIndex < len(h.data) && h.data[rightChildIndex] < h.data[leftChildIndex] {
            smallestIndex = rightChildIndex
        }
 
        // если текущий элемент уже меньше — стоп
        if h.data[currentIndex] <= h.data[smallestIndex] {
            break
        }
 
        h.data[currentIndex], h.data[smallestIndex] = h.data[smallestIndex], h.data[currentIndex]
        currentIndex = smallestIndex
    }
 
    return returnValue, nil
}
 
// Peek Возвращает элемент в корне кучи
func (h *binaryHeap) Peek() (int, error) {
    if len(h.data) == 0 {
        return 0, ErrEmptyHeap
    }
    return h.data[0], nil
}
 
// Len возвращает длину двоичной кучи
func (h *binaryHeap) Len() int {
    return len(h.data)
}
 
// IsEmpty возвращает true если куча пуста, иначе false
func (h *binaryHeap) IsEmpty() bool {
    return len(h.data) == 0
}

package binaryHeap
 
import (
    "errors"
    "testing"
)
 
func TestPeekOnEmptyHeap(t *testing.T) {
    h := NewBinaryHeap()
    _, err := h.Peek()
    if err == nil {
        t.Error("expected error on empty heap")
    }
}
 
func TestPopOnEmptyHeap(t *testing.T) {
    h := NewBinaryHeap()
    _, err := h.Pop()
    if err == nil {
        t.Error("expected error on empty heap")
    }
}
 
func TestIsEmptyOnNewHeap(t *testing.T) {
    h := NewBinaryHeap()
    if !h.IsEmpty() {
        t.Error("expected new heap to be empty")
    }
}
 
func TestLenOnNewHeap(t *testing.T) {
    h := NewBinaryHeap()
    if h.Len() != 0 {
        t.Errorf("expected len 0, got %d", h.Len())
    }
}
 
func TestPushSingleElement(t *testing.T) {
    h := NewBinaryHeap()
    h.Push(42)
 
    if h.IsEmpty() {
        t.Error("expected heap to be non-empty after Push")
    }
    if h.Len() != 1 {
        t.Errorf("expected len 1, got %d", h.Len())
    }
 
    val, err := h.Peek()
    if err != nil {
        t.Fatalf("unexpected error: %v", err)
    }
    if val != 42 {
        t.Errorf("expected 42, got %d", val)
    }
}
 
func TestPushMultipleElementsPeekReturnsMin(t *testing.T) {
    h := NewBinaryHeap()
    h.Push(30)
    h.Push(10)
    h.Push(20)
 
    val, err := h.Peek()
    if err != nil {
        t.Fatalf("unexpected error: %v", err)
    }
    if val != 10 {
        t.Errorf("expected min 10, got %d", val)
    }
}
 
func TestPopReturnsSortedOrder(t *testing.T) {
    h := NewBinaryHeap()
    input := []int{50, 10, 40, 20, 30}
    for _, v := range input {
        h.Push(v)
    }
 
    expected := []int{10, 20, 30, 40, 50}
    for _, want := range expected {
        got, err := h.Pop()
        if err != nil {
            t.Fatalf("unexpected error: %v", err)
        }
        if got != want {
            t.Errorf("expected %d, got %d", want, got)
        }
    }
}
 
func TestPopDecreasesLen(t *testing.T) {
    h := NewBinaryHeap()
    h.Push(1)
    h.Push(2)
    h.Push(3)
 
    h.Pop()
    if h.Len() != 2 {
        t.Errorf("expected len 2, got %d", h.Len())
    }
}
 
func TestIsEmptyAfterPopAll(t *testing.T) {
    h := NewBinaryHeap()
    h.Push(1)
    h.Pop()
 
    if !h.IsEmpty() {
        t.Error("expected heap to be empty after popping all elements")
    }
}
 
func TestPeekDoesNotRemoveElement(t *testing.T) {
    h := NewBinaryHeap()
    h.Push(5)
 
    h.Peek()
    if h.Len() != 1 {
        t.Errorf("expected len 1 after Peek, got %d", h.Len())
    }
}
 
func TestErrorType(t *testing.T) {
    h := NewBinaryHeap()
    _, err := h.Pop()
    if !errors.Is(err, ErrEmptyHeap) {
        t.Errorf("expected ErrEmptyHeap, got %v", err)
    }
}

graph := map[int][]int{
    0: {1, 5},  // Из вершины 0 можно перейти в вершины 1 и 5
    1: {2, 6},  // Из вершины 1 можно перейти в вершины 2 и 6
    2: {3, 7},  // Из вершины 2 можно перейти в вершины 3 и 7
    3: {4, 8},  // Из вершины 3 можно перейти в вершины 4 и 8
    4: {0, 9},  // Из вершины 4 можно перейти в вершины 0 и 9
    5: {7},     // Из вершины 5 можно перейти в вершину 7
    7: {9},     // Из вершины 7 можно перейти в вершину 9
    9: {6},     // Из вершины 9 можно перейти в вершину 6
    6: {8},     // Из вершины 6 можно перейти в вершину 8
    8: {5},     // Из вершины 8 можно перейти в вершину 5
}

// breadthFirstSearch выполняет обход графа в ширину (BFS), начиная с указанной вершины.
//
// Параметры:
//   - graph: граф, представленный в виде map[int][]int, где ключ — вершина,
//     а значение — срез смежных вершин (направленные или ненаправленные рёбра).
//   - start: начальная вершина, с которой начинается обход.
//
// Возвращаемое значение:
//   - []int: порядок обхода вершин в ширину.
//
// Особенности:
//   - Функция использует множество visited (map[int]struct{}{}) для отслеживания
//     уже посещённых вершин, что предотвращает зацикливание и повторный обход.
//   - Обход выполняется итеративно с использованием очереди (queue).
//   - Если граф содержит недостижимые из start вершины, они не будут включены в результат.
//   - Функция корректно работает как с направленными, так и с ненаправленными графами
//     (при условии корректного задания смежных вершин).
func breadthFirstSearch(graph map[int][]int, start int) []int {
 
    // visited — Heshset посещённых вершин.
    // Используем map[int]struct{}{}, а не map[int]bool, потому что:
    // - struct{}{} занимает 0 байт (экономия памяти)
    // - это идиоматичный способ реализации set в Go
    // - явно показывает, что значение не имеет смысла, важен только ключ
    visited := map[int]struct{}{}
 
    // queue — очередь для обхода в ширину (BFS).
    // Используем срез []int как очередь FIFO (First-In-First-Out):
    // - добавление в конец: queue = append(queue, node)
    // - извлечение из начала: currentNode := queue[0]; queue = queue[1:]
    queue := []int{start}
 
    // visited[start] = struct{}{} — отмечаем начальную вершину как посещённую.
    // Добавляем в множество (hash set) до помещения в очередь, чтобы избежать повторного добавления.
    // struct{}{} — пустая структура, занимающая 0 байт (экономия памяти).
    // Альтернатива с true была бы visited[start] = true, но struct{}{} — идиоматичный способ для set в Go.
    visited[start] = struct{}{}
 
    // path — результирующий срез для хранения вершин в порядке обхода BFS.
    // Nil-срез (нулевое значение), память выделится динамически при первом append.
    var path []int
 
    // Продолжаем обход, пока очередь не опустеет.
    // Условие len(queue) > 0 — идиоматичный способ проверить, есть ли элементы в очереди на основе среза.
    // Пустая очередь означает, что все достижимые вершины обработаны.
    for len(queue) > 0 {
 
        // Берём вершину из начала очереди (принцип FIFO для BFS).
        currentNode := queue[0]
 
        // Удаляем первый элемент из очереди (сдвигаем начало среза).
        // queue[1:] создаёт новый срез, указывающий на те же данные, но без первого элемента.
        // Это эквивалент операции "dequeue" в очереди FIFO.
        queue = queue[1:]
 
        // Добавляем текущую вершину в результат обхода.
        // Порядок добавления соответствует порядку посещения вершин (BFS order).
        // append автоматически расширит срез при необходимости.
        path = append(path, currentNode)
 
        // Перебираем всех соседей (смежные вершины) текущей вершины.
        // graph[currentNode] возвращает срез всех вершин, в которые можно перейти из currentNode.
        // _ — игнорируем индекс, используем только значение (саму вершину-соседа).
        for _, childNode := range graph[currentNode] {
 
            // Проверяем, не посещали ли мы уже эту вершину.
            // _, ok — comma ok идиома для проверки существования ключа в map.
            // ok == true — вершина уже в множестве (посещена).
            // !ok — вершина ещё не посещена, значит можно добавить в очередь.
            if _, ok := visited[childNode]; !ok {
 
                // Отмечаем соседнюю вершину как посещённую.
                // Делаем это ДО добавления в очередь, чтобы избежать дублирования.
                // Если отметить после добавления, вершина может попасть в очередь несколько раз.
                visited[childNode] = struct{}{}
 
                // Добавляем не посещённого соседа в конец очереди.
                // Теперь он будет обработан после всех текущих вершин (FIFO).
                // Это и есть суть BFS — сначала обрабатываем вершины на текущем уровне, потом на следующем.
                queue = append(queue, childNode)
            }
        }
    }
    return path
}

func TestBreadthFirstSearch(t *testing.T) {
    testCases := []struct {
        desc     string
        graph    map[int][]int
        start    int
        expected []int
    }{
        {
            desc: "binary tree",
            graph: map[int][]int{
                0: {1, 2},
                1: {3, 4},
                2: {5, 6},
                3: {},
                4: {},
                5: {},
                6: {},
            },
            start:    0,
            expected: []int{0, 1, 2, 3, 4, 5, 6},
        },
        {
            desc: "peterson graph",
            graph: map[int][]int{
                0: {1, 5},
                1: {2, 6},
                2: {3, 7},
                3: {4, 8},
                4: {0, 9},
                5: {7},
                7: {9},
                9: {6},
                6: {8},
                8: {5},
            },
            start:    0,
            expected: []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
        },
        {
            desc: "single node",
            graph: map[int][]int{
                0: {},
            },
            start:    0,
            expected: []int{0},
        },
        {
            desc: "linear chain",
            graph: map[int][]int{
                0: {1},
                1: {2},
                2: {3},
                3: {},
            },
            start:    0,
            expected: []int{0, 1, 2, 3},
        },
    }
    for _, tC := range testCases {
        t.Run(tC.desc, func(t *testing.T) {
            result := breadthFirstSearch(tC.graph, tC.start)
 
            got := make([]int, len(result))
            copy(got, result)
            exp := make([]int, len(tC.expected))
            copy(exp, tC.expected)
 
            slices.Sort(got)
            slices.Sort(exp)
 
            if !reflect.DeepEqual(got, exp) {
                t.Errorf("breadthFirstSearch (%v, start=%d): expected %v, got %v", tC.graph, tC.start, tC.expected, result)
            }
        })
    }
}

// ConcurrentBFSQueries обходит граф конкурентно из нескольких вершин queries
func ConcurrentBFSQueries(graph map[int][]int, queries []int, numWorkers int) map[int][]int {
 
    // К заданию был тест с нулевым количеством воркунов который должен вернуть map[int][]int{}
    // поэтому просто оставлю это тут
    if numWorkers == 0 {
        return map[int][]int{}
    }
 
    // Приметив синхронизации WaitGroup
    // используется для того чтобы дождаться выполнения всех параллельных
    // горутин и двигаться дальше
    var wg sync.WaitGroup
 
    // Приметив синхронизации Mutex, реализация дефолтного map потоко не безопасна
    // использую Mutex для безлопастной конкурентной работы с map 
    var mu sync.Mutex
    
    // Map для результатов
    result := make(map[int][]int)
 
    // Шаблон семафор реализуется в go через канал буферизированный канал в который пишется
    // пустая структура для экономии памяти, когда буфер заполнен следующая горутина
    // пытающаяся записать в канал выхватывает блокировку до момента пока кто то не вычитает из канала
    semaphore := make(chan struct{}, numWorkers)
 
    // Цикл по узлам с которых начинается поиск в ширину
    for _, query := range queries {
 
        // занимаем один слот в WaitGroup
        wg.Add(1)
 
        // занимаем слот в семафоре
        semaphore <- struct{}{}
 
        // конкурентно запускаем функцию
        go func(q int) {
 
            // это выполнится в конце функции независимо от того где из нее вышли
            // высвобождаем слот в WaitGroup
            defer wg.Done()
 
            // это выполнится в конце функции независимо от того где из нее вышли
            // высвобождаем слот в семафоре
            defer func() { <-semaphore }()
 
            // получаем результат поиска 
            bfsResult := breadthFirstSearch(graph, q)
 
            // вешаем блокировку
            mu.Lock()
 
            // безопасно добавляем результат
            result[q] = bfsResult
 
            // снимаем блокировку
            mu.Unlock()
        }(query)
    }
 
    // тут ждем пока все слоты в WaitGroup высвободятся 
    wg.Wait()
 
    // возвращаем result
    return result
}

func NextCombination(x uint8) uint8 {
  c := x & -x             // шаг 1: младший установленный бит
  r := x + c              // шаг 2: сдвигаем правый блок единиц влево
  changed := r ^ x        // шаг 3: биты которые изменились
  shifted := changed >> 2 // шаг 4: убираем два лишних бита
  tail := shifted / c     // шаг 5: нормализуем к нулевой позиции
  next := tail | r        // шаг 6: собираем результат
  return next
}

import (
  "testing"
)
 
func TestNextCombination(t *testing.T) {
  tests := []struct {
    name string
    x    uint8
    want uint8
  }{
    {"6 -> 9 (биты 1,2 -> биты 0,3)", 6, 9},
    {"9 -> 10 (биты 0,3 -> биты 1,3)", 9, 10},
    {"10 -> 12 (биты 1,3 -> биты 2,3)", 10, 12},
    {"12 -> 17 (биты 2,3 -> биты 0,4)", 12, 17},
    {"7 -> 11 (биты 0,1,2 -> биты 0,1,3)", 7, 11},
    {"11 -> 13", 11, 13},
    {"13 -> 14", 13, 14},
    {"14 -> 19", 14, 19},
    {"1 -> 2 (один бит)", 1, 2},
    {"2 -> 4", 2, 4},
    {"4 -> 8", 4, 8},
  }
 
  for _, tt := range tests {
    t.Run(tt.name, func(t *testing.T) {
      got := NextCombination(tt.x)
      if got != tt.want {
        t.Errorf("NextCombination(%d) = %d, want %d", tt.x, got, tt.want)
      }
    })
  }
}

c := x & -x

r := x + c

changed := r ^ x

shifted := changed >> 2

tail := shifted / c

next := tail | r

import "math"
 
func angleClock(hour int, minutes int) float64 {
 
    const (
        oneMinuteAngle = 6.0
        oneHourAngle = 30.0
        oneMinuteForHourAngle = .5
    )
 
    if hour >= 12 {
        hour -= 12
    }
 
    minutesAngle := float64(minutes) * oneMinuteAngle
    hourAngle := float64(hour) * oneHourAngle + float64(minutes) * oneMinuteForHourAngle
 
    angle := math.Abs(hourAngle - minutesAngle)
    if angle > 180 {
        angle = 360 - angle
    }
 
    return angle
 
}

func TestAngleClock(t *testing.T) {
    testCases := []struct {
        desc     string
        hour     int
        minutes  int
        expected float64
    }{
        {
            desc:     "#1",
            hour:     12,
            minutes:  30,
            expected: 165,
        },
        {
            desc:     "#2",
            hour:     3,
            minutes:  30,
            expected: 75,
        },
        {
            desc:     "#3",
            hour:     3,
            minutes:  15,
            expected: 7.5,
        },
        {
            desc:     "#4",
            hour:     1,
            minutes:  57,
            expected: 76.5,
        },
    }
    for _, tC := range testCases {
        t.Run(tC.desc, func(t *testing.T) {
            result := angleClock(tC.hour, tC.minutes)
            if result != tC.expected {
                t.Errorf("Unexpected result for test %s, expected: %g, but got: %g", tC.desc, tC.expected, result)
            }
        })
    }
}

// Наркоман
type Junkie struct {
    ID       int
    Infected bool
}
 
// Эксперимент
type Trial struct {
    Junkies []Junkie
}
 
func NewDefaultTrial() *Trial {
 
    t := Trial{}
 
    t.Junkies = append(t.Junkies, Junkie{Infected: true, ID: 0})
 
    for i := range 9 {
        t.Junkies = append(t.Junkies, Junkie{Infected: false, ID: i + 1})
    }
 
    return &t
}
 
func (t *Trial) ShootUpJunkies() {
 
    rand.Shuffle(len(t.Junkies), func(i, j int) {
        t.Junkies[i], t.Junkies[j] = t.Junkies[j], t.Junkies[i]
    })
 
    isNeedleInfected := false
 
    for i, junkie := range t.Junkies {
 
        if junkie.Infected {
            isNeedleInfected = true
        }
 
        if isNeedleInfected {
            t.Junkies[i].Infected = t.Junkies[i].Infected || (rand.Intn(100) < 2)
        }
    }
}
 
func (t *Trial) IsAllInfected() bool {
 
    var result bool
 
    result = true
 
    for _, j := range t.Junkies {
        result = result && j.Infected
    }
 
    return result
}

package main
 
import (
    "fmt"
 
    "github.com/alhaos/junkiesInection/internal/model"
)
 
const count = 1_000_000
 
func main() {
 
    var sum int
 
    for _ = range count {
        t := model.NewDefaultTrial()
        i := 0
        for ; !t.IsAllInfected(); i++ {
            t.ShootUpJunkies()
        }
        sum += i
    }
 
    fmt.Printf("avg days: %d", sum/count)
}

// [url]https://leetcode.com/studyplan/top-interview-150/[/url]
 
package topInterview
 
// convert
//
// 6. Zigzag Conversion
//
// The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
//
// P   A   H   N
// A P L S I I G
// Y   I   R
// And then read line by line: "PAHNAPLSIIGYIR"
//
// Write the code that will take a string and make this conversion given a number of rows:
//
// string convert(string s, int numRows);
//
// Example 1:
//
// Input: s = "PAYPALISHIRING", numRows = 3
// Output: "PAHNAPLSIIGYIR"
// Example 2:
//
// Input: s = "PAYPALISHIRING", numRows = 4
// Output: "PINALSIGYAHRPI"
// Explanation:
// P     I    N
// A   L S  I G
// Y A   H R
// P     I
// Example 3:
//
// Input: s = "A", numRows = 1
// Output: "A"
//
// Constraints:
//
// 1 <= s.length <= 1000
// s consists of English letters (lower-case and upper-case), ',' and '.'.
// 1 <= numRows <= 1000//
func convert(s string, numRows int) string {
 
    // Если строка одна возвращаем ее сразу
    if numRows == 1 {
        return s
    }
 
    // Создаем слайс строк длиной numRows
    rows := make([]string, numRows)
    // Указательна текущую строку
    currentRowIndex := 0
    // Флаг движения вниз
    directionDown := true
 
    // Цикл по строке
    for i := range len(s) {
 
        // Если указатель строк на первой строке
        if currentRowIndex == 0 {
            // Подымаем флаг движения вниз
            directionDown = true
        }
 
        // Если указатель строк на крайней строке
        if currentRowIndex == len(rows)-1 {
            // Опускаем флаг движения вниз
            directionDown = false
        }
 
        // Добавляем символ в строку на которой указатель текущей строки
        rows[currentRowIndex] += string(s[i])
 
        // Если поднят флаг движения вниз
        if directionDown {
            // Увеличиваем указатель текущей строки
            currentRowIndex++
        } else { // Если не поднят флаг движения вниз
            // Уменьшаем указатель текущей строки
            currentRowIndex--
        }
    }
    
    // Возвращаем строку из объединенного слайса строк  
    return strings.Join(rows, "")
}

func TestConvert(t *testing.T) {
    data := []struct {
        s        string
        rowNums  int
        expected string
    }{
        {"PAYPALISHIRING", 3, "PAHNAPLSIIGYIR"},
        {"PAYPALISHIRING", 4, "PINALSIGYAHRPI"},
        {"A", 1, "A"},
        {"AB", 1, "AB"},
    }
 
    for i, datum := range data {
        result := convert(datum.s, datum.rowNums)
 
        if result != datum.expected {
            t.Errorf(
                "unexpected result for test data index %d (%s), expected [%s], but got [%s]",
                i,
                datum.s,
                datum.expected,
                result,
            )
        }
    }
}

// [url]https://leetcode.com/studyplan/top-interview-150/[/url]
 
package topInterview
 
import (
    "strings"
)
 
// reverseWords
//
// 151. Reverse Words in a String
//
// Given an input string s, reverse the order of the words.
//
// A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
//
// Return a string of the words in reverse order concatenated by a single space.
//
// Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra // spaces.
//
// Example 1:
//
// Input: s = "the sky is blue"
// Output: "blue is sky the"
// Example 2:
//
// Input: s = "  hello world  "
// Output: "world hello"
// Explanation: Your reversed string should not contain leading or trailing spaces.
// Example 3:
//
// Input: s = "a good   example"
// Output: "example good a"
// Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.
//
// Constraints:
//
// 1 <= s.length <= 104
// s contains English letters (upper-case and lower-case), digits, and spaces ' '.
// There is at least one word in s.
func reverseWords(s string) string {
 
    // Разбиваем строку на подстроки по условию
    words := strings.Fields(s)
 
    // Меняем порядок элементов в слайсе классическим методом
    for i, j := 0, len(words)-1; i < j; i, j = i+1, j-1 {
        words[i], words[j] = words[j], words[i]
    }
    
    // Возвращаем строку, полученную после объединения элементов слайса через пробел
    return strings.Join(words, " ")
}

func TestReverseWords(t *testing.T) {
    data := []struct {
        s        string
        expected string
    }{
        {"the sky is blue", "blue is sky the"},
        {"  hello world  ", "world hello"},
        {"a good   example", "example good a"},
    }
 
    for i, datum := range data {
        result := reverseWords(datum.s)
 
        if result != datum.expected {
            t.Errorf(
                "unexpected result for test data index %d (%s), expected [%s], but got [%s]",
                i,
                datum.s,
                datum.expected,
                result,
            )
        }
    }
}

// [url]https://leetcode.com/studyplan/top-interview-150/[/url]
 
package topInterview
 
// longestCommonPrefix
//
// 14. Longest Common Prefix
//
// Write a function to find the longest common prefix string amongst an array of strings.
//
// If there is no common prefix, return an empty string "".
//
// Example 1:
//
// Input: strs = ["flower","flow","flight"]
// Output: "fl"
// Example 2:
//
// Input: strs = ["dog","racecar","car"]
// Output: ""
// Explanation: There is no common prefix among the input strings.
//
// Constraints:
//
// 1 <= strs.length <= 200
// 0 <= strs[i].length <= 200
// strs[i] consists of only lowercase English letters if it is non-empty.//
func longestCommonPrefix(strs []string) string {
 
    // Далее minLength инициируется длиной первой строки в strs
    // необходимо проверить что этот элемент есть
    if len(strs) == 0 {
        return ""
    }
 
    // Инициируем переменную minLength длиной первого элемента strs
    minLength := len(strs[0])
 
    // Обходим strs вычисляем минимум длины среди элементов strs
    for i := 1; i < len(strs); i++ {
        minLength = min(minLength, len(strs[i]))
    }
 
    // Если минимальная длина 0 возвращаем пустую сроку
    if minLength == 0 {
        return ""
    }
 
    // Тут крайний индекс префикса
    prefixCharsCounter := 0
 
    // rootLoop: это метка так как цикл может быть прерван из внутреннего цикла
rootLoop:
    // Цикл по диапазону [0..minLength-1]
    for i := range minLength {
        // Текущий байт первого элемента будет эталоном
        // с которым будем сравнивать остальные байты элементов strs
        reference := strs[0][i]
        // Обходим strs
        for j := 1; j < len(strs); j++ {
            // Если текущий байт в текущем элементе strs не совпадает с эталоном
            if reference != strs[j][i] {
                // Перерываем внешний цикл rootLoop
                break rootLoop
            }
        }
        // Актуализируем крайний индекс префикса
        prefixCharsCounter++
    }
 
    // Возвращаем префикс первого элемента strs
    return strs[0][0:prefixCharsCounter]
}

func TestLongestCommonPrefix(t *testing.T) {
    data := []struct {
        strs     []string
        expected string
    }{
        {[]string{"flower", "flow", "flight"}, "fl"},
        {[]string{"dog", "racecar", "car"}, ""},
    }
 
    for i, datum := range data {
        result := longestCommonPrefix(datum.strs)
 
        if result != datum.expected {
            t.Errorf(
                "unexpected result for test data index %d (%+v), expected [%s], but got [%s]",
                i,
                datum.strs,
                datum.expected,
                result,
            )
        }
    }
}

// [url]https://leetcode.com/studyplan/top-interview-150/[/url]
 
package topInterview
 
// lengthOfLastWord
//
// 58. Length of Last Word
// Given a string s consisting of words and spaces, return the length of the last word in the string.
//
// A word is a maximal
// substring
//
//  consisting of non-space characters only.
//
// Example 1:
//
// Input: s = "Hello World"
// Output: 5
// Explanation: The last word is "World" with length 5.
// Example 2:
//
// Input: s = "   fly me   to   the moon  "
// Output: 4
// Explanation: The last word is "moon" with length 4.
// Example 3:
//
// Input: s = "luffy is still joyboy"
// Output: 6
// Explanation: The last word is "joyboy" with length 6.
//
// Constraints:
//
// 1 <= s.length <= 104
// s consists of only English letters and spaces ' '.
// There will be at least one word in s.//
func lengthOfLastWord(s string) int {
 
    // Далее указатель цикла будет инициирован длиной строки минус один
    // что приведет к панике, поэтому добавляю проверку.
    if len(s) == 0 {
        return 0
    }
 
    // Счетчик символов
    charCount := 0
 
    // Обходим строку в справа налево
    for i := len(s) - 1; i >= 0; i-- {
        // Если текущий элемент пробел
        if s[i] == 0x20 {
            // Если мы уже что-то посчитали
            if charCount > 0 {
                // Возвращаем счетчик символов
                return charCount
            }
        } else { // Если не пробел
            // Счетчик символов увеличиваем на один
            charCount++
        }
    }
 
    // Эта часть кода сработает если строка состоит только из пробелов
    return charCount
}

func TestLengthOfLastWord(t *testing.T) {
    data := []struct {
        s        string
        expected int
    }{
        {"Hello World", 5},
        {"   fly me   to   the moon  ", 4},
        {"luffy is still joyboy", 6},
    }
 
    for i, datum := range data {
        result := lengthOfLastWord(datum.s)
 
        if result != datum.expected {
            t.Errorf(
                "unexpected result for test data index %d (%s), expected [%d], but got [%d]",
                i,
                datum.s,
                datum.expected,
                result,
            )
        }
    }
}

// [url]https://leetcode.com/studyplan/top-interview-150/[/url]
 
package topInterview
 
import (
    "bytes"
 
// intToRoman
//
// 12. Integer to Roman
//
// Seven different symbols represent Roman numerals with the following values:
//
// Symbol      Value
// I     1
// V     5
// X     10
// L     50
// C     100
// D     500
// M     1000
// Roman numerals are formed by appending the conversions of decimal place values from highest to lowest. Converting a decimal place value into a Roman numeral has the following rules:
//
// If the value does not start with 4 or 9, select the symbol of the maximal value that can be subtracted from the input, append that symbol to the result, subtract its value, and convert the // remainder to a Roman numeral.
// If the value starts with 4 or 9 use the subtractive form representing one symbol subtracted from the following symbol, for example, 4 is 1 (I) less than 5 (V): IV and 9 is 1 (I) less than 10 // (X): IX. Only the following subtractive forms are used: 4 (IV), 9 (IX), 40 (XL), 90 (XC), 400 (CD) and 900 (CM).
// Only powers of 10 (I, X, C, M) can be appended consecutively at most 3 times to represent multiples of 10. You cannot append 5 (V), 50 (L), or 500 (D) multiple times. If you need to append a // symbol 4 times use the subtractive form.
// Given an integer, convert it to a Roman numeral.
//
// Example 1:
//
// Input: num = 3749
//
// Output: "MMMDCCXLIX"
//
// Explanation:
//
// 3000 = MMM as 1000 (M) + 1000 (M) + 1000 (M)
//
//  700 = DCC as 500 (D) + 100 (C) + 100 (C)
//   40 = XL as 10 (X) less of 50 (L)
//    9 = IX as 1 (I) less of 10 (X)
//
// Note: 49 is not 1 (I) less of 50 (L) because the conversion is based on decimal places
// Example 2:
//
// Input: num = 58
//
// Output: "LVIII"
//
// Explanation:
//
// 50 = L
//
//  8 = VIII
//
// Example 3:
//
// Input: num = 1994
//
// Output: "MCMXCIV"
//
// Explanation:
//
// 1000 = M
//
//  900 = CM
//   90 = XC
//    4 = IV
//
// Constraints:
//
// 1 <= num <= 3999//
func intToRoman(num int) string {
 
    // Инициировать буфер для сбора римских цифр
    b := bytes.Buffer{}
 
    // Повторять цикл пока num > 0
    for num > 0 {
        // В конструкции switch будем определять какое максимально возможное число мы можем вычесть
        // В каждом случае, добавляем соответствующую римскую цифру и уменьшаем num на соответствующее число
        // пока от num ничего не останется
        switch {
        case num >= 1000:
            b.WriteString("M")
            num -= 1000
        case num >= 900:
            b.WriteString("CM")
            num -= 900
        case num >= 500:
            b.WriteString("D")
            num -= 500
        case num >= 400:
            b.WriteString("CD")
            num -= 400
        case num >= 100:
            b.WriteString("C")
            num -= 100
        case num >= 90:
            b.WriteString("XC")
            num -= 90
        case num >= 50:
            b.WriteString("L")
            num -= 50
        case num >= 40:
            b.WriteString("XL")
            num -= 40
        case num >= 10:
            b.WriteString("X")
            num -= 10
        case num >= 9:
            b.WriteString("IX")
            num -= 9
        case num >= 5:
            b.WriteString("V")
            num -= 5
        case num >= 4:
            b.WriteString("IV")
            num -= 4
        case num >= 1:
            b.WriteString("I")
            num -= 1
        }
    }
    // Выводим строку полученную из буфера 
    return b.String()
}

func TestIntToRoman(t *testing.T) {
 
    data := []struct {
        num      int
        expected string
    }{
        {3749, "MMMDCCXLIX"},
        {58, "LVIII"},
        {1994, "MCMXCIV"},
    }
 
    for i, datum := range data {
        result := intToRoman(datum.num)
 
        if result != datum.expected {
            t.Errorf(
                "unexpected result for test data index %d (%d), expected [%s], but got [%s]",
                i,
                datum.num,
                datum.expected,
                result,
            )
        }
    }
}

// [url]https://leetcode.com/studyplan/top-interview-150/[/url]
 
package topInterview
 
// romanToInt
//
// 13. Roman to Integer
//
// Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.
//
// Symbol       Value
// I             1
// V             5
// X             10
// L             50
// C             100
// D             500
// M             1000
// For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.
//
// Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:
//
// I can be placed before V (5) and X (10) to make 4 and 9.
// X can be placed before L (50) and C (100) to make 40 and 90.
// C can be placed before D (500) and M (1000) to make 400 and 900.
// Given a roman numeral, convert it to an integer.//
func romanToInt(s string) int {
 
    // Создаю карту соответствия римской цифры и десятичного числа
    m := map[uint8]int{
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000,
    }
 
    // Значение текущей римской цифры зависит от предыдущей
    // previous содержит предыдущее число
    previous := 0
 
    // Sum содержит сумму
    sum := 0
 
    // Обходим строку циклом range при таком обходе текущий элемент это руна
    for i, _ := range s {
        // Обходить слайс нужно в обратном порядке поэтому вычисляем реверсивней указатель
        reverseI := len(s) - i - 1
 
        // Если число из карты по текущей руне строки меньше предыдущего числа
        if m[s[reverseI]] < previous {
            // Вычитаем это число из общей суммы
            sum -= m[s[reverseI]]
        } else { // Если число из карты по текущей руне строки не меньше предыдущего числа
            // Увеличиваем общую сумму на это число
            sum += m[s[reverseI]]
        }
        // Обновляем предыдущее число для следящей итерации цикла
        previous = m[s[reverseI]]
    }
    // Возвращаем сумму
    return sum
}

func TestRomanToInt(t *testing.T) {
 
    data := []struct {
        s        string
        expected int
    }{
        {"III", 3},
        {"LVIII", 58},
        {"MCMXCIV", 1994},
    }
 
    for i, datum := range data {
        result := romanToInt(datum.s)
 
        if result != datum.expected {
            t.Errorf(
                "unexpected result for test data index %d (%s), expected [%d], but got [%d]",
                i,
                datum.s,
                datum.expected,
                result,
            )
        }
    }
}

// [url]https://leetcode.com/studyplan/top-interview-150/[/url]
 
package topInterview
 
// trap
//
// 42. Trapping Rain Water
//
// Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
//
// Example 1:
//
// Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
// Output: 6
// Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
//
// Example 2:
//
// Input: height = [4,2,0,3,2,5]
// Output: 9
//
// Constraints:
//
// n == height.length
// 1 <= n <= 2 * 104
// 0 <= height[i] <= 105//
func trap(height []int) int {
 
    // length содержит длину слайса height
    length := len(height)
 
    // Далее инициализируются переменные ссылающиеся на первый элемент слайса
    // и на последний, надо проверить что эти элементы есть чтобы не было паники
    if length == 0 {
        return 0
    }
 
    // left, right Указатели на текущие элементы справа и слева
    left, right := 0, length-1
 
    // leftMax, rightMax обнаруженные максимумы слева и справа
    leftMax, rightMax := height[left], height[right]
 
    // water Общее количество воды
    water := 0
 
    // Обходим слайс пока не сравняются указатели
    for left < right {
 
        // Если текущая значение слева меньше текущего значения справа
        if height[left] < height[right] {
            // Если текущее значение слева больше или равно обнаруженного на текущий момент
            // максимума слева
            if height[left] >= leftMax {
                // Обнаруженный максимум слева равен ткущему элементу
                leftMax = height[left]
            } else { // Если текущий элемент слева меньше чем текущий элемент справа
                // Повышаем общий уровень воды на разность обнаруженного максимума
                // слева и значения текущего элемента слева
                water += leftMax - height[left]
            }
            // Увеличиваем указатель на левый элемент
            left++
        } else { // Если правый элемент меньше или равно левый элемент
            // Если правый элемент больше обнаруженного максимума справа
            if height[right] >= rightMax {
                // Обнаруженный максимум справа равен текущему элементу справа
                rightMax = height[right]
            } else { // Если текущий элемент справа меньше обнаруженного максимума справа
                // Общий уровень воды повышаем на разность обнаруженного максимума справа и значение элемента справа
                water += rightMax - height[right]
            }
            // Увеличиваем указатель правого элемента
            right--
        }
    }
    // Возвращаем общий уровень воды
    return water
}

func TestTrap(t *testing.T) {
 
    data := []struct {
        height   []int
        expected int
    }{
        {
            []int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1},
            6,
        },
        {
            []int{4, 2, 0, 3, 2, 5},
            9,
        },
    }
 
    for i, datum := range data {
        result := trap(datum.height)
 
        if result != datum.expected {
            t.Errorf(
                "unexpected result for test data index %d (%+v), expected [%d], but got [%d]",
                i,
                datum.height,
                datum.expected,
                result,
            )
        }
    }
}

// [url]https://leetcode.com/studyplan/top-interview-150/[/url]
 
package topInterview
 
// candy
//
// 135. Candy
// There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.
//
// You are giving candies to these children subjected to the following requirements:
//
// Each child must have at least one candy.
// Children with a higher rating get more candies than their neighbors.
// Return the minimum number of candies you need to have to distribute the candies to the children.
//
// Example 1:
//
// Input: ratings = [1,0,2]
// Output: 5
// Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
// Example 2:
//
// Input: ratings = [1,2,2]
// Output: 4
// Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
// The third child gets 1 candy because it satisfies the above two conditions.
//
// Constraints:
//
// n == ratings.length
// 1 <= n <= 2 * 104
// 0 <= ratings[i] <= 2 * 104
func candy(ratings []int) int {
 
    // Length содержит длину массива ratings
    length := len(ratings)
 
    // Создаем слайс для подсчета и сравнения полученных конфет
    candies := make([]int, length)
 
    // Раздаем по конфете
    // Условие "Each child must have at least one candy."
    for i, _ := range candies {
        candies[i] = 1
    }
 
    // Обходим слайс слева направо до предпоследнего элемента
    for i := range length - 1 {
        // Если рейтинг текущего ребенка меньше рейтинга ребенка справа
        if ratings[i] < ratings[i+1] {
            // Ребенок справа получает на одну конфету больше чем есть у текущего ребенка
            candies[i+1] = candies[i] + 1
        }
    }
 
    // Обходим слайс справа налево до второго элемента
    for i := length - 1; i > 0; i-- {
        // Если у текущего ребенка рейтинг ниже чему у ребенка слева
        // и у конфет у текущего ребенка больше или столько же как у ребенка слева
        if ratings[i] < ratings[i-1] && candies[i] >= candies[i-1] {
            // У ребенка слева становится конфет больше на одну чем у текущего
            candies[i-1] = candies[i] + 1
        }
    }
 
    // Возвращаем сумму конфет
    sum := 0
    for _, n := range candies {
        sum += n
    }
    return sum
}

func TestCandy(t *testing.T) {
    data := []struct {
        ratings  []int
        expected int
    }{
        {
            []int{1, 0, 2},
            5,
        },
        {
            []int{1, 2, 2},
            4,
        },
        {
            []int{1, 3, 2, 2, 1},
            7,
        },
        {
            []int{1, 2, 87, 87, 87, 2, 1},
            13,
        }, {
            []int{1, 3, 4, 5, 2},
            11,
        },
    }
 
    for i, datum := range data {
        result := candy(datum.ratings)
 
        if result != datum.expected {
            t.Errorf("unexpected result for test index %d expected [%d] got [%d]", i, datum.expected, result)
        }
    }
}

// [url]https://leetcode.com/studyplan/top-interview-150/[/url]
 
package topInterview
 
// 134. Gas Station
// There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].
// 
// You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.
// 
// Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a  solution, it is guaranteed to be unique.
// 
//  
// 
// Example 1:
// 
// Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
// Output: 3
// Explanation:
// Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
// Travel to station 4. Your tank = 4 - 1 + 5 = 8
// Travel to station 0. Your tank = 8 - 2 + 1 = 7
// Travel to station 1. Your tank = 7 - 3 + 2 = 6
// Travel to station 2. Your tank = 6 - 4 + 3 = 5
// Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
// Therefore, return 3 as the starting index.
// Example 2:
// 
// Input: gas = [2,3,4], cost = [3,4,3]
// Output: -1
// Explanation:
// You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
// Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
// Travel to station 0. Your tank = 4 - 3 + 2 = 3
// Travel to station 1. Your tank = 3 - 3 + 3 = 3
// You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
// Therefore, you can't travel around the circuit once no matter where you start.
//  
// 
// Constraints:
// 
// n == gas.length == cost.length
// 1 <= n <= 105
// 0 <= gas[i], cost[i] <= 104
 
func canCompleteCircuit(gas []int, cost []int) int {
 
    sumGas := 0 // Сюда суммирую элементы слайса gas
    for _, n := range gas {
        sumGas += n
    }
 
    sumCost := 0 // Сюда суммирую элементы слайса cost
    for _, n := range cost {
        sumCost += n
    }
 
    // Пути нет в том случае если сумма топлива меньше суммы топлива необходимого на перемещение
    if sumGas < sumCost {
        return -1
    }
 
    tank := 0 // Количество топлива в баке
    iterationIndex := 0 // Индекс итерации по слайсу
    startIndex := 0 // Индекс элемента с которого возможно начать путь
 
    // Прерываю цикл когда все элементы перебраны
    for len(gas) > iterationIndex { 
        // Количество топлива в баке равно оставшееся топливо полюс топлива наи итерируемой станции
        // минус количество топлива необходимое чтобы добраться до следующей станции.
        tank += gas[iterationIndex] - cost[iterationIndex]
        // Если расчетное количество топлива в баке меньше нуля
        if tank < 0 {
            // Обнулить количество топлива в баке
            tank = 0
            // Начать путь со следующего индекса
            startIndex = iterationIndex + 1
        }
        // Инкрементировать индекс итерации
        iterationIndex++
    }
    // Вернуть индекс начала пусти
    return startIndex
}

func TestCanCompleteCircuit(t *testing.T) {
    data := []struct {
        gas      []int
        cost     []int
        expected int
    }{
        {
            []int{1, 2, 3, 4, 5},
            []int{3, 4, 5, 1, 2},
            3,
        },
        {
            []int{2, 3, 4},
            []int{3, 4, 3},
            -1,
        },
    }
 
    for i, datum := range data {
        result := canCompleteCircuit(datum.gas, datum.cost)
 
        if result != datum.expected {
            t.Errorf("unexpected result for test index %d expected [%d] got [%d]", i, datum.expected, result)
        }
    }
}

// [url]https://leetcode.com/studyplan/top-interview-150/[/url]
 
package topInterview
 
// productExceptSelf
//
// 238. Product of Array Except Self
// Medium
// Topics
// Companies
// Hint
// Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].
//
// The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
//
// You must write an algorithm that runs in O(n) time and without using the division operation.
//
// Example 1:
//
// Input: nums = [1,2,3,4]
// Output: [24,12,8,6]
// Example 2:
//
// Input: nums = [-1,1,0,-3,3]
// Output: [0,0,9,0,0]
//
// Constraints:
//
// 2 <= nums.length <= 105
// -30 <= nums[i] <= 30
// The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.
func productExceptSelf(nums []int) []int {
 
    // Инициировать переменную содержащую накопленное произведение единицей
    cumulativeProduct := 1
    // Инициировать переменную содержащую индекс итерируемого элемента слайса нулем
    index := 0
    // Инициировать промежуточный слайс нулями, длиной аналогичной nums
    output := make([]int, len(nums))
 
    // Запустить цикл
    for {
        // Значение элемента промежуточного слайса с индексом Index
        // прировнять к значению переменной накопленной произведения
        output[index] = cumulativeProduct
        // Значение накопленного произведения приравнять к произведению накопленного
        // произведения и значения элемента nums c индексом Index
        cumulativeProduct *= nums[index]
        // Если значение Index выходит за приделы крайнего элемента слайса nums
        if index >= len(nums)-1 {
            // Прервать цикл
            break
        }
        // Инкрементировать Index
        index++
    }
 
    // Значение накопленного предвидения прировнять к единице
    cumulativeProduct = 1
 
    for {
        // Значение элемента промежуточного слайса с индексом Index прировнять к произведению
        // значение элемента промежуточного слайса с индексом Index и накопленного произведения
        output[index] *= cumulativeProduct
        // Значение накопленного произведения прировнять к произведению наколенного произведения
        // и элемента слайса nums с индексом Index
        cumulativeProduct *= nums[index]
        // Если Index меньше нуля
        if index <= 0 {
            // Прервать цикл
            break
        }
        // Декриментировать Index
        index--
 
    }
 
    // Вернуть промежуточный слайс
    return output
}

func TestProductExceptSelf(t *testing.T) {
    data := []struct {
        nums     []int
        expected []int
    }{
        {
            []int{1, 2, 3, 4},
            []int{24, 12, 8, 6},
        },
        {
            []int{-1, 1, 0, -3, 3},
            []int{0, 0, 9, 0, 0},
        },
    }
    for i, datum := range data {
 
        result := productExceptSelf(datum.nums)
 
        if !reflect.DeepEqual(result, datum.expected) {
            t.Errorf("unexpected result for test index %d expected [%+v] got [%+v]", i, datum.expected, result)
        }
    }
}

type RandomizedSet interface {
 // Insert Добавляет элемент к списку уникальных элементов
 // в случае успеха возвращает ИСТИНУ
 // в обратном случае ЛОЖЬ
 Insert(val int) bool
 // Remove Удаляет элемент из списка уникальных элементов
 // в случае успеха возвращает ИСТИНУ
 // в обратном случае ЛОЖЬ
 Remove(val int) bool
 // GetRandom Возвращает случайный элемент из списка
 GetRandom() int
}

// [url]https://leetcode.com/studyplan/top-interview-150/[/url]
 
package topInterview
 
// RandomizedSet 380. Insert Delete GetRandom O(1)
// Implement the RandomizedSet class:
// 
// RandomizedSet() Initializes the RandomizedSet object.
// bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
// bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
// int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.
// You must implement the functions of the class such that each function works in average O(1) time complexity.
// 
// Example 1:
// 
// Input
// ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
// [[], [1], [2], [2], [], [1], [2], []]
// Output
// [null, true, false, true, 2, true, false, 2]
// 
// Explanation
// RandomizedSet randomizedSet = new RandomizedSet();
// randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
// randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
// randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
// randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
// randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
// randomizedSet.insert(2); // 2 was already in the set, so return false.
// randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.
// 
// Constraints:
// 
// -231 <= val <= 231 - 1
// At most 2 * 105 calls will be made to insert, remove, and getRandom.
// There will be at least one element in the data structure when getRandom is called.
 
// RandomizedSet структура содержащая данные
type RandomizedSet struct {
    elements        []int       // слайс элементов
    elementIndexMap map[int]int // карта содержащая значение элемента и массив элемента
}
 
// Constructor конструктор для структуры RandomizedSet
func Constructor() RandomizedSet {
    // Вернуть RandomizedSet
    return RandomizedSet{
        elements:        []int{},           // Поле elements инициировать пустым слайсом целочисленных элементов
        elementIndexMap: make(map[int]int), // Создать пустую карту
    }
}
 
// Insert вставляет элемент при отсутствии данного элемента
// Возвращает ИСТИНУ в случае успеха, ЛОЖЬ в противоположном
func (this *RandomizedSet) Insert(val int) bool {
 
    // Инициировать exist бинарным признаком наличия элемента в карте элементов
    _, exist := this.elementIndexMap[val]
    // В случае наличия элемента
    if exist {
        // Вернуть ЛОЖЬ
        return false
    }
 
    // Добавить элемент в слайс элементов
    this.elements = append(this.elements, val)
 
    // Добавить элемент в карту индексов элементов
    this.elementIndexMap[val] = len(this.elements) - 1
 
    // Вернуть ИСТИНУ
    return true
}
 
// Remove удаляет элемент при наличии данного элемента
// Возвращает ИСТИНУ в случае успеха, ЛОЖЬ в противоположном
func (this *RandomizedSet) Remove(val int) bool {
 
    // Инициировать exist бинарным признаком наличия элемента в карте элементов
    _, exist := this.elementIndexMap[val]
    // В случае отсутствия элемента
    if !exist {
        // Вернуть ЛОЖЬ
        return false
    }
 
    // Определить индекс элемента по карте
    index := this.elementIndexMap[val]
 
    // Заменить значение элемента с индексом index на значение крайнего элемента в слайсе элементов
    this.elements[index] = this.elements[len(this.elements)-1]
 
    // Заменить значение индекса, нового значения элемента в карте индексов элементов
    this.elementIndexMap[this.elements[index]] = index
 
    // Переопределить слайс элементов им же без крайнего элемента
    this.elements = this.elements[:len(this.elements)-1]
 
    // Удалить элемент из карты элементов
    delete(this.elementIndexMap, val)
 
    // Вернуть ИСТИНУ
    return true
}
 
// GetRandom возвращает случайный элемент
func (this *RandomizedSet) GetRandom() int {
    // Проверить наличие элементов в слайсе
    if len(this.elements) == 0 {
        // Вернуть ноль
        return 0
    }
    // Получить индекс случайного элемента
    index := rand.Intn(len(this.elements))
 
    // Вернуть значение случайного элемента
    return this.elements[index]
}

// [url]https://leetcode.com/studyplan/top-interview-150/[/url]
 
package topInterview
 
import (
    "sort"
)
 
// hIndex
//
// 274. H-Index
//
// Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return the researcher's h-index.
//
// According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.
//
// Example 1:
//
// Input: citations = [3,0,6,1,5]
// Output: 3
// Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively.
// Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.
// Example 2:
//
// Input: citations = [1,3,1]
// Output: 1
//
// Constraints:
//
// n == citations.length
// 1 <= n <= 5000
// 0 <= citations[i] <= 1000//
func hIndex(citations []int) int {
 
    // Воспользуюсь сортировкой целочисленных слайсов с произвольной функцией сортировки
    // Отсортировать слайс по убыванию
    sort.Slice(citations, func(i, j int) bool {
        return citations[i] > citations[j]
    })
 
    // Переменная hIndexValue содержит крайний h-индекс подходящий под критерии
    hIndexValue := 0
    // Цикл range по элементам слайса citations
    // i индекс текущего элемента слайса
    // v значение текущего элемента слайса
    for i, v := range citations {
        // если значение текущего элемента слайса больше индекса элемента
        if v >= i+1 {
            // Обновляем hIndexValue становится индексом текущего элемента плюс единица так как чети индекса ведется с единицы
            hIndexValue = i + 1
            // Прервать итерацию цикла
            continue
        }
        // Прервать цикл
        break
    }
 
    // Вернуть значение h-индекса
    return hIndexValue
}

func TestHIndex(t *testing.T) {
 
    data := []struct {
        citations []int
        expected  int
    }{
        {
            []int{3, 0, 6, 1, 5},
            3,
        },
        {
            []int{1, 3, 1},
            1,
        },
    }
 
    for i, datum := range data {
 
        result := hIndex(datum.citations)
 
        if result != datum.expected {
            t.Errorf("unexpected result for test index %d expected [%+v] got [%+v]", i, datum.expected, result)
        }
    }
}

// [url]https://leetcode.com/studyplan/top-interview-150/[/url]
 
package topInterview
 
// jump
//
// 45. Jump Game II
//
// You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].
//
// Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums// [i + j] where:
//
// 0 <= j <= nums[i] and
// i + j < n
// Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].
//
// Example 1:
//
// Input: nums = [2,3,1,1,4]
// Output: 2
// Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
// Example 2:
//
// Input: nums = [2,3,0,1,4]
// Output: 2
//
// Constraints:
//
// 1 <= nums.length <= 104
// 0 <= nums[i] <= 1000
// It's guaranteed that you can reach nums[n - 1].
func jump(nums []int) int {
 
    // lastNumsIndex содержит крайний индекс слайса
    lastNumsIndex := len(nums) - 1
 
    // currentAvailableIndex содержит индекс элемента до которого мы можем допрыгнуть в текущей итерации цикла
    currentAvailableIndex := 0
 
    // farthestAvailableIndex содержит индекс самого дальнего элемента из обнаруженных за все предыдущие итерации цикла
    farthestAvailableIndex := 0
 
    // jumps счетчик прыжков
    jumps := 0
 
    // index итерируемого элемента цикла
    index := 0
 
    for {
 
        // Обновить элемент до которого можно допрыгнуть вообще, учитывая предыдущие итерации цикла
        farthestAvailableIndex = max(farthestAvailableIndex, index+nums[index])
 
        // Если элемент до которого можно допрыгнуть равен крайнему элементу - цель достигнута
        if farthestAvailableIndex >= lastNumsIndex {
            // Увеличить счетчик прыжков на один
            jumps++
            // Прервать цикл
            break
        }
 
        // Если текущий индекс равен индексу элемента до которого мы можем допрыгнуть за эту
        // итерацию - значит мы дошли в тупик, но по условия задачи гарантируется наличие пути к крайнему
        // элементу
        if index == currentAvailableIndex {
            // Увеличить счетчик прыжков на один
            jumps++
            // Индекс элемента до которого можно допрыгнуть за текущую итерацию приравнять
            // к индексу наиболее дальнего элемента который найден за все предыдущие итерации цикла
            currentAvailableIndex = farthestAvailableIndex
        }
 
        // Увеличить текущий индекс на единицу
        index++
    }
    // Вернуть счетчик прыжков
    return jumps
}

func TestJump(t *testing.T) {
    data := []struct {
        mums     []int
        expected int
    }{
        {
            []int{2, 3, 1, 1, 4},
            2,
        },
        {
            []int{2, 3, 0, 1, 4},
            2,
        },
    }
 
    for i, datum := range data {
 
        result := jump(datum.mums)
 
        if result != datum.expected {
            t.Errorf("unexpected result for test index %d expected [%+v] got [%+v]", i, datum.expected, result)
        }
    }
}