Задача: 733. Flood Fill
Сложность: easy

Изображение представлено в виде целочисленной сетки m x n, где image[i][j] - значение пикселя изображения. Вам также даны три целых числа sr, sc и color. Вы должны выполнить заливку изображения, начиная с пикселя image[sr][sc]. Чтобы выполнить заливку, рассмотрите начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с начальным пикселем, того же цвета, что и начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с этими пикселями (также того же цвета), и так далее. Замените цвет всех вышеупомянутых пикселей на цвет. Верните измененное изображение после выполнения заливки.

Пример:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

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

1⃣Получите цвет начального пикселя.

2⃣Используйте обход в глубину (DFS) или обход в ширину (BFS) для замены цвета всех пикселей, которые соединены с начальным пикселем и имеют тот же цвет.

3⃣Обновите изображение и верните его.

😎 Решение:

package main

func floodFill(image [][]int, sr int, sc int, color int) [][]int {
    originalColor := image[sr][sc]
    if originalColor == color {
        return image
    }

    var dfs func(x, y int)
    dfs = func(x, y int) {
        if x < 0 || x >= len(image) || y < 0 || y >= len(image[0]) || image[x][y] != originalColor {
            return
        }
        image[x][y] = color
        dfs(x+1, y)
        dfs(x-1, y)
        dfs(x, y+1)
        dfs(x, y-1)
    }

    dfs(sr, sc)
    return image
}

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

Задача: 528. Random Pick with Weight
Сложность: medium

Вам дан массив положительных целых чисел w, где w[i] описывает вес индекса i.
Вам нужно реализовать функцию pickIndex(), которая случайным образом выбирает индекс в диапазоне [0, w.length - 1] (включительно) и возвращает его. Вероятность выбора индекса i равна w[i] / sum(w).

Например, если w = [1, 3], вероятность выбора индекса 0 составляет 1 / (1 + 3) = 0.25 (т.е. 25%), а вероятность выбора индекса 1 составляет 3 / (1 + 3) = 0.75 (т.е. 75%).

Пример:

Input
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]

Explanation
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.

Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
and so on.

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

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

2⃣ Генерация случайного числа и выбор индекса:
В функции pickIndex() сгенерируйте случайное число в диапазоне от 0 до общей суммы весов totalSum.
Используйте линейный поиск, чтобы найти первый индекс в prefixSums, который больше или равен сгенерированному числу.

3⃣ Возврат результата:
Верните найденный индекс.

😎 Решение:

import (
    "math/rand"
    "time"
)

type Solution struct {
    prefixSums []int
    totalSum   int
}

func Constructor(w []int) Solution {
    prefixSums := make([]int, len(w))
    prefixSum := 0
    for i, weight := range w {
        prefixSum += weight
        prefixSums[i] = prefixSum
    }
    return Solution{prefixSums, prefixSum}
}

func (this *Solution) PickIndex() int {
    rand.Seed(time.Now().UnixNano())
    target := float64(this.totalSum) * rand.Float64()
    for i, prefixSum := range this.prefixSums {
        if target < float64(prefixSum) {
            return i
        }
    }
    return len(this.prefixSums) - 1
}

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

Задача: 644. Maximum Average Subarray II
Сложность: hard

Вам дан целочисленный массив nums, состоящий из n элементов, и целое число k. Найдите смежный подмассив, длина которого больше или равна k и который имеет максимальное среднее значение, и верните это значение. Принимается любой ответ с погрешностью вычислений менее 10-5.

Пример:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000

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

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

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

3⃣Следите за максимальным средним значением и верните его после проверки всех возможных окон.

😎 Решение:

func findMaxAverage(nums []int, k int) float64 {
    n := len(nums)
    currSum := 0
    for i := 0; i < k; i++ {
        currSum += nums[i]
    }
    maxSum := currSum
    for i := k; i < n; i++ {
        currSum += nums[i] - nums[i - k]
        if currSum > maxSum {
            maxSum = currSum
        }
    }
    return float64(maxSum) / float64(k)
}

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

Задача: 747. Largest Number At Least Twice of Others
Сложность: easy

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

Пример:

Input: nums = [3,6,1,0]
Output: 1

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

1⃣Найдите максимальный элемент в массиве и его индекс.

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

3⃣Если условие выполняется, верните индекс максимального элемента, иначе верните -1.

😎 Решение:

package main

func minCostClimbingStairs(cost []int) int {
    n := len(cost)
    dp := make([]int, n)
    copy(dp, cost)
    for i := 2; i < n; i++ {
        dp[i] += min(dp[i-1], dp[i-2])
    }
    return min(dp[n-1], dp[n-2])
}

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

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

Задача: 542. 01 Matrix
Сложность: medium

Дана бинарная матрица размера m x n, верните расстояние до ближайшего нуля для каждой ячейки.
Расстояние между двумя соседними ячейками равно 1.

Пример:

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

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

1⃣Создайте копию матрицы mat, назовем её matrix. Используйте структуру данных seen для пометки уже посещенных узлов и очередь для выполнения BFS. Поместите все узлы с 0 в очередь и отметьте их в seen.

2⃣Выполните BFS:
Пока очередь не пуста, извлекайте текущие row, col, steps из очереди.
Итеративно пройдите по четырем направлениям. Для каждой nextRow, nextCol проверьте, находятся ли они в пределах границ и не были ли они уже посещены в seen.

3⃣Если так, установите matrix[nextRow][nextCol] = steps + 1 и поместите nextRow, nextCol, steps + 1 в очередь. Также отметьте nextRow, nextCol в seen. Верните matrix.

😎 Решение:

package main

import (
    "container/list"
)

type Solution struct {
    m, n      int
    directions [4][2]int
}

func Constructor() Solution {
    return Solution{
        directions: [4][2]int{
            {0, 1},
            {1, 0},
            {0, -1},
            {-1, 0},
        },
    }
}

func (s *Solution) updateMatrix(mat [][]int) [][]int {
    s.m = len(mat)
    s.n = len(mat[0])
    matrix := make([][]int, s.m)
    seen := make([][]bool, s.m)
    queue := list.New()

    for i := 0; i < s.m; i++ {
        matrix[i] = make([]int, s.n)
        seen[i] = make([]bool, s.n)
        for j := 0; j < s.n; j++ {
            matrix[i][j] = mat[i][j]
            if matrix[i][j] == 0 {
                queue.PushBack([3]int{i, j, 0})
                seen[i][j] = true
            }
        }
    }

    for queue.Len() > 0 {
        curr := queue.Remove(queue.Front()).([3]int)
        row, col, steps := curr[0], curr[1], curr[2]

        for _, direction := range s.directions {
            nextRow, nextCol := row+direction[0], col+direction[1]
            if s.isValid(nextRow, nextCol) && !seen[nextRow][nextCol] {
                seen[nextRow][nextCol] = true
                queue.PushBack([3]int{nextRow, nextCol, steps + 1})
                matrix[nextRow][nextCol] = steps + 1
            }
        }
    }

    return matrix
}

func (s *Solution) isValid(row, col int) bool {
    return 0 <= row && row < s.m && 0 <= col && col < s.n
}

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

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

Дан массив nums, содержащий n различных чисел в диапазоне [0, n]. Верните единственное число в этом диапазоне, которого нет в массиве.

Пример:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

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

1⃣Сначала отсортируйте массив nums.

2⃣Проверьте особые случаи: убедитесь, что число 0 находится в начале массива, а число n — в конце.

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

😎 Решение:

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

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

Задача: 147. Insertion Sort List
Сложность: medium

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

Шаги алгоритма сортировки вставками:

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

Пример:

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

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

1⃣Создание вспомогательного узла (pseudo_head):
В качестве первого шага создайте вспомогательный узел, который называется pseudo_head. Этот узел будет использоваться как указатель на начало результирующего списка. Этот узел облегчает доступ к результирующему списку, особенно когда необходимо вставить новый элемент в начало списка. Этот прием значительно упрощает логику работы с односвязным списком.

2⃣Механизм вставки узла:
В односвязном списке каждый узел содержит только один указатель, который указывает на следующий узел. Чтобы вставить новый узел (например, B) перед определенным узлом (например, A), необходимо знать узел (например, C), который находится перед узлом A (т.е. C -> A). Имея ссылку на узел C, можно вставить новый узел так, чтобы получилось C -> B -> A.

3⃣Использование пары указателей для вставки:
Используя пару указателей (prev и next), которые служат местом для вставки нового элемента между ними, вставьте новый элемент в список. Это делается путем установки prev -> new_node -> next. Этот метод позволяет точно и безопасно вставлять новые элементы в список, сохраняя при этом правильный порядок элементов без необходимости перемещения других узлов списка.

😎 Решение:

func insertionSortList(head *ListNode) *ListNode {
    dummy := &ListNode{}
    curr := head
    for curr != nil {
        prev := dummy
        for prev.Next != nil && prev.Next.Val <= curr.Val {
            prev = prev.Next
        }
        next := curr.Next
        curr.Next = prev.Next
        prev.Next = curr
        curr = next
    }
    return dummy.Next
}

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

Задача: 659. Split Array into Consecutive Subsequences
Сложность: medium

Вам дан отсортированный в неубывающем порядке массив целых чисел nums.

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

Каждая подпоследовательность является последовательностью последовательных возрастающих чисел (то есть каждое целое число на 1 больше предыдущего).
Все подпоследовательности имеют длину 3 или более.
Верните true, если можно разделить nums согласно вышеуказанным условиям, или false в противном случае.

Подпоследовательность массива — это новый массив, который формируется из исходного массива путем удаления некоторых (может быть, ни одного) элементов без нарушения относительных позиций оставшихся элементов. (например, [1,3,5] является подпоследовательностью [1,2,3,4,5], тогда как [1,3,2] не является).

Пример:

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

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

1⃣Подсчет частоты элементов:
Создайте хеш-таблицу для подсчета количества вхождений каждого элемента в массиве nums.

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

3⃣Проверка результата:
Верните true, если все элементы успешно распределены по подпоследовательностям.

😎 Решение:

func isPossible(nums []int) bool {
    freq := make(map[int]int)
    need := make(map[int]int)
    
    for _, num := range nums {
        freq[num]++
    }
    
    for _, num := range nums {
        if freq[num] == 0 {
            continue
        }
        if need[num] > 0 {
            need[num]--
            need[num+1]++
        } else if freq[num+1] > 0 && freq[num+2] > 0 {
            freq[num+1]--
            freq[num+2]--
            need[num+3]++
        } else {
            return false
        }
        freq[num]--
    }
    
    return true
}

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

Задача: 684. Redundant Connection
Сложность: medium

В этой задаче дерево — это неориентированный граф, который является связным и не содержит циклов.

Вам дан граф, который изначально был деревом с n узлами, пронумерованными от 1 до n, и к которому добавили одно дополнительное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее. Граф представлен массивом edges длины n, где edges[i] = [ai, bi] указывает на то, что существует ребро между узлами ai и bi в графе.

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

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

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

1⃣Для каждого ребра (u, v) создайте представление графа с использованием списка смежности. Это позволит легко выполнять обход в глубину (DFS) для проверки соединений между узлами.

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

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

😎 Решение:

package main

func findRedundantConnection(edges [][]int) []int {
    const MAX_EDGE_VAL = 1000
    graph := make([][]int, MAX_EDGE_VAL+1)
    for i := range graph {
        graph[i] = make([]int, 0)
    }
    seen := make(map[int]bool)

    var dfs func(source, target int) bool
    dfs = func(source, target int) bool {
        if !seen[source] {
            seen[source] = true
            if source == target {
                return true
            }
            for _, nei := range graph[source] {
                if dfs(nei, target) {
                    return true
                }
            }
        }
        return false
    }

    for _, edge := range edges {
        seen = make(map[int]bool)
        if len(graph[edge[0]]) > 0 && len(graph[edge[1]]) > 0 && dfs(edge[0], edge[1]) {
            return edge
        }
        graph[edge[0]] = append(graph[edge[0]], edge[1])
        graph[edge[1]] = append(graph[edge[1]], edge[0])
    }
    return nil
}

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

Задача: 107. Binary Tree Level Order Traversal II
Сложность: medium

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

Пример:

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

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

1⃣Инициализируйте список вывода levels. Длина этого списка определяет, какой уровень в данный момент обновляется. Вам следует сравнить этот уровень len(levels) с уровнем узла level, чтобы убедиться, что вы добавляете узел на правильный уровень. Если вы все еще находитесь на предыдущем уровне, добавьте новый уровень, вставив новый список в levels.

2⃣Добавьте значение узла в последний уровень в levels.

3⃣Рекурсивно обработайте дочерние узлы, если они не равны None, используя функцию helper(node.left / node.right, level + 1).

😎 Решение:

func levelOrderBottom(root *TreeNode) [][]int {
    levels := make([][]int, 0)
    var helper func(node *TreeNode, level int)
    helper = func(node *TreeNode, level int) {
        if node == nil {
            return
        }
        if len(levels) == level {
            levels = append(levels, []int{})
        }
        levels[level] = append(levels[level], node.Val)
        if node.Left != nil {
            helper(node.Left, level+1)
        }
        if node.Right != nil {
            helper(node.Right, level+1)
        }
    }
    helper(root, 0)
    for i := 0; i < len(levels)/2; i++ {
        levels[i], levels[len(levels)-1-i] = levels[len(levels)-1-i], levels[i]
    }
    return levels
}

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

Задача: 168. Excel Sheet Column Title
Сложность: easy

Дано целое число columnNumber, верните соответствующий заголовок столбца, как он отображается в таблице Excel.

Например:
A -> 1
B -> 2
C -> 3
Z -> 26
AA -> 27
AB -> 28

Пример:

Input: columnNumber = 1  
Output: "A"  

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

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

2⃣Циклическое преобразование числа в буквы:
Пока columnNumber больше 0, выполняйте следующие действия:
- Вычтите 1 из columnNumber для корректировки индекса (Excel использует 1-индексацию).
- Найдите символ, соответствующий остатку от деления columnNumber на 26, и добавьте его в начало строки ans.
- Присвойте columnNumber значение от деления columnNumber на 26.

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

😎 Решение:

func convertToTitle(columnNumber int) string {
    ans := ""
    for columnNumber > 0 {
        columnNumber = columnNumber - 1
        ans = string(rune((columnNumber)%26+'A')) + ans
        columnNumber = (columnNumber) / 26
    }
    return ans
}

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

Задача: 291. Word Pattern II
Сложность: medium

Дан шаблон и строка s, вернуть true, если строка s соответствует шаблону.

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

Пример:

Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"

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

1⃣Инициализация структур данных и определение рекурсивной функции:
Создайте хеш-таблицу symbolMap для отображения символов шаблона на подстроки строки s.
Создайте множество wordSet для хранения уникальных подстрок строки s, которые были отображены на символ.
Определите рекурсивную функцию isMatch, принимающую индексы в строке s (sIndex) и в шаблоне (pIndex), чтобы определить, соответствует ли строка s шаблону.

2⃣Рекурсивная проверка соответствия:
Базовый случай: если pIndex равно длине шаблона, верните true, если sIndex равно длине строки s; иначе верните false.
Получите символ из шаблона по индексу pIndex.
Если символ уже ассоциирован с подстрокой, проверьте, совпадают ли следующие символы в строке s с этой подстрокой. Если нет, верните false. Если совпадают, вызовите isMatch для следующего символа в шаблоне.

3⃣Отображение новых подстрок:
Если символ новый, попробуйте сопоставить его с новыми подстроками строки s, начиная с sIndex и до конца строки.
Для каждой новой подстроки проверьте, существует ли она уже в `

😎 Решение:

package main

func wordPatternMatch(pattern string, s string) bool {
    symbolMap := make(map[rune]string)
    wordSet := make(map[string]bool)
    return isMatch(s, 0, pattern, 0, symbolMap, wordSet)
}

func isMatch(s string, sIndex int, pattern string, pIndex int,
    symbolMap map[rune]string, wordSet map[string]bool) bool {
    if pIndex == len(pattern) {
        return sIndex == len(s)
    }
    symbol := rune(pattern[pIndex])
    if word, ok := symbolMap[symbol]; ok {
        if !startsWith(s, sIndex, word) {
            return false
        }
        return isMatch(s, sIndex+len(word), pattern, pIndex+1, symbolMap, wordSet)
    }
    for k := sIndex + 1; k <= len(s); k++ {
        newWord := s[sIndex:k]
        if wordSet[newWord] {
            continue
        }
        symbolMap[symbol] = newWord
        wordSet[newWord] = true
        if isMatch(s, k, pattern, pIndex+1, symbolMap, wordSet) {
            return true
        }
        delete(symbolMap, symbol)
        delete(wordSet, newWord)
    }
    return false
}

func startsWith(s string, sIndex int, word string) bool {
    if len(s)-sIndex < len(word) {
        return false
    }
    for i := 0; i < len(word); i++ {
        if s[sIndex+i] != word[i] {
            return false
        }
    }
    return true
}

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

Задача: 1249. Minimum Remove to Make Valid Parentheses
Сложность: medium

Дана строка s из '(' , ')' и строчных английских символов. Ваша задача - удалить минимальное количество скобок ( '(' или ')' в любых позициях), чтобы полученная строка со скобками была допустимой, и вернуть любую допустимую строку. Формально строка со скобками допустима тогда и только тогда, когда: она пустая, содержит только строчные символы, или может быть записана как AB (A, конкатенированная с B), где A и B - допустимые строки, или может быть записана как (A), где A - допустимая строка.

Пример:
Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"

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

1⃣Пройдите по строке s и сохраните индексы всех открывающих скобок '(' в стек. При встрече закрывающей скобки ')', удалите соответствующую открытую скобку из стека. Если в стеке нет соответствующей открывающей скобки, пометьте эту закрывающую скобку для удаления.

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

3⃣Создайте новую строку, удалив все помеченные скобки.

😎 Решение:

func minRemoveToMakeValid(s string) string {
    stack := []int{}
    res := []byte(s)
    for i := 0; i < len(res); i++ {
        if res[i] == '(' {
            stack = append(stack, i)
        } else if res[i] == ')' {
            if len(stack) > 0 {
                stack = stack[:len(stack)-1]
            } else {
                res[i] = '*'
            }
        }
    }
    for len(stack) > 0 {
        res[stack[len(stack)-1]] = '*'
        stack = stack[:len(stack)-1]
    }
    return strings.ReplaceAll(string(res), "*", "")
}

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

Задача: 270. Closest Binary Search Tree Value
Сложность: easy

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

Пример:

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

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

1⃣Построить массив с помощью inorder обхода:
Выполнить inorder обход дерева и собрать элементы в отсортированный массив.

2⃣Найти ближайший элемент:
Пройти по массиву и определить элемент, наиболее близкий к целевому значению.

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

😎 Решение:

package main

import "math"

func closestValue(root *TreeNode, target float64) int {
    closest := root.Val
    for root != nil {
        if math.Abs(float64(root.Val)-target) < math.Abs(float64(closest)-target) {
            closest = root.Val
        } else if math.Abs(float64(root.Val)-target) == math.Abs(float64(closest)-target) {
            if root.Val < closest {
                closest = root.Val
            }
        }
        if target < float64(root.Val) {
            root = root.Left
        } else {
            root = root.Right
        }
    }
    return closest
}

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

Задача: 101. Symmetric Tree
Сложность: easy

Дан корень бинарного дерева. Проверьте, является ли это дерево зеркальным отражением самого себя (то есть симметричным относительно своего центра).

Пример:

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

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

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

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

3️⃣Проверку удобно реализовать через рекурсивную функцию, сравнивающую два поддерева на симметричность.

😎 Решение:

func isSymmetric(root *TreeNode) bool {
    return isMirror(root, root)
}

func isMirror(t1 *TreeNode, t2 *TreeNode) bool {
    if t1 == nil && t2 == nil {
        return true
    }
    if t1 == nil || t2 == nil {
        return false
    }
    return (t1.Val == t2.Val) && 
           isMirror(t1.Right, t2.Left) &&
           isMirror(t1.Left, t2.Right)
}

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

Задача: 85. Maximal Rectangle
Сложность: hard

Дана бинарная матрица размером rows x cols, заполненная 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: 6
Explanation: The maximal rectangle is shown in the above picture.

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

1⃣Вычисление максимальной ширины прямоугольника для каждой координаты: Для каждой ячейки в каждой строке сохраняем количество последовательных единиц. При прохождении по строке обновляем максимально возможную ширину в этой точке, используя формулу row[i] = row[i - 1] + 1, если row[i] == '1'.

2⃣Определение максимальной площади прямоугольника с нижним правым углом в данной точке: При итерации вверх по столбцу максимальная ширина прямоугольника от исходной точки до текущей точки является минимальным значением среди всех максимальных ширин, с которыми мы сталкивались. Используем формулу maxWidth = min(maxWidth, widthHere) и curArea = maxWidth * (currentRow - originalRow + 1), затем обновляем maxArea = max(maxArea, curArea).

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

😎 Решение:

func maximalRectangle(matrix [][]byte) int {
    if len(matrix) == 0 {
        return 0
    }
    maxarea := 0
    dp := make([][]int, len(matrix))
    for i := range dp {
        dp[i] = make([]int, len(matrix[0]))
    }
    for i := 0; i < len(matrix); i++ {
        for j := 0; j < len(matrix[0]); j++ {
            if matrix[i][j] == '1' {
                dp[i][j] = 1
                if j != 0 {
                    dp[i][j] += dp[i][j-1]
                }
                width := dp[i][j]
                for k := i; k >= 0; k-- {
                    width = min(width, dp[k][j])
                    maxarea = max(maxarea, width*(i-k+1))
                }
            }
        }
    }
    return maxarea
}

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

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

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

Задача: 681. Next Closest Time
Сложность: medium

Дано время, представленное в формате "ЧЧ:ММ". Сформируйте ближайшее следующее время, используя текущие цифры. Количество раз, которое можно использовать цифру, не ограничено.

Можно предположить, что заданная строка всегда корректна. Например, "01:34", "12:09" являются корректными. "1:34", "12:9" являются некорректными.

Пример:

Input: time = "19:34"
Output: "19:39"
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later.
It is not 19:33, because this occurs 23 hours and 59 minutes later.

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

1⃣Симулируйте ход часов, увеличивая время на одну минуту. Каждый раз, когда время увеличивается, если все цифры допустимы, верните текущее время.

2⃣Представьте время как целое число t в диапазоне 0 <= t < 24 * 60. Тогда часы равны t / 60, минуты равны t % 60.

3⃣Найдите каждую цифру часов и минут: часы / 10, часы % 10 и т.д.

😎 Решение:

package main

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

func nextClosestTime(time string) string {
    cur := 60*atoi(time[:2]) + atoi(time[3:])
    allowed := make(map[int]bool)
    for _, c := range time {
        if c != ':' {
            allowed[int(c-'0')] = true
        }
    }

    for {
        cur = (cur + 1) % (24 * 60)
        digits := []int{cur / 60 / 10, cur / 60 % 10, cur % 60 / 10, cur % 60 % 10}
        valid := true
        for _, d := range digits {
            if !allowed[d] {
                valid = false
                break
            }
        }
        if valid {
            return fmt.Sprintf("%02d:%02d", cur/60, cur%60)
        }
    }
}

func atoi(s string) int {
    i, _ := strconv.Atoi(s)
    return i
}

func main() {
    fmt.Println(nextClosestTime("19:34"))
}

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

Задача: 1533. Find the Index of the Large Integer
Сложность: medium

У нас есть целочисленный массив arr, в котором все элементы равны, кроме одного элемента, который больше остальных. Вам не будет предоставлен прямой доступ к массиву, вместо этого у вас будет API ArrayReader, который имеет следующие функции:

int compareSub(int l, int r, int x, int y): где 0 <= l, r, x, y < ArrayReader.length(), l <= r и x <= y. Функция сравнивает сумму подмассива arr[l..r] с суммой подмассива arr[x..y] и возвращает:
1, если arr[l] + arr[l+1] + ... + arr[r] > arr[x] + arr[x+1] + ... + arr[y].
0, если arr[l] + arr[l+1] + ... + arr[r] == arr[x] + arr[x+1] + ... + arr[y].
-1, если arr[l] + arr[l+1] + ... + arr[r] < arr[x] + arr[x+1] + ... + arr[y].

int length(): Возвращает размер массива.

Вам разрешено вызывать compareSub() не более 20 раз. Вы можете предположить, что обе функции работают за O(1) время.

Верните индекс массива arr, который содержит наибольший элемент.

Пример:

Input: arr = [7,7,7,7,10,7,7,7]
Output: 4
Explanation: The following calls to the API
reader.compareSub(0, 0, 1, 1) // returns 0 this is a query comparing the sub-array (0, 0) with the sub array (1, 1), (i.e. compares arr[0] with arr[1]).
Thus we know that arr[0] and arr[1] doesn't contain the largest element.
reader.compareSub(2, 2, 3, 3) // returns 0, we can exclude arr[2] and arr[3].
reader.compareSub(4, 4, 5, 5) // returns 1, thus for sure arr[4] is the largest element in the array.
Notice that we made only 3 calls, so the answer is valid.

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

1⃣Установите left = 0 и length = reader.length. left - это самый левый индекс нашего поискового пространства, а length - это размер нашего поискового пространства. Индекс большего числа всегда должен находиться в пределах [left, left + length).

2⃣Пока length > 1:
— Обновите length до length / 2.
— Установите cmp равным reader.compareSub(left, left + length - 1, left + length, left + length + length - 1).
— Если cmp равно 0, верните left + length + length, так как оставшийся элемент является большим числом. Это возможно только если текущее поисковое пространство имеет нечетную длину, поэтому если у нас четная длина, мы не беспокоимся об этом случае.
— Если cmp равно -1, увеличьте left на length.
— Если cmp равно 1, ничего не делайте, так как наш left остается прежним и мы уже разделили length на 2.

3⃣Верните left. Это стандартная процедура для бинарного поиска, когда если поиск завершается без возврата, то левая граница указывает на ответ.

😎 Решение

type ArrayReader struct{}

func (ar *ArrayReader) CompareSub(l, r, x, y int) int {
    return 0
}

func (ar *ArrayReader) Length() int {
    return 0
}

type Solution struct{}

func (s *Solution) GetIndex(reader *ArrayReader) int {
    left := 0
    length := reader.Length()
    for length > 1 {
        length /= 2
        cmp := reader.CompareSub(left, left+length-1, left+length, left+2*length-1)
        if cmp == 0 {
            return left + 2*length
        }
        if cmp < 0 {
            left += length
        }
    }
    return left
}

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

Задача: 971. Flip Binary Tree To Match Preorder Traversal
Сложность: medium

Дано корневое дерево с n узлами, где каждому узлу уникально присвоено значение от 1 до n. Также дана последовательность из n значений voyage, которая является желаемым обходом дерева в порядке pre-order.

Любой узел в бинарном дереве можно перевернуть, поменяв местами его левое и правое поддеревья. Например, переворот узла 1 будет иметь следующий эффект:

Переверните минимальное количество узлов, чтобы обход дерева в порядке pre-order соответствовал voyage.

Верните список значений всех перевернутых узлов. Вы можете вернуть ответ в любом порядке. Если невозможно перевернуть узлы в дереве, чтобы сделать обход в порядке pre-order соответствующим voyage, верните список [-1].

Пример:

Input: root = [1,2], voyage = [2,1]
Output: [-1]
Explanation: It is impossible to flip the nodes such that the pre-order traversal matches voyage.

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

1⃣Выполните поиск в глубину. Если в каком-либо узле значение узла не соответствует значению в voyage, верните [-1].

2⃣Иначе определите, когда нужно перевернуть: если следующее ожидаемое число в voyage (voyage[i]) отличается от следующего потомка.

3⃣Переверните узел, добавьте его значение в список перевернутых узлов и продолжите обход дерева, пока весь порядок обхода pre-order не будет соответствовать voyage.

😎 Решение:

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

type Solution struct {
    flipped []int
    index   int
    voyage  []int
}

func (s *Solution) flipMatchVoyage(root *TreeNode, voyage []int) []int {
    s.flipped = []int{}
    s.index = 0
    s.voyage =

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

Задача: 277. Find the Celebrity
Сложность: medium

Предположим, вы находитесь на вечеринке с n людьми, обозначенными от 0 до n - 1, и среди них может быть один знаменитость. Определение знаменитости: все остальные n - 1 человек знают знаменитость, но знаменитость не знает никого из них.
Теперь вы хотите выяснить, кто является знаменитостью, или убедиться, что ее нет. Вам разрешено задавать вопросы типа: "Привет, A. Ты знаешь B?", чтобы получить информацию о том, знает ли A B. Вам нужно найти знаменитость (или убедиться, что ее нет), задав как можно меньше вопросов (в асимптотическом смысле).
Вам предоставлена вспомогательная функция bool knows(a, b), которая сообщает, знает ли a b. Реализуйте функцию int findCelebrity(n). На вечеринке будет ровно одна знаменитость, если она есть.
Верните метку знаменитости, если она есть на вечеринке. Если знаменитости нет, верните -1.

Пример:

Input: graph = [[1,1,0],[0,1,0],[1,1,1]]
Output: 1
Explanation: There are three persons labeled with 0, 1 and 2. graph[i][j] = 1 means person i knows person j, otherwise graph[i][j] = 0 means person i does not know person j. The celebrity is the person labeled as 1 because both 0 and 2 know him but 1 does not know anybody.

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

1⃣Найти потенциального кандидата на знаменитость:
Использовать один проход через всех людей, чтобы определить возможного кандидата.
Если человек a знает человека b, то a не может быть знаменитостью, и переключаем кандидата на b.

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

3⃣Возвращение результата:
Если кандидат проходит все проверки в isCelebrity(candidate), вернуть его метку.
В противном случае вернуть -1.

😎 Решение:

type Solution struct {
    n     int
    cache map[pair]bool
}

type pair struct {
    a, b int
}

func (s *Solution) findCelebrity(n int) int {
    s.n = n
    s.cache = make(map[pair]bool)
    celebrityCandidate := 0
    for i := 1; i < n; i++ {
        if s.cachedKnows(celebrityCandidate, i) {
            celebrityCandidate = i
        }
    }
    if s.isCelebrity(celebrityCandidate) {
        return celebrityCandidate
    }
    return -1
}

func (s *Solution) isCelebrity(i int) bool {
    for j := 0; j < s.n; j++ {
        if i == j {
            continue
        }
        if s.cachedKnows(i, j) || !s.cachedKnows(j, i) {
            return false
        }
    }
    return true
}

func (s *Solution) cachedKnows(a, b int) bool {
    key := pair{a, b}
    if _, exists := s.cache[key]; !exists {
        s.cache[key] = knows(a, b)
    }
    return s.cache[key]
}

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