Задача: 724. Find Pivot Index
Сложность: easy

Если задан массив целых чисел nums, вычислите поворотный индекс этого массива. Поворотный индекс - это индекс, при котором сумма всех чисел строго слева от индекса равна сумме всех чисел строго справа от индекса. Если индекс находится на левом краю массива, то сумма слева равна 0, так как слева нет элементов. Это относится и к правому краю массива. Возвращается самый левый поворотный индекс. Если такого индекса не существует, возвращается -1.

Пример:

Input: nums = [1,7,3,6,5,6]
Output: 3

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

1⃣Вычислите сумму всех элементов массива.

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

3⃣Если текущий индекс удовлетворяет условию, верните его; если нет, продолжайте проверку. Если такой индекс не найден, верните -1.

😎 Решение:

package main

func pivotIndex(nums []int) int {
    totalSum := 0
    for _, num := range nums {
        totalSum += num
    }
    leftSum := 0
    for i, num := range nums {
        if leftSum == totalSum - leftSum - num {
            return i
        }
        leftSum += num
    }
    return -1
}

func main() {
    nums := []int{1, 7, 3, 6, 5, 6}
    result := pivotIndex(nums)
    println(result)
}

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

Задача: 361. Bomb Enemy
Сложность: medium

Дана матрица размером m x n, где каждая ячейка является либо стеной 'W', либо врагом 'E', либо пустой '0'. Верните максимальное количество врагов, которых можно уничтожить, используя одну бомбу. Вы можете разместить бомбу только в пустой ячейке.

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

Пример:

Input: grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
Output: 3

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

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

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

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

😎 Решение:

package main

import "fmt"

type Solution struct{}

func (s *Solution) maxKilledEnemies(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }

    rows := len(grid)
    cols := len(grid[0])
    maxCount := 0

    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            if grid[row][col] == '0' {
                hits := s.killEnemies(row, col, grid)
                if hits > maxCount {
                    maxCount = hits
                }
            }
        }
    }

    return maxCount
}

func (s *Solution) killEnemies(row, col int, grid [][]byte) int {
    enemyCount := 0
    directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

    for _, dir := range directions {
        r, c := row+dir[0], col+dir[1]

        for r >= 0 && r < len(grid) && c >= 0 && c < len(grid[0]) {
            if grid[r][c] == 'W' {
                break
            }
            if grid[r][c] == 'E' {
                enemyCount++
            }
            r += dir[0]
            c += dir[1]
        }
    }

    return enemyCount
}

func main() {
    grid := [][]byte{
        {'0', 'E', '0', '0'},
        {'E', '0', 'W', 'E'},
        {'0', 'E', '0', '0'},
    }

    sol := Solution{}
    fmt.Println(sol.maxKilledEnemies(grid)) 
}

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

Задача: 764. Largest Plus Sign
Сложность: medium

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

Пример:

Input: n = 5, mines = [[4,2]]
Output: 2

Пояснение: максимальный крест — центр в (2,2), лучи по длине 1 во все стороны.

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

1⃣Инициализация сетки
Создаём матрицу grid n x n, заполняем единицами, и для каждого [x, y] из mines выставляем grid[x][y] = 0.

2⃣Динамика в 4 направлениях
Создаём 4 матрицы:
- left[i][j] — длина непрерывных 1 слева от (i,j)
- right[i][j] — справа
- up[i][j] — сверху
- down[i][j] — снизу
Каждую заполняем проходом по строкам/столбцам.

3⃣Определение порядка
Для каждой ячейки (i, j) считаем order = min(left[i][j], right[i][j], up[i][j], down[i][j]).
Ответ — максимальный order.

Решение (оптимизированное O(n²) с динамикой):

func orderOfLargestPlusSign(n int, mines [][]int) int {
    grid := make([][]int, n)
    for i := range grid {
        grid[i] = make([]int, n)
        for j := range grid[i] {
            grid[i][j] = n // максимальная возможная длина
        }
    }

    for _, mine := range mines {
        grid[mine[0]][mine[1]] = 0
    }

    for i := 0; i < n; i++ {
        count := 0
        for j := 0; j < n; j++ { // слева направо
            if grid[i][j] == 0 {
                count = 0
            } else {
                count++
                grid[i][j] = min(grid[i][j], count)
            }
        }

        count = 0
        for j := n - 1; j >= 0; j-- { // справа налево
            if grid[i][j] == 0 {
                count = 0
            } else {
                count++
                grid[i][j] = min(grid[i][j], count)
            }
        }
    }

    for j := 0; j < n; j++ {
        count := 0
        for i := 0; i < n; i++ { // сверху вниз
            if grid[i][j] == 0 {
                count = 0
            } else {
                count++
                grid[i][j] = min(grid[i][j], count)
            }
        }

        count = 0
        for i := n - 1; i >= 0; i-- { // снизу вверх
            if grid[i][j] == 0 {
                count = 0
            } else {
                count++
                grid[i][j] = min(grid[i][j], count)
            }
        }
    }

    res := 0
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            res = max(res, grid[i][j])
        }
    }

    return res
}

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
}

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

Задача: 157. Read N Characters Given Read4
Сложность: easy

Предположим, что у вас есть файл, и вы можете читать файл только с помощью данного метода read4. Реализуйте метод для чтения n символов.
Метод read4 читает до 4 символов за раз во временный буфер, и вы должны использовать его, чтобы скопировать максимум n символов в целевой буфер buf.

Пример:

Input: file = "abc", n = 4  
Output: 3

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

1⃣Инициализируем счётчики copiedChars = 0 и readChars = 4, а также создаём временный буфер buf4 размером 4 символа.

2⃣Пока считанные символы меньше n и readChars == 4, читаем с помощью read4(buf4) и посимвольно копируем в buf.

3⃣Если достигли n символов или read4 вернул меньше 4 — завершаем и возвращаем количество считанных символов.

😎 Решение:

type Reader4 interface {
    Read4(buf []byte) int
}

type Solution struct {
    Reader4
}

func (sol *Solution) Read(buf []byte, n int) int {
    copiedChars := 0
    readChars := 4
    buf4 := make([]byte, 4)

    for copiedChars < n && readChars == 4 {
        readChars = sol.Read4(buf4)
        for i := 0; i < readChars; i++ {
            if copiedChars == n {
                return copiedChars
            }
            buf[copiedChars] = buf4[i]
            copiedChars++
        }
    }
    return copiedChars
}

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

Задача: 716. Max Stack
Сложность: hard

Разработайте структуру данных max-стека, поддерживающую операции со стеком и поиск максимального элемента стека. Реализуйте класс MaxStack: MaxStack() Инициализирует объект стека. void push(int x) Вставляет элемент x в стек. int pop() Удаляет элемент на вершине стека и возвращает его. int top() Получает элемент на вершине стека без его удаления. int peekMax() Получает максимальный элемент в стеке без его удаления. int popMax() Получает максимальный элемент в стеке и удаляет его. Если максимальных элементов несколько, удалите только самый верхний. Вы должны придумать решение, которое поддерживает O(1) для каждого вызова вершины и O(logn) для каждого другого вызова.

Пример:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

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

1⃣Инициализируйте MaxStack с двумя стеками: один для хранения всех элементов, другой для отслеживания максимальных элементов.

2⃣Для операции push(x) добавьте элемент в оба стека: в основной стек и, если это необходимо, в стек максимумов. Для операции pop() удалите элемент из основного стека и, если этот элемент является текущим максимальным, удалите его и из стека максимумов. Для операции top() верните верхний элемент основного стека.

3⃣Для операции peekMax() верните верхний элемент стека максимумов. Для операции popMax() удалите и верните верхний элемент стека максимумов. Для этого временно извлеките элементы из основного стека до тех пор, пока не будет найден максимальный элемент, затем верните остальные элементы обратно.

😎 Решение:

package main

type MaxStack struct {
    stack    []int
    maxStack []int
}

func Constructor() MaxStack {
    return MaxStack{}
}

func (this *MaxStack) Push(x int) {
    this.stack = append(this.stack, x)
    if len(this.maxStack) == 0 || x >= this.maxStack[len(this.maxStack)-1] {
        this.maxStack = append(this.maxStack, x)
    }
}

func (this *MaxStack) Pop() int {
    x := this.stack[len(this.stack)-1]
    this.stack = this.stack[:len(this.stack)-1]
    if x == this.maxStack[len(this.maxStack)-1] {
        this.maxStack = this.maxStack[:len(this.maxStack)-1]
    }
    return x
}

func (this *MaxStack) Top() int {
    return this.stack[len(this.stack)-1]
}

func (this *MaxStack) PeekMax() int {
    return this.maxStack[len(this.maxStack)-1]
}

func (this *MaxStack) PopMax() int {
    maxVal := this.maxStack[len(this.maxStack)-1]
    this.maxStack = this.maxStack[:len(this.maxStack)-1]
    buffer := []int{}
    for this.stack[len(this.stack)-1] != maxVal {
        buffer = append(buffer, this.stack[len(this.stack)-1])
        this.stack = this.stack[:len(this.stack)-1]
    }
    this.stack = this.stack[:len(this.stack)-1]
    for len(buffer) > 0 {
        this.Push(buffer[len(buffer)-1])
        buffer = buffer[:len(buffer)-1]
    }
    return maxVal
}

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

Задача: 1202. Smallest String With Swaps
Сложность: medium

Вам дана строка s и массив пар индексов в строке pairs, где pairs[i] = [a, b] указывает на 2 индекса (начиная с 0) в строке.
Вы можете менять местами символы в любой паре индексов в заданных парах любое количество раз.
Верните лексикографически наименьшую строку, которую можно получить после выполнения перестановок.

Пример:

Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[1] and s[2], s = "bacd"

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

1⃣Создание списка смежности:
Итеративно пройдитесь по парам и создайте список смежности adj, где adj[source] содержит все смежные вершины вершины source.

2⃣Обход графа и сбор индексов и символов:
Итеративно пройдитесь по индексам от 0 до s.size() - 1. Для каждого индекса vertex:
- выполните DFS, если вершина еще не посещена (visited[vertex] = false).
- во время выполнения DFS сохраняйте vertex в список indices и символ s[vertex] в список characters.

3⃣Сортировка и построение результирующей строки:
Отсортируйте списки indices и characters.
Пройдитесь по индексам и символам, и разместите i-й символ в i-й индекс результирующей строки smallestString.
Верните smallestString.

😎 Решение:

import (
    "sort"
)

func smallestStringWithSwaps(s string, pairs [][]int) string {
    n := len(s)
    adj := make([][]int, n)
    for _, pair := range pairs {
        adj[pair[0]] = append(adj[pair[0]], pair[1])
        adj[pair[1]] = append(adj[pair[1]], pair[0])
    }

    visited := make([]bool, n)
    sArray := []rune(s)

    var dfs func(node int, indices *[]int, chars *[]rune)
    dfs = func(node int, indices *[]int, chars *[]rune) {
        visited[node] = true
        *indices = append(*indices, node)
        *chars = append(*chars, sArray[node])
        for _, neighbor := range adj[node] {
            if !visited[neighbor] {
                dfs(neighbor, indices, chars)
            }
        }
    }

    for i := 0; i < n; i++ {
        if !visited[i] {
            indices := []int{}
            chars := []rune{}
            dfs(i, &indices, &chars)
            sort.Ints(indices)
            sort.Slice(chars, func(i, j int) bool { return chars[i] < chars[j] })
            for j, index := range indices {
                sArray[index] = chars[j]
            }
        }
    }

    return string(sArray)
}

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

Задача: 911. Online Election
Сложность: medium

Вам даны два целочисленных массива persons и times. На выборах i-й голос был отдан за person[i] в момент времени times[i]. Для каждого запроса в момент времени t найдите человека, который лидировал на выборах в момент времени t. Голоса, отданные в момент времени t, будут учитываться в нашем запросе. В случае равенства голосов побеждает тот, кто проголосовал последним (среди равных кандидатов). Реализация класса TopVotedCandidate: TopVotedCandidate(int[] persons, int[] times) Инициализирует объект с массивами persons и times. int q(int t) Возвращает номер человека, который лидировал на выборах в момент времени t в соответствии с указанными правилами.

Пример:

Input
["TopVotedCandidate", "q", "q", "q", "q", "q", "q"]
[[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]
Output
[null, 0, 1, 1, 0, 0, 1]

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

1⃣Использовать два массива для хранения лиц и времени голосования.

2⃣Поддерживать текущий счет для каждого кандидата и текущего лидера на момент времени.

3⃣На каждый запрос времени t, найти наибольший индекс времени, который не превышает t, и вернуть лидера на этот момент времени.

😎 Решение:

package main

import (
    "sort"
)

type TopVotedCandidate struct {
    times   []int
    leaders []int
}

func Constructor(persons []int, times []int) TopVotedCandidate {
    counts := make(map[int]int)
    leader := -1
    leaders := make([]int, len(persons))

    for i, person := range persons {
        counts[person]++
        if counts[person] >= counts[leader] {
            leader = person
        }
        leaders[i] = leader
    }

    return TopVotedCandidate{times, leaders}
}

func (this *TopVotedCandidate) Q(t int) int {
    idx := sort.Search(len(this.times), func(i int) bool {
        return this.times[i] > t
    }) - 1
    return this.leaders[idx]
}

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

Задача: 656. Coin Path
Сложность: hard

Вам дан целочисленный массив монет (1-индексированный) длины n и целое число maxJump. Вы можете перейти на любой индекс i массива coins, если coins[i] != -1 и вы должны заплатить coins[i] при посещении индекса i. Кроме того, если вы в данный момент находитесь на индексе i, вы можете перейти только на любой индекс i + k, где i + k <= n и k - значение в диапазоне [1, maxJump]. Изначально вы находитесь на индексе 1 (coins[1] не -1). Вы хотите найти путь, который достигнет индекса n с минимальной стоимостью. Верните целочисленный массив индексов, которые вы посетите в таком порядке, чтобы достичь индекса n с минимальной стоимостью. Если существует несколько путей с одинаковой стоимостью, верните лексикографически наименьший такой путь. Если невозможно достичь индекса n, возвращается пустой массив. Путь p1 = [Pa1, Pa2, ..., Pax] длины x лексикографически меньше, чем p2 = [Pb1, Pb2, ..., Pbx] длины y, если и только если при первом j, где Paj и Pbj отличаются, Paj < Pbj; если такого j нет, то x < y.

Пример:

Input: coins = [1,2,4,-1,2], maxJump = 2
Output: [1,3,5]

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

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

2⃣Храните путь до каждого индекса для отслеживания наименьшего лексикографического пути.

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

😎 Решение:

package main

import (
    "container/heap"
    "fmt"
    "math"
    "sort"
)

type Item struct {
    cost, index int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].cost < pq[j].cost
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
    *pq = append(*pq, x.(*Item))
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[0 : n-1]
    return item
}

func minCostPath(coins []int, maxJump int) []int {
    n := len(coins)
    if coins[0] == -1 {
        return []int{}
    }

    dp := make([]int, n)
    for i := range dp {
        dp[i] = math.MaxInt32
    }
    dp[0] = coins[0]
    path := make([][]int, n)
    for i := range path {
        path[i] = []int{}
    }
    path[0] = []int{1}

    pq := &PriorityQueue{&Item{cost: coins[0], index: 0}}
    heap.Init(pq)

    for pq.Len() > 0 {
        current := heap.Pop(pq).(*Item)
        currentCost, i := current.cost, current.index
        if currentCost > dp[i] {
            continue
        }
        for k := 1; k <= maxJump; k++ {
            if i+k < n && coins[i+k] != -1 {
                newCost := currentCost + coins[i+k]
                newPath := append([]int{}, path[i]...)
                newPath = append(newPath, i+k+1)
                if newCost < dp[i+k] || (newCost == dp[i+k] && lexicographicalLess(newPath, path[i+k])) {
                    dp[i+k] = newCost
                    path[i+k] = newPath
                    heap.Push(pq, &Item{cost: newCost, index: i+k})
                }
            }
        }
    }

    if dp[n-1] == math.MaxInt32 {
        return []int{}
    }
    return path[n-1]
}

func lexicographicalLess(a, b []int) bool {
    for i := range a {
        if i >= len(b) {
            return false
        }
        if a[i] != b[i] {
            return a[i] < b[i]
        }
    }
    return len(a) < len(b)
}

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

Задача: 1214. Two Sum BSTs
Сложность: medium

Даны корни двух бинарных деревьев поиска, root1 и root2, верните true, если и только если существует узел в первом дереве и узел во втором дереве, значения которых в сумме равны заданному целому числу target.

Пример:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
Output: false

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

1⃣Создайте два пустых множества node_set1 и node_set2. Выполните обход дерева root1, добавляя значения каждого узла в node_set1, и выполните обход дерева root2, добавляя значения каждого узла в node_set2.

2⃣Итерация по элементам в node_set1: для каждого элемента value1 проверяйте, находится ли target - value1 в node_set2.

3⃣Если target - value1 находится в node_set2, верните true. Если после завершения итерации не найдено ни одной подходящей пары, верните false.

😎 Решение:

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

func dfs(node *TreeNode, nodeSet map[int]struct{}) {
    if node == nil {
        return
    }
    dfs(node.Left, nodeSet)
    nodeSet[node.Val] = struct{}{}
    dfs(node.Right, nodeSet)
}

func twoSumBSTs(root1 *TreeNode, root2 *TreeNode, target int) bool {
    nodeSet1 := make(map[int]struct{})
    nodeSet2 := make(map[int]struct{})
    dfs(root1, nodeSet1)
    dfs(root2, nodeSet2)
    
    for value1 := range nodeSet1 {
        if _, found := nodeSet2[target - value1]; found {
            return true
        }
    }
    
    return false
}

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

Задача: 759. Employee Free Time
Сложность: hard

Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. Верните список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или массивами. Например, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину.

Пример:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]

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

1⃣Объедините все интервалы всех сотрудников в один список и отсортируйте его по начальным временам.

2⃣Объедините пересекающиеся интервалы в один.

3⃣Найдите промежутки между объединенными интервалами, представляющие свободное время.

😎 Решение:

package main

import (
    "sort"
)

type Interval struct {
    Start int
    End   int
}

func employeeFreeTime(schedule [][]Interval) []Interval {
    intervals := []Interval{}
    for _, employee := range schedule {
        intervals = append(intervals, employee...)
    }
    
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i].Start < intervals[j].Start
    })
    
    merged := []Interval{}
    for _, interval := range intervals {
        if len(merged) == 0 || merged[len(merged)-1].End < interval.Start {
            merged = append(merged, interval)
        } else {
            merged[len(merged)-1].End = max(merged[len(merged)-1].End, interval.End)
        }
    }
    
    freeTime := []Interval{}
    for i := 1; i < len(merged); i++ {
        if merged[i].Start > merged[i-1].End {
            freeTime = append(freeTime, Interval{Start: merged[i-1].End, End: merged[i].Start})
        }
    }
    
    return freeTime
}

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

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

Задача: 957. Prison Cells After N Days
Сложность: medium

Есть 8 тюремных камер в ряду, и каждая камера либо занята, либо пуста.
Каждый день статус камеры, занята она или пуста, меняется по следующим правилам:
Если у камеры два соседних соседа, которые оба заняты или оба пусты, то камера становится занятой.
В противном случае, она становится пустой.
Учтите, что поскольку тюрьма — это ряд, у первой и последней камер в ряду не может быть двух соседних соседей.

Вам дан целочисленный массив cells, где cells[i] == 1, если i-я камера занята, и cells[i] == 0, если i-я камера пуста, и вам дано целое число n.
Верните состояние тюрьмы после n дней (т.е. после n таких изменений, описанных выше).

Пример:

Input: cells = [0,1,0,1,1,0,0,1], n = 7
Output: [0,0,1,1,0,0,0,0]
Explanation: The following table summarizes the state of the prison on each day:
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

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

1⃣Преобразуйте текущее состояние камер в целое число с помощью битовой маски. Это позволит удобно отслеживать повторяющиеся состояния.

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

3⃣Продолжайте симуляцию, пока не достигнете заданного числа дней, либо используйте цикл для ускорения процесса.

😎 Решение:

func cellsToBitmap(cells []int) int {
    stateBitmap := 0
    for _, cell := range cells {
        stateBitmap = (stateBitmap << 1) | cell
    }
    return stateBitmap
}

func nextDay(cells []int) []int {
    newCells := make([]int, len(cells))
    for i := 1; i < len(cells)-1; i++ {
        newCells[i] = 0
        if cells[i-1] == cells[i+1] {
            newCells[i] = 1
        }
    }
    return newCells
}

func prisonAfterNDays(cells []int, N int) []int {
    seen := make(map[int]int)
    isFastForwarded := false

    for N > 0 {
        if !isFastForwarded {
            stateBitmap := cellsToBitmap(cells)
            if _, ok := seen[stateBitmap]; ok {
                N %= seen[stateBitmap] - N
                isFastForwarded = true
            } else {
                seen[stateBitmap] = N
            }
        }

        if N > 0 {
            N--
            cells = nextDay(cells)
        }
    }
    return cells
}

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

Задача: 1801. Number of Orders in the Backlog
Сложность: medium

Дан двумерный целочисленный массив orders, где каждый элемент orders[i] = [pricei, amounti, orderTypei] обозначает, что было размещено amounti заказов типа orderTypei по цене pricei. Тип заказа orderTypei может быть:

- 0, если это партия заказов на покупку, или
- 1, если это партия заказов на продажу.

Обратите внимание, что orders[i] представляет собой партию из amounti независимых заказов с одинаковой ценой и типом. Все заказы, представленные orders[i], будут размещены перед всеми заказами, представленными orders[i+1] для всех допустимых i.

Существует список невыполненных заказов (backlog), который изначально пуст. При размещении заказа происходит следующее:

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

Верните общее количество заказов в списке невыполненных заказов после размещения всех заказов из входных данных. Поскольку это число может быть большим, верните его по модулю 10^9 + 7.

Пример:
Input: orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]]
Output: 6

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

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

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

3⃣Подсчитайте общее количество оставшихся заказов в списке и верните его по модулю 10^9 + 7.

😎 Решение:

import "container/heap"

type Order struct {
    price  int
    amount int
}

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

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

Задача: 359. Logger Rate Limiter
Сложность: easy

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

Реализуйте класс Logger:
Logger() Инициализирует объект логгера.
bool shouldPrintMessage(int timestamp, string message) Возвращает true, если сообщение должно быть напечатано в данной временной метке, в противном случае возвращает false.

Пример:

Input
["Logger", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage"]
[[], [1, "foo"], [2, "bar"], [3, "foo"], [8, "bar"], [10, "foo"], [11, "foo"]]
Output
[null, true, true, false, false, false, true]

Explanation
Logger logger = new Logger();
logger.shouldPrintMessage(1, "foo");  // return true, next allowed timestamp for "foo" is 1 + 10 = 11
logger.shouldPrintMessage(2, "bar");  // return true, next allowed timestamp for "bar" is 2 + 10 = 12
logger.shouldPrintMessage(3, "foo");  // 3 < 11, return false
logger.shouldPrintMessage(8, "bar");  // 8 < 12, return false
logger.shouldPrintMessage(10, "foo"); // 10 < 11, return false
logger.shouldPrintMessage(11, "foo"); // 11 >= 11, return true, next allowed timestamp for "foo" is 11 + 10 = 21

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

1⃣Инициализируем хеш-таблицу/словарь для хранения сообщений вместе с временной меткой.

2⃣При поступлении нового сообщения оно может быть напечатано при выполнении одного из следующих условий: Мы никогда раньше не видели это сообщение. Мы видели это сообщение ранее, и оно было напечатано более 10 секунд назад.

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

😎 Решение:

type Logger struct {
    msgDict map[string]int
}

func Constructor() Logger {
    return Logger{msgDict: make(map[string]int)}
}

func (this *Logger) ShouldPrintMessage(timestamp int, message string) bool {
    if oldTimestamp, exists := this.msgDict[message]; !exists || timestamp-oldTimestamp >= 10 {
        this.msgDict[message] = timestamp
        return true
    }
    return false
}

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

Задача: 254. Factor Combinations
Сложность: medium

Числа можно рассматривать как произведение их множителей.

Например, 8 = 2 x 2 x 2 = 2 x 4.
Дано целое число n, верните все возможные комбинации его множителей. Вы можете вернуть ответ в любом порядке.

Обратите внимание, что множители должны быть в диапазоне [2, n - 1].

Пример:

Input: n = 1
Output: []

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

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

2⃣Основная логика функции backtracking:
Если размер factors больше 1, добавьте его копию в ans, так как это одно из желаемых решений.
Получите последний элемент factors (lastFactor) и удалите его из factors.
Если factors пуст, итерируйте i от 2. В противном случае, итерируйте i от последнего значения в factors. Итерируйте, пока i <= lastFactor / i.
Для каждого i, если lastFactor % i == 0, добавьте i и lastFactor / i в factors и вызовите backtracking(factors, ans).
Восстановите список (откат) factors, удалив последние два элемента из factors.
Восстановите список (откат) factors, добавив обратно lastFactor.

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

😎 Решение:

package main

func backtracking(factors []int, ans *[][]int) {
    if len(factors) > 1 {
        combo := make([]int, len(factors))
        copy(combo, factors)
        *ans = append(*ans, combo)
    }
    lastFactor := factors[len(factors)-1]
    factors = factors[:len(factors)-1]
    start := 2
    if len(factors) > 0 {
        start = factors[len(factors)-1]
    }
    for i := start; i*i <= lastFactor; i++ {
        if lastFactor%i == 0 {
            factors = append(factors, i)
            factors = append(factors, lastFactor/i)
            backtracking(factors, ans)
            factors = factors[:len(factors)-2]
        }
    }
    factors = append(factors, lastFactor)
}

func getFactors(n int) [][]int {
    var ans [][]int
    backtracking([]int{n}, &ans)
    return ans
}

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

Задача: 591. Tag Validator
Сложность: hard

Дана строка, представляющая фрагмент кода, реализуйте валидатор тегов для разбора кода и определения его корректности.

Фрагмент кода считается корректным, если соблюдаются все следующие правила:
Код должен быть заключен в корректный закрытый тег. В противном случае код некорректен.
Закрытый тег (не обязательно корректный) имеет точно следующий формат: <TAG_NAME>TAG_CONTENT</TAG_NAME>. Среди них <TAG_NAME> — это начальный тег, а </TAG_NAME> — конечный тег. TAG_NAME в начальном и конечном тегах должен быть одинаковым. Закрытый тег корректен, если и только если TAG_NAME и TAG_CONTENT корректны.
Корректное TAG_NAME содержит только заглавные буквы и имеет длину в диапазоне [1, 9]. В противном случае TAG_NAME некорректен.
Корректное TAG_CONTENT может содержать другие корректные закрытые теги, cdata и любые символы (см. примечание 1), КРОМЕ неподходящих <, неподходящих начальных и конечных тегов, и неподходящих или закрытых тегов с некорректным TAG_NAME. В противном случае TAG_CONTENT некорректен.
Начальный тег неподходящий, если нет конечного тега с тем же TAG_NAME, и наоборот. Однако нужно также учитывать проблему несбалансированных тегов, когда они вложены.
< неподходящий, если не удается найти последующий >. И когда вы находите < или </, все последующие символы до следующего > должны быть разобраны как TAG_NAME (не обязательно корректный).
cdata имеет следующий формат: <![CDATA[CDATA_CONTENT]]>. Диапазон CDATA_CONTENT определяется как символы между <![CDATA[ и первым последующим ]]>.
CDATA_CONTENT может содержать любые символы. Функция cdata заключается в том, чтобы запретить валидатору разбирать CDATA_CONTENT, поэтому даже если в нем есть символы, которые могут быть разобраны как тег (корректный или некорректный), вы должны рассматривать их как обычные символы.

Пример:

Input: code = "<DIV>This is the first line <![CDATA[<div>]]></DIV>"
Output: true

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

1⃣Инициализируйте стек для отслеживания открытых тегов и флаг для определения наличия тегов. Используйте регулярное выражение для проверки корректности TAG_NAME, TAG_CONTENT и CDATA.

2⃣Пройдитесь по строке, проверяя каждый символ. Если встретите <, определите тип тега (начальный, конечный или CDATA). Обновите стек и индексы в зависимости от найденного типа.

3⃣В конце проверьте, что стек пуст (все теги корректно закрыты) и верните результат.

😎 Решение:

package main

import (
    "regexp"
    "strings"
)

type Solution struct {
    stack       []string
    containsTag bool
}

func (s *Solution) isValidTagName(tag string, ending bool) bool {
    if ending {
        if len(s.stack) > 0 && s.stack[len(s.stack)-1] == tag {
            s.stack = s.stack[:len(s.stack)-1]
        } else {
            return false
        }
    } else {
        s.containsTag = true
        s.stack = append(s.stack, tag)
    }
    return true
}

func (s *Solution) IsValid(code string) bool {
    regex := "<[A-Z]{0,9}>([^<]*(<((\\/?[A-Z]{1,9}>)|(!\\[CDATA\\[(.*?)]]>)))?)*"
    matched, _ := regexp.MatchString(regex, code)
    if !matched {
        return false
    }

    for i := 0; i < len(code); i++ {
        ending := false
        if len(s.stack) == 0 && s.containsTag {
            return false
        }
        if code[i] == '<' {
            if code[i+1] == '!' {
                i = strings.Index(code[i+1:], "]]>") + i + 2
                if i == -1 {
                    return false
                }
                continue
            }
            if code[i+1] == '/' {
                i++
                ending = true
            }
            closeIndex := strings.Index(code[i+1:], ">") + i + 1
            if closeIndex == -1 || !s.isValidTagName(code[i+1:closeIndex], ending) {
                return false
            }
            i = closeIndex
        }
    }
    return len(s.stack) == 0
}

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

Задача: 1231. Divide Chocolate
Сложность: hard

У вас есть одна шоколадка, состоящая из нескольких кусочков. Каждый кусочек имеет свою сладость, заданную массивом сладости. Вы хотите поделиться шоколадом со своими k друзьями, поэтому начинаете разрезать шоколадку на k + 1 кусочков с помощью k разрезов, каждый кусочек состоит из нескольких последовательных кусочков. Будучи щедрым, вы съедите кусочек с минимальной общей сладостью, а остальные кусочки отдадите своим друзьям. Найдите максимальную общую сладость кусочка, который вы можете получить, оптимально разрезав шоколадку.

Пример:

Input: sweetness = [1,2,3,4,5,6,7,8,9], k = 5
Output: 6

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

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

2⃣Двоичный поиск:
Мы будем искать ответ в диапазоне от минимальной сладости до суммы всех сладостей. Начнем с середины этого диапазона и проверим, можно ли разрезать шоколад таким образом, чтобы минимальная сладость была не менее этого значения.

3⃣Проверка делимости:
Для каждой попытки значения сладости в двоичном поиске проверим, можем ли мы разрезать шоколад так, чтобы каждая из k+1 частей имела сладость не меньше текущего значения.

😎 Решение:

func maximizeSweetness(sweetness []int, k int) int {
    canDivide := func(minSweetness int) bool {
        currentSum, cuts := 0, 0
        for _, sweet := range sweetness {
            currentSum += sweet
            if currentSum >= minSweetness {
                cuts++
                currentSum = 0
            }
        }
        return cuts >= k + 1
    }
    
    left, right := sweetness[0], 0
    for _, sweet := range sweetness {
        if sweet < left {
            left = sweet
        }
        right += sweet
    }
    right /= k + 1
    
    for left < right {
        mid := (left + right + 1) / 2
        if canDivide(mid) {
            left = mid
        } else {
            right = mid - 1
        }
    }
    
    return left
}

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

Задача: 514. Freedom Trail
Сложность: hard

В видеоигре Fallout 4 в квесте "Дорога к свободе" игрокам нужно добраться до металлического диска, называемого "Кольцо Свободы", и использовать его для набора определённого ключевого слова, чтобы открыть дверь.

Дана строка ring, представляющая код, выгравированный на внешнем кольце, и другая строка key, представляющая ключевое слово, которое нужно набрать. Верните минимальное количество шагов, чтобы набрать все символы ключевого слова.

Изначально первый символ кольца выровнен в направлении "12 часов". Вы должны набирать все символы из строки key один за другим, поворачивая кольцо по часовой или против часовой стрелки, чтобы каждый символ строки key выровнять в направлении "12 часов", а затем нажимая на центральную кнопку.

На этапе вращения кольца для набора символа key[i]:

Вы можете вращать кольцо по часовой или против часовой стрелки на одно место, что считается одним шагом. Конечная цель вращения — выровнять один из символов кольца в направлении "12 часов", и этот символ должен быть равен key[i].
Если символ key[i] уже выровнен в направлении "12 часов", нажмите центральную кнопку, чтобы набрать его, что также считается одним шагом. После нажатия вы можете начинать набирать следующий символ из key (следующий этап). Иначе, вы завершили весь набор.

Пример:

Input: ring = "godding", key = "godding"
Output: 13

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

1⃣Определите функцию countSteps для вычисления минимального пути между двумя индексами кольца ring. Создайте переменные ringLen и keyLen для хранения длин кольца и ключа соответственно. Создайте словарь bestSteps для хранения минимального количества шагов для нахождения символа на keyIndex, когда ringIndex кольца выровнен в позиции "12 часов".

2⃣Определите функцию tryLock, которая возвращает минимальное количество шагов для набора ключевого слова. Параметры: ringIndex, keyIndex, minSteps (минимальные шаги для набора ключевого слова на данный момент). Проверьте, равен ли keyIndex значению keyLen; если да, верните 0. Проверьте, есть ли пара (ringIndex, keyIndex) в bestSteps. Если есть, верните bestSteps[ringIndex][keyIndex]. Пройдите по каждому charIndex в ring. Если ring[charIndex] равен key[keyIndex], вычислите totalSteps, добавляя результат countSteps, единицу (нажатие центральной кнопки) и результат tryLock для следующего символа в key. Сохраните минимальное значение между totalSteps и текущим minSteps в minSteps. Сохраните minSteps для (ringIndex, keyIndex) в bestSteps.

3⃣Вызовите tryLock(0, 0, INT_MAX), начиная с нулевого индекса ring в позиции "12 часов" и первого символа в key. Наибольшее целое число передается как последний параметр, так как путь между нулевым индексом ring и первым символом key еще не определен.

😎 Решение:

import (
    "math"
    "strconv"
)

func findRotateSteps(ring string, key string) int {
    ringLen := len(ring)
    keyLen := len(key)
    bestSteps := make(map[string]int)
    
    countSteps := func(curr, next int) int {
        stepsBetween := int(math.Abs(float64(curr - next)))
        stepsAround := ringLen - stepsBetween
        return int(math.Min(float64(stepsBetween), float64(stepsAround)))
    }
    
    var tryLock func(int, int) int
    tryLock = func(ringIndex, keyIndex int) int {
        keyPair := strconv.Itoa(ringIndex) + "-" + strconv.Itoa(keyIndex)
        if val, ok := bestSteps[keyPair]; ok {
            return val
        }
        
        if keyIndex == keyLen {
            bestSteps[keyPair] = 0
            return 0
        }
        
        minSteps := math.MaxInt32
        for charIndex := 0; charIndex < ringLen; charIndex++ {
            if ring[charIndex] == key[keyIndex] {
                minSteps = int(math.Min(float64(minSteps), 
                    float64(countSteps(ringIndex, charIndex) + 1 + tryLock(charIndex, keyIndex + 1))))
            }
        }
        bestSteps[keyPair] = minSteps
        return minSteps
    }
    
    return tryLock(0,

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

Задача: 319. Bulb Switcher
Сложность: medium

Есть n лампочек, которые изначально выключены. Сначала вы включаете все лампочки, затем выключаете каждую вторую лампочку.

На третьем раунде вы переключаете каждую третью лампочку (включаете, если она выключена, или выключаете, если она включена). На i-ом раунде вы переключаете каждую i-ую лампочку. На n-ом раунде вы переключаете только последнюю лампочку.

Верните количество лампочек, которые будут включены после n раундов.

Пример:

Input: n = 3
Output: 1
Explanation: At first, the three bulbs are [off, off, off].
After the first round, the three bulbs are [on, on, on].
After the second round, the three bulbs are [on, off, on].
After the third round, the three bulbs are [on, off, off]. 
So you should return 1 because there is only one bulb is on.
Explanation: The two words can be "abcw", "xtfn".

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

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

2⃣Определение состояния лампочки
Лампочка останется включенной только в том случае, если у нее нечетное количество делителей, что возможно только для квадратных чисел.

3⃣Подсчет включенных лампочек
Количество лампочек, которые будут включены после n раундов.

😎 Решение:

import "math"

func bulbSwitch(n int) int {
    return int(math.Sqrt(float64(n)))
}

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

Задача: 842. Split Array into Fibonacci Sequence
Сложность: medium

Вам дана строка цифр num, такая как "123456579". Мы можем разделить её на последовательность, похожую на Фибоначчи [123, 456, 579].
Формально, последовательность, похожая на Фибоначчи, это список f неотрицательных целых чисел, таких что:
0 <= f[i] < 2^31 (то есть каждое число помещается в 32-битный знаковый целый тип),
f.length >= 3, и
f[i] + f[i + 1] == f[i + 2] для всех 0 <= i < f.length - 2.
Обратите внимание, что при разделении строки на части каждая часть не должна иметь лишних ведущих нулей, за исключением случая, если эта часть является числом 0.

Верните любую последовательность, похожую на Фибоначчи, из строки num, или верните [] если это невозможно.

Пример:

Input: num = "1101111"
Output: [11,0,11,11]
Explanation: The output [110, 1, 111] would also be accepted.

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

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

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

3⃣Если последовательность Фибоначчи найдена, верните её, иначе продолжайте перебор.

😎 Решение:

import (
    "strconv"
)

func splitIntoFibonacci(S string) []int {
    N := len(S)
    for i := 0; i < min(10, N); i++ {
        if S[0] == '0' && i > 0 {
            break
        }
        a, _ := strconv.ParseInt(S[:i+1], 10, 64)
        if a >= (1 << 31) - 1 {
            break
        }

        for j := i + 1; j < min(i + 10, N); j++ {
            if S[i+1] == '0' && j > i+1 {
                break
            }
            b, _ := strconv.ParseInt(S[i+1:j+1], 10, 64)
            if b >= (1 << 31) - 1 {
                break
            }

            fib := []int{int(a), int(b)}
            k := j + 1
            for k < N {
                nxt := int64(fib[len(fib)-2] + fib[len(fib)-1])
                if nxt >= (1 << 31) - 1 {
                    break
                }
                nxtS := strconv.FormatInt(nxt, 10)
                if len(S[k:]) >= len(nxtS) && S[k:k+len(nxtS)] == nxtS {
                    k += len(nxtS)
                    fib = append(fib, int(nxt))
                } else {
                    break
                }
            }
            if len(fib) >= 3 {
                return fib
            }
        }
    }
    return []int{}
}

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

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

Задача: 75. Sort Colors
Сложность: medium

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

Мы будем использовать целые числа 0, 1 и 2 для обозначения красного, белого и синего цветов соответственно.

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

Пример:

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

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

1⃣Инициализация крайней правой границы нулей: p0 = 0. Во время выполнения алгоритма nums[idx < p0] = 0.

2⃣Инициализация крайней левой границы двоек: p2 = n - 1. Во время выполнения алгоритма nums[idx > p2] = 2.

3⃣Инициализация индекса текущего элемента для рассмотрения: curr = 0.
Пока curr <= p2:
Если nums[curr] = 0: поменять местами элементы с индексами curr и p0, и сдвинуть оба указателя вправо.
Если nums[curr] = 2: поменять местами элементы с индексами curr и p2. Сдвинуть указатель p2 влево.
Если nums[curr] = 1: сдвинуть указатель curr вправо.

😎 Решение:

func sortColors(nums []int) {
    p0, curr := 0, 0
    p2 := len(nums) - 1
    for curr <= p2 {
        if nums[curr] == 0 {
            nums[curr], nums[p0] = nums[p0], nums[curr]
            curr++
            p0++
        } else if nums[curr] == 2 {
            nums[curr], nums[p2] = nums[p2], nums[curr]
            p2--
        } else {
            curr++
        }
    }
}

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