#medium
Задача: 331. Verify Preorder Serialization of a Binary Tree

Один из способов сериализации бинарного дерева — использование обхода в порядке предварительного прохода (preorder traversal). Когда мы встречаем ненулевой узел, мы записываем значение узла. Если это нулевой узел, мы записываем его с использованием специального значения, такого как '#'.

Дана строка, содержащая значения, разделенные запятыми, представляющие предварительный обход дерева (preorder). Верните true, если это правильная сериализация предварительного обхода бинарного дерева.

Гарантируется, что каждое значение в строке, разделенное запятыми, должно быть либо целым числом, либо символом '#', представляющим нулевой указатель.
Вы можете предположить, что формат ввода всегда действителен.
Например, он никогда не может содержать две последовательные запятые, такие как "1,,3".
Примечание: Вам не разрешено восстанавливать дерево.

Пример:

Input: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
Output: true

👨‍💻 Алгоритм:

1⃣Инициализация и разбор строки:
Инициализируйте переменную slots значением 1, представляющую количество доступных слотов.
Разделите строку по запятым, чтобы получить массив элементов.

2⃣Итерация по элементам и проверка:
Перебирайте каждый элемент массива. Для каждого элемента уменьшайте количество слотов на 1.
Если количество слотов становится отрицательным, верните false, так как это означает неправильную сериализацию.
Если элемент не равен '#', увеличьте количество слотов на 2, так как непустой узел создает два новых слота.

3⃣Проверка завершения:
После итерации по всем элементам проверьте, равно ли количество слотов 0. Если да, верните true, в противном случае false.

😎 Решение:

func isValidSerialization(preorder string) bool {
    slots := 1
    nodes := strings.Split(preorder, ",")
    
    for _, node := range nodes {
        slots--
        if slots < 0 {
            return false
        }
        if node != "#" {
            slots += 2
        }
    }
    
    return slots == 0
}

Ставь 👍 и забирай 📚 Базу знаний

#easy
Задача: 234. Palindrome Linked List

Дан головной элемент односвязного списка. Верните true, если список является палиндромом, и false в противном случае.

Пример:

Input: head = [1,2,2,1]
Output: true

👨‍💻 Алгоритм:

1⃣Копирование односвязного списка в массив: Итеративно пройдите по односвязному списку, добавляя каждое значение в массив. Для этого используйте переменную currentNode, указывающую на текущий узел. На каждой итерации добавляйте currentNode.val в массив и обновляйте currentNode, чтобы он указывал на currentNode.next. Остановите цикл, когда currentNode укажет на null.

2⃣Проверка массива на палиндром: Используйте метод с двумя указателями для проверки массива на палиндром. Разместите один указатель в начале массива, а другой в конце. На каждом шаге проверяйте, равны ли значения, на которые указывают указатели, и перемещайте указатели к центру, пока они не встретятся.

3⃣Сравнение значений: Помните, что необходимо сравнивать значения узлов, а не сами узлы. Используйте node_1.val == node_2.val для сравнения значений узлов. Сравнение узлов как объектов node_1 == node_2 не даст ожидаемого результата.

😎 Решение:

func isPalindrome(head *ListNode) bool {
    vals := []int{}
    currentNode := head

    for currentNode != nil {
        vals = append(vals, currentNode.Val)
        currentNode = currentNode.Next
    }

    front := 0
    back := len(vals) - 1
    for front < back {
        if vals[front] != vals[back] {
            return false
        }
        front++
        back--
    }
    return true
}

Ставь 👍 и забирай 📚 Базу знаний

#hard
Задача: 460. LFU Cache

Спроектируйте и реализуйте структуру данных для кеша с наименьшим количеством использования (Least Frequently Used, LFU).

Реализуйте класс LFUCache:

LFUCache(int capacity): Инициализирует объект с указанной вместимостью структуры данных.
int get(int key): Возвращает значение ключа, если ключ существует в кеше. В противном случае возвращает -1.
void put(int key, int value): Обновляет значение ключа, если он уже присутствует, или вставляет ключ, если его еще нет. Когда кеш достигает своей вместимости, он должен аннулировать и удалить ключ, используемый наименее часто, перед вставкой нового элемента. В этой задаче, если имеется несколько ключей с одинаковой частотой использования, аннулируется наименее недавно использованный ключ.
Чтобы определить наименее часто используемый ключ, для каждого ключа в кеше поддерживается счетчик использования. Ключ с наименьшим счетчиком использования является наименее часто используемым ключом.
Когда ключ впервые вставляется в кеш, его счетчик использования устанавливается на 1 (из-за операции put). Счетчик использования для ключа в кеше увеличивается при вызове операции get или put для этого ключа.

Функции get и put должны иметь среднюю временную сложность O(1).

Пример:

Input
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

👨‍💻 Алгоритм:

1⃣insert(int key, int frequency, int value):
Вставить пару частота-значение в cache с заданным ключом.
Получить LinkedHashSet, соответствующий данной частоте (по умолчанию пустой Set), и вставить в него ключ.

2⃣int get(int key):
Если ключа нет в кеше, вернуть -1.
Получить частоту и значение из кеша.
Удалить ключ из LinkedHashSet, связанного с частотой.
Если minf == frequency и LinkedHashSet пуст, увеличить minf на 1 и удалить запись частоты из frequencies.
Вызвать insert(key, frequency + 1, value).
Вернуть значение.

3⃣void put(int key, int value):
Если capacity <= 0, выйти.
Если ключ существует, обновить значение и вызвать get(key).
Если размер кеша равен capacity, удалить первый элемент из LinkedHashSet, связанного с minf, и из кеша.
Установить minf в 1.
Вызвать insert(key, 1, value).

😎 Решение:

package main
type LFUCache struct {
    cache       map[int][2]int
    frequencies map[int][]int
    capacity    int
    minf        int
}
func Constructor(capacity int) LFUCache {
    return LFUCache{
        cache:       make(map[int][2]int),
        frequencies: make(map[int][]int),
        capacity:    capacity,
    }
}
func (c *LFUCache) insert(key, freq, value int) {
    c.frequencies[freq] = append(c.frequencies[freq], key)
    c.cache[key] = [2]int{freq, value}
}
func (c *LFUCache) Get(key int) int {
    if val, found := c.cache[key]; !found {
        return -1
    } else {
        freq, value := val[0], val[1]
        c.frequencies[freq] = removeKey(c.frequencies[freq], key)
        if len(c.frequencies[freq]) == 0 {
            delete(c.frequencies, freq)
            if c.minf == freq {
                c.minf++
            }
        }
        c.insert(key, freq+1, value)
        return value
    }
}
func (c *LFUCache) Put(key int, value int) {
    if c.capacity <= 0 {
        return
    }
    if val, found := c.cache[key]; found {
        c.cache[key] = [2]int{val[0], value}
        c.Get(key)
        return
    }
    if len(c.cache) == c.capacity {
        minFreqKeys := c.frequencies[c.minf]
        delete(c.cache, minFreqKeys[0])
        c.frequencies[c.minf] = minFreqKeys[1:]
        if len(c.frequencies[c.minf]) == 0 {
            delete(c.frequencies, c.minf)
        }
    }
    c.minf = 1
    c.insert(key, 1, value)
}
func removeKey(slice []int, key int) []int {
    for i, v := range slice {
        if v == key {
            return append(slice[:i], slice[i+1:]...)
        }
    }
    return slice
}

Ставь 👍 и забирай 📚 Базу знаний

#medium
Задача: 370. Range Addition

Дано целое число length и массив updates, где updates[i] = [startIdxi, endIdxi, inci].

У вас есть массив arr длины length, заполненный нулями. Вам нужно применить некоторые операции к arr. В i-й операции следует увеличить все элементы arr[startIdxi], arr[startIdxi + 1], ..., arr[endIdxi] на inci.

Верните arr после применения всех обновлений.

Пример:

Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output: [-2,0,3,5,3]

👨‍💻 Алгоритм:

1⃣Для каждого обновления (start, end, val) выполните две операции:
Увеличьте значение в позиции start на val: arr[start] = arr[start] + val.
Уменьшите значение в позиции end + 1 на val: arr[end + 1] = arr[end + 1] - val.

2⃣Примените конечное преобразование: вычислите кумулятивную сумму всего массива (с индексами, начиная с 0).

3⃣Верните обновленный массив arr.

😎 Решение:

fun getModifiedArray(length: Int, updates: Array<IntArray>): IntArray {
    val result = IntArray(length)

    for (update in updates) {
        val start = update[0]
        val end = update[1]
        val `val` = update[2]
        result[start] += `val`
        if (end + 1 < length) {
            result[end + 1] -= `val`
        }
    }

    for (i in 1 until length) {
        result[i] += result[i - 1]
    }

    return result
}

Ставь 👍 и забирай 📚 Базу знаний

#medium
Задача: 370. Range Addition

Дано целое число length и массив updates, где updates[i] = [startIdxi, endIdxi, inci].

У вас есть массив arr длины length, заполненный нулями. Вам нужно применить некоторые операции к arr. В i-й операции следует увеличить все элементы arr[startIdxi], arr[startIdxi + 1], ..., arr[endIdxi] на inci.

Верните arr после применения всех обновлений.

Пример:

Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output: [-2,0,3,5,3]

👨‍💻 Алгоритм:

1⃣Для каждого обновления (start, end, val) выполните две операции:
Увеличьте значение в позиции start на val: arr[start] = arr[start] + val.
Уменьшите значение в позиции end + 1 на val: arr[end + 1] = arr[end + 1] - val.

2⃣Примените конечное преобразование: вычислите кумулятивную сумму всего массива (с индексами, начиная с 0).

3⃣Верните обновленный массив arr.

😎 Решение:

func getModifiedArray(length int, updates [][]int) []int {
    result := make([]int, length)

    for _, update := range updates {
        start, end, val := update[0], update[1], update[2]
        result[start] += val
        if end+1 < length {
            result[end+1] -= val
        }
    }

    for i := 1; i < length; i++ {
        result[i] += result[i-1]
    }

    return result
}

Ставь 👍 и забирай 📚 Базу знаний

#medium
Задача: 371. Sum of Two Integers

Даны два целых числа a и b. Вернуть сумму этих двух чисел, не используя операторы + и -.

Пример:

Input: a = 1, b = 2
Output: 3

👨‍💻 Алгоритм:

1⃣Упростите задачу до двух случаев: сумма или вычитание двух положительных целых чисел: x ± y, где x > y. Запомните знак результата.

2⃣Если нужно вычислить сумму:
Пока перенос не равен нулю (y != 0):
Текущий ответ без переноса равен XOR x и y: answer = x ^ y.
Текущий перенос равен сдвинутому влево AND x и y: carry = (x & y) << 1.
Подготовьтесь к следующему циклу: x = answer, y = carry.
Верните x * sign.

3⃣Если нужно вычислить разность:
Пока заимствование не равно нулю (y != 0):
Текущий ответ без заимствования равен XOR x и y: answer = x ^ y.
Текущее заимствование равно сдвинутому влево AND НЕ x и y: borrow = ((~x) & y) << 1.
Подготовьтесь к следующему циклу: x = answer, y = borrow.
Верните x * sign.

😎 Решение:

package main

import "math"

func getSum(a int, b int) int {
    x, y := int(math.Abs(float64(a))), int(math.Abs(float64(b)))
    if x < y {
        return getSum(b, a)
    }
    sign := 1
    if a < 0 {
        sign = -1
    }

    if a * b >= 0 {
        for y != 0 {
            carry := (x & y) << 1
            x ^= y
            y = carry
        }
    } else {
        for y != 0 {
            borrow := ((^x) & y) << 1
            x ^= y
            y = borrow
        }
    }
    return x * sign
}

Ставь 👍 и забирай 📚 Базу знаний

#medium
Задача: 372. Super Pow

Ваша задача — вычислить а^b mod 1337, где a - положительное число, а b - чрезвычайно большое положительное целое число, заданное в виде массива.

Пример:

Input: a = 2, b = [3]
Output: 8

👨‍💻 Алгоритм:

1⃣Разделите задачу на более мелкие задачи: вычислите a^b mod 1337, используя свойства модульной арифметики и степенной функции. Разделите большой показатель b на меньшие части, чтобы обрабатывать их по очереди.

2⃣Используйте метод быстрого возведения в степень (pow) для эффективного вычисления больших степеней с модулем 1337.

3⃣Объедините результаты для каждой части показателя b, используя свойства модульной арифметики: (a^b) % 1337 = ((a^(b1)) % 1337 * (a^(b2)) % 1337 * ...) % 1337.

😎 Решение:

package main

import "math"

func getSum(a int, b int) int {
    x, y := int(math.Abs(float64(a))), int(math.Abs(float64(b)))
    if x < y {
        return getSum(b, a)
    }
    sign := 1
    if a < 0 {
        sign = -1
    }

    if a * b >= 0 {
        for y != 0 {
            carry := (x & y) << 1
            x ^= y
            y = carry
        }
    } else {
        for y != 0 {
            borrow := ((^x) & y) << 1
            x ^= y
            y = borrow
        }
    }
    return x * sign
}

Ставь 👍 и забирай 📚 Базу знаний

#easy
Задача: 461. Hamming Distance

Расстояние Хэмминга между двумя целыми числами — это количество позиций, в которых соответствующие биты различны.

Даны два целых числа x и y, верните расстояние Хэмминга между ними.

Пример:

Input: x = 3, y = 1
Output: 1

👨‍💻 Алгоритм:

1⃣Во-первых, стоит упомянуть, что в большинстве (или, по крайней мере, во многих) языков программирования есть встроенные функции для подсчета битов, установленных в 1. Если вам нужно решить такую задачу в реальном проекте, то лучше использовать эти функции, чем изобретать велосипед.

2⃣Однако, поскольку это задача на LeetCode, использование встроенных функций можно сравнить с "реализацией LinkedList с использованием LinkedList". Поэтому рассмотрим также несколько интересных ручных алгоритмов для подсчета битов.

3⃣Пошаговый подсчет битов:
Выполните побитовое XOR между x и y.
Инициализируйте счетчик bitCount = 0.
Пока число не равно нулю:
Если текущий бит равен 1, увеличьте bitCount.
Сдвиньте число вправо на один бит.
Возвращайте bitCount.

😎 Решение:

package main

import (
    "math/bits"
)

func hammingDistance(x int, y int) int {
    return bits.OnesCount(uint(x ^ y))
}

Ставь 👍 и забирай 📚 Базу знаний

#hard
Задача: 332. Reconstruct Itinerary

Вам дан список авиабилетов, где tickets[i] = [fromi, toi] представляют собой аэропорты отправления и прибытия одного рейса. Восстановите маршрут в порядке следования и верните его.

Все билеты принадлежат человеку, который вылетает из "JFK", поэтому маршрут должен начинаться с "JFK". Если существует несколько возможных маршрутов, вы должны вернуть маршрут, который имеет наименьший лексикографический порядок при чтении как одна строка.
Например, маршрут ["JFK", "LGA"] имеет меньший лексикографический порядок, чем ["JFK", "LGB"].
Вы можете предположить, что все билеты формируют хотя бы один действительный маршрут. Вы должны использовать все билеты один раз и только один раз.

Пример:

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]

👨‍💻 Алгоритм:

1⃣Построение графа и сортировка:
Создайте граф flightMap, где ключи - это аэропорты отправления, а значения - это списки аэропортов прибытия.
Пройдите по всем билетам и заполните flightMap соответствующими значениями.
Отсортируйте списки аэропортов прибытия в лексикографическом порядке.

2⃣Пост-упорядоченный обход (DFS):
Создайте функцию DFS, которая будет рекурсивно проходить по всем ребрам (рейсам), начиная с аэропорта "JFK".
Во время обхода удаляйте использованные рейсы из графа, чтобы не проходить по ним повторно.

3⃣Формирование маршрута:
По мере завершения обхода добавляйте текущий аэропорт в начало списка результата.
После завершения DFS верните сформированный маршрут.

😎 Решение:

func findItinerary(tickets [][]string) []string {
    flightMap := make(map[string][]string)
    result := []string{}
    
    for _, ticket := range tickets {
        flightMap[ticket[0]] = append(flightMap[ticket[0]], ticket[1])
    }
    
    for key := range flightMap {
        sort.Strings(flightMap[key])
    }
    
    var dfs func(string)
    dfs = func(origin string) {
        for len(flightMap[origin]) > 0 {
            nextDest := flightMap[origin][0]
            flightMap[origin] = flightMap[origin][1:]
            dfs(nextDest)
        }
        result = append([]string{origin}, result...)
    }
    
    dfs("JFK")
    return result
}

Ставь 👍 и забирай 📚 Базу знаний

#medium
Задача: 333. Largest BST Subtree

Дан корень бинарного дерева, найдите самое большое поддерево, которое также является деревом бинарного поиска (BST), где "самое большое" означает поддерево с наибольшим количеством узлов.

Дерево бинарного поиска (BST) — это дерево, в котором все узлы соблюдают следующие свойства:
Значения в левом поддереве меньше значения их родительского (корневого) узла.
Значения в правом поддереве больше значения их родительского (корневого) узла.
Примечание: Поддерево должно включать всех своих потомков.

Пример:

Input: root = [10,5,15,1,8,null,7]
Output: 3
Explanation: The Largest BST Subtree in this case is the highlighted one. The return value is the subtree's size, which is 3.

👨‍💻 Алгоритм:

1⃣Пост-упорядоченный обход дерева:
Обходите каждую ноду дерева в пост-упорядоченном порядке (left-right-root). Это позволит гарантировать, что обе поддеревья ноды уже проверены на соответствие критериям BST перед проверкой самой ноды.

2⃣Проверка условий BST для каждой ноды:
Для каждой ноды определите минимальное и максимальное значения в её левом и правом поддеревьях. Проверьте, удовлетворяет ли текущее поддерево условиям BST:
- значение текущей ноды должно быть больше максимального значения в левом поддереве.
- значение текущей ноды должно быть меньше минимального значения в правом поддереве.
Если условия выполняются, вычислите размер текущего поддерева как сумму размеров левого и правого поддеревьев плюс 1 (для текущей ноды).

3⃣Возврат максимального размера BST:
Если текущее поддерево не является BST, верните максимальный размер BST из его левого или правого поддерева.
В конце рекурсивного обхода верните максимальный размер BST в дереве.

😎 Решение:

import "math"

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

type NodeValue struct {
    minNode, maxNode, maxSize int
}

func largestBSTSubtreeHelper(root *TreeNode) NodeValue {
    if root == nil {
        return NodeValue{math.MaxInt64, math.MinInt64, 0}
    }
    
    left := largestBSTSubtreeHelper(root.Left)
    right := largestBSTSubtreeHelper(root.Right)
    
    if left.maxNode < root.Val && root.Val < right.minNode {
        return NodeValue{min(root.Val, left.minNode), max(root.Val, right.maxNode), 
                         left.maxSize + right.maxSize + 1}
    }
    
    return NodeValue{math.MinInt64, math.MaxInt64, max(left.maxSize, right.maxSize)}
}

func largestBSTSubtree(root *TreeNode) int {
    return largestBSTSubtreeHelper(root).maxSize
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Ставь 👍 и забирай 📚 Базу знаний

#medium
Задача: 462. Minimum Moves to Equal Array Elements II

Дан массив целых чисел nums размера n, вернуть минимальное количество ходов, необходимых для того, чтобы сделать все элементы массива равными.

В одном ходе вы можете увеличить или уменьшить элемент массива на 1.

Тестовые случаи составлены так, что ответ поместится в 32-битное целое число.

Пример:

Input: nums = [1,2,3]
Output: 2
Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

👨‍💻 Алгоритм:

1⃣Найти минимальный и максимальный элементы в массиве. Пусть k будет числом, к которому должны быть приведены все элементы массива.
2⃣Перебирать значения k в диапазоне между минимальным и максимальным элементами, вычисляя количество ходов, необходимых для каждого k.
3⃣Определить минимальное количество ходов среди всех возможных k, что и будет конечным результатом.

😎 Решение:

package main

import (
    "math"
    "sort"
)

func minMoves2(nums []int) int {
    ans := math.MaxInt64
    minval, maxval := nums[0], nums[0]
    for _, num := range nums {
        if num < minval {
            minval = num
        }
        if num > maxval {
            maxval = num
        }
    }
    for i := minval; i <= maxval; i++ {
        sum := 0
        for _, num := range nums {
            sum += int(math.Abs(float64(num - i)))
        }
        if sum < ans {
            ans = sum
        }
    }
    return ans
}

Ставь 👍 и забирай 📚 Базу знаний

#easy
Задача: 374. Guess Number Higher or Lower

Мы играем в игру "Угадай число". Правила игры следующие:

Я загадываю число от 1 до n. Вам нужно угадать, какое число я загадал.

Каждый раз, когда вы угадываете неправильно, я говорю вам, загаданное число больше или меньше вашего предположения.

Вы вызываете предопределенный API int guess(int num), который возвращает один из трех возможных результатов:

-1: Ваше предположение больше загаданного числа (т.е. num > pick).
1: Ваше предположение меньше загаданного числа (т.е. num < pick).
0: Ваше предположение равно загаданному числу (т.е. num == pick).
Верните загаданное число.

Пример:

Input: n = 10, pick = 6
Output: 6

👨‍💻 Алгоритм:

1⃣Применяем бинарный поиск для нахождения загаданного числа. Начинаем с числа, расположенного в середине диапазона. Передаем это число функции guess.

2⃣Если функция guess возвращает -1, это означает, что загаданное число меньше предположенного. Продолжаем бинарный поиск в диапазоне чисел, меньших данного.

3⃣Если функция guess возвращает 1, это означает, что загаданное число больше предположенного. Продолжаем бинарный поиск в диапазоне чисел, больших данного.

😎 Решение:

package main

func guessNumber(n int) int {
    low, high := 1, n
    for low <= high {
        mid := low + (high - low) / 2
        res := guess(mid)
        if res == 0 {
            return mid
        } else if res < 0 {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    return -1
}

Ставь 👍 и забирай 📚 Базу знаний

#easy
Задача: 375. Guess Number Higher or Lower II

Мы играем в угадайку. Правила игры следующие:

Я загадываю число между 1 и n.
Вы угадываете число.
Если вы угадаете правильное число, вы выигрываете игру.
Если вы угадаете неправильное число, я скажу вам, загаданное число больше или меньше, и вы продолжите угадывать.
Каждый раз, когда вы угадываете неправильное число x, вы платите x долларов. Если у вас закончились деньги, вы проигрываете игру.
Дано число n. Верните минимальную сумму денег, необходимую для гарантированной победы независимо от того, какое число я загадаю.
Пример:

Input: n = 1
Output: 0
Explanation: There is only one possible number, so you can guess 1 and not have to pay anything.

👨‍💻 Алгоритм:

1⃣В методе "грубой силы" для чисел в диапазоне (i, j) выбираем каждое число от i до j в качестве опорного и находим максимальную стоимость из его левых и правых сегментов. Если выбрать число из диапазона (i, (i + j) / 2) как опорное, правый сегмент будет длиннее левого, что приведет к большему максимальному затратам из правого сегмента.

2⃣Наша цель - уменьшить большие затраты, приходящиеся на правый сегмент. Поэтому целесообразно выбирать опорное число из диапазона ((i + j) / 2, j). В этом случае затраты на оба сегмента будут ближе друг к другу, что минимизирует общую стоимость.

3⃣Вместо перебора от i до j, итерируем от (i + j) / 2 до j, находя минимально возможные затраты аналогично методу грубой силы.

😎 Решение:

package main

func calculate(low, high int) int {
    if low >= high {
        return 0
    }
    minres := int(^uint(0) >> 1)
    for i := low; i <= high; i++ {
        res := i + max(calculate(i+1, high), calculate(low, i-1))
        if res < minres {
            minres = res
        }
    }
    return minres
}

func getMoneyAmount(n int) int {
    return calculate(1, n)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Ставь 👍 и забирай 📚 Базу знаний

#Medium
Задача: 477. Total Hamming Distance

Хэммингово расстояние между двумя целыми числами — это количество позиций, в которых соответствующие биты отличаются.

Дан целочисленный массив nums, верните сумму Хэмминговых расстояний между всеми парами чисел в nums.

Пример:

Input: nums = [4,14,2]
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

👨‍💻 Алгоритм:

1⃣Для каждой уникальной пары элементов из массива вычисляем битовое XOR, чтобы найти позиции, где биты различаются. Бит, равный 1 в результате, указывает на различие.

2⃣Для каждой пары элементов используем XOR, чтобы получить битовую разницу, и подсчитываем количество битов, равных 1, чтобы определить Хэммингово расстояние между парой.

3⃣Суммируем все Хэмминговы расстояния для всех пар, чтобы получить общую сумму Хэмминговых расстояний.

😎 Решение:

package main

func totalHammingDistance(nums []int) int {
    ans := 0
    if len(nums) == 0 {
        return ans
    }
    for i := 0; i < len(nums)-1; i++ {
        for j := i + 1; j < len(nums); j++ {
            ans += countBits(nums[i] ^ nums[j])
        }
    }
    return ans
}

func countBits(n int) int {
    count := 0
    for n > 0 {
        count += n & 1
        n >>= 1
    }
    return count
}

func main() {}

Ставь 👍 и забирай 📚 Базу знаний

#medium
Задача: 334. Increasing Triplet Subsequence

Дан массив целых чисел nums. Верните true, если существуют такие три индекса (i, j, k), что i < j < k и nums[i] < nums[j] < nums[k]. Если таких индексов не существует, верните false.

Пример:

Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

👨‍💻 Алгоритм:

1⃣Инициализация переменных:
Создайте две переменные first_num и second_num и установите их значение на максимальное целое значение (Integer.MAX_VALUE или аналогичный максимум для выбранного языка программирования). Эти переменные будут хранить минимальные значения, необходимые для проверки существования возрастающей тройки.

2⃣Итерация по массиву:
Пройдите по каждому элементу массива nums. Для каждого элемента выполните следующие проверки:
- если текущий элемент меньше или равен first_num, обновите first_num текущим элементом.
- иначе, если текущий элемент меньше или равен second_num, обновите second_num текущим элементом.
- иначе, если текущий элемент больше second_num, это означает, что найдена возрастающая тройка, поэтому верните true.

3⃣Возврат результата:
Если после завершения итерации по массиву не была найдена возрастающая тройка, верните false.

😎 Решение:

func increasingTriplet(nums []int) bool {
    firstNum := int(^uint(0) >> 1)  // Maximum integer
    secondNum := int(^uint(0) >> 1) // Maximum integer
    
    for _, n := range nums {
        if n <= firstNum {
            firstNum = n
        } else if n <= secondNum {
            secondNum = n
        } else {
            return true
        }
    }
    return false
}

Ставь 👍 и забирай 📚 Базу знаний

#medium
Задача: 376. Wiggle Subsequence

Колеблющаяся последовательность — это последовательность, в которой разности между последовательными числами строго чередуются между положительными и отрицательными. Первая разность (если она существует) может быть как положительной, так и отрицательной. Последовательность с одним элементом и последовательность с двумя неравными элементами тривиально являются колеблющимися последовательностями.

Например, [1, 7, 4, 9, 2, 5] — это колеблющаяся последовательность, потому что разности (6, -3, 5, -7, 3) чередуются между положительными и отрицательными.
В отличие от нее, [1, 4, 7, 2, 5] и [1, 7, 4, 5, 5] не являются колеблющимися последовательностями. Первая не является, потому что первые две разности положительные, а вторая не является, потому что последняя разность равна нулю.
Подпоследовательность получается путем удаления некоторых элементов (возможно, нуля) из исходной последовательности с сохранением оставшихся элементов в их первоначальном порядке.

Дан целочисленный массив nums, верните длину самой длинной колеблющейся подпоследовательности из nums.

Пример:

Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).

👨‍💻 Алгоритм:

1⃣Для понимания этого подхода создайте два массива для динамического программирования, названных up и down. Эти массивы будут хранить длины наибольших колеблющихся подпоследовательностей, заканчивающихся соответственно восходящим или нисходящим колебанием.

2⃣up[i] относится к длине самой длинной колеблющейся подпоследовательности на данный момент, если рассматривать i-й элемент как последний элемент последовательности, заканчивающейся восходящим колебанием. Аналогично, down[i] относится к длине самой длинной колеблющейся подпоследовательности, если рассматривать i-й элемент как последний элемент последовательности, заканчивающейся нисходящим колебанием.

3⃣up[i] обновляется каждый раз, когда мы находим восходящее колебание, заканчивающееся на i-м элементе. Чтобы найти up[i], необходимо учесть максимальное значение всех предыдущих подпоследовательностей, заканчивающихся нисходящим колебанием, т.е. down[j], для каждого j<i и nums[i]>nums[j]. Аналогично, down[i] обновляется при нахождении нисходящего колебания.

😎 Решение:

package main

func islandPerimeter(grid [][]int) int {
    rows := len(grid)
    cols := len(grid[0])
    
    result := 0
    
    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if grid[r][c] == 1 {
                up := 0
                if r != 0 {
                    up = grid[r-1][c]
                }
                left := 0
                if c != 0 {
                    left = grid[r][c-1]
                }
                down := 0
                if r != rows-1 {
                    down = grid[r+1][c]
                }
                right := 0
                if c != cols-1 {
                    right = grid[r][c+1]
                }
                
                result += 4 - (up + left + right + down)
            }
        }
    }
    
    return result
}

Ставь 👍 и забирай 📚 Базу знаний

#easy
Задача: 463. Island Perimeter

Дан массив размером row x col, представляющий карту, где grid[i][j] = 1 обозначает сушу, а grid[i][j] = 0 обозначает воду.

Клетки сетки соединены горизонтально/вертикально (не по диагонали). Сетка полностью окружена водой, и на ней находится ровно один остров (т.е. одна или более соединённых ячеек суши).

У острова нет "озёр", то есть вода внутри не соединена с водой вокруг острова. Одна ячейка - это квадрат со стороной 1. Сетка прямоугольная, ширина и высота не превышают 100. Определите периметр острова.

Пример:
Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Explanation: The perimeter is the 16 yellow stripes in the image above.

👨‍💻 Алгоритм:

1⃣Пройти через каждую ячейку сетки и, когда вы находитесь в ячейке с значением 1 (ячейка суши), проверить окружающие (СВЕРХУ, СПРАВА, СНИЗУ, СЛЕВА) ячейки.
2⃣Ячейка суши без каких-либо окружающих ячеек суши будет иметь периметр 4. Вычесть 1 за каждую окружающую ячейку суши.
3⃣Когда вы находитесь в ячейке с значением 0 (ячейка воды), ничего не делать. Просто перейти к следующей ячейке.

😎 Решение:

package main

func islandPerimeter(grid [][]int) int {
    rows := len(grid)
    cols := len(grid[0])
    
    result := 0
    
    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if grid[r][c] == 1 {
                up := 0
                if r != 0 {
                    up = grid[r-1][c]
                }
                left := 0
                if c != 0 {
                    left = grid[r][c-1]
                }
                down := 0
                if r != rows-1 {
                    down = grid[r+1][c]
                }
                right := 0
                if c != cols-1 {
                    right = grid[r][c+1]
                }
                
                result += 4 - (up + left + right + down)
            }
        }
    }
    
    return result
}

Ставь 👍 и забирай 📚 Базу знаний

#medium
Задача: 377. Combination Sum IV

Дан массив различных целых чисел nums и целое число target. Верните количество возможных комбинаций, которые в сумме дают target.

Тестовые случаи сгенерированы так, что ответ помещается в 32-битное целое число.

Пример:

Input: nums = [9], target = 3
Output: 0

👨‍💻 Алгоритм:

1⃣В этом подходе мы начнем со стратегии сверху вниз, которая, пожалуй, более интуитивна. Как следует из названия, стратегия сверху вниз начинается с исходных данных, и затем мы рекурсивно уменьшаем входные данные до меньшего масштаба, пока не достигнем уровней, которые больше невозможно разбить.

2⃣Из-за рекурсивной природы формулы мы можем напрямую перевести формулу в рекурсивную функцию.

3⃣Здесь, соответственно, мы определяем рекурсивную функцию под названием combs(remain), которая возвращает количество комбинаций, где каждая комбинация в сумме дает значение remain.

😎 Решение:

package main

func combinationSum4(nums []int, target int) int {
    memo := make(map[int]int)
    return combs(nums, target, memo)
}

func combs(nums []int, remain int, memo map[int]int) int {
    if remain == 0 {
        return 1
    }
    if val, found := memo[remain]; found {
        return val
    }

    result := 0
    for _, num := range nums {
        if remain - num >= 0 {
            result += combs(nums, remain - num, memo)
        }
    }
    memo[remain] = result
    return result
}

Ставь 👍 и забирай 📚 Базу знаний

#hard
Задача: 336. Palindrome Pairs

Вам дан массив уникальных строк words, индексируемый с 0.

Пара палиндромов — это пара целых чисел (i, j), таких что:
0 <= i, j < words.length,
i != j, и
words[i] + words[j] (конкатенация двух строк) является палиндромом.
Верните массив всех пар палиндромов из слов.

Вы должны написать алгоритм с временной сложностью O(сумма длин всех слов в words).

Пример:

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]

👨‍💻 Алгоритм:

1⃣Инициализация и подготовка данных:
Создайте структуру для хранения результатов (список пар индексов).
Создайте словарь для хранения слов и их индексов, чтобы ускорить поиск.

2⃣Итерация по всем парам слов и проверка:
Пройдите по всем парам слов в массиве words, используя два вложенных цикла.
Для каждой пары слов проверяйте, образуют ли они палиндром при конкатенации. Это делается путем объединения строк и проверки, равна ли объединенная строка своей обратной версии.

3⃣Добавление найденных пар в результат:
Если проверка на палиндром проходит, добавьте текущую пару индексов в список результатов.
Верните итоговый список всех найденных пар.

😎 Решение:

func palindromePairs(words []string) [][]int {
    var pairs [][]int
    
    for i := 0; i < len(words); i++ {
        for j := 0; j < len(words); j++ {
            if i == j {
                continue
            }
            combined := words[i] + words[j]
            if combined == reverseString(combined) {
                pairs = append(pairs, []int{i, j})
            }
        }
    }
    
    return pairs
}

func reverseString(s string) string {
    runes := []rune(s)
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
    return string(runes)
}

Ставь 👍 и забирай 📚 Базу знаний

#medium
Задача: 465. Optimal Account Balancing

Дан массив транзакций transactions, где transactions[i] = [fromi, toi, amounti] указывает на то, что человек с ID = fromi дал сумму amounti долларов человеку с ID = toi.

Верните минимальное количество транзакций, необходимых для урегулирования долгов.

Пример:

Input: transactions = [[0,1,10],[2,0,5]]
Output: 2

👨‍💻 Алгоритм:

1⃣Создать хеш-таблицу для хранения чистого баланса каждого человека.

2⃣Собрать все ненулевые чистые балансы в массив balance_list.

3⃣Определить рекурсивную функцию dfs(cur) для очистки всех балансов в диапазоне balance_list[0 ~ cur]:
Игнорировать cur, если баланс уже равен 0. Пока balance_list[cur] = 0, переходить к следующему человеку, увеличивая cur на 1.
Если cur = n, вернуть 0.
В противном случае установить cost на большое значение, например, inf.
Пройтись по индексу nxt от cur + 1, если balance_list[nxt] * balance_list[cur] < 0,
Добавить баланс balance_list[cur] к balance_list[nxt]: balance_list[nxt] += balance_list[cur].
Рекурсивно вызвать dfs(cur + 1) как dfs(cur) = 1 + dfs(cur + 1).
Убрать ранее переданный баланс от cur: balance_list[nxt] -= balance_list[cur] (откат).
Повторить с шага 5 и отслеживать минимальное количество операций cost = min(cost, 1 + dfs(cur + 1)), найденных в итерации.
Вернуть cost, когда итерация завершена. Вернуть dfs(0).

😎 Решение:

package main

func minTransfers(transactions [][]int) int {
    creditMap := make(map[int]int)
    for _, t := range transactions {
        creditMap[t[0]] += t[2]
        creditMap[t[1]] -= t[2]
    }
    
    creditList := []int{}
    for _, amount := range creditMap {
        if amount != 0 {
            creditList = append(creditList, amount)
        }
    }
    
    n := len(creditList)
    var dfs func(int) int
    dfs = func(cur int) int {
        for cur < n && creditList[cur] == 0 {
            cur++
        }
        if cur == n {
            return 0
        }
        cost := int(^uint(0) >> 1)
        for nxt := cur + 1; nxt < n; nxt++ {
            if creditList[nxt] * creditList[cur] < 0 {
                creditList[nxt] += creditList[cur]
                cost = min(cost, 1 + dfs(cur + 1))
                creditList[nxt] -= creditList[cur]
            }
        }
        return cost
    }
    
    return dfs(0)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Ставь 👍 и забирай 📚 Базу знаний