Задача: 948. Bag of Tokens
Сложность: medium

Вы начинаете с начальной силой, равной power, начальным счетом 0 и мешком жетонов, представленным в виде целочисленного массива tokens, где каждый tokens[i] обозначает значение tokeni. Ваша цель - максимизировать общее количество очков, стратегически разыгрывая эти жетоны. За один ход вы можете разыграть неразыгранный жетон одним из двух способов (но не обоими для одного и того же жетона): лицом вверх: Если ваша текущая сила не меньше жетонов[i], вы можете сыграть токени, потеряв силу жетонов[i] и получив 1 очко. Лицом вниз: Если ваш текущий счет не меньше 1, вы можете сыграть токени, получив силу токенов[i] и потеряв 1 счет. Верните максимально возможный счет, который вы можете получить, сыграв любое количество токенов.

Пример:

Input: tokens = [100], power = 50

Output: 0

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

1⃣Отсортировать массив tokens.
Использовать два указателя: left и right, чтобы отслеживать начало и конец массива токенов.
Инициализировать переменные для текущей силы power, текущего счета score и максимального счета maxScore

2⃣Повторять следующие шаги, пока left не превысит right:
Если текущая сила power достаточна для разыгрывания токена tokens[left] лицом вверх, разыграть его и увеличить счет.
Если текущая сила недостаточна, но счет больше 0, разыграть токен tokens[right] лицом вниз и уменьшить счет.
Обновить максимальный счет, если текущий счет больше максимального.

3⃣Вернуть максимальный счет.

😎 Решение:

package main

import "sort"

func bagOfTokensScore(tokens []int, power int) int {
    sort.Ints(tokens)
    left, right := 0, len(tokens) - 1
    score, maxScore := 0, 0
    
    for left <= right {
        if power >= tokens[left] {
            power -= tokens[left]
            score++
            left++
            if score > maxScore {
                maxScore = score
            }
        } else if score > 0 {
            power += tokens[right]
            score--
            right--
        } else {
            break
        }
    }
    
    return maxScore
}

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

Задача: №33. Search in Rotated Sorted Array
Сложность: medium

Есть массив целых чисел nums, отсортированный в порядке возрастания (с уникальными значениями).

Перед передачей в вашу функцию массив nums может быть повёрнут в неизвестном индексе поворота k (1 <= k < nums.length), так что результирующий массив будет иметь вид [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (с индексацией с нуля). Например, [0,1,2,4,5,6,7] может быть повёрнут в индексе поворота 3 и стать [4,5,6,7,0,1,2].

Для данного массива nums после возможного поворота и целого числа target, верните индекс target, если он есть в массиве, или -1, если его нет в массиве.

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

Пример:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

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

1⃣Выполните двоичный поиск для определения индекса поворота, инициализируя границы области поиска значениями left = 0 и right = n - 1. Пока left < right:
Пусть mid = left + (right - left) // 2.
Если nums[mid] > nums[n - 1], это предполагает, что точка поворота находится справа от mid, следовательно, мы устанавливаем left = mid + 1. В противном случае, поворот может находиться на позиции mid или левее от mid, в этом случае мы должны установить right = mid.

2⃣По завершении двоичного поиска мы имеем индекс поворота, обозначенный как pivot = left.
nums состоит из двух отсортированных подмассивов, nums[0 ~ left - 1] и nums[left ~ n - 1].

3⃣Выполните двоичный поиск по подмассиву nums[0 ~ left - 1] для поиска target. Если target находится в этом подмассиве, верните его индекс.
В противном случае выполните двоичный поиск по подмассиву nums[left ~ n - 1] для поиска target. Если target находится в этом подмассиве, верните его индекс. В противном случае верните -1.

😎 Решение:

func search(nums []int, target int) int {
    n := len(nums)
    left, right := 0, n-1
    for left <= right {
        mid := (left + right) / 2
        if nums[mid] > nums[n-1] {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    binarySearch := func(left_boundary int, right_boundary int, target int) int {
        left, right := left_boundary, right_boundary
        for left <= right {
            mid := (left + right) / 2
            if nums[mid] == target {
                return mid
            } else if nums[mid] > target {
                right = mid - 1
            } else {
                left = mid + 1
            }
        }
        return -1
    }
    if answer := binarySearch(0, left-1, target); answer != -1 {
        return answer
    }
    return binarySearch(left, n-1, target)
}

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

Задача: 989. Add to Array-Form of Integer
Сложность: medium

Массивная форма целого числа num - это массив, представляющий его цифры в порядке слева направо.

Например, для num = 1321, массивная форма - это [1, 3, 2, 1].
Дано num в массивной форме целого числа и целое число k, верните массивную форму числа num + k.

Пример:

Input: num = [1,2,0,0], k = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234

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

1⃣Инициализация переменных:
Преобразуйте число k в массив его цифр и переверните оба массива (массив num и массив цифр k).
Завести переменную carry для хранения переноса и инициализировать ее нулем.
Создать пустой массив result для хранения результата.

2⃣Сложение массивов:
Пройдите по элементам массивов num и цифр k, начиная с их конца, сложите соответствующие цифры вместе с переносом (carry).
Если сумма больше 9, сохраните последнюю цифру в текущей позиции результата, а carry установите в 1.
Если сумма меньше 10, установите carry в 0.
Добавьте результат текущего сложения в массив result

3⃣Обработка оставшихся цифр и переноса:
Если один из массивов закончился раньше, продолжайте сложение оставшихся цифр другого массива с переносом.
Если после окончания всех сложений остается перенос (carry), добавьте его в начало массива result.
Переверните массив result обратно и верните его.

😎 Решение:

func addToArrayForm(num []int, k int) []int {
    var result []int
    n := len(num)
    
    for i := n - 1; i >= 0; i-- {
        k += num[i]
        result = append(result, k % 10)
        k /= 10
    }
    for k > 0 {
        result = append(result, k % 10)
        k /= 10
    }
    
    for i, j := 0, len(result) - 1; i < j; i, j = i + 1, j - 1 {
        result[i], result[j] = result[j], result[i]
    }
    
    return result
}

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

Задача: 339. Nested List Weight Sum
Сложность: medium

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

Глубина целого числа — это количество списков, в которых оно находится. Например, вложенный список [1,[2,2],[[3],2],1] имеет значения каждого целого числа, установленные в его глубину.

Верните сумму каждого целого числа в nestedList, умноженного на его глубину.

Пример:

Input: nestedList = [1,[4,[6]]]
Output: 27
Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 1*1 + 4*2 + 6*3 = 27.

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

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

2⃣ Рекурсивное исследование списка:
В вспомогательной функции пройдите по каждому элементу списка. Если элемент является целым числом, добавьте его значение, умноженное на текущую глубину, к общей сумме. Если элемент является списком, вызовите вспомогательную функцию рекурсивно с увеличенной глубиной.

3⃣ Возврат результата:
Возвращайте общую сумму на каждом уровне рекурсии. Основная функция возвращает итоговую сумму.

😎 Решение:

func depthSum(nestedList []*NestedInteger) int {
    return dfs(nestedList, 1)
}

func dfs(list []*NestedInteger, depth int) int {
    total := 0
    for _, nested := range list {
        if nested.IsInteger() {
            total += nested.GetInteger() * depth
        } else {
            total += dfs(nested.GetList(), depth + 1)
        }
    }
    return total
}

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

Задача: 776. Split BST
Сложность: medium

Дан корень бинарного дерева поиска (BST) и целое число target. Необходимо разделить дерево на два поддерева:

- Первое содержит узлы меньше или равные target
- Второе — узлы больше target

Структура дерева должна сохраняться, насколько это возможно.

Пример:

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

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

1⃣Если текущий узел nil, вернём [nil, nil] — базовый случай для рекурсии.

2⃣Если root.Val > target, значит, root и правое поддерево точно больше. Рекурсивно разбиваем root.Left, а правую часть прикрепляем обратно к root.Left.

3⃣Если root.Val <= target, значит, root входит в левую часть. Рекурсивно разбиваем root.Right, а левую часть прикрепляем к root.Right.

😎 Решение:

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

func splitBST(root *TreeNode, target int) []*TreeNode {
    if root == nil {
        return []*TreeNode{nil, nil}
    }

    if root.Val > target {
        left := splitBST(root.Left, target)
        root.Left = left[1]
        return []*TreeNode{left[0], root}
    } else {
        right := splitBST(root.Right, target)
        root.Right = right[0]
        return []*TreeNode{root, right[1]}
    }
}

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

Задача: 994. Rotting Oranges
Сложность: hard

Дан m x n сетка, где каждая ячейка может иметь одно из трех значений:

0, представляющее пустую ячейку,
1, представляющее свежий апельсин,
2, представляющее гнилой апельсин.
Каждую минуту любой свежий апельсин, который находится в 4-х направленно смежной ячейке с гнилым апельсином, становится гнилым.

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

Пример:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

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

1⃣Инициализация очереди и подсчет апельсинов:
Пройдите по всей сетке, добавьте все гнилые апельсины в очередь и подсчитайте общее количество свежих апельсинов.
Если нет свежих апельсинов, верните 0.

2⃣Использование BFS для распространения гнили:
Выполняйте BFS, начиная с всех гнилых апельсинов, добавленных в очередь.
Каждый раз, когда апельсин становится гнилым, уменьшайте счетчик свежих апельсинов.
Если свежих апельсинов больше не осталось, верните текущее количество минут.

3⃣Проверка оставшихся свежих апельсинов:
Если после завершения BFS все еще остаются свежие апельсины, верните -1.

😎 Решение:

func orangesRotting(grid [][]int) int {
    directions := [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}
    queue := [][]int{}
    freshCount := 0
    minutes := 0
    
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] == 2 {
                queue = append(queue, []int{i, j})
            } else if grid[i][j] == 1 {
                freshCount++
            }
        }
    }
    
    if freshCount == 0 {
        return 0
    }
    
    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            x, y := queue[0][0], queue[0][1]
            queue = queue[1:]
            for _, dir := range directions {
                nx, ny := x+dir[0], y+dir[1]
                if nx >= 0 && nx < len(grid) && ny >= 0 && ny < len(grid[0]) && grid[nx][ny] == 1 {
                    grid[nx][ny] = 2
                    freshCount--
                    queue = append(queue, []int{nx, ny})
                }
            }
        }
        if len(queue) > 0 {
            minutes++
        }
    }
    
    if freshCount == 0 {
        return minutes
    }
    return -1
}

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

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

Переверните биты заданного 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)
}

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

Задача: 382. Linked List Random Node
Сложность: medium

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

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

Solution(ListNode head) Инициализирует объект с головой односвязного списка head.
int getRandom() Выбирает узел случайным образом из списка и возвращает его значение. Все узлы списка должны иметь равные шансы быть выбранными.

Пример:

Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.

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

1⃣Реализуйте интерфейс init(head), который будет вызываться при создании объекта. Преобразуйте связанный список в массив для дальнейшего использования.

2⃣В интерфейсе init(head) преобразуйте переданный связанный список в массив, чтобы его можно было использовать позже.

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

😎 Решение:

package main

import (
  "math/rand"
  "time"
)

type ListNode struct {
  Val  int
  Next *ListNode
}

type Solution struct {
  rangeVals []int
}

func Constructor(head *ListNode) Solution {
  var rangeVals []int
  for head != nil {
    rangeVals = append(rangeVals, head.Val)
    head = head.Next
  }
  rand.Seed(time.Now().UnixNano())
  return Solution{rangeVals: rangeVals}
}

func (this *Solution) GetRandom() int {
  pick := rand.Intn(len(this.rangeVals))
  return this.rangeVals[pick]
}

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

Задача: 1015. Smallest Integer Divisible by K
Сложность: medium

Задано целое положительное число k, необходимо найти длину наименьшего целого положительного числа n, такого, что n делится на k, и n содержит только цифру 1. Верните длину n. Если такого n не существует, верните -1. Примечание: n может не поместиться в 64-битное знаковое целое число.

Пример:

Input: k = 1
Output: 1

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

1⃣Использование остатка для нахождения числа с цифрами 1:
Создайте переменную num и установите ее равной 1.
Создайте переменную length и установите ее равной 1 для отслеживания длины числа.

2⃣Итеративное нахождение числа:
Используйте цикл, чтобы умножать num на 10 и добавлять 1 в каждой итерации, и каждый раз вычисляйте остаток от деления num на k.
Увеличивайте length на 1 в каждой итерации.
Если в какой-то итерации num % k == 0, верните length.

3⃣Проверка бесконечного цикла:
Если цикл длится слишком долго (например, 10^6 итераций), верните -1, чтобы предотвратить бесконечный цикл для случаев, когда решение не существует.

😎 Решение:

func smallestRepunitDivByK(k int) int {
    num, length := 1, 1
    seen := make(map[int]bool)
    
    for num % k != 0 {
        if seen[num % k] {
            return -1
        }
        seen[num % k] = true
        num = (num * 10 + 1) % k
        length++
    }
    
    return length
}

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

Задача: 1265. Print Immutable Linked List in Reverse
Сложность: medium

Вам дан неизменяемый связный список, распечатайте все значения каждого узла в обратном порядке с помощью следующего интерфейса: ImmutableListNode:Интерфейс неизменяемого связанного списка, вам дана голова списка. Для доступа к связанному списку необходимо использовать следующие функции (напрямую к ImmutableListNode обращаться нельзя): ImmutableListNode.printValue(): Выводит значение текущего узла. ImmutableListNode.getNext(): Возвращает следующий узел. Входные данные даются только для внутренней инициализации связанного списка.Вы должны решить эту задачу, не изменяя связанный список. Другими словами, вы должны работать со связанным списком, используя только упомянутые API.

Пример:
Input: head = [1,2,3,4]
Output: [4,3,2,1]

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

1⃣Используйте рекурсию для достижения конца связного списка.

2⃣На обратном пути рекурсии распечатайте значение каждого узла.

3⃣Обратный порядок достигается благодаря природе рекурсии (стек вызовов).

😎 Решение:

type ImmutableListNode interface {
    PrintValue()
    GetNext() ImmutableListNode
}

func printLinkedListInReverse(head ImmutableListNode) {
    if head.GetNext() != nil {
        printLinkedListInReverse(head.GetNext())
    }
    head.PrintValue()
}

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

Задача: 309. Best Time to Buy and Sell Stock with Cooldown
Сложность: medium

Дан массив prices, где prices[i] — цена данной акции в i-й день.

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

После продажи акции вы не можете покупать акции на следующий день (т. е. необходимо один день подождать).

Пример:

Input: prices = [1]
Output: 0

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

1⃣Инициализация состояний
Используйте три состояния для отслеживания максимальной прибыли: hold: максимальная прибыль на данный день, если у вас есть акция. sold: максимальная прибыль на данный день, если вы продали акцию. cooldown: максимальная прибыль на данный день, если вы находитесь в периоде ожидания после продажи.

2⃣Обновление состояний
Итерируйте по каждому дню, обновляя состояния: hold: максимальная прибыль, если у вас есть акция на текущий день. sold: максимальная прибыль, если вы продаете акцию на текущий день. cooldown: максимальная прибыль, если вы находитесь в периоде ожидания на текущий день.

3⃣Определение максимальной прибыли
В конце итерации максимальная прибыль будет максимальным значением между состояниями sold и cooldown, так как hold состояние не может быть конечным состоянием для получения максимальной прибыли.

😎 Решение:

func maxProfit(prices []int) int {
    if len(prices) == 0 {
        return 0
    }
    
    hold := -prices[0]
    sold := 0
    cooldown := 0
    
    for i := 1; i < len(prices); i++ {
        newHold := max(hold, cooldown - prices[i])
        newSold := hold + prices[i]
        newCooldown := max(cooldown, sold)
        
        hold = newHold
        sold = newSold
        cooldown = newCooldown
    }
    
    return max(sold, cooldown)
}

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

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

Задача: 368. Largest Divisible Subset
Сложность: medium

Дан набор различных положительных целых чисел nums. Вернуть наибольшее подмножество answer, такое что каждая пара (answer[i], answer[j]) элементов в этом подмножестве удовлетворяет условию:

answer[i] % answer[j] == 0, или
answer[j] % answer[i] == 0
Если существует несколько решений, вернуть любое из них.

Пример:

Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also accepted.

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

1⃣Если число 8 может быть разделено на элемент X_i, то добавив число 8 к EDS(X_i), мы получим еще одно делимое подмножество, которое заканчивается на 8, согласно нашему следствию I. И это новое подмножество является потенциальным значением для EDS(8). Например, поскольку 8 % 2 == 0, то {2,8} может быть конечным значением для EDS(8), и аналогично для подмножества {2,4,8}, полученного из EDS(4).

2⃣Если число 8 не может быть разделено на элемент X_i, то можно быть уверенным, что значение EDS(X_i) не повлияет на EDS(8), согласно определению делимого подмножества. Например, подмножество EDS(7)={7} не имеет влияния на EDS(8).

3⃣Затем мы выбираем наибольшие новые подмножества, которые мы формируем с помощью EDS(X_i). В частности, подмножество {8} является допустимым кандидатом для EDS(8). И в гипотетическом случае, когда 8 не может быть разделено ни на один из предыдущих элементов, мы бы имели EDS(8)={8}.

😎 Решение:

package main

import (
  "fmt"
  "sort"
)

func largestDivisibleSubset(nums []int) []int {
  n := len(nums)
  if n == 0 {
    return []int{}
  }

  sort.Ints(nums)
  EDS := make([][]int, n)

  for i := 0; i < n; i++ {
    maxSubset := []int{}
    for k := 0; k < i; k++ {
      if nums[i]%nums[k] == 0 && len(maxSubset) < len(EDS[k]) {
        maxSubset = EDS[k]
      }
    }
    EDS[i] = append([]int{}, maxSubset...)
    EDS[i] = append(EDS[i], nums[i])
  }

  ret := []int{}
  for _, subset := range EDS {
    if len(ret) < len(subset) {
      ret = subset
    }
  }
  return ret
}

func main() {
  nums := []int{1, 2, 4, 8}
  fmt.Println(largestDivisibleSubset(nums))
}

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

Задача: 289. Game of Life
Сложность: medium

Согласно статье Википедии: "Игра Жизнь, также известная просто как Жизнь, — это клеточный автомат, созданный британским математиком Джоном Хортоном Конуэем в 1970 году."

Доска состоит из сетки клеток размером m x n, где каждая клетка имеет начальное состояние: живая (представляется числом 1) или мёртвая (представляется числом 0). Каждая клетка взаимодействует с восемью соседями (по горизонтали, вертикали и диагоналям) согласно следующим четырём правилам (взято из вышеупомянутой статьи Википедии):

Любая живая клетка с менее чем двумя живыми соседями умирает, как будто из-за недостатка населения.
Любая живая клетка с двумя или тремя живыми соседями остаётся живой до следующего поколения.
Любая живая клетка с более чем тремя живыми соседями умирает, как будто из-за перенаселения.
Любая мёртвая клетка с ровно тремя живыми соседями становится живой, как будто вследствие размножения.
Следующее состояние создаётся путем одновременного применения вышеупомянутых правил ко всем клеткам в текущем состоянии, где рождения и смерти происходят одновременно. Дано текущее состояние сетки m x n, верните следующее состояние.

Пример:

Input: board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
Output: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

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

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

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

3⃣Обновление доски:
Пройдите через доску ещё раз и обновите состояния клеток:
Если значение клетки больше 0, установите её в 1 (живая).
Если значение клетки меньше или равно 0, установите её в 0 (мёртвая).

😎 Решение:

func gameOfLife(board [][]int) {
    neighbors := []int{0, 1, -1}
    rows := len(board)
    cols := len(board[0])

    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            liveNeighbors := 0

            for _, i := range neighbors {
                for _, j := range neighbors {
                    if !(i == 0 && j == 0) {
                        r := row + i
                        c := col + j

                        if r >= 0 && r < rows && c >= 0 && c < cols && abs(board[r][c]) == 1 {
                            liveNeighbors++
                        }
                    }
                }
            }

            if board[row][col] == 1 && (liveNeighbors < 2 || liveNeighbors > 3) {
                board[row][col] = -1
            }
            if board[row][col] == 0 && liveNeighbors == 3 {
                board[row][col] = 2
            }
        }
    }

    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            if board[row][col] > 0 {
                board[row][col] = 1
            } else {
                board[row][col] = 0
            }
        }
    }
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

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

Задача: 1004. Max Consecutive Ones III
Сложность: medium

Если задан двоичный массив nums и целое число k, верните максимальное количество последовательных 1 в массиве, если можно перевернуть не более k 0.

Пример:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6

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

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

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

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

😎 Решение:

func longestOnes(nums []int, k int) int {
    left, maxOnes, zeroCount := 0, 0, 0

    for right := 0; right < len(nums); right++ {
        if nums[right] == 0 {
            zeroCount++
        }

        while zeroCount > k {
            if nums[left] == 0 {
                zeroCount--
            }
            left++
        }

        maxOnes = max(maxOnes, right - left + 1)
    }

    return maxOnes
}

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

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

Задача: 1402. Reducing Dishes
Сложность: hard

Шеф-повар собрал данные об уровне удовлетворенности от своих n блюд. Шеф может приготовить любое блюдо за 1 единицу времени.

Коэффициент удовольствия от блюда определяется как время, затраченное на приготовление этого блюда вместе с предыдущими блюдами, умноженное на уровень удовлетворенности от этого блюда, то есть time[i] * satisfaction[i].

Верните максимальную сумму коэффициентов удовольствия, которую шеф-повар может получить после приготовления некоторого количества блюд.

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

Пример:

Input: satisfaction = [-1,-8,0,5,-9]
Output: 14
Explanation: After Removing the second and last dish, the maximum total like-time coefficient will be equal to (-1*1 + 0*2 + 5*3 = 14).
Each dish is prepared in one unit of time.

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

1⃣Отсортируйте массив satisfaction в порядке возрастания.

2⃣Создайте таблицу мемоизации memo размером N x N и инициализируйте все значения -1, что будет означать, что ответ для всех состояний еще не рассчитан.

3⃣Реализуйте функцию, которая вызывается с параметрами index = 0 и time = 1, чтобы найти ответ:
Если достигнут конец массива, т.е. index == satisfaction.length, верните 0, так как больше нет блюд для приготовления и нельзя получить дополнительное значение.
Если значение в массиве memo для пары {index, time} не равно -1, верните это значение, так как это подразумевает, что данная подзадача уже была решена; поэтому рекурсивный вызов не требуется, и можно вернуть сохраненное значение из таблицы memo.
Рассчитайте максимум из двух вариантов:
- добавьте значение коэффициента для данного блюда satisfaction[index] * time к рекурсивному результату с index = index + 1 и time = time + 1.
- пропустите текущее блюдо и сделайте рекурсивный вызов для index = index + 1 и time = time.

😎 Решение:

import "sort"

func maxSatisfaction(satisfaction []int) int {
    sort.Ints(satisfaction)
    memo := make([][]int, len(satisfaction)+1)
    for i := range memo {
        memo[i] = make([]int, len(satisfaction)+1)
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }

    var findMaxSatisfaction func(satisfaction []int, memo [][]int, index, time int) int
    findMaxSatisfaction = func(satisfaction []int, memo [][]int, index, time int) int {
        if index == len(satisfaction) {
            return 0
        }
        if memo[index][time] != -1 {
            return memo[index][time]
        }
        memo[index][time] = max(satisfaction[index]*time+findMaxSatisfaction(satisfaction, memo, index+1, time+1),
                                findMaxSatisfaction(satisfaction, memo, index+1, time))
        return memo[index][time]
    }

    return findMaxSatisfaction(satisfaction, memo, 0, 1)
}

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

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

Задача: 221. Maximal Square
Сложность: medium

Дана бинарная матрица размером m x n, заполненная 0 и 1. Найдите наибольший квадрат, содержащий только 1, и верните его площадь.

Пример:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

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

1⃣Инициализировать 1D массив dp с нулями, чтобы хранить промежуточные результаты для каждого столбца, а также переменные maxsqlen для максимальной длины квадрата и prev для предыдущего значения.

2⃣Пройти по каждому элементу матрицы. Если текущий элемент равен '1', обновить dp[j] по формуле dp[j]=min(dp[j−1],prev,dp[j])+1 и обновить maxsqlen. Если текущий элемент равен '0', установить dp[j] в 0. Обновить prev на значение dp[j] перед его изменением.

3⃣По завершении пройти по всем строкам и столбцам, вернуть квадрат maxsqlen как площадь наибольшего квадрата.

😎 Решение:

func maximalSquare(matrix [][]byte) int {
    rows := len(matrix)
    cols := 0
    if rows > 0 {
        cols = len(matrix[0])
    }
    dp := make([]int, cols+1)
    maxsqlen := 0
    prev := 0
    
    for i := 1; i <= rows; i++ {
        for j := 1; j <= cols; j++ {
            temp := dp[j]
            if matrix[i-1][j-1] == '1' {
                dp[j] = min(dp[j-1], min(prev, dp[j])) + 1
                maxsqlen = max(maxsqlen, dp[j])
            } else {
                dp[j] = 0
            }
            prev = temp
        }
    }
    
    return maxsqlen * maxsqlen
}

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
}

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

Задача: 641. Design Circular Deque
Сложность: medium

Разработайте свою реализацию круговой двусторонней очереди (deque). Реализуйте класс MyCircularDeque: MyCircularDeque(int k) Инициализирует deque с максимальным размером k. boolean insertFront() Добавляет элемент в переднюю часть Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean insertLast() Добавляет элемент в заднюю часть Deque. Возвращает true, если операция выполнена успешно, или false в противном случае. boolean deleteFront() Удаляет элемент из передней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean deleteLast() Удаляет элемент из задней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. int getFront() Возвращает передний элемент из Deque. Возвращает -1, если Deque пуст. int getRear() Возвращает последний элемент из Deque. Возвращает -1, если Deque пуст. boolean isEmpty() Возвращает true, если Deque пуст, или false в противном случае. boolean isFull() Возвращает true, если Deque полон, или false в противном случае.

Пример:

Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]

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

1⃣Инициализация и проверка состояний
Реализуйте конструктор для инициализации кольцевой двусторонней очереди заданного размера и методы для проверки пустоты и полноты очереди.

2⃣Операции вставки
Реализуйте методы вставки элементов в переднюю и заднюю части очереди с учетом кольцевой структуры.

3⃣Операции удаления
Реализуйте методы удаления элементов из передней и задней частей очереди с учетом кольцевой структуры и методы для получения переднего и заднего элементов очереди.

😎 Решение:

package main

type MyCircularDeque struct {
    deque    []int
    front    int
    rear     int
    size     int
    capacity int
}

func Constructor(k int) MyCircularDeque {
    return MyCircularDeque{
        deque:    make([]int, k),
        front:    0,
        rear:     0,
        size:     0,
        capacity: k,
    }
}

func (this *MyCircularDeque) InsertFront(value int) bool {
    if this.IsFull() {
        return false
    }
    this.front = (this.front - 1 + this.capacity) % this.capacity
    this.deque[this.front] = value
    this.size++
    return true
}

func (this *MyCircularDeque) InsertLast(value int) bool {
    if this.IsFull() {
        return false
    }
    this.deque[this.rear] = value
    this.rear = (this.rear + 1) % this.capacity
    this.size++
    return true
}

func (this *MyCircularDeque) DeleteFront() bool {
    if this.IsEmpty() {
        return false
    }
    this.front = (this.front + 1) % this.capacity
    this.size--
    return true
}

func (this *MyCircularDeque) DeleteLast() bool {
    if this.IsEmpty() {
        return false
    }
    this.rear = (this.rear - 1 + this.capacity) % this.capacity
    this.size--
    return true
}

func (this *MyCircularDeque) GetFront() int {
    if this.IsEmpty() {
        return -1
    }
    return this.deque[this.front]
}

func (this *MyCircularDeque) GetRear() int {
    if this.IsEmpty() {
        return -1
    }
    return this.deque[(this.rear-1+this.capacity)%this.capacity]
}

func (this *MyCircularDeque) IsEmpty() bool {
    return this.size == 0
}

func (this *MyCircularDeque) IsFull() bool {
    return this.size == this.capacity
}

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

Задача: 1103. Distribute Candies to People
Сложность: easy

Мы распределяем некоторое количество конфет ряду из n = num_people человек следующим образом:
Сначала даем 1 конфету первому человеку, 2 конфеты второму человеку и так далее, пока не дадим n конфет последнему человеку.
Затем мы возвращаемся к началу ряда, давая n + 1 конфету первому человеку, n + 2 конфеты второму человеку и так далее, пока не дадим 2 * n конфет последнему человеку.

Этот процесс повторяется (мы каждый раз даем на одну конфету больше и возвращаемся к началу ряда после достижения конца), пока у нас не закончатся конфеты. Последний человек получит все оставшиеся конфеты (не обязательно на одну больше, чем в предыдущий раз).

Верните массив (длиной num_people и суммой candies), который представляет собой окончательное распределение конфет.

Пример:

Input: candies = 7, num_people = 4
Output: [1,2,3,1]
Explanation:
On the first turn, ans[0] += 1, and the array is [1,0,0,0].
On the second turn, ans[1] += 2, and the array is [1,2,0,0].
On the third turn, ans[2] += 3, and the array is [1,2,3,0].
On the fourth turn, ans[3] += 1 (because there is only one candy left), and the final array is [1,2,3,1].

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

1⃣Вычислите количество людей, получивших полные подарки, и оставшиеся конфеты:
p = floor(sqrt(2C+0.25)-0.5)
remainig = C - p(p+1)/2

2⃣Вычислите количество полных циклов и распределите конфеты:
rows = p // n
d[i]= i*rows + n*rows*(rows-1)/2

3⃣Добавьте конфеты за дополнительный неполный цикл и оставшиеся конфеты:
d[i]+=i+n⋅rows для первых p%n людей
d[p%n]+=remaining
Верните распределение конфет d


😎 Решение:

import (
    "math"
)

func distributeCandies(candies int, num_people int) []int {
    n := num_people
    p := int(math.Floor(math.Sqrt(2*float64(candies)+0.25) - 0.5))
    remaining := candies - (p+1)*p/2
    rows := p / n
    cols := p % n
    
    d := make([]int, n)
    for i := 0; i < n; i++ {
        d[i] = (i + 1) * rows + (rows * (rows - 1) / 2) * n
        if i < cols {
            d[i] += i + 1 + rows * n
        }
    }
    d[cols] += remaining
    return d
}

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

Задача: 1178. Number of Valid Words for Each PuzzleHardTopicsHint
Сложность: hard

Относительно заданной строки-головоломки, слово является допустимым, если выполняются оба следующих условия:

Слово содержит первую букву головоломки.
Каждая буква в слове присутствует в головоломке.
Например, если головоломка "abcdefg", то допустимыми словами являются "faced", "cabbage" и "baggage", а недопустимыми словами являются "beefed" (не включает 'a') и "based" (включает 's', которой нет в головоломке).

Верните массив answer, где answer[i] - это количество слов в данном списке слов words, которые допустимы относительно головоломки puzzles[i].

Пример:

Input: words = ["apple","pleas","please"], puzzles = ["aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy"]
Output: [0,1,3,2,0]

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

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

2⃣Подсчитайте количество допустимых слов для каждой головоломки. Для каждой головоломки в списке puzzles:
Преобразуйте ее в битовую маску ее символов. Итерируйте по каждой возможной подмаске, содержащей первую букву головоломки (puzzle[i][0]). Слово является допустимым для головоломки, если его битовая маска совпадает с одной из подмасок головоломки.

3⃣Для каждой подмаски увеличивайте счетчик на количество слов, соответствующих подмаске. Мы можем найти количество слов, соответствующих подмаске, используя карту, построенную на предыдущем шаге.

😎 Решение

func bitmask(word string) int {
    mask := 0
    for _, letter := range word {
        mask |= 1 << (letter - 'a')
    }
    return mask
}

func findNumOfValidWords(words []string, puzzles []string) []int {
    wordCount := make(map[int]int)
    for _, word := range words {
        mask := bitmask(word)
        wordCount[mask]++
    }

    result := make([]int, 0, len(puzzles))
    for _, puzzle := range puzzles {
        first := 1 << (puzzle[0] - 'a')
        count := wordCount[first]
        mask := bitmask(puzzle[1:])
        for submask := mask; submask > 0; submask = (submask - 1) & mask {
            count += wordCount[submask | first]
        }
        result = append(result, count)
    }
    return result
}

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

Задача: 1203. Sort Items by Groups Respecting Dependencies
Сложность: hard

Есть n предметов, каждый из которых принадлежит нулевой или одной из m групп, где group[i] — это группа, к которой принадлежит i-й предмет, и равно -1, если i-й предмет не принадлежит никакой группе. Предметы и группы имеют индексацию с нуля. Группа может не иметь ни одного предмета.

Верните отсортированный список предметов таким образом:
Предметы, принадлежащие одной группе, расположены рядом друг с другом в отсортированном списке.
Существуют некоторые отношения между этими предметами, где beforeItems[i] — это список, содержащий все предметы, которые должны быть перед i-м предметом в отсортированном массиве (слева от i-го предмета).
Верните любое решение, если существует более одного решения, и верните пустой список, если решения не существует.

Пример:

Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
Output: [6,3,4,1,5,2,0,7]

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

1⃣Инициализация и создание графов:
Присвоить уникальные идентификаторы группам для элементов без группы.
Создать два графа: item_graph для элементов и group_graph для групп. Также создать два массива для учета входящих рёбер для элементов и групп.

2⃣Построение графов:
Пройти по массиву beforeItems и добавить зависимости между элементами в item_graph, увеличивая счётчик входящих рёбер.
Если элементы принадлежат разным группам, добавить зависимость между группами в group_graph, увеличивая счётчик входящих рёбер.

3⃣Топологическая сортировка и создание итогового списка:
Выполнить топологическую сортировку для элементов и групп. Если есть цикл, вернуть пустой список.
Создать итоговый список, добавляя отсортированные элементы каждой группы.

😎 Решение:

func sortItems(n int, m int, group []int, beforeItems [][]int) []int {
    groupId := m
    for i := 0; i < n; i++ {
        if group[i] == -1 {
            group[i] = groupId
            groupId++
        }
    }

    itemGraph := make(map[int][]int)
    groupGraph := make(map[int][]int)
    itemIndegree := make([]int, n)
    groupIndegree := make([]int, groupId)

    for i := 0; i < n; i++ {
        itemGraph[i] = []int{}
    }
    for i := 0; i < groupId; i++ {
        groupGraph[i] = []int{}
    }

    for curr := 0; curr < n; curr++ {
        for _, prev := range beforeItems[curr] {
            itemGraph[prev] = append(itemGraph[prev], curr)
            itemIndegree[curr]++
            if group[curr] != group[prev] {
                groupGraph[group[prev]] = append(groupGraph[group[prev]], group[curr])
                groupIndegree[group[curr]]++
            }
        }
    }

    itemOrder := topologicalSort(itemGraph, itemIndegree)
    groupOrder := topologicalSort(groupGraph, groupIndegree)
    if len(itemOrder) == 0 || len(groupOrder) == 0 {
        return []int{}
    }

    orderedGroups := make(map[int][]int)
    for _, item := range itemOrder {
        orderedGroups[group[item]] = append(orderedGroups[group[item]], item)
    }

    answerList := []int{}
    for _, groupIndex := range groupOrder {
        answerList = append(answerList, orderedGroups[groupIndex]...)
    }

    return answerList
}

func topologicalSort(graph map[int][]int, indegree []int) []int {
    visited := []int{}
    stack := []int{}
    for key := range graph {
        if indegree[key] == 0 {
            stack = append(stack, key)
        }
    }

    for len(stack) > 0 {
        curr := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        visited = append(visited, curr)
        for _, next := range graph[curr] {
            indegree[next]--
            if indegree[next] == 0 {
                stack = append(stack, next)
            }
        }
    }

    if len(visited) != len(graph) {
        return []int{}
    }
    return visited
}

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

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

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

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: true

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

1⃣Сначала мы определяем функцию height, которая для любого узла p в дереве T возвращает:
-1, если p является пустым поддеревом, т.е. null;
1 + max(height(p.left), height(p.right)) в противном случае.

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

3⃣Следовательно, мы можем сравнить высоты двух дочерних поддеревьев, а затем рекурсивно проверить каждое из них:
Если root == NULL, возвращаем true.
Если abs(height(root.left) - height(root.right)) > 1, возвращаем false.
В противном случае возвращаем isBalanced(root.left) && isBalanced(root.right).

😎 Решение:

func height(root *TreeNode) int {
    if root == nil {
        return -1
    }
    return 1 + max(height(root.Left), height(root.Right))
}

func isBalanced(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return abs(height(root.Left)-height(root.Right)) < 2 &&
        isBalanced(root.Left) &&
        isBalanced(root.Right)
}

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

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

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