Алгоритмы - Другие

Код реализует структуру данных очередь (FIFO - First In First Out) с использованием двух стеков. Это позволяет эмулировать поведение очереди, используя только операции стека (LIFO - Last In First Out).

Алгоритм решения

Использование двух стеков: stackPush для добавления элементов и stackPop для удаления элементов
При добавлении элемента (Push), он всегда помещается в stackPush
При удалении (Pop) или просмотре (Peek) элемента:
- Если stackPop пуст, все элементы из stackPush перемещаются в stackPop в обратном порядке
- Затем операция выполняется с верхним элементом stackPop

Constructor(): Создает новую пустую очередь
Push(x int): Добавляет элемент в конец очереди
Pop() int: Удаляет и возвращает элемент из начала очереди
Peek() int: Возвращает элемент из начала очереди без удаления
Empty() bool: Проверяет, пуста ли очередь
PeekPop(): Вспомогательный метод для перемещения элементов между стеками

Временная сложность:
- Push: O(1) (амортизированная)
- Pop: O(1) (амортизированная)
- Peek: O(1) (амортизированная)
- Empty: O(1)
Пространственная сложность: O(n), где n - количество элементов в очереди

type MyQueue struct {
    stackPush []int
    stackPop  []int
}

func Constructor() MyQueue {
    return MyQueue{}
}

func (this *MyQueue) Push(x int) {
    this.stackPush = append(this.stackPush, x)
}

func (this *MyQueue) Pop() int {
    this.PeekPop()
    if len(this.stackPop) == 0 {
        return 0 // или можно вернуть ошибку, если очередь пуста
    }
    val := this.stackPop[len(this.stackPop)-1]
    this.stackPop = this.stackPop[:len(this.stackPop)-1]
    return val
}

func (this *MyQueue) Peek() int {
    this.PeekPop()
    if len(this.stackPop) == 0 {
        return 0 // или можно вернуть ошибку, если очередь пуста
    }
    return this.stackPop[len(this.stackPop)-1]
}

func (this *MyQueue) Empty() bool {
    return len(this.stackPush) == 0 && len(this.stackPop) == 0
}

// PeekPop перемещает элементы из stackPush в stackPop, если stackPop пуст
func (this *MyQueue) PeekPop() {
    if len(this.stackPop) == 0 {
        for len(this.stackPush) > 0 {
            this.stackPop = append(this.stackPop, this.stackPush[len(this.stackPush)-1])
            this.stackPush = this.stackPush[:len(this.stackPush)-1]
        }
    }
}

Этот код реализует структуру данных RecentCounter, которая отслеживает количество вызовов (пингов) за последние 3000 миллисекунд.

Алгоритм решения

Хранение всех временных меток вызовов в слайсе requests
При каждом вызове Ping:
- Добавление новой временной метки в конец слайса
- Удаление всех временных меток, которые старше чем (t - 3000)
- Возврат количества оставшихся элементов в слайсе

Constructor(): Инициализирует пустой слайс для хранения временных меток
Ping(t int):
- Добавляет новую временную метку t
- Использует цикл для нахождения индекса первого элемента в пределах 3000 мс
- Обрезает слайс, удаляя старые элементы
- Возвращает количество элементов в обновленном слайсе

Временная сложность:
- В худшем случае: O(n), где n - количество элементов в слайсе
- Амортизированная: O(1), так как каждый элемент добавляется и удаляется только один раз
Пространственная сложность: O(m), где m - максимальное количество вызовов за 3000 мс

type RecentCounter struct {
	requests []int
}

func Constructor() RecentCounter {
	return RecentCounter{
		requests: []int{},
	}
}

func (this *RecentCounter) Ping(t int) int {
	this.requests = append(this.requests, t)

	// Удаляем запросы старше 3000 мс
	idx := -1
	for len(this.requests) > 0 && this.requests[idx+1] < t-3000 {
		idx++
	}

	if idx >= 0 {
		this.requests = this.requests[idx+1:]
	}

	return len(this.requests)
}

Функция findItinerary восстанавливает маршрут путешествия из списка авиабилетов, начиная с аэропорта "JFK" и используя все билеты ровно один раз.

Алгоритм решения

Построение графа:
- Использование map для хранения списка смежности
- Ключ - аэропорт отправления, значение - список аэропортов назначения
Сортировка пунктов назначения:
- Обеспечивает выбор лексикографически наименьшего маршрута
Модифицированный DFS:
- Рекурсивно обходит граф, удаляя использованные рейсы
- Добавляет аэропорты в начало результирующего списка (обратный порядок)

Временная сложность: O(N * log N), где N - количество билетов
- Построение графа: O(N)
- Сортировка пунктов назначения: O(N * log N)
- DFS: O(N)
Пространственная сложность: O(N)
- Для хранения графа и результирующего маршрута

func findItinerary(tickets [][]string) []string {
	graph := make(map[string][]string)

	// Построение графа
	for _, ticket := range tickets {
		from, to := ticket[0], ticket[1]
		graph[from] = append(graph[from], to)
	}

	// Сортировка пунктов назначения в лексикографическом порядке
	for _, destinations := range graph {
		sort.Strings(destinations)
	}

	result := make([]string, 0)

	var dfs func(airport string)
	dfs = func(airport string) {
		for len(graph[airport]) > 0 {
			nextDest := graph[airport][0]
			graph[airport] = graph[airport][1:]
			dfs(nextDest)
		}
		result = append([]string{airport}, result...)
	}

	dfs("JFK")

	return result
}

Эта функция numSquares находит наименьшее количество квадратов целых чисел, сумма которых равна заданному положительному целому числу n.

Алгоритм решения

Использование динамического программирования
Создание массива dp длиной n+1 для хранения промежуточных результатов
Итерация от 1 до n:
- Для каждого числа i находим минимальное количество квадратов, необходимое для его составления
- Проверяем все возможные квадраты j*j, не превышающие i
- Обновляем минимальное количество, используя формулу: min(текущее_мин, dp[i-j*j] + 1)
Возвращаем значение dp[n], которое содержит ответ для числа n

Временная сложность: O(n * n^2)
- Внешний цикл выполняется n раз
- Внутренний цикл выполняется n^2 раз в худшем случае
Пространственная сложность: O(n)
- Используется дополнительный массив dp длиной n+1

func numSquares(n int) int {
	dp := make([]int, n+1)
	dp[0] = 0

	for i := 1; i <= n; i++ {
		m := i
		for j := 1; j*j <= i; j++ {
			m = min(m, dp[i-j*j]+1)
		}
		dp[i] = m
	}

	return dp[n]
}

Этот код реализует структуру данных RandomizedSet, которая поддерживает операции вставки, удаления и получения случайного элемента за O(1) времени.

Структура данных:

numMap: карта для хранения значений и их индексов в списке
numList: слайс для хранения значений в порядке вставки

Алгоритм решения

Insert(val int):
- Проверяет, существует ли значение в множестве
- Если нет, добавляет его в конец numList и в numMap с соответствующим индексом
Remove(val int):
- Находит индекс удаляемого элемента в numMap
- Заменяет удаляемый элемент последним элементом в numList
- Обновляет индекс перемещенного элемента в numMap
- Удаляет последний элемент из numList и запись из numMap
GetRandom():
- Возвращает случайный элемент из numList с помощью rand.Intn()

Временная сложность:
- Insert: O(1) в среднем
- Remove: O(1) в среднем
- GetRandom: O(1)
Пространственная сложность: O(n), где n - количество элементов в множестве

type RandomizedSet struct {
    numMap map[int]int
    numList []int
}

func Constructor() RandomizedSet {
    return RandomizedSet{
        numMap: make(map[int]int),
        numList: []int{},
    }
}

func (this *RandomizedSet) Insert(val int) bool {
    if _, exists := this.numMap[val]; exists {
        return false
    }
    this.numMap[val] = len(this.numList)
    this.numList = append(this.numList, val)
    return true
}

func (this *RandomizedSet) Remove(val int) bool {
    if idx, exists := this.numMap[val]; exists {
        lastElement := this.numList[len(this.numList)-1]
        this.numList[idx] = lastElement
        this.numMap[lastElement] = idx
        this.numList = this.numList[:len(this.numList)-1]
        delete(this.numMap, val)
        return true
    }
    return false
}

func (this *RandomizedSet) GetRandom() int {
    return this.numList[rand.Intn(len(this.numList))]
}

Этот код реализует структуру данных LRU Cache (кэш с вытеснением давно неиспользуемых элементов). LRU Cache поддерживает операции вставки и получения элементов с ограничением по емкости.

Структура данных

Node: структура для хранения пар ключ-значение и связей в двусвязном списке
LRUCache:
- capacity: максимальная емкость кэша
- cache: карта для быстрого доступа к узлам по ключу
- head и tail: фиктивные узлы для упрощения операций с двусвязным списком

Алгоритм решения

Get(key int):
- Если ключ существует, перемещает соответствующий узел в начало списка и возвращает значение
- Если ключ не существует, возвращает -1
Put(key int, value int):
- Если ключ существует, обновляет значение и перемещает узел в начало списка
- Если ключ не существует:
  - Создает новый узел и добавляет его в начало списка
  - Если достигнута максимальная емкость, удаляет последний (наименее недавно использованный) элемент

addNode: добавляет узел в начало списка
removeNode: удаляет узел из списка
moveToHead: перемещает узел в начало списка
popTail: удаляет и возвращает последний узел в списке

Временная сложность:
- Get: O(1)
- Put: O(1)
Пространственная сложность: O(capacity), где capacity - максимальная емкость кэша

type Node struct {
	key, value int
	prev, next *Node
}

type LRUCache struct {
	capacity int
	cache    map[int]*Node
	head     *Node
	tail     *Node
}

func Constructor(capacity int) LRUCache {
	lru := LRUCache{
		capacity: capacity,
		cache:    make(map[int]*Node),
		head:     &Node{},
		tail:     &Node{},
	}
	lru.head.next = lru.tail
	lru.tail.prev = lru.head
	return lru
}

func (this *LRUCache) Get(key int) int {
	if node, exists := this.cache[key]; exists {
		this.moveToHead(node)
		return node.value
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	if node, exists := this.cache[key]; exists {
		node.value = value
		this.moveToHead(node)
	} else {
		newNode := &Node{key: key, value: value}
		this.cache[key] = newNode
		this.addNode(newNode)
		if len(this.cache) > this.capacity {
			tail := this.popTail()
			delete(this.cache, tail.key)
		}
	}
}

func (this *LRUCache) addNode(node *Node) {
	node.prev = this.head
	node.next = this.head.next
	this.head.next.prev = node
	this.head.next = node
}

func (this *LRUCache) removeNode(node *Node) {
	node.prev.next = node.next
	node.next.prev = node.prev
}

func (this *LRUCache) moveToHead(node *Node) {
	this.removeNode(node)
	this.addNode(node)
}

func (this *LRUCache) popTail() *Node {
	node := this.tail.prev
	this.removeNode(node)
	return node
}

Этот код решает задачу о сборе дождевой воды. Дан массив целых чисел height, представляющий высоту стен. Функция trap вычисляет, сколько воды может быть собрано между стенами после дождя.

Алгоритм решения

Используется метод двух указателей: left и right
Поддерживаются переменные leftMax и rightMax для отслеживания максимальной высоты с левой и правой стороны соответственно
На каждом шаге:
- Сравниваются высоты на позициях left и right
- Обрабатывается меньшая высота:
  - Если текущая высота больше или равна максимальной с этой стороны, обновляется максимум
  - Иначе, добавляется количество воды, которое может быть собрано над текущей позицией
- Соответствующий указатель сдвигается к центру
Процесс продолжается, пока указатели не встретятся

Временная сложность: O(n), где n - количество элементов в массиве height
Пространственная сложность: O(1), используется постоянное количество дополнительной памяти

func trap(height []int) int {
	if len(height) < 3 {
		return 0
	}

	left, right := 0, len(height)-1
	leftMax, rightMax := 0, 0
	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
}

Этот код реализует два варианта бинарного поиска:

Стандартный бинарный поиск в отсортированном массиве
Модифицированный бинарный поиск для частично отсортированного (повернутого) массива

Алгоритм решения

1. Стандартный бинарный поиск (`binarySearch`):

Инициализация указателей left и right на начало и конец массива
Пока left <= right:
- Вычисление среднего индекса mid
- Если элемент найден, возврат его индекса
- Если целевое значение больше среднего, сдвиг left
- Иначе, сдвиг right
Возврат -1, если элемент не найден

2. Модифицированный бинарный поиск (`binarySearchNotSorted`):

Аналогичная инициализация указателей
Пока left <= right:
- Вычисление среднего индекса mid
- Если элемент найден, возврат его индекса
- Определение, какая половина массива отсортирована
- Проверка, находится ли целевое значение в отсортированной половине
- Сдвиг указателей соответственно
Возврат -1, если элемент не найден

Временная сложность: O(log n) для обоих алгоритмов
Пространственная сложность: O(1) для обоих алгоритмов

func binarySearch(arr []int, target int) int {
	left, right := 0, len(arr)-1
	for left <= right {
		mid := left + (right-left)/2
		if arr[mid] == target {
			return mid
		}
		if arr[mid] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	return -1 // Target not found in the array
}

func binarySearchNotSorted(arr []int, target int) int {
	left, right := 0, len(arr)-1
	for left <= right {
		mid := left + (right-left)/2
		if arr[mid] == target {
			return mid
		}
		if arr[left] <= arr[mid] && (arr[left] <= target && target <= arr[mid]) ||
			(arr[left] > arr[mid] && (arr[left] <= target || target <= arr[mid])) {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return -1 // Target not found in the array
}

Этот алгоритм решает задачу объединения пользователей, у которых есть общие email-адреса. Он использует структуру графа для представления связей между пользователями и их email-адресами, а затем находит связанные компоненты в этом графе.

Алгоритм решения

Создание графа:
- Каждый пользователь представлен как вершина.
- Каждый email-адрес связывает пользователей, которым он принадлежит.
Добавление пользователей в граф:
- Для каждого пользователя создается запись в графе.
- Каждый email-адрес пользователя связывается с его именем.
Поиск связанных компонентов:
- Используется алгоритм поиска в глубину (DFS) для нахождения всех связанных пользователей.
- Каждый найденный компонент представляет группу связанных пользователей.
Удаление дубликатов email-адресов в каждой группе.
Сортировка результата по именам пользователей.

Временная сложность: O(N * E + N log N), где:
- N - количество пользователей
- E - общее количество email-адресов
Пространственная сложность: O(N + E)

// User представляет пользователя с именем и списком email-адресов
type User struct {
	name   string
	emails []string
}

// Graph представляет граф пользователей и их email-адресов
type Graph struct {
	users  map[string]*User  // Карта пользователей по имени
	emails map[string]string // Карта email-адресов к именам пользователей
}

// NewGraph создает и возвращает новый экземпляр Graph
func NewGraph() *Graph {
	return &Graph{
		users:  make(map[string]*User),
		emails: make(map[string]string),
	}
}

// AddUser добавляет пользователя в граф
func (g *Graph) AddUser(user User) {
	// Добавляем пользователя, если его еще нет в графе
	if _, exists := g.users[user.name]; !exists {
		g.users[user.name] = &user
	}
	// Связываем каждый email с именем пользователя
	for _, email := range user.emails {
		g.emails[email] = user.name
	}
}

// dfs выполняет поиск в глубину для нахождения связанных пользователей
func (g *Graph) dfs(userName string, visited map[string]bool, component *User) {
	visited[userName] = true
	user := g.users[userName]
	component.emails = append(component.emails, user.emails...)

	// Рекурсивно обходим всех связанных пользователей
	for _, email := range user.emails {
		if connectedUser, exists := g.emails[email]; exists && !visited[connectedUser] {
			g.dfs(connectedUser, visited, component)
		}
	}
}

// FindConnectedUsers находит все группы связанных пользователей
func (g *Graph) FindConnectedUsers() []User {
	visited := make(map[string]bool)
	var result []User

	// Обходим всех пользователей и находим связанные компоненты
	for userName := range g.users {
		if !visited[userName] {
			continue
		}

		component := &User{name: userName}
		g.dfs(userName, visited, component)
		component.emails = g.removeDuplicates(component.emails)
		result = append(result, *component)
	}

	// Сортируем результат по именам пользователей
	sort.Slice(result, func(i, j int) bool {
		return result[i].name < result[j].name
	})

	return result
}

// removeDuplicates удаляет дубликаты email-адресов
func (g *Graph) removeDuplicates(emails []string) []string {
	seen := make(map[string]bool)
	var result []string
	for _, email := range emails {
		if !seen[email] {
			seen[email] = true
			result = append(result, email)
		}
	}
	return result
}

// mergeUsers объединяет пользователей на основе общих email-адресов
func mergeUsers(users []User) []User {
	graph := NewGraph()
	for _, user := range users {
		graph.AddUser(user)
	}

	return graph.FindConnectedUsers()
}

Алгоритмы - Другие

Реализация очереди с использованием двух стеков

Алгоритм решения

Счетчик недавних вызовов

Алгоритм решения

Восстановление маршрута путешествия

Алгоритм решения

Наименьшее количество идеальных квадратов

Алгоритм решения

Рандомизированное множество

Структура данных:

Алгоритм решения

LRU Cache (Least Recently Used Cache)

Структура данных

Алгоритм решения

Задача о сборе дождевой воды (Trapping Rain Water)

Алгоритм решения

Бинарный поиск (Binary Search)

Алгоритм решения

1. Стандартный бинарный поиск (binarySearch):

2. Модифицированный бинарный поиск (binarySearchNotSorted):

Объединение пользователей на основе общих email-адресов

Алгоритм решения

1. Стандартный бинарный поиск (`binarySearch`):

2. Модифицированный бинарный поиск (`binarySearchNotSorted`):