Задача: 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
}

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

Задача: 513. Find Bottom Left Tree Value
Сложность: medium

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

Пример:

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

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

1⃣Инициализируйте переменную maxDepth для хранения глубины нижнего уровня дерева. Инициализируйте переменную bottomLeftValue для хранения самого левого значения в последней строке дерева.

2⃣Реализуйте рекурсивную функцию dfs, которая обходит дерево и находит самое левое значение в последней строке дерева. Параметры функции: current (текущий узел) и depth (его глубина). Проверьте, пуст ли текущий узел. Если да, то вернитесь.

3⃣Проверьте, превышает ли текущая глубина глобальную переменную maxDepth. Если да, это значит, что мы нашли новый уровень. Установите maxDepth в значение текущей глубины. Установите bottomLeftValue в значение текущего узла. Рекурсивно вызовите dfs для левого поддерева текущего узла, увеличив глубину на один. Рекурсивно вызовите dfs для правого поддерева текущего узла, увеличив глубину на один. Вызовите dfs с корнем и начальной глубиной 0. Верните bottomLeftValue.

😎 Решение:

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

type Solution struct {
    maxDepth       int
    bottomLeftValue int
}

func (s *Solution) findBottomLeftValue(root *TreeNode) int {
    s.maxDepth = -1
    s.bottomLeftValue = 0
    s.dfs(root, 0)
    return s.bottomLeftValue
}

func (s *Solution) dfs(current *TreeNode, depth int) {
    if current == nil {
        return
    }
    
    if depth > s.maxDepth {
        s.maxDepth = depth
        s.bottomLeftValue = current.Val
    }
    
    s.dfs(current.Left, depth+1)
    s.dfs(current.Right, depth+1)
}

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

Задача: 1020. Number of Enclaves
Сложность: medium

Вам дана двоичная матричная сетка m x n, где 0 обозначает морскую ячейку, а 1 - сухопутную. Ход состоит из перехода от одной сухопутной ячейки к другой соседней (в 4-х направлениях) или выхода за границу сетки. Верните количество сухопутных ячеек в сетке, для которых мы не можем выйти за границу сетки за любое количество ходов.

Пример:

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

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

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

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

3⃣Возврат результата:
Верните количество не посещенных сухопутных ячеек.

😎 Решение:

func numEnclaves(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    
    var dfs func(x, y int)
    dfs = func(x, y int) {
        if x < 0 || y < 0 || x >= m || y >= n || grid[x][y] != 1 {
            return
        }
        grid[x][y] = 0
        dfs(x+1, y)
        dfs(x-1, y)
        dfs(x, y+1)
        dfs(x, y-1)
    }
    
    for i := 0; i < m; i++ {
        if grid[i][0] == 1 {
            dfs(i, 0)
        }
        if grid[i][n-1] == 1 {
            dfs(i, n-1)
        }
    }
    
    for j := 0; j < n; j++ {
        if grid[0][j] == 1 {
            dfs(0, j)
        }
        if grid[m-1][j] == 1 {
            dfs(m-1, j)
        }
    }
    
    count := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                count++
            }
        }
    }
    
    return count
}

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

Задача: 748. Shortest Completing Word
Сложность: easy

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

Пример:

Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]
Output: "steps"

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

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

2⃣Пройти по массиву words, проверяя каждое слово на соответствие требованиям.

3⃣Найти самое короткое завершающее слово среди подходящих.

😎 Решение:

package main

func shortestCompletingWord(licensePlate string, words []string) string {
    licenseCount := getCharCount(licensePlate)
    
    var result string
    for _, word := range words {
        if isCompletingWord(word, licenseCount) {
            if result == "" || len(word) < len(result) {
                result = word
            }
        }
    }
    return result
}

func getCharCount(s string) map[rune]int {
    count := make(map[rune]int)
    for _, c := range s {
        if isLetter(c) {
            count[toLower(c)]++
        }
    }
    return count
}

func isCompletingWord(word string, licenseCount map[rune]int) bool {
    wordCount := make(map[rune]int)
    for _, c := range word {
        wordCount[c]++
    }
    for char, cnt := range licenseCount {
        if wordCount[char] < cnt {
            return false
        }
    }
    return true
}

func isLetter(c rune) bool {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')
}

func toLower(c rune) rune {
    if c >= 'A' && c <= 'Z' {
        return c + 'a' - 'A'
    }
    return c
}

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

Задача: 288. Unique Word Abbreviation
Сложность: medium

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

Например:
dog --> d1g, потому что между первой буквой 'd' и последней буквой 'g' одна буква.
internationalization --> i18n, потому что между первой буквой 'i' и последней буквой 'n' 18 букв.
it --> it, потому что любое слово из двух символов является своим собственным сокращением.
Реализуйте класс ValidWordAbbr:

ValidWordAbbr(String[] dictionary) Инициализирует объект со словарем слов.
boolean isUnique(string word) Возвращает true, если выполняется одно из следующих условий (в противном случае возвращает false):
В словаре нет слова, сокращение которого равно сокращению слова word.
Для любого слова в словаре, сокращение которого равно сокращению слова word, это слово и word одинаковы.

Пример:

Input
["ValidWordAbbr", "isUnique", "isUnique", "isUnique", "isUnique", "isUnique"]
[[["deer", "door", "cake", "card"]], ["dear"], ["cart"], ["cane"], ["make"], ["cake"]]
Output
[null, false, true, false, true, true]

Explanation
ValidWordAbbr validWordAbbr = new ValidWordAbbr(["deer", "door", "cake", "card"]);
validWordAbbr.isUnique("dear"); // return false, dictionary word "deer" and word "dear" have the same abbreviation "d2r" but are not the same.
validWordAbbr.isUnique("cart"); // return true, no words in the dictionary have the abbreviation "c2t".
validWordAbbr.isUnique("cane"); // return false, dictionary word "cake" and word "cane" have the same abbreviation  "c2e" but are not the same.
validWordAbbr.isUnique("make"); // return true, no words in the dictionary have the abbreviation "m2e".
validWordAbbr.isUnique("cake"); // return true, because "cake" is already in the dictionary and no other word in the dictionary has "c2e" abbreviation.

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

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

2⃣Генерация сокращений:
При инициализации объекта ValidWordAbbr пройдите через каждое слово в словаре и создайте его сокращение.
Если сокращение уже существует в abbrDict, установите значение в false (не уникальное). В противном случае установите значение в true (уникальное).

3⃣Проверка уникальности:
Для метода isUnique создайте сокращение для входного слова и проверьте, есть ли это сокращение в abbrDict.
Если сокращение отсутствует в abbrDict, возвращайте true.
Если сокращение присутствует и оно уникально, проверьте, есть ли это слово в словаре. Если да, возвращайте true, в противном случае - false.

😎 Решение:

type ValidWordAbbr struct {
    abbrDict map[string]bool
    dict     map[string]struct{}
}

func Constructor(dictionary []string) ValidWordAbbr {
    abbrDict := make(map[string]bool)
    dict := make(map[string]struct{})
    for _, word := range dictionary {
        dict[word] = struct{}{}
        abbr := toAbbr(word)
        abbrDict[abbr] = !abbrDict[abbr]
    }
    return ValidWordAbbr{abbrDict: abbrDict, dict: dict}
}

func (this *ValidWordAbbr) IsUnique(word string) bool {
    abbr := toAbbr(word)
    _, hasAbbr := this.abbrDict[abbr]
    _, inDict := this.dict[word]
    return !hasAbbr || (this.abbrDict[abbr] && inDict)
}

func toAbbr(word string) string {
    n := len(word)
    if n <= 2 {
        return word
    }
    return fmt.Sprintf("%c%d%c", word[0], n-2, word[n-1])
}

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

Задача: 137. Single Number II
Сложность: medium

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

Вы должны реализовать решение с линейной сложностью выполнения и использовать только постоянное дополнительное пространство.

Пример:

Input: nums = [2,2,3,2]
Output: 3

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

1⃣Сортировка массива:
Отсортируйте массив nums. Это упорядочит все элементы так, чтобы одинаковые числа находились рядом.

2⃣Итерация с проверкой:
Используйте цикл for для перебора элементов массива от начала до nums.size() - 2 с шагом 3. Таким образом, каждый проверяемый индекс будет иметь следующий за ним индекс в пределах массива.
Если элемент на текущем индексе совпадает с элементом на следующем индексе (проверка nums[i] == nums[i + 1]), продолжайте следующую итерацию цикла.

3⃣Возврат уникального элемента:
Если элемент на текущем индексе не совпадает с следующим, значит, это искомый уникальный элемент, который встречается только один раз. В этом случае возвращайте элемент на текущем индексе.
Если до последнего элемента цикл не нашёл уникального элемента, возвращайте последний элемент массива nums[nums.size() - 1], поскольку он, очевидно, будет уникальным, если предыдущие проверки не выявили уникального элемента раньше.

😎 Решение:

func singleNumber(nums []int) int {
    sort.Ints(nums)
    for i := 0; i < len(nums)-1; i += 3 {
        if nums[i] == nums[i+1] {
            continue
        } else {
            return nums[i]
        }
    }
    return nums[len(nums)-1]
}

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

Задача: 173. Binary Search Tree Iterator
Сложность: medium

Реализуйте класс BSTIterator, который представляет итератор по обходу бинарного дерева поиска (BST) в порядке in-order:

BSTIterator(TreeNode root): Инициализирует объект класса BSTIterator. Корень BST передается в качестве параметра конструктора. Указатель должен быть инициализирован на несуществующее число, меньшее любого элемента в BST.
boolean hasNext(): Возвращает true, если в обходе справа от указателя существует число, иначе возвращает false.
int next(): Перемещает указатель вправо, затем возвращает число на указателе.
Обратите внимание, что при инициализации указателя на несуществующее наименьшее число, первый вызов next() вернет наименьший элемент в BST.
Можно предположить, что вызовы next() всегда будут допустимы. То есть, при вызове next() в обходе всегда будет хотя бы одно следующее число.

Пример:

Input
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output
[null, 3, 7, true, 9, true, 15, true, 20, false]

Explanation
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // return 3
bSTIterator.next();    // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 20
bSTIterator.hasNext(); // return False

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

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

2⃣Мы обходим бинарное дерево поиска в порядке in-order и для каждого узла, который обрабатываем, добавляем его в наш массив узлов. Обратите внимание, что перед обработкой узла сначала нужно обработать (или рекурсивно вызвать) его левое поддерево, а после обработки узла — его правое поддерево.

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

😎 Решение:

package main

import "fmt"

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

type BSTIterator struct {
    nodesSorted []int
    index       int
}

func Constructor(root *TreeNode) BSTIterator {
    iterator := BSTIterator{nodesSorted: []int{}, index: -1}
    iterator.inorder(root)
    return iterator
}

func (this *BSTIterator) inorder(root *TreeNode) {
    if root == nil {
        return
    }
    this.inorder(root.Left)
    this.nodesSorted = append(this.nodesSorted, root.Val)
    this.inorder(root.Right)
}

func (this *BSTIterator) Next() int {
    this.index++
    return this.nodesSorted[this.index]
}

func (this *BSTIterator) HasNext() bool {
    return this.index+1 < len(this.nodesSorted)
}

func main() {
    root := &TreeNode{7, 
                &TreeNode{3, nil, nil}, 
                &TreeNode{15, 
                    &TreeNode{9, nil, nil}, 
                    &TreeNode{20, nil, nil}}}
    iterator := Constructor(root)
    fmt.Println(iterator.Next())  
    fmt.Println(iterator.HasNext()) 
    fmt.Println(iterator.Next())  
    fmt.Println(iterator.HasNext()) 
    fmt.Println(iterator.Next())   
    fmt.Println(iterator.HasNext()) 
    fmt.Println(iterator.Next()) 
    fmt.Println(iterator.HasNext()) 
    fmt.Println(iterator.Next())  
    fmt.Println(iterator.HasNext()) 
}

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

Задача: 928. Minimize Malware Spread II
Сложность: hard

Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом.

Пример:

Input: graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
Output: 0

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

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

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

3⃣Найти узел, удаление которого минимизирует количество зараженных узлов. Если несколько узлов минимизируют количество зараженных узлов одинаково, выбрать узел с наименьшим индексом.

😎 Решение:

package main

func minMalwareSpread(graph [][]int, initial []int) int {
    n := len(graph)
    visited := make(map[int]struct{})
    components := []map[int]struct{}{}

    var dfs func(int)
    dfs = func(node int) {
        stack := []int{node}
        component := make(map[int]struct{})
        for len(stack) > 0 {
            u := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            if _, ok := visited[u]; !ok {
                visited[u] = struct{}{}
                component[u] = struct{}{}
                for v := 0; v < n; v++ {
                    if graph[u][v] == 1 {
                        if _, ok := visited[v]; !ok {
                            stack = append(stack, v)
                        }
                    }
                }
            }
        }
        components = append(components, component)
    }

    for i := 0; i < n; i++ {
        if _, ok := visited[i]; !ok {
            dfs(i)
        }
    }

    infectedInComponent := make([]int, len(components))
    nodeToComponent := make([]int, n)

    for i := range nodeToComponent {
        nodeToComponent[i] = -1
    }

    for idx, component := range components {
        for node := range component {
            nodeToComponent[node] = idx
            for _, init := range initial {
                if node == init {
                    infectedInComponent[idx]++
                }
            }
        }
    }

    minInfected := int(^uint(0) >> 1)
    resultNode := initial[0]

    for _, node := range initial {
        componentIdx := nodeToComponent[node]
        if infectedInComponent[componentIdx] == 1 {
            componentSize := len(components[componentIdx])
            if componentSize < minInfected || (componentSize == minInfected && node < resultNode) {
                minInfected = componentSize
                resultNode = node
            }
        }
    }

    return resultNode
}

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

Задача: 1071. Greatest Common Divisor of Strings
Сложность: easy

Для двух строк s и t мы говорим, что "t делит s", если и только если s = t + t + t + ... + t (т.е. t соединена сама с собой один или более раз).

Даны две строки str1 и str2, верните наибольшую строку x, такую что x делит и str1, и str2.

Пример:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

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

1⃣Найдите более короткую строку среди str1 и str2, для простоты пусть это будет str1.

2⃣Начните с base = str1 и проверьте, состоят ли обе строки str1 и str2 из множителей строки base. Если это так, верните base. В противном случае, попробуйте более короткую строку, удалив последний символ из base.

3⃣Если вы проверили все префиксные строки и не нашли строку GCD, верните "".

😎 Решение:

func valid(str1, str2 string, k int) bool {
    len1, len2 := len(str1), len(str2)
    if len1 % k > 0 || len2 % k > 0 {
        return false
    } else {
        base := str1[:k]
        n1, n2 := len1 / k, len2 / k
        return str1 == joinWords(base, n1) && str2 == joinWords(base, n2)
    }
}

func joinWords(str string, k int) string {
    ans := ""
    for i := 0; i < k; i++ {
        ans += str
    }
    return ans
}

func gcdOfStrings(str1, str2 string) string {
    len1, len2 := len(str1), len(str2)
    for i := min(len1, len2); i >= 1; i-- {
        if valid(str1, str2, i) {
            return str1[:i]
        }
    }
    return ""
}

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

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

Задача: 530. Minimum Absolute Difference in BST
Сложность: easy

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

Пример:

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

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

1⃣ Обход дерева в порядке возрастания (инфиксный обход):
Создайте список inorderNodes для хранения значений узлов.
Выполните инфиксный обход дерева, добавляя значения узлов в список.

2⃣ Нахождение минимальной разницы:
Создайте переменную minDifference и инициализируйте её бесконечностью.
Пройдите по списку inorderNodes, начиная с индекса 1, и найдите минимальную абсолютную разницу между последовательными элементами.

3⃣ Возврат результата:
Верните minDifference.

😎 Решение:

import (
    "math"
)

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

type Solution struct {
    inorderNodes []int
}

func (s *Solution) getMinimumDifference(root *TreeNode) int {
    s.inorderNodes = []int{}
    s.inorderTraversal(root)
    minDifference := math.MaxInt32
    for i := 1; i < len(s.inorderNodes); i++ {
        minDifference = min(minDifference, s.inorderNodes[i]-s.inorderNodes[i-1])
    }
    return minDifference
}

func (s *Solution) inorderTraversal(node *TreeNode) {
    if node == nil {
        return
    }
    s.inorderTraversal(node.Left)
    s.inorderNodes = append(s.inorderNodes, node.Val)
    s.inorderTraversal(node.Right)
}

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

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

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

Запутанное число - это число, которое при повороте на 180 градусов становится другим числом, каждая цифра которого действительна. Мы можем повернуть цифры числа на 180 градусов, чтобы получить новые цифры. Когда 0, 1, 6, 8 и 9 поворачиваются на 180 градусов, они становятся 0, 1, 9, 8 и 6 соответственно.
При повороте на 180 градусов 2, 3, 4, 5 и 7 становятся недействительными. Обратите внимание, что после поворота числа мы можем игнорировать ведущие нули. Например, после поворота 8000 мы получим 0008, которое считается просто 8. Если задано целое число n, верните true, если это запутанное число, или false в противном случае.

Пример:

Input: n = 6
Output: true

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

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

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

3⃣Проверь, что перевернутая строка отличается от исходной.

😎 Решение:

package main

import (
    "strconv"
)

func isConfusingNumber(n int) bool {
    rotationMap := map[rune]rune{'0': '0', '1': '1', '6': '9', '8': '8', '9': '6'}
    nStr := strconv.Itoa(n)
    rotatedStr := ""

    for _, ch := range nStr {
        if _, exists := rotationMap[ch]; !exists {
            return false
        }
        rotatedStr = string(rotationMap[ch]) + rotatedStr
    }

    return rotatedStr != nStr
}

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

Задача: 1522. Diameter of N-Ary Tree
Сложность: medium

Дано N-арное дерево, нужно найти диаметр — длину самого длинного пути между двумя узлами дерева (не обязательно проходящего через корень).

Пример:

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

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

1⃣Рекурсивная функция высоты
Реализуем height(node) — возвращает максимальную высоту поддерева. Для листа это 0. Для внутреннего узла — 1 + макс(высота дочернего).

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

3⃣Обновление диаметра
Если сумма двух наибольших высот больше текущего значения s.diameter, обновляем его.

😎 Решение:

type Node struct {
    Val      int
    Children []*Node
}

type Solution struct {
    diameter int
}

func (s *Solution) height(node *Node) int {
    if len(node.Children) == 0 {
        return 0
    }

    maxHeight1, maxHeight2 := 0, 0

    for _, child := range node.Children {
        h := s.height(child) + 1
        if h > maxHeight1 {
            maxHeight2 = maxHeight1
            maxHeight1 = h
        } else if h > maxHeight2 {
            maxHeight2 = h
        }

        if maxHeight1+maxHeight2 > s.diameter {
            s.diameter = maxHeight1 + maxHeight2
        }
    }

    return maxHeight1
}

func (s *Solution) Diameter(root *Node) int {
    s.diameter = 0
    s.height(root)
    return s.diameter
}

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

Задача: 723. Candy Crush
Сложность: medium

Этот вопрос касается реализации базового алгоритма исключения для Candy Crush. Дан целочисленный массив board размером m x n, представляющий сетку конфет, где board[i][j] представляет тип конфеты. Значение board[i][j] == 0 означает, что ячейка пуста. Данная доска представляет собой состояние игры после хода игрока. Теперь необходимо вернуть доску в стабильное состояние, раздавив конфеты по следующим правилам: если три или более конфет одного типа находятся рядом по вертикали или горизонтали, раздавите их все одновременно - эти позиции станут пустыми. После одновременного раздавливания всех конфет, если на пустом месте доски есть конфеты, расположенные сверху, то эти конфеты будут падать, пока не ударятся о конфету или дно одновременно. Новые конфеты не будут падать за верхнюю границу. После выполнения описанных выше действий может остаться больше конфет, которые можно раздавить. Если конфет, которые можно раздавить, больше не существует (т. е. доска стабильна), верните текущую доску. Выполняйте описанные выше правила, пока доска не станет стабильной, затем верните стабильную доску.

Пример:

Input: board = [[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]]
Output: [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[110,0,0,0,114],[210,0,0,0,214],[310,0,0,113,314],[410,0,0,213,414],[610,211,112,313,614],[710,311,412,613,714],[810,411,512,713,1014]]

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

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

2⃣Удалите отмеченные конфеты, установив их значение в 0.

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

😎 Решение:

package main

func candyCrush(board [][]int) [][]int {
    m := len(board)
    n := len(board[0])
    stable := false

    for !stable {
        stable = true
        crush := make([][]bool, m)
        for i := range crush {
            crush[i] = make([]bool, n)
        }

        for i := 0; i < m; i++ {
            for j := 0; j < n-2; j++ {
                if abs(board[i][j]) == abs(board[i][j+1]) && abs(board[i][j+1]) == abs(board[i][j+2]) && board[i][j] != 0 {
                    stable = false
                    crush[i][j] = true
                    crush[i][j+1] = true
                    crush[i][j+2] = true
                }
            }
        }

        for i := 0; i < m-2; i++ {
            for j := 0; j < n; j++ {
                if abs(board[i][j]) == abs(board[i+1][j]) && abs(board[i+1][j]) == abs(board[i+2][j]) && board[i][j] != 0 {
                    stable = false
                    crush[i][j] = true
                    crush[i+1][j] = true
                    crush[i+2][j] = true
                }
            }
        }

        for i := 0; i < m; i++ {
            for j := 0; j < n; j++ {
                if crush[i][j] {
                    board[i][j] = 0
                }
            }
        }

        for j := 0; j < n; j++ {
            idx := m - 1
            for i := m - 1; i >= 0; i-- {
                if board[i][j] != 0 {
                    board[idx][j] = board[i][j]
                    idx--
                }
            }
            for i := idx; i >= 0; i-- {
                board[i][j] = 0
            }
        }
    }

    return board
}

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

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

Задача: 1180. Count Substrings with Only One Distinct Letter
Сложность: easy

Дана строка s. Верните количество подстрок, которые содержат только одну уникальную букву.

Пример:

Input: s = "aaaba"
Output: 8
Explanation: The substrings with one distinct letter are "aaa", "aa", "a", "b".
"aaa" occurs 1 time.
"aa" occurs 2 times.
"a" occurs 4 times.
"b" occurs 1 time.
So the answer is 1 + 2 + 4 + 1 = 8.

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

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

2⃣Итерируйте по строке S: Если мы не достигли конца и новый символ S[right] такой же, как и начальный символ S[left], увеличьте right на 1 для дальнейшего исследования строки S; в противном случае вычислите длину подстроки как right - left и примените формулу суммы арифметической последовательности; не забудьте установить right в left для начала исследования новой подстроки.

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

😎 Решение

func countLetters(S string) int {
    total := 0
    left := 0

    for right := 0; right <= len(S); right++ {
        if right == len(S) || S[left] != S[right] {
            lenSubstring := right - left
            total += (1 + lenSubstring) * lenSubstring / 2
            left = right
        }
    }

    return total
}

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