#hard
Задача: 174. Dungeon Game

Демоны поймали принцессу и заперли её в самой нижней правой комнате подземелья. Подземелье состоит из комнат, расположенных в форме сетки размером m x n. Наш отважный рыцарь изначально находится в комнате в верхнем левом углу и должен пробиться через подземелье, чтобы спасти принцессу.

Рыцарь имеет начальный запас здоровья, представленный положительным целым числом. Если в какой-то момент его уровень здоровья упадет до 0 или ниже, он умирает мгновенно.

Некоторые комнаты охраняются демонами (представлены отрицательными числами), так что рыцарь теряет здоровье, входя в эти комнаты; другие комнаты либо пусты (обозначены как 0), либо содержат магические сферы, которые увеличивают здоровье рыцаря (представлены положительными числами).

Чтобы как можно скорее добраться до принцессы, рыцарь решает двигаться только вправо или вниз на каждом шаге.

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

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

Пример:

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: The initial health of the knight must be at least 7 if he follows the optimal path

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

1️⃣Определение матрицы dp:
Создайте матрицу dp размером с подземелье, где элемент dp[row][col] указывает минимальное количество здоровья, необходимое рыцарю, чтобы начать путь из ячейки dungeon[row][col] и достигнуть цели (нижней правой ячейки).

2️⃣Инициализация и заполнение dp:
Начните с правого нижнего угла подземелья и идите в обратном направлении — справа налево и снизу вверх. Для каждой ячейки вычислите соответствующее значение в dp:
Если возможно, шаг вправо из текущей ячейки подземелья требует right_health здоровья.
Если возможно, шаг вниз из текущей ячейки подземелья требует down_health здоровья.
Возьмите минимальное значение из right_health и down_health для dp[row][col].
Если ни один из вышеперечисленных вариантов не доступен (то есть вы находитесь в ячейке назначения), учитывайте два подслучая:
Если в ячейке магический шар, достаточно 1 единицы здоровья.
Если в ячейке демон, рыцарю необходимо иметь единицу здоровья плюс урон, который может нанести демон.

3️⃣Результат вычислений:
Значение в dp[0][0] будет указывать на минимальное количество здоровья, необходимое рыцарю, чтобы начать свой путь из верхней левой ячейки подземелья и успешно спасти принцессу, учитывая все угрозы на его пути.

😎 Решение:

type MyCircularQueue struct {
    queue []int
    index int
}

func NewMyCircularQueue(size int) *MyCircularQueue {
    return &MyCircularQueue{make([]int, size), 0}
}

func (q *MyCircularQueue) EnQueue(value int) {
    q.queue[q.index] = value
    q.index = (q.index + 1) % len(q.queue)
}

func (q *MyCircularQueue) Get(index int) int {
    return q.queue[index % len(q.queue)]
}

func calculateMinimumHP(dungeon [][]int) int {
    rows, cols := len(dungeon), len(dungeon[0])
    dp := NewMyCircularQueue(cols)
    inf := int(^uint(0) >> 1)

    getMinHealth := func(curr, r, c int) int {
        if r < 0 || c < 0 {
            return inf
        }
        return max(1, dp.Get(cols*r+c) - curr)
    }

    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            curr := dungeon[rows-row-1][cols-col-1]
            right, down := getMinHealth(curr, row, col-1), getMinHealth(curr, row-1, col)
            minHealth := min(right, down)
            if minHealth == inf {
                minHealth = max(1, 1 - curr)
            }
            dp.EnQueue(minHealth)
        }
    }

    return dp.Get(cols - 1)
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 179. Largest Number

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

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

Пример:

Input: nums = [10,2]
Output: "210"

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

1️⃣Преобразование и сортировка: Преобразовать каждое число в строку и отсортировать массив строк с использованием специального компаратора, который для двух строк 𝑎 и b сравнивает результаты конкатенации 𝑎+𝑏 и 𝑏+𝑎.

2️⃣Проверка на нули: Если после сортировки первый элемент массива равен "0", вернуть "0", так как все числа в массиве нули.

3️⃣Формирование результата: Конкатенировать отсортированные строки для формирования наибольшего числа и вернуть это число в виде строки.

😎 Решение:

package main

import (
    "sort"
    "strconv"
    "strings"
)

type Solution struct{}

func (s *Solution) LargestNumber(nums []int) string {
    strNums := make([]string, len(nums))
    for i, num := range nums {
        strNums[i] = strconv.Itoa(num)
    }

    sort.Slice(strNums, func(i, j int) bool {
        return strNums[i]+strNums[j] > strNums[j]+strNums[i]
    })

    if strNums[0] == "0" {
        return "0"
    }

    return strings.Join(strNums, "")
}

func main() {
    solution := Solution{}
    nums := []int{3, 30, 34, 5, 9}
    result := solution.LargestNumber(nums)
    println(result)
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 186. Reverse Words in a String II

Дан массив символов s, переверните порядок слов.

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

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

Пример:

Input: s = ["a"]
Output: ["a"]

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

1️⃣Перевернуть всю строку: применить функцию reverse, которая переворачивает весь массив символов от начала до конца.

2️⃣Перевернуть каждое слово: пройти по всей строке, идентифицировать границы каждого слова и использовать функцию reverse для переворачивания символов в пределах каждого слова.

3️⃣Окончательная корректировка: проверить, чтобы между словами оставался только один пробел, и удалить лишние пробелы в начале и конце строки, если это необходимо.

😎 Решение:

func reverseWords(s []byte) {
    reverse := func(s []byte) {
        for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
            s[i], s[j] = s[j], s[i]
        }
    }

    reverse(s)
    start, n := 0, len(s)
    for start < n {
        end := start
        for end < n && s[end] != ' ' {
            end++
        }
        reverse(s[start:end])
        start = end + 1
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 187. Repeated DNA Sequences

ДНК состоит из серии нуклеотидов, обозначаемых как 'A', 'C', 'G' и 'T'.

Например, "ACGAATTCCG" — это последовательность ДНК.
При изучении ДНК полезно определять повторяющиеся последовательности внутри молекулы ДНК.

Дана строка s, представляющая последовательность ДНК. Верните все последовательности длиной 10 букв (подстроки), которые встречаются более одного раза в молекуле ДНК. Ответ можно возвращать в любом порядке.

Пример:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]

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

1️⃣Перебираем начальные позиции последовательности от 1 до 𝑁−𝐿, где 𝑁 — длина строки, а 𝐿 — длина подстроки (в данном случае 10):
Если начальная позиция 𝑠𝑡𝑎𝑟𝑡==0, вычисляем хеш первой последовательности 𝑠[0:𝐿].
В противном случае вычисляем скользящий хеш из предыдущего значения хеша.

2️⃣Проверяем хеш в хешсете:
Если хеш уже существует в хешсете, значит, мы нашли повторяющуюся последовательность, и пора обновить вывод.
В противном случае добавляем хеш в хешсет.

3️⃣Возвращаем список вывода, содержащий все повторяющиеся последовательности.

😎 Решение:

type MyCircularQueue struct {
    queue     []int
    tailIndex int
    capacity  int
}

func CreateMyCircularQueue(capacity int) MyCircularQueue {
    return MyCircularQueue{make([]int, capacity), 0, capacity}
}

func (q *MyCircularQueue) enQueue(value int) {
    q.queue[q.tailIndex] = value
    q.tailIndex = (q.tailIndex + 1) % q.capacity
}

func (q *MyCircularQueue) get(index int) int

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 188. Best Time to Buy and Sell Stock IV

Дан массив целых чисел prices, где prices[i] - это цена данной акции в i-й день, и целое число k.

Найдите максимальную прибыль, которую вы можете получить. Вы можете завершить не более чем k транзакций, т.е. вы можете купить не более k раз и продать не более k раз.

Обратите внимание: Вы не можете участвовать в нескольких транзакциях одновременно (т.е., вы должны продать акцию, прежде чем снова купить).

Пример:

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

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

1️⃣Инициализация DP массива: Инициализируйте трехмерный массив dp, где dp[i][j][l] представляет максимальную прибыль на конец i-го дня с j оставшимися транзакциями и l акциями в портфеле. Начните с dp[0][0][0] = 0 (нет прибыли без акций и транзакций) и dp[0][1][1] = -prices[0] (покупка первой акции).

2️⃣Вычисление переходов: Для каждого дня и каждого возможного количества транзакций вычислите возможные действия: держать акцию, не держать акцию, купить акцию, если j > 0, или продать акцию. Обновляйте dp с использованием:
dp[i][j][1] = max(dp[i−1][j][1], dp[i−1][j−1][0] - prices[i]) (максимум между удержанием акции и покупкой новой).
dp[i][j][0] = max(dp[i−1][j][0], dp[i−1][j][1] + prices[i]) (максимум между неудержанием акции и продажей).

3️⃣Расчет результатов: По завершении всех дней, возвращайте максимальное значение dp[n-1][j][0] для всех j от 0 до k, что представляет максимальную прибыль без удержания акций на последний день. Обработайте специальный случай, когда 𝑘×2≥𝑛, чтобы избежать лишних расчетов.

😎 Решение:

type Solution struct{}

func maxProfit(k int, prices []int) int {
    n := len(prices)
    if n == 0 || k == 0 {
        return 0
    }
    if k*2 >= n {
        res := 0
        for i := 1; i < n; i++ {
            if prices[i] > prices[i-1] {
                res += prices[i] - prices[i-1]
            }
        }
        return res
    }
    dp := make([][][]int, n)
    for i := range dp {
        dp[i] = make([][]int, k+1)
        for j := range dp[i] {
            dp[i][j] = make([]int, 2)
            dp[i][j][0], dp[i][j][1] = -1<<31/2, -1<<31/2
        }
    }
    dp[0][0][0] = 0
    dp[0][1][1] = -prices[0]

    for i := 1; i < n; i++ {
        for j := 0; j <= k; j++ {
            dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]+prices[i])
            if j > 0 {
                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0]-prices[i])
            }
        }
    }
    res := 0
    for j := 0; j <= k; j++ {
        res = max(res, dp[n-1][j][0])
    }
    return res
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 189. Rotate Array

Для целочисленного массива nums, поверните массив вправо на k шагов, где k — неотрицательное число.

Пример:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

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

1️⃣Создаем дополнительный массив, в который будем помещать каждый элемент исходного массива на его новую позицию. Элемент на позиции i в исходном массиве будет размещен на индексе (i+k) % длина массива.

2️⃣Копируем элементы из нового массива в исходный массив, сохраняя новый порядок элементов.

3️⃣Заменяем исходный массив полученным результатом, завершая процесс поворота массива.

😎 Решение:

package main

func rotate(nums []int, k int) {
    n := len(nums)
    a := make([]int, n)
    for i := 0; i < n; i++ {
        a[(i+k)%n] = nums[i]
    }
    for i := 0; i < n; i++ {
        nums[i] = a[i]
    }
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 190. Reverse Bits

Переверните биты заданного 32-битного беззнакового целого числа.

Пример:

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.
Example 2:

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

1️⃣Итерируем по байтам целого числа, используя побитовую операцию И (n & 0xff) с маской 11111111, чтобы извлечь крайний правый байт числа.

2️⃣Для каждого байта сначала переворачиваем биты внутри байта с помощью функции reverseByte(byte). Затем сдвигаем перевернутые биты на их окончательные позиции.

3️⃣В функции reverseByte(byte) используем технику мемоизации, которая сохраняет результат функции и возвращает его непосредственно при последующих вызовах с тем же входным значением. Мемоизация — это компромисс между использованием памяти и объемом вычислений.

😎 Решение:

func reverseByte(b uint32, cache map[uint32]uint64) uint64 {
    value, ok := cache[b]
    if ok {
        return value
    }
    value = (uint64(b) * 0x0202020202 & 0x010884422010) % 1023
    cache[b] = value
    return value
}

func reverseBits(num uint32) uint32 {
    ret := uint64(0)
    power := uint64(24)
    var cache = map[uint32]uint64{}

    for num != 0 {
        ret += reverseByte(num & 0xff, cache) << power
        num = num >> 8
        power -= 8
    }
    return uint32(ret)
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 191. Number of 1 Bits

Напишите функцию, которая принимает бинарное представление положительного целого числа и возвращает количество установленных битов (также известных как вес Хэмминга).

Пример:

Input: n = 11

Output: 3

Explanation:

The input binary string 1011 has a total of three set bits.

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

1️⃣Решение простое: проверяем каждый из 32 битов числа. Если бит равен 1, увеличиваем количество 1-битов на единицу.

2️⃣Для проверки i-го бита числа используем битовую маску. Начинаем с маски m=1, так как двоичное представление 1 это 0000 0000 0000 0000 0000 0000 0000 0001. Логическое И между любым числом и маской 1 дает нам младший бит этого числа.

3️⃣Для проверки следующего бита сдвигаем маску влево на один:
0000 0000 0000 0000 0000 0000 0000 0010 и так далее.

😎 Решение:

func hammingWeight(n int) int {
    bits := 0
    mask := 1
    for i := 0; i < 32; i++ {
        if (n & mask != 0 {
            bits++
        }
        mask <<= 1
    }
    return bits
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 198. House Robber

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

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

Пример:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

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

1️⃣Определите функцию robFrom(), которая принимает индекс дома, который грабитель должен осмотреть, и массив nums, необходимый для вычислений. На каждом шаге рекурсивного вызова у грабителя есть два варианта: ограбить текущий дом или нет.

2️⃣Если грабитель выбирает ограбить текущий дом, он должен пропустить следующий, т.е. вызвать robFrom(i + 2, nums). Ответ будет равен значению robFrom(i + 2, nums) плюс сумма, которую грабитель получит, ограбив текущий дом, т.е. nums[i]. В противном случае он может перейти к следующему дому и вернуть прибыль, которую он получит в подзадаче, т.е. robFrom(i + 1, nums).

3️⃣Нужно найти, сохранить в кэше и вернуть максимум из этих двух вариантов на каждом шаге. robFrom(0, nums) даст ответ на всю задачу.

😎 Решение:

package main

import (
    "math"
)

type Solution struct {
    memo []int
}

func (s *Solution) Rob(nums []int) int {
    s.memo = make([]int, 100)
    for i := range s.memo {
        s.memo[i] = -1
    }
    return s.robFrom(0, nums)
}

func (s *Solution) robFrom(i int, nums []int) int {
    if i >= len(nums) {
        return 0
    }
    if s.memo[i] != -1 {
        return s.memo[i]
    }
    ans := int(math.Max(float64(s.robFrom(i + 1, nums)), float64(s.robFrom(i + 2, nums) + nums[i])))
    s.memo[i] = ans
    return ans
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 199. Binary Tree Right Side View

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

Пример:

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

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

1️⃣Инициализируйте список правого обзора rightside. Инициализируйте две очереди: одну для текущего уровня и одну для следующего. Добавьте корень в очередь nextLevel.

2️⃣Пока очередь nextLevel не пуста:
Инициализируйте текущий уровень: currLevel = nextLevel и очистите очередь следующего уровня nextLevel.
Пока очередь текущего уровня не пуста:
Извлеките узел из очереди текущего уровня.
Добавьте сначала левый, а затем правый дочерний узел в очередь nextLevel.
Теперь очередь currLevel пуста, и узел, который у нас есть, является последним и составляет часть правого обзора. Добавьте его в rightside.

3️⃣Верните rightside.

😎 Решение:

package main

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

func rightSideView(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }

    nextLevel := []*TreeNode{root}
    rightside := []int{}

    for len(nextLevel) > 0 {
        currLevel := nextLevel
        nextLevel = []*TreeNode{}

        for _, node := range currLevel {
            if node.Left != nil {
                nextLevel = append(nextLevel, node.Left)
            }
            if node.Right != nil {
                nextLevel = append(nextLevel, node.Right)
            }
        }

        rightside = append(rightside, currLevel[len(currLevel)-1].Val)
    }

    return rightside
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 200. Number of Islands

Дана двумерная бинарная сетка размером m x n, представляющая карту из '1' (земля) и '0' (вода). Верните количество островов.

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

Пример:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

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

1️⃣Линейно просканируйте двумерную карту, если узел содержит '1', то это корневой узел, который запускает поиск в глубину (DFS).

2️⃣Во время выполнения DFS каждый посещённый узел следует установить в '0', чтобы пометить его как посещённый.

3️⃣Подсчитайте количество корневых узлов, запускающих DFS. Это количество будет равно количеству островов, так как каждый DFS, начинающийся с какого-либо корня, идентифицирует остров.

😎 Решение:

package main

func numIslands(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }

    numIslands := 0
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] == '1' {
                dfs(grid, i, j)
                numIslands++
            }
        }
    }
    return numIslands
}

func dfs(grid [][]byte, r, c int) {
    if r < 0 || c < 0 || r >= len(grid) || c >= len(grid[0]) || grid[r][c] != '1' {
        return
    }

    grid[r][c] = '0'
    dfs(grid, r-1, c)
    dfs(grid, r+1, c)
    dfs(grid, r, c-1)
    dfs(grid, r, c+1)
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 201. Bitwise AND of Numbers Range

Даны два целых числа left и right, которые представляют диапазон [left, right], верните побитовое И всех чисел в этом диапазоне включительно.

Пример:

Input: left = 5, right = 7
Output: 4

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

1️⃣Сдвигать left и right вправо, пока они не станут равными.

2️⃣Подсчитать количество сдвигов.

3️⃣Сдвинуть left влево на количество сдвигов и вернуть результат.

😎 Решение:

package main

func rangeBitwiseAnd(m int, n int) int {
    shift := 0
    for m < n {
        m >>= 1
        n >>= 1
        shift++
    }
    return m << shift
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 202. Happy Number

Напишите алгоритм для определения, является ли число n счастливым.

Счастливое число определяется следующим процессом:

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

Пример:

Input: n = 2
Output: false

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

1️⃣Для заданного числа n определите следующее число в последовательности: используйте операторы деления и взятия остатка для последовательного извлечения цифр из числа, пока не закончатся все цифры. Каждую извлеченную цифру возводите в квадрат и суммируйте полученные значения. Это техника "последовательного извлечения цифр" является полезным инструментом для решения множества задач.

2️⃣Отслеживайте цепочку чисел и определяйте, не вошли ли вы в цикл, используя структуру данных HashSet. Каждый раз, генерируя следующее число в цепочке, проверяйте, присутствует ли оно уже в HashSet.

3️⃣Если числа нет в HashSet, добавьте его туда. Если число уже есть в HashSet, это означает, что вы находитесь в цикле, и следует вернуть false. HashSet используется вместо Vector, List или Array, потому что проверка присутствия числа в HashSet занимает время O(1), тогда как в других структурах данных это займет время O(n). Правильный выбор структур данных является ключевым элементом решения подобных задач.

😎 Решение:

package main

import "fmt"

func getNext(n int) int {
    totalSum := 0
    for n > 0 {
        digit := n % 10
        n /= 10
        totalSum += digit * digit
    }
    return totalSum
}

func isHappy(n int) bool {
    seen := make(map[int]bool)
    for n != 1 && !seen[n] {
        seen[n] = true
        n = getNext(n)
    }
    return n == 1
}

func main() {
    fmt.Println(isHappy(19))
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 203. Remove Linked List Elements

Для заданного начала связного списка и целого числа val удалите все узлы связного списка, у которых Node.val равно val, и верните новое начало списка.

Пример:

Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

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

1️⃣Инициализируйте сторожевой узел как ListNode(0) и установите его новым началом: sentinel.next = head. Инициализируйте два указателя для отслеживания текущего узла и его предшественника: curr и prev.

2️⃣Пока curr не является нулевым указателем, сравните значение текущего узла со значением для удаления. Если значения равны, удалите текущий узел: prev.next = curr.next, иначе установите предшественника равным текущему узлу. Переместитесь к следующему узлу: curr = curr.next.

3️⃣Верните sentinel.next.

😎 Решение:

type ListNode struct {
    Val  int
    Next *ListNode
}

func deleteNode(head *ListNode, value int) *ListNode {
    sentinel := &ListNode{Next: head}
    prev, curr := sentinel, head

    for curr != nil {
        if curr.Val == value {
            prev.Next = curr.Next
        } else {
            prev = curr
        }
        curr = curr.Next
    }
    return sentinel.Next
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 204. Count Primes

Дано целое число n, верните количество простых чисел, которые строго меньше n.

Пример:

Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

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

1️⃣Создайте список последовательных целых чисел от 2 до n: (2, 3, 4, ..., n). Пусть p будет переменной, используемой во внешнем цикле, проходящем от 2 до n. Изначально p равно 2, самому маленькому простому числу.

2️⃣Перечислите кратные числа p, считая с шагом p от pp до n и отметьте их в списке (это будут pp, pp + p, pp + 2*p и т.д.; само число p должно быть простым). Найдите наименьшее число в списке, большее p, которое не отмечено. Если такого числа нет, остановитесь. В противном случае, пусть p теперь равно этому новому числу (следующее простое) и повторите шаг 2.

3️⃣Когда алгоритм завершится, все оставшиеся числа, которые не отмечены, являются простыми.

😎 Решение:

package main

import (
    "math"
)

func countPrimes(n int) int {
    if n <= 2 {
        return 0
    }

    numbers := make([]bool, n)
    for i := range numbers {
        numbers[i] = true
    }

    for p := 2; p <= int(math.Sqrt(float64(n))); p++ {
        if numbers[p] {
            for j := p * p; j < n; j += p {
                numbers[j] = false
            }
        }
    }

    numberOfPrimes := 0
    for i := 2; i < n; i++ {
        if numbers[i] {
            numberOfPrimes++
        }
    }

    return numberOfPrimes
}

func main() {
    n := 10
    result := countPrimes(n)
    println(result) 
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 205. Isomorphic Strings

Даны две строки s и t, определите, являются ли они изоморфными.

Две строки s и t являются изоморфными, если символы в s могут быть заменены для получения t.

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

Пример:

Input: s = "egg", t = "add"
Output: true

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

1️⃣Определите два словаря: mapping_s_t для отображения символов из строки s в символы строки t, и mapping_t_s для отображения символов из строки t в символы строки s.

2️⃣Итеративно пройдитесь по символам строк s и t. Для каждого символа c1 из s и соответствующего c2 из t, если c1 нет в mapping_s_t и c2 нет в mapping_t_s, добавьте соответствующие отображения; если одно из отображений существует, проверьте, соответствует ли оно ожидаемому значению.

3️⃣Если в процессе проверки какое-либо отображение неверно, верните false. Если все проверки пройдены успешно, верните true после окончания итерации по строкам.

😎 Решение:

package main

func isIsomorphic(s string, t string) bool {
    mappingStoT := make(map[byte]byte)
    mappingTtoS := make(map[byte]byte)

    for i := 0; i < len(s); i++ {
        c1 := s[i]
        c2 := t[i]

        if mappingStoT[c1] == 0 && mappingTtoS[c2] == 0 {
            mappingStoT[c1] = c2
            mappingTtoS[c2] = c1
        } else if mappingStoT[c1] != c2 || mappingTtoS[c2] != c1 {
            return false
        }
    }

    return true
}

func main() {
    s := "egg"
    t := "add"
    result := isIsomorphic(s, t)
    println(result) 
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 206. Reverse Linked List

Дан односвязный список, разверните этот список и верните развернутый список.

Пример:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

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

1️⃣Инициализируйте две переменные: prev как nullptr и curr как head списка. Эти переменные будут использоваться для отслеживания предыдущего и текущего узлов в процессе разворота списка.

2️⃣Пройдитесь по списку с помощью цикла:
Сохраните ссылку на следующий узел curr в переменную nextTemp.
Измените ссылку next текущего узла curr на prev, чтобы развернуть направление ссылки.
Переместите prev на текущий узел curr и переместите curr на следующий узел nextTemp.

3️⃣После завершения цикла верните prev как новую голову развернутого списка.

😎 Решение:

package main

type ListNode struct {
    val  int
    next *ListNode
}

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode = nil
    curr := head
    for curr != nil {
        nextTemp := curr.next
        curr.next = prev
        prev = curr
        curr = nextTemp
    }
    return prev
}

func main() {
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 207. Course Schedule

Всего у вас есть numCourses курсов, которые нужно пройти, пронумерованных от 0 до numCourses - 1. Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai.

Например, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1.
Верните true, если вы можете завершить все курсы. В противном случае верните false.

Пример:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

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

1️⃣Создайте массив indegree длины n, где indegree[x] хранит количество входящих рёбер в узел x. Создайте список смежности adj, в котором adj[x] содержит все узлы с входящим ребром от узла x, то есть соседей узла x. Создайте этот список смежности, итерируя prerequisites. Для каждого prerequisites добавьте ребро от prerequisites[1] к prerequisites[0] и увеличьте indegree prerequisites[0] на 1.

2️⃣Инициализируйте очередь целых чисел q и начните алгоритм BFS, перемещаясь от листовых узлов к родительским узлам. Начните обход BFS, поместив все листовые узлы (indegree равное 0) в очередь. Создайте целочисленную переменную nodesVisited = 0 для подсчета количества посещенных узлов.

3️⃣Пока очередь не пуста:
Извлеките первый узел из очереди.
Увеличьте nodesVisited на 1.
Для каждого соседа (узлы, которые имеют входящее ребро от узла) узла уменьшите indegree[neighbor] на 1, чтобы удалить ребро node -> neighbor.
Если indegree[neighbor] == 0, это означает, что neighbor ведет себя как листовой узел, поэтому добавьте neighbor в очередь.
Если количество посещенных узлов меньше общего количества узлов, то есть nodesVisited < n, верните false, так как должен быть цикл. В противном случае, если nodesVisited == numCourses, верните true. Можно сократить это до просто возвращения nodesVisited == numCourses.

😎 Решение:

package main

func canFinish(numCourses int, prerequisites [][]int) bool {
    indegree := make([]int, numCourses)
    adj := make([][]int, numCourses)
    
    for _, prerequisite := range prerequisites {
        adj[prerequisite[1]] = append(adj[prerequisite[1]], prerequisite[0])
        indegree[prerequisite[0]]++
    }

    queue := []int{}
    for i := 0; i < numCourses; i++ {
        if indegree[i] == 0 {
            queue = append(queue, i)
        }
    }

    nodesVisited := 0
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        nodesVisited++

        for _, neighbor := range adj[node] {
            indegree[neighbor]--
            if indegree[neighbor] == 0 {
                queue = append(queue, neighbor)
            }
        }
    }

    return nodesVisited == numCourses
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 208. Implement Trie (Prefix Tree)

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

Реализуйте класс Trie:
Trie() инициализирует объект trie.
void insert(String word) вставляет строку word в trie.
boolean search(String word) возвращает true, если строка word есть в trie (то есть была вставлена ранее), и false в противном случае.
boolean startsWith(String prefix) возвращает true, если есть ранее вставленная строка word, которая имеет префикс prefix, и false в противном случае.

Пример:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

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

1️⃣Инициализация и вставка в Trie:
Создайте класс Trie, который включает в себя метод insert(String word) для добавления строк в Trie.
Метод insert инициализирует текущий узел как корень и проходит по каждому символу строки. Если текущий узел не содержит символа, создайте новый узел. В конце отметьте последний узел как конец слова.

2️⃣Поиск строки в Trie:
Создайте метод search(String word), который использует вспомогательный метод searchPrefix(String word) для поиска строки или префикса в Trie.
В методе searchPrefix начните с корневого узла и для каждого символа строки перемещайтесь к следующему узлу. Если на каком-то этапе узел не содержит текущего символа, верните null. В противном случае, в конце строки верните текущий узел.

3️⃣Проверка наличия префикса в Trie:
Создайте метод startsWith(String prefix), который также использует метод searchPrefix(String prefix).
Метод startsWith вызывает searchPrefix и возвращает true, если возвращаемый узел не равен null, что указывает на наличие префикса в Trie.

😎 Решение:

package main

type TrieNode struct {
    links [26]*TrieNode
    isEnd bool
}

func (node *TrieNode) containsKey(ch byte) bool {
    return node.links[ch-'a'] != nil
}

func (node *TrieNode) get(ch byte) *TrieNode {
    return node.links[ch-'a']
}

func (node *TrieNode) put(ch byte, newNode *TrieNode) {
    node.links[ch-'a'] = newNode
}

func (node *TrieNode) setEnd() {
    node.isEnd = true
}

func (node *TrieNode) isEndNode() bool {
    return node.isEnd
}

type Trie struct {
    root *TrieNode
}

func Constructor() Trie {
    return Trie{root: &TrieNode{}}
}

func (this *Trie) Insert(word string) {
    node := this.root
    for i := 0; i < len(word); i++ {
        ch := word[i]
        if !node.containsKey(ch) {
            node.put(ch, &TrieNode{})
        }
        node = node.get(ch)
    }
    node.setEnd()
}

func (this *Trie) searchPrefix(word string) *TrieNode {
    node := this.root
    for i := 0; i < len(word); i++ {
        ch := word[i]
        if node.containsKey(ch) {
            node = node.get(ch)
        } else {
            return nil
        }
    }
    return node
}

func (this *Trie) Search(word string) bool {
    node := this.searchPrefix(word)
    return node != nil && node.isEndNode()
}

func (this *Trie) StartsWith(prefix string) bool {
    return this.searchPrefix(prefix) != nil
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 209. Minimum Size Subarray Sum

Дан массив положительных целых чисел nums и положительное целое число target. Верните минимальную длину подмассива, сумма которого больше или равна target. Если такого подмассива нет, верните 0.

Пример:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

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

1️⃣Инициализация переменных:
Создайте три целочисленные переменные left, right и sumOfCurrentWindow. Переменные left и right формируют подмассив, указывая на начальные и конечные индексы текущего подмассива (или окна), а sumOfCurrentWindow хранит сумму этого окна. Инициализируйте все их значением 0.
Создайте еще одну переменную res для хранения ответа на задачу. Инициализируйте ее большим целым значением.

2️⃣Итерация по массиву:
Итерируйте по массиву nums с помощью right, начиная с right = 0 до nums.length - 1, увеличивая right на 1 после каждой итерации. Выполняйте следующее внутри этой итерации:
Добавьте элемент с индексом right к текущему окну, увеличив sumOfCurrentWindow на nums[right].
Проверьте, если sumOfCurrentWindow >= target. Если да, у нас есть подмассив, который удовлетворяет условию. В результате, попытайтесь обновить переменную ответа res длиной этого подмассива. Выполните res = min(res, right - left + 1). Затем удалите первый элемент из этого окна, уменьшив sumOfCurrentWindow на nums[left] и увеличив left на 1. Этот шаг повторяется во внутреннем цикле, пока sumOfCurrentWindow >= target.

3️⃣Возврат результата:
Текущая сумма окна теперь меньше target. Нужно добавить больше элементов в окно. В результате, увеличивается right на 1.
Верните res.

😎 Решение:

func minSubArrayLen(target int, nums []int) int {
    left, sumOfCurrentWindow, res := 0, 0, int(^uint(0) >> 1)

    for right := 0; right < len(nums); right++ {
        sumOfCurrentWindow += nums[right]

        for sumOfCurrentWindow >= target {
            if res > right - left + 1 {
                res = right - left + 1
            }
            sumOfCurrentWindow -= nums[left]
            left++
        }
    }

    if res == int(^uint(0) >> 1) {
        return 0
    }
    return res
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых