Задача: 172. Factorial Trailing Zeroes
Сложность: medium

Дано целое число n, верните количество конечных нулей в n!.

Обратите внимание, что n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.

Пример:

Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.

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

1⃣Вычислите факториал n:
Инициализируйте переменную nFactorial значением 1.
Для каждого i от 2 до n включительно умножайте nFactorial на i.

2⃣Подсчитайте количество конечных нулей в nFactorial:
Инициализируйте переменную zeroCount значением 0.
Пока nFactorial делится на 10 без остатка, делите его на 10 и увеличивайте zeroCount на 1.

3⃣Верните значение zeroCount как количество конечных нулей в n!.

😎 Решение:

import (
    "math/big"
)

func trailingZeroes(n int) int {
    nFactorial := big.NewInt(1)
    for i := 2; i <= n; i++ {
        nFactorial.Mul(nFactorial, big.NewInt(int64(i)))
    }

    zeroCount := 0
    ten := big.NewInt(10)
    zero := big.NewInt(0)
    modResult := new(big.Int)

    for {
        modResult.Mod(nFactorial, ten)
        if modResult.Cmp(zero) == 0 {
            nFactorial.Div(nFactorial, ten)
            zeroCount++
        } else {
            break
        }
    }

    return zeroCount
}

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

Задача: 460. LFU Cache
Сложность: hard

Спроектируйте и реализуйте структуру данных для кеша с наименьшим количеством использования (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
}

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

Задача: 1396. Design Underground System
Сложность: medium

Подземная железнодорожная система отслеживает время поездок между станциями для вычисления среднего времени поездки от одной станции до другой.

Реализуйте класс UndergroundSystem:
- void checkIn(int id, string stationName, int t)
Пассажир с карточкой, идентификатор которой равен id, регистрируется на станции stationName в момент времени t.
Пассажир может быть зарегистрирован только в одном месте в одно и то же время.
- void checkOut(int id, string stationName, int t)
Пассажир с карточкой, идентификатор которой равен id, покидает станцию stationName в момент времени t.
- double getAverageTime(string startStation, string endStation)
Возвращает среднее время, необходимое для поездки от startStation до endStation.
Среднее время рассчитывается на основе всех предыдущих поездок от startStation до endStation, где пассажиры зарегистрировались на startStation и вышли на endStation. Время поездки от startStation до endStation может отличаться от времени поездки от endStation до startStation. Перед вызовом getAverageTime как минимум один пассажир уже совершил поездку от startStation до endStation. Предполагается, что все вызовы методов checkIn и checkOut последовательны и происходят в хронологическом порядке.

Пример:

Input
["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]
[[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]
Output
[null,null,null,5.00000,null,null,5.50000]
Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8); // Customer 10 "Leyton" -> "Paradise" in 8-3 = 5
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000, (5) / 1 = 5
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16); // Customer 5 "Leyton" -> "Paradise" in 16-10 = 6
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000, (5 + 6) / 2 = 5.5

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

1⃣При регистрации на входе сохраняем информацию о начале пути (станция и время) в словаре checkInData.

2⃣При регистрации на выходе извлекаем информацию о начале пути из checkInData, вычисляем время поездки и обновляем статистику для маршрута в journeyData.

3⃣Для получения среднего времени поездки по заданному маршруту извлекаем статистику из journeyData и вычисляем среднее значение.

😎 Решение:

type UndergroundSystem struct {
    journeyData map[string][2]float64
    checkInData map[int][2]interface{}
}

func Constructor() UndergroundSystem {
    return UndergroundSystem{
        journeyData: make(map[string][2]float64),
        checkInData: make(map[int][2]interface{}),
    }
}

func (this *UndergroundSystem) CheckIn(id int, stationName string, t int) {
    this.checkInData[id] = [2]interface{}{stationName, t}
}

func (this *UndergroundSystem) CheckOut(id int, stationName string, t int) {
    checkIn := this.checkInData[id]
    startStation := checkIn[0].(string)
    startTime := checkIn[1].(int)
    delete(this.checkInData, id)
    routeKey := startStation + "->" + stationName
    tripTime := float64(t - startTime)
    if _, exists := this.journeyData[routeKey]; !exists {
        this.journeyData[routeKey] = [2]float64{0, 0}
    }
    this.journeyData[routeKey][0] += tripTime
    this.journeyData[routeKey][1] += 1
}

func (this *UndergroundSystem) GetAverageTime(startStation string, endStation string) float64 {
    stats := this.journeyData[startStation+"->"+endStation]
    return stats[0] / stats[1]
}

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

Задача: 476. Number Complement
Сложность: easy

Дополнение целого числа — это число, которое получается при замене всех 0 на 1 и всех 1 на 0 в его двоичном представлении.
Например, целое число 5 в двоичной системе — "101", и его дополнение — "010", что соответствует целому числу 2. Дано целое число num, верните его дополнение.

Пример:

Input: num = 5 
Output: 2  

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

1⃣Вычислите длину в битах входного числа: l = ⌊log₂(num)⌋ + 1.

2⃣Постройте битовую маску из 1-битов длины l: bitmask = (1 << l) − 1.

3⃣Верните результат операции XOR числа и битовой маски: num ⊕ bitmask.

😎 Решение:

package main

func findComplement(num int) int {
    bitmask := num
    bitmask |= (bitmask >> 1)
    bitmask |= (bitmask >> 2)
    bitmask |= (bitmask >> 4)
    bitmask |= (bitmask >> 8)
    bitmask |= (bitmask >> 16)
    return bitmask ^ num
}

func main() {}

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

Задача: 486. Predict the Winner
Сложность: medium

Дан массив nums. Игроки 1 и 2 поочередно берут по одному числу с любого конца массива.
Оба игрока играют оптимально. Нужно определить, сможет ли игрок 1 выиграть (или хотя бы не проиграть, т.е. равный счёт тоже считается победой).

Пример:

Input: nums = [1,5,2]
Output: false

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

1⃣Определяем рекурсивную функцию maxDiff(left, right), которая возвращает максимальную разницу очков между текущим игроком и соперником при игре на подотрезке массива.

2⃣На каждом шаге игрок может взять число либо с начала (left), либо с конца (right). После выбора число вычитается из результата рекурсивного вызова для оставшегося отрезка. Выбирается максимум из двух стратегий.

3⃣Игра начинается с полного массива: maxDiff(0, len(nums)-1). Если результат больше либо равен 0, игрок 1 может выиграть (или хотя бы не проиграть).

😎 Решение:

func maxDiff(nums []int, left int, right int) int {
    if left == right {
        return nums[left]
    }

    scoreByLeft := nums[left] - maxDiff(nums, left+1, right)
    scoreByRight := nums[right] - maxDiff(nums, left, right-1)

    if scoreByLeft > scoreByRight {
        return scoreByLeft
    }
    return scoreByRight
}

func predictTheWinner(nums []int) bool {
    return maxDiff(nums, 0, len(nums)-1) >= 0
}

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

Задача: 1370. Increasing Decreasing String
Сложность: easy

Дана строка s. Переставьте символы строки, используя следующий алгоритм:

Выберите наименьший символ из s и добавьте его к результату.
Выберите наименьший символ из s, который больше последнего добавленного символа, и добавьте его.
Повторяйте шаг 2, пока не сможете выбрать больше символов.
Выберите наибольший символ из s и добавьте его к результату.
Выберите наибольший символ из s, который меньше последнего добавленного символа, и добавьте его.
Повторяйте шаг 5, пока не сможете выбрать больше символов.
Повторяйте шаги с 1 по 6, пока не выберете все символы из s.
На каждом этапе, если наименьший или наибольший символ появляется более одного раза, вы можете выбрать любое его вхождение и добавить его к результату.

Верните результирующую строку после сортировки s с помощью этого алгоритма.

Пример:
Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

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

1⃣Инициализация и сортировка:
Создайте словарь для подсчета количества каждого символа в строке s. Создайте результирующую строку result.

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

3⃣Проверка завершения:
Повторяйте шаги 2 и 3, пока не будут добавлены все символы из строки s в result.

😎 Решение:

func sortString(s string) string {
    charCount := make([]int, 26)
    for _, c := range s {
        charCount[c - 'a']++
    }
    
    result := make([]byte, 0, len(s))
    for len(result) < len(s) {
        for c := byte('a'); c <= 'z'; c++ {
            if charCount[c - 'a'] > 0 {
                result = append(result, c)
                charCount[c - 'a']--
            }
        }
        for c := byte('z'); c >= 'a'; c-- {
            if charCount[c - 'a'] > 0 {
                result = append(result, c)
                charCount[c - 'a']--
            }
        }
    }
    
    return string(result)
}

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

Задача: 655. Print Binary Tree
Сложность: medium

Учитывая корень двоичного дерева, постройте строковую матрицу res с индексом 0 размером m x n, которая представляет собой форматированную раскладку дерева. Форматированная матрица должна быть построена по следующим правилам: высота дерева равна height, количество строк m должно быть равно height + 1. Количество столбцов n должно быть равно 2height+1 - 1. Поместите корневой узел в середину верхней строки (более формально, в позицию res[0][(n-1)/2]).
Для каждого узла, который был помещен в матрицу в позицию res[r][c], поместите его левого ребенка в res[r+1][c-2height-r-1], а правого - в res[r+1][c+2height-r-1]. Продолжайте этот процесс, пока не будут размещены все узлы дерева. Любые пустые ячейки должны содержать пустую строку "". Верните построенную матрицу res.

Пример:

Input: root = [1,2]
Output: 
[["","1",""],
 ["2","",""]]

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

1⃣Найдите высоту дерева и определите размер матрицы (m x n).

2⃣Рекурсивно разместите узлы в матрице, начиная с корневого узла.

3⃣Верните заполненную матрицу.

😎 Решение:

package main

import (
    "fmt"
    "strconv"
    "strings"
)

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

func findHeight(root *TreeNode) int {
    if root == nil {
        return -1
    }
    leftHeight := findHeight(root.Left)
    rightHeight := findHeight(root.Right)
    if leftHeight > rightHeight {
        return 1 + leftHeight
    }
    return 1 + rightHeight
}

func fill(res [][]string, root *TreeNode, r, c, height int) {
    if root == nil {
        return
    }
    res[r][c] = strconv.Itoa(root.Val)
    if root.Left != nil {
        fill(res, root.Left, r+1, c-(1<<(height-r-1)), height)
    }
    if root.Right != nil {
        fill(res, root.Right, r+1, c+(1<<(height-r-1)), height)
    }
}

func printTree(root *TreeNode) [][]string {
    height := findHeight(root)
    m := height + 1
    n := (1 << (height + 1)) - 1
    res := make([][]string, m)
    for i := range res {
        res[i] = make([]string, n)
        for j := range res[i] {
            res[i][j] = ""
        }
    }
    fill(res, root, 0, (n-1)/2, height)
    return res
}

func main() {
    root := &TreeNode{Val: 1, Left: &TreeNode{Val: 2}, Right: &TreeNode{Val: 3}}
    result := printTree(root)
    for _, row := range result {
        fmt.Println(strings.Join(row, " "))
    }
}

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

Задача: 313. Super Ugly Number
Сложность: medium

Супер некрасивое число — это положительное целое число, простые множители которого находятся в массиве primes.

Дано целое число n и массив целых чисел primes. Верните n-е супер некрасивое число.

Гарантируется, что n-е супер некрасивое число помещается в 32-битное знаковое целое число.

Пример:

Input: n = 12, primes = [2,7,13,19]
Output: 32
Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 super ugly numbers given primes = [2,7,13,19].

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

1⃣Инициализация
Создайте массив ugly_numbers длиной n для хранения супер некрасивых чисел. Создайте массив indices длиной primes для отслеживания позиций в массиве ugly_numbers. Создайте массив next_ugly длиной primes для хранения следующего возможного супер некрасивого числа для каждого простого числа из primes.

2⃣Генерация супер некрасивых чисел
Установите первое значение в ugly_numbers как 1. Повторяйте до тех пор, пока не заполните массив ugly_numbers: Найдите минимальное значение в массиве next_ugly и добавьте его в ugly_numbers. Обновите соответствующий индекс в indices и пересчитайте значение в next_ugly.

3⃣Возврат результата
Верните последнее значение в массиве ugly_numbers, которое будет n-м супер некрасивым числом.

😎 Решение:

func nthSuperUglyNumber(n int, primes []int) int {
    ugly_numbers := make([]int, n)
    ugly_numbers[0] = 1
    indices := make([]int, len(primes))
    next_ugly := append([]int(nil), primes...)
    
    for i := 1; i < n; i++ {
        next_val := min(next_ugly)
        ugly_numbers[i] = next_val
        
        for j := 0; j < len(primes); j++ {
            if next_val == next_ugly[j] {
                indices[j]++
                next_ugly[j] = ugly_numbers[indices[j]] * primes[j]
            }
        }
    }
    
    return ugly_numbers[n-1]
}

func min(arr []int) int {
    minVal := arr[0]
    for _, val := range arr {
        if val < minVal {
            minVal = val
        }
    }
    return minVal
}

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

Задача: 408. Valid Word Abbreviation
Сложность: easy

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

Например, строка "замена" может быть сокращена следующим образом (но не ограничивается этим): "s10n" ("s ubstitutio n") "sub4u4" ("sub stit u tion") "12" ("замена") "su3i1u2on" ("su bst i t u ti on") "substitution" (без замены подстрок) Следующие сокращения не являются допустимыми:

"s55n" ("s ubsti tutio n", заменяемые подстроки смежные) "s010n" (содержит ведущие нули) "s0ubstitution" (заменяет пустую подстроку) Если задано строковое слово и аббревиатура abbr, верните, соответствует ли строка заданной аббревиатуре.

Подстрока - это непрерывная непустая последовательность символов в строке.

Пример:

Input: word = "internationalization", abbr = "i12iz4n"
Output: true

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

1⃣Инициализируйте два указателя: один для строки word и один для аббревиатуры abbr. Начните сравнение символов строки и аббревиатуры с начала.

2⃣Если символ аббревиатуры - это цифра, вычислите полное число и переместите указатель строки word на это количество символов. Если символ аббревиатуры - это буква, убедитесь, что он совпадает с текущим символом строки.

3⃣Повторяйте шаг 2, пока оба указателя не достигнут конца строки и аббревиатуры соответственно. Если это так, верните true, иначе false.

😎 Решение:

package main

import (
    "strconv"
    "unicode"
)

func validWordAbbreviation(word string, abbr string) bool {
    i, j := 0, 0
    for i < len(word) && j < len(abbr) {
        if unicode.IsDigit(rune(abbr[j])) {
            if abbr[j] == '0' {
                return false
            }
            num := 0
            for j < len(abbr) && unicode.IsDigit(rune(abbr[j])) {
                n, _ := strconv.Atoi(string(abbr[j]))
                num = num*10 + n
                j++
            }
            i += num
        } else {
            if word[i] != abbr[j] {
                return false
            }
            i++
            j++
        }
    }
    return i == len(word) && j == len(abbr)
}

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

Задача: 677. Map Sum Pairs
Сложность: medium

Создайте карту, которая позволяет выполнять следующие действия:

Отображает строковый ключ на заданное значение.
Возвращает сумму значений, у которых ключ имеет префикс, равный заданной строке.
Реализуйте класс MapSum:

MapSum() Инициализирует объект MapSum.
void insert(String key, int val) Вставляет пару ключ-значение в карту. Если ключ уже существовал, исходная пара ключ-значение будет заменена на новую.
int sum(string prefix) Возвращает сумму всех значений пар, у которых ключ начинается с данного префикса.

Пример:

Input
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
Output
[null, null, 3, null, 5]

Explanation
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);  
mapSum.sum("ap");           // return 3 (apple = 3)
mapSum.insert("app", 2);    
mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)

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

1⃣Для каждого ключа в карте проверить, начинается ли этот ключ с данного префикса.

2⃣Если ключ начинается с префикса, добавить его значение к ответу.

3⃣Вернуть полученную сумму как результат.

😎 Решение:

package main

import "strings"

type MapSum struct {
    mapData map[string]int
}

func Constructor() MapSum {
    return MapSum{mapData: make(map[string]int)}
}

func (this *MapSum) Insert(key string, val int) {
    this.mapData[key] = val
}

func (this *MapSum) Sum(prefix string) int {
    ans := 0
    for key, val := range this.mapData {
        if strings.HasPrefix(key, prefix) {
            ans += val
        }
    }
    return ans
}

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

Задача: 936. Stamping The Sequence
Сложность: hard

Вам даны две строки stamp и target. Изначально имеется строка s длины target.length со всеми s[i] == '?'. За один ход вы можете поместить штамп над s и заменить каждую букву в s на соответствующую букву из штампа. Например, если штамп = "abc" и target = "abcba", то s изначально будет "?????". За один ход вы можете: поместить штамп в индекс 0 s, чтобы получить "abc??", поместить штамп в индекс 1 s, чтобы получить "?abc?", или поместить штамп в индекс 2 s, чтобы получить "??abc". Обратите внимание, что штамп должен полностью находиться в границах s, чтобы штамповать (то есть вы не можете поместить штамп в индекс 3 s). Мы хотим преобразовать s в цель, используя не более 10 * target.length ходов. Верните массив индекса самой левой буквы, которая штампуется на каждом ходу. Если мы не можем получить цель из s за 10 * target.length оборотов, верните пустой массив

Пример:

Input: stamp = "abc", target = "ababc"
Output: [0,2]

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

1⃣Инициализировать переменные:
s как массив символов '?', длиной target.length.
res как список для хранения результатов.
done как массив булевых значений для отслеживания того, какие позиции уже штампованы.
target как массив символов для удобства.

2⃣Использовать функцию canStamp для проверки, можно ли штамповать stamp в target начиная с индекса i.
Использовать функцию doStamp для штампования stamp в target начиная с индекса i.
Повторять шаги, пока штампы возможны или достигнут максимум ходов (10 * target.length):
Перебрать все возможные начальные позиции для штампа.
Проверить, можно ли штамповать в текущей позиции.
Если можно, штамповать и добавить индекс в res.

3⃣Если все символы в s соответствуют символам в target, вернуть массив res в обратном порядке. Иначе, вернуть пустой массив.

😎 Решение:

package main

func movesToStamp(stamp string, target string) []int {
    s, t := []rune(stamp), []rune(target)
    m, n := len(s), len(t)
    res := []int{}
    done := make([]bool, n)
    
    canStamp := func(i int) bool {
        for j := 0; j < m; j++ {
            if t[i + j] != '?' && t[i + j] != s[j] {
                return false;
            }
        }
        return true;
    }
    
    doStamp := func(i int) {
        for j := 0; j < m; j++ {
            t[i + j] = '?'
        }
        res = append(res, i)
        done[i] = true
    }
    
    changed := true
    for changed {
        changed = false
        for i := 0; i <= n - m; i++ {
            if !done[i] && canStamp(i) {
                doStamp(i)
                changed = true
            }
        }
    }
    
    for _, c := range t {
        if c != '?' {
            return []int{}
        }
    }
    
    for i, j := 0, len(res) - 1; i < j; i, j = i + 1, j - 1 {
        res[i], res[j] = res[j], res[i]
    }
    return res
}

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

Задача: 253. Meeting Rooms II
Сложность: medium

Дан массив интервалов времени встреч intervals, где intervals[i] = [starti, endi]. Верните минимальное количество необходимых конференц-залов.

Пример:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

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

1⃣Отсортируйте встречи по времени их начала и инициализируйте мин-кучу с временем окончания первой встречи.

2⃣Для каждой последующей встречи проверьте, свободна ли комната (сравните время начала встречи с минимальным временем окончания в куче):
Если свободна, обновите время окончания этой комнаты.
Если не свободна, добавьте новое время окончания в кучу.

3⃣После обработки всех встреч размер кучи будет равен минимальному количеству необходимых комнат.

😎 Решение:

package main

import (
    "container/heap"
    "sort"
)

type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func minMeetingRooms(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    h := &MinHeap{intervals[0][1]}
    heap.Init(h)
    
    for i := 1; i < len(intervals); i++) {
        if intervals[i][0] >= (*h)[0] {
            heap.Pop(h)
        }
        heap.Push(h, intervals[i][1])
    }
    return h.Len()
}

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

Задача: 162. Find Peak Element
Сложность: medium

Пиковым элементом называется элемент, который строго больше своих соседей.

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

Вы можете представить, что nums[-1] = nums[n] = -∞. Другими словами, элемент всегда считается строго большим, чем сосед, находящийся за пределами массива.

Необходимо написать алгоритм, который работает за время O(log n).

Пример:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

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

1⃣Начальная проверка:
Определяем средний элемент массива mid как mid = low + (high - low) / 2. Это помогает предотвратить возможное переполнение при больших значениях индексов.

2⃣Определение направления поиска:
Сравниваем элемент nums[mid] с его правым соседом nums[mid + 1]. Если nums[mid] меньше nums[mid + 1], это указывает на наличие восходящей последовательности, и мы двигаемся вправо, устанавливая low = mid + 1. Это потому, что пик гарантированно находится в правой части.
Если nums[mid] больше nums[mid + 1], это указывает на наличие нисходящей последовательности, и пик находится либо в mid, либо слева от него, тогда устанавливаем high = mid.

3⃣Завершение поиска:
Процесс продолжается до тех пор, пока low не станет равным high, что означает сужение поисковой области до одного элемента, который и является пиком, поскольку мы исключили все другие возможности.

😎 Решение:

func findPeakElement(nums []int) int {
    return search(nums, 0, len(nums)-1)
}

func search(nums []int, l int, r int) int {
    if l == r {
        return l
    }
    mid := (l + r) / 2
    if nums[mid] > nums[mid+1] {
        return search(nums, l, mid)
    }
    return search(nums, mid+1, r)
}

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

Задача: 482. License Key Formatting
Сложность: easy

Вам дан лицензионный ключ, представленный в виде строки s, которая состоит только из буквенно-цифровых символов и тире. Строка разделена на n + 1 групп с помощью n тире. Вам также дано целое число k.

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

Пример:

Input: s = "5F3Z-2e-9-w", k = 4
 Output: "5F3Z-2E9W"
Explanation: The string s has been split into two parts, each part has 4 characters. Note that the two extra dashes are not needed and can be removed.

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

1⃣Инициализация
Установите count в 0 для подсчета символов в текущей группе. Установите ans в пустую строку для хранения конечного результата.

2⃣Итерация по входной строке в обратном порядке
Пропускайте символы '-'. Если текущий символ не '-', добавьте его в ans и увеличьте count на 1. Если count достигает k, добавьте '-' в ans и сбросьте count.

3⃣Завершение
Проверьте, есть ли в конце строки ans тире, и удалите его, если оно есть. Переверните строку ans и верните её.

😎 Решение:

package main

import (
    "strings"
    "unicode"
)

func licenseKeyFormatting(s string, k int) string {
    count := 0
    var ans strings.Builder

    for i := len(s) - 1; i >= 0; i-- {
        if s[i] != '-' {
            ans.WriteByte(byte(unicode.ToUpper(rune(s[i]))))
            count++
            if count == k {
                ans.WriteByte('-')
                count = 0
            }
        }
    }

    res := ans.String()
    if len(res) > 0 && res[len(res)-1] == '-' {
        res = res[:len(res)-1]
    }

    runes := []rune(res)
    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)
}

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

Задача: 1342. Number of Steps to Reduce a Number to Zero
Сложность: easy

Дано целое число num, вернуть количество шагов, необходимых для его сокращения до нуля.

На каждом шаге, если текущее число четное, его нужно разделить на 2, в противном случае, вы должны вычесть из него 1.

Пример:

Input: num = 14
Output: 6
Explanation: 
Step 1) 14 is even; divide by 2 and obtain 7. 
Step 2) 7 is odd; subtract 1 and obtain 6.
Step 3) 6 is even; divide by 2 and obtain 3. 
Step 4) 3 is odd; subtract 1 and obtain 2. 
Step 5) 2 is even; divide by 2 and obtain 1. 
Step 6) 1 is odd; subtract 1 and obtain 0.

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

1⃣На каждом шаге проверяйте, четное ли текущее число, используя оператор остатка от деления (%). Если число четное (number % 2 == 0), разделите его на 2.

2⃣Если число нечетное (number % 2 == 1), вычтите из него 1.

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

😎 Решение:

func numberOfSteps(num int) int {
    steps := 0
    for num != 0 {
        if num % 2 == 0 {
            num /= 2
        } else {
            num--
        }
        steps++
    }
    return steps
}

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

Задача: 242. Valid Anagram
Сложность: easy

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

Анаграмма — это слово или фраза, сформированная путём перестановки букв другого слова или фразы, обычно используя все исходные буквы ровно один раз.

Пример:

Input: s = "anagram", t = "nagaram"
Output: true

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

1⃣Создайте массив размером 26 для подсчета частот каждой буквы (поскольку s и t содержат только буквы от 'a' до 'z').

2⃣Пройдитесь по строке s, увеличивая счетчик соответствующей буквы. Затем пройдитесь по строке t, уменьшая счетчик для каждой буквы.

3⃣Проверьте, не опустился ли счетчик ниже нуля во время обхода строки t. Если это произошло, значит в t есть лишняя буква, которой нет в s, и следует вернуть false. Если после проверки всех букв все счетчики равны нулю, возвращайте true, указывая на то, что t является анаграммой s.

😎 Решение:

func isAnagram(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }
    count := [26]int{}
    for i := range s {
        count[s[i]-'a']++
        count[t[i]-'a']--
    }
    for _, c := range count {
        if c != 0 {
            return false
        }
    }
    return true
}

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

Задача: 405. Convert a Number to Hexadecimal
Сложность: easy

Если задано целое число num, верните строку, представляющую его шестнадцатеричное представление. Для отрицательных целых чисел используется метод дополнения до двух. Все буквы в строке ответа должны быть строчными, и в ответе не должно быть никаких ведущих нулей, кроме самого нуля. Примечание: Вам не разрешается использовать какие-либо встроенные библиотечные методы для непосредственного решения этой задачи.

Пример:

Input: num = 26
Output: "1a"

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

1⃣Определите, является ли число отрицательным. Если да, преобразуйте его в положительное число с помощью метода дополнения до двух. Для этого прибавьте к числу 2^32 и используйте битовую операцию И с маской 0xFFFFFFFF.

2⃣Создайте строку с шестнадцатеричными символами. Последовательно делите число на 16 и добавляйте соответствующий символ к результату, пока число не станет равным нулю.

3⃣Переверните строку результата и удалите ведущие нули, если они есть. Если строка пустая, верните "0".

😎 Решение:

package main

import (
    "fmt"
    "strings"
)

func toHex(num int) string {
    if num == 0 {
        return "0"
    }
    hexChars := "0123456789abcdef"
    if num < 0 {
        num += 1 << 32
    }
    result := []byte{}
    for num > 0 {
        result = append(result, hexChars[num%16])
        num /= 16
    }
    for i, j := 0, len(result)-1; i < j; i, j = i+1, j-1 {
        result[i], result[j] = result[j], result[i]
    }
    return string(result)
}

func main() {
    fmt.Println(toHex(26))
    fmt.Println(toHex(-1))
}

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

Задача: 1431. Kids With the Greatest Number of Candies
Сложность: easy

Дано n детей с конфетами. Вам дан целочисленный массив candies, где каждый candies[i] представляет количество конфет у i-го ребенка, и целое число extraCandies, обозначающее количество дополнительных конфет, которые у вас есть.

Вернуть булев массив result длиной n, где result[i] равно true, если, дав i-му ребенку все дополнительные конфеты, он будет иметь наибольшее количество конфет среди всех детей, или false в противном случае.

Обратите внимание, что несколько детей могут иметь наибольшее количество конфет.

Пример:

Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true] 
Explanation: If you give all extraCandies to:
- Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids.
- Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
- Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids.
- Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids.
- Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.

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

1⃣Найдите максимальное количество конфет в массиве candies, сохраняя его в переменной maxCandies.

2⃣Создайте булев список answer и пройдитесь по массиву candies, добавляя в answer значение true, если текущий ребенок с добавленными extraCandies имеет количество конфет больше или равное maxCandies, иначе добавляйте false.

3⃣Верните список answer.

😎 Решение:

func kidsWithCandies(candies []int, extraCandies int) []bool {
    maxCandies := 0
    for _, candy := range candies {
        if candy > maxCandies {
            maxCandies = candy
        }
    }
    result := make([]bool, len(candies))
    for i, candy := range candies {
        result[i] = candy + extraCandies >= maxCandies
    }
    return result
}

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

Задача: 120. Triangle
Сложность: medium

Дан массив в виде треугольника, верните минимальную сумму пути сверху вниз.

На каждом шаге вы можете перейти к соседнему числу в строке ниже. Более формально, если вы находитесь на индексе i в текущей строке, вы можете перейти либо к индексу i, либо к индексу i + 1 в следующей строке.

Пример:

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
   2
  3 4
 6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).

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

1⃣Простейший способ реализации этого заключается в перезаписи входных данных, то есть в использовании алгоритма "на месте". В подходе 2 мы рассмотрим, как модифицировать алгоритм так, чтобы он не перезаписывал входные данные, но при этом не требовал более чем O(n) дополнительного пространства.

2⃣Когда этот алгоритм завершит свою работу, каждая ячейка (строка, столбец) входного треугольника будет перезаписана минимальной суммой пути от (0, 0) (вершины треугольника) до (строка, столбец) включительно.
Совет на собеседовании: Алгоритмы "на месте" перезаписывают входные данные для экономии места, но иногда это может вызвать проблемы. Вот несколько ситуаций, когда алгоритм "на месте" может быть неуместен.

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

😎 Решение:

func minimumTotal(triangle [][]int) int {
    for row := 1; row < len(triangle); row++ {
        for col := 0; col <= row; col++ {
            smallestAbove := math.MaxInt32
            if col > 0 {
                smallestAbove = triangle[row-1][col-1]
            }
            if col < row {
                smallestAbove = min(smallestAbove, triangle[row-1][col])
            }
            triangle[row][col] += smallestAbove
        }
    }
    return minSlice(triangle[len(triangle)-1])
}

func minSlice(slice []int) int {
    minVal := slice[0]
    for _, val := range slice {
        minVal = min(minVal, val)
    }
    return minVal
}

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

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

Задача: 338. Counting Bits
Сложность: easy

Дано целое число n, верните массив ans длиной n + 1, такой что для каждого i (0 <= i <= n), ans[i] будет равняться количеству единиц в двоичном представлении числа i.

Пример:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

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

1⃣Инициализация массива:
Создайте массив ans длиной n + 1, заполненный нулями. Этот массив будет содержать количество единиц в двоичном представлении каждого числа от 0 до n.

2⃣Итерация и вычисление:
Пройдите в цикле по всем числам от 1 до n. Для каждого числа x используйте битовую операцию x & (x - 1), чтобы убрать последнюю установленную биту, и добавьте 1 к значению ans для этого результата. Это количество единиц в двоичном представлении числа x.

3⃣Возврат результата:
Верните заполненный массив ans, который содержит количество единиц для каждого числа от 0 до n.

😎 Решение:

func countBits(num int) []int {
    ans := make([]int, num + 1)
    for x := 1; x <= num; x++ {
        ans[x] = ans[x & (x - 1)] + 1
    }
    return ans
}

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