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

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

Задача: 1472. Design Browser History
Сложность: medium

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

Реализуйте класс BrowserHistory:
BrowserHistory(string homepage) Инициализирует объект с домашней страницей браузера.
void visit(string url) Посещает URL с текущей страницы. Это очищает всю историю вперёд.
string back(int steps) Перемещает на steps шагов назад в истории. Если вы можете вернуться только на x шагов в истории, а steps > x, вы вернётесь только на x шагов. Возвращает текущий URL после перемещения назад в истории на не более чем steps шагов.
string forward(int steps) Перемещает на steps шагов вперёд в истории. Если вы можете переместиться только на x шагов вперёд в истории, а steps > x, вы переместитесь только на x шагов. Возвращает текущий URL после перемещения вперёд в истории на не более чем steps шагов.

Пример:

Input:
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
Output:
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

Explanation:
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");       // You are in "leetcode.com". Visit "google.com"
browserHistory.visit("facebook.com");     // You are in "google.com". Visit "facebook.com"
browserHistory.visit("youtube.com");      // You are in "facebook.com". Visit "youtube.com"
browserHistory.back(1);                   // You are in "youtube.com", move back to "facebook.com" return "facebook.com"
browserHistory.back(1);                   // You are in "facebook.com", move back to "google.com" return "google.com"
browserHistory.forward(1);                // You are in "google.com", move forward to "facebook.com" return "facebook.com"
browserHistory.visit("linkedin.com");     // You are in "facebook.com". Visit "linkedin.com"
browserHistory.forward(2);                // You are in "linkedin.com", you cannot move forward any steps.

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

1⃣Инициализация:
Создайте класс BrowserHistory с двумя стеками (history и future) и строковой переменной current для хранения текущего URL. Инициализируйте current с домашней страницей.

2⃣Посещение URL:
Метод visit(url) сохраняет текущий URL в стеке history, устанавливает url как текущий и очищает стек future.

3⃣Навигация назад и вперед:
Метод back(steps) перемещает текущий URL в стек future и извлекает URL из стека history, пока шаги не будут исчерпаны или стек history не станет пустым.
Метод forward(steps) перемещает текущий URL в стек history и извлекает URL из стека future, пока шаги не будут исчерпаны или стек future не станет пустым.

😎 Решение:

package main

type BrowserHistory struct {
    history []string
    future  []string
    current string
}

func Constructor(homepage string) BrowserHistory {
    return BrowserHistory{
        current: homepage,
    }
}

func (this *BrowserHistory) Visit(url string) {
    this.history = append(this.history, this.current)
    this.current = url
    this.future = []string{}
}

func (this *BrowserHistory) Back(steps int) string {
    for steps > 0 && len(this.history) > 0 {
        this.future = append(this.future, this.current)
        this.current = this.history[len(this.history)-1]
        this.history = this.history[:len(this.history)-1]
        steps--
    }
    return this.current
}

func (this *BrowserHistory) Forward(steps int) string {
    for steps > 0 && len(this.future) > 0 {
        this.history = append(this.history, this.current)
        this.current = this.future[len(this.future)-1]
        this.future = this.future[:len(this.future)-1]
        steps--
    }
    return this.current
}

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

Задача: 998. Maximum Binary Tree II
Сложность: medium

Максимальное дерево - это дерево, в котором каждый узел имеет значение большее, чем любое другое значение в его поддереве. Вам дан корень максимального двоичного дерева и целое число val. Как и в предыдущей задаче, данное дерево было построено из списка a (root = Construct(a)) рекурсивно с помощью следующей процедуры Construct(a): Если a пусто, верните null.
В противном случае пусть a[i] - наибольший элемент a. Создайте корневой узел со значением a[i]. Левым ребенком root будет Construct([a[0], a[1], ..., a[i - 1]]). Правым ребенком root будет Construct([a[i + 1], a[i + 2], ..., a[a.length])...., a[a.length - 1]]). Возвращаем root. Обратите внимание, что нам не было дано непосредственно a, а только корневой узел root = Construct(a). Предположим, что b - это копия a с добавленным к ней значением val. Гарантируется, что b имеет уникальные значения. Возвращаем Construct(b).

Пример:

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

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

1⃣Поиск места вставки:
Итерируйте через дерево, начиная с корня. Найдите место для вставки нового значения val так, чтобы дерево оставалось максимальным деревом. Если значение val больше, чем значение текущего узла, создайте новый узел с val и сделайте текущий узел его левым ребенком.

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

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

😎 Решение:

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

func insertIntoMaxTree(root *TreeNode, val int) *TreeNode {
    if root == nil || val > root.Val {
        return &TreeNode{Val: val, Left: root}
    }
    root.Right = insertIntoMaxTree(root.Right, val)
    return root
}

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

Задача: 1008. Construct Binary Search Tree from Preorder Traversal
Сложность: medium

Дается массив целых чисел preorder, который представляет собой обход BST (т.е, гарантируется, что для заданных тестовых случаев всегда можно найти дерево двоичного поиска с заданными требованиями. Дерево двоичного поиска - это двоичное дерево, в котором для каждого узла любой потомок Node.left имеет значение строго меньше, чем Node.val, а любой потомок Node.right имеет значение строго больше, чем Node.val. При обходе бинарного дерева в предварительном порядке сначала выводится значение узла, затем обход Node.left, затем обход Node.right.

Пример:

Input: preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

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

1⃣Инициализация переменных и функций:
Создайте класс узла дерева TreeNode с атрибутами val, left и right.
Инициализируйте индекс, который будет отслеживать текущую позицию в массиве preorder.

2⃣Рекурсивная функция для построения дерева:
Создайте рекурсивную функцию constructBST с аргументами preorder, lower и upper, которые будут ограничивать значения узлов для текущей ветви дерева.
Если текущий индекс выходит за границы массива preorder, верните null.
Получите текущее значение из preorder и проверьте, находится ли оно в пределах допустимого диапазона [lower, upper]. Если нет, верните null.

3⃣Создание узла и рекурсивное построение поддеревьев:
Создайте новый узел с текущим значением и увеличьте индекс.
Рекурсивно вызовите функцию constructBST для создания левого поддерева с обновленным верхним пределом (upper равным значению текущего узла).
Рекурсивно вызовите функцию constructBST для создания правого поддерева с обновленным нижним пределом (lower равным значению текущего узла).
Верните созданный узел.

😎 Решение:

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

func bstFromPreorder(preorder []int) *TreeNode {
    index := 0
    return constructBST(preorder, &index, int(^uint(0) >> 1), -int(^uint(0) >> 1) - 1)
}

func constructBST(preorder []int, index *int, upper, lower int) *TreeNode {
    if *index == len(preorder) {
        return nil
    }

    val := preorder[*index]
    if val < lower || val > upper {
        return nil
    }

    *index++
    root := &TreeNode{Val: val}
    root.Left = constructBST(preorder, index, val, lower)
    root.Right = constructBST(preorder, index, upper, val)
    return root
}

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

Задача: 823. Binary Trees With Factors
Сложность: medium

Дан массив уникальных целых чисел arr, где каждое целое число arr[i] строго больше 1.

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

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

Пример:

Input: arr = [2,4]
Output: 3
Explanation: We can make these trees: [2], [4], [4, 2, 2]

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

1⃣Пусть dp[i] будет количеством способов иметь корневой узел со значением A[i]. Поскольку в приведенном примере мы всегда имеем x < v и y < v, мы можем вычислить значения dp[i] в порядке возрастания, используя динамическое программирование.

2⃣Для некоторого значения корня A[i] попробуем найти кандидатов для дочерних узлов со значениями A[j] и A[i] / A[j] (так, чтобы очевидно A[j] * (A[i] / A[j]) = A[i]). Для быстрой реализации этого нам понадобится индекс, который ищет это значение: если A[k] = A[i] / A[j], тогда index[A[i] / A[j]] = k.

3⃣После этого добавим все возможные dp[j] * dp[k] (с j < i, k < i) к нашему ответу dp[i]. В нашей реализации на Java мы тщательно использовали long, чтобы избежать проблем с переполнением.

😎 Решение:

func numFactoredBinaryTrees(A []int) int {
    const MOD = 1_000_000_007
    sort.Ints(A)
    dp := make([]int64, len(A))
    for i := range dp {
        dp[i] = 1
    }
    index := make(map[int]int)
    for i, x := range A {
        index[x] = i
    }

    for i, x := range A {
        for j := 0; j < i; j++ {
            if x%A[j] == 0 {
                right := x / A[j]
                if k, ok := index[right]; ok {
                    dp[i] = (dp[i] + dp[j]*dp[k]) % MOD
                }
            }
        }
    }

    result := int64(0)
    for _, x := range dp {
        result = (result + x) % MOD
    }
    return int(result)
}

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

Задача: 303. Range Sum Query - Immutable
Сложность: easy

Дан целочисленный массив nums. Обработайте несколько запросов следующего типа:
Вычислите сумму элементов массива nums между индексами left и right включительно, где left <= right.
Реализуйте класс NumArray:
- NumArray(int[] nums) Инициализирует объект с целочисленным массивом nums.
- int sumRange(int left, int right) Возвращает сумму элементов массива nums между индексами left и right включительно (т.е. nums[left] + nums[left + 1] + ... + nums[right]).

Пример:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

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

1⃣Инициализация:
Создайте массив sum длиной на один элемент больше, чем массив nums, и заполните его накопленными суммами элементов массива nums.

2⃣Предварительное вычисление сумм:
Заполните массив sum, где каждый элемент sum[i + 1] является суммой всех предыдущих элементов массива nums до индекса i включительно.

3⃣Вычисление диапазонной суммы:
Для каждого запроса суммы элементов между индексами left и right используйте разницу между sum[right + 1] и sum[left], чтобы быстро получить результат.

😎 Решение:

package main

type NumArray struct {
    sum []int
}

func Constructor(nums []int) NumArray {
    sum := make([]int, len(nums)+1)
    for i := 0; i < len(nums); i++ {
        sum[i+1] = sum[i] + nums[i]
    }
    return NumArray{sum}
}

func (this *NumArray) SumRange(i int, j int) int {
    return this.sum[j+1] - this.sum[i]
}

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

Задача: 521. Longest Uncommon Subsequence I
Сложность: easy

Даны две строки a и b. Верните длину самой длинной несообщей подпоследовательности.
Несообщая подпоследовательность — это строка, которая является подпоследовательностью только одной из двух строк.

Пример:

Input: a = "aba", b = "cdc"  
Output: 3

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

1⃣Проверяем, равны ли строки a и b. Если они полностью совпадают, то все подпоследовательности у них одинаковы, и несообщей не существует — возвращаем -1.

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

3⃣Возвращаем длину более длинной строки, так как это и будет длина самой длинной несообщей подпоследовательности.

😎 Решение:

func findLUSlength(a string, b string) int {
    if a == b {
        return -1
    } else {
        if len(a) > len(b) {
            return len(a)
        } else {
            return len(b)
        }
    }
}

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

Задача: 1192. Critical Connections in a Network
Сложность: hard

Существует n серверов, пронумерованных от 0 до n - 1, соединенных неориентированными соединениями "сервер-сервер", образуя сеть, где connections[i] = [ai, bi] представляет собой соединение между серверами ai и bi. Любой сервер может достичь других серверов напрямую или косвенно через сеть.

Критическое соединение — это соединение, удаление которого сделает невозможным достижение некоторыми серверами других серверов.
Верните все критические соединения в сети в любом порядке.

Пример:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

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

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

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

3⃣Поиск критических соединений:
После завершения обхода DFS преобразуйте оставшиеся соединения в список и верните его.

😎 Решение:

type Solution struct {
    graph    map[int][]int
    rank     map[int]int
    connDict map[[2]int]bool
}

func (s *Solution) CriticalConnections(n int, connections [][]int) [][]int {
    s.formGraph(n, connections)
    s.dfs(0, 0)
    
    var result [][]int
    for conn := range s.connDict {
        result = append(result, []int{conn[0], conn[1]})
    }
    return result
}

func (s *Solution) dfs(node, discoveryRank int) int {
    if r, ok := s.rank[node]; ok {
        return r
    }
    
    s.rank[node] = discoveryRank
    minRank := discoveryRank + 1
    
    for _, neighbor := range s.graph[node] {
        if neighRank, ok := s.rank[neighbor]; ok && neighRank == discoveryRank-1 {
            continue
        }
        
        recursiveRank := s.dfs(neighbor, discoveryRank+1)
        
        if recursiveRank <= discoveryRank {
            delete(s.connDict, [2]int{min(node, neighbor), max(node, neighbor)})
        }
        
        minRank = min(minRank, recursiveRank)
    }
    
    return minRank
}

func (s *Solution) formGraph(n int, connections [][]int) {
    s.graph = make(map[int][]int)
    s.rank = make(map[int]int)
    s.connDict = make(map[[2]int]bool)
    
    for i := 0; i < n; i++ {
        s.graph[i] = []int{}
    }
    
    for _, edge := range connections {
        u, v := edge[0], edge[1]
        s.graph[u] = append(s.graph[u], v)
        s.graph[v] = append(s.graph[v], u)
        s.connDict[[2]int{min(u, v), max(u, v)}] = true
    }
}

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
}

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

Задача: 1198. Find Smallest Common Element in All Rows
Сложность: medium

Дана матрица mat размером m x n, где каждая строка отсортирована в строго возрастающем порядке. Верните наименьший общий элемент во всех строках.

Если общего элемента нет, верните -1.

Пример:

Input: mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]
Output: 5

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

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

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

3⃣Проверка счетчика:
Если счетчик равен количеству строк, возвращайте текущий максимум.
Повторите шаг 2.

😎 Решение:

func smallestCommonElement(mat [][]int) int {
    n := len(mat)
    m := len(mat[0])
    pos := make([]int, n)
    cur_max := 0
    cnt := 0

    for {
        for i := 0; i < n; i++ {
            for pos[i] < m && mat[i][pos[i]] < cur_max {
                pos[i]++
            }
            if pos[i] >= m {
                return -1
            }
            if mat[i][pos[i]] != cur_max {
                cnt = 1
                cur_max = mat[i][pos[i]]
            } else {
                cnt++
                if cnt == n {
                    return cur_max
                }
            }
        }
    }
}

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

Задача: 474. Ones and Zeroes
Сложность: medium

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

Пример:

Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3 
Output: 4  

Explanation: Подмножество {"10", "0001", "1", "0"} содержит 5 нулей и 3 единицы — это максимум по условию. Размер = 4.

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

1⃣Рассматриваем все возможные подмножества с помощью побитовой маски: от 0 до 2^len(strs).

2⃣Для каждой маски определяем, какие строки входят в подмножество. Считаем количество 0 и 1.

3⃣Если сумма не превышает m и n — учитываем длину подмножества как кандидата в ответ.

😎 Решение:

package main

import (
    "fmt"
)

type Solution struct{}

func (s *Solution) findMaxForm(strs []string, m int, n int) int {
    maxlen := 0
    for i := 0; i < (1 << len(strs)); i++ {
        zeroes, ones, length := 0, 0, 0
        for j := 0; j < len(strs); j++ {
            if (i & (1 << j)) != 0 {
                count := s.countZeroesOnes(strs[j])
                zeroes += count[0]
                ones += count[1]
                if zeroes > m || ones > n {
                    break
                }
                length++
            }
        }
        if zeroes <= m && ones <= n {
            maxlen = max(maxlen, length)
        }
    }
    return maxlen
}

func (s *Solution) countZeroesOnes(str string) [2]int {
    count := [2]int{}
    for _, char := range str {
        count[char-'0']++
    }
    return count
}

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

func main() {
    sol := Solution{}
    fmt.Println(sol.findMaxForm([]string{"10", "0001", "111001", "1", "0"}, 5, 3))
}

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

Задача: 1219. Path with Maximum Gold
Сложность: medium

В золотом руднике размером m x n каждая ячейка содержит целое число, представляющее количество золота в этой ячейке, или 0, если она пуста.

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

Пример:

Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
 [5,8,7],
 [0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.

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

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

2⃣Функция DFS и обратный трек:
Реализуйте функцию dfsBacktrack для поиска пути с максимальным золотом с помощью DFS и обратного трека.
Обрабатывайте базовый случай, проверяя выход за пределы сетки или ячейки без золота.
Пометьте текущую ячейку как посещённую и сохраните её значение.
Исследуйте каждую из четырёх смежных ячеек и обновите максимальное количество золота, если найден лучший путь.
Сбросьте текущую ячейку до её исходного значения для дальнейших исследований.

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

😎 Решение:

type Solution struct{}

func (s *Solution) getMaximumGold(grid [][]int) int {
    directions := []int{0, 1, 0, -1, 0}
    rows, cols := len(grid), len(grid[0])
    maxGold := 0

    var dfsBacktrack func(grid [][]int, rows, cols, row, col int) int
    dfsBacktrack = func(grid [][]int, rows, cols, row, col int) int {
        if row < 0 || col < 0 || row >= rows || col >= cols || grid[row][col] == 0 {
            return 0
        }
        originalVal := grid[row][col]
        grid[row][col] = 0
        maxGold := 0

        for i := 0; i < 4; i++ {
            maxGold = max(maxGold, dfsBacktrack(grid, rows, cols, row+directions[i], col+directions[i+1]))
        }

        grid[row][col] = originalVal
        return maxGold + originalVal
    }

    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            maxGold = max(maxGold, dfsBacktrack(grid, rows, cols, row, col))
        }
    }

    return maxGold
}

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

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

Задача: 1051. Height Checker
Сложность: easy

Школа пытается сделать ежегодную фотографию всех учеников. Учеников просят встать в одну шеренгу в неубывающем порядке по росту. Пусть этот порядок представлен целочисленным массивом expected, где expected[i] - ожидаемый рост i-го студента в очереди. Вам дан целочисленный массив heights, представляющий текущий порядок, в котором стоят студенты. Каждый heights[i] - это высота i-го студента в очереди (с индексом 0). Верните количество индексов, в которых heights[i] != expected[i].

Пример:

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

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

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

2⃣Пройди по обоим массивам и сравни элементы.

3⃣Подсчитай количество индексов, где элементы двух массивов не равны

😎 Решение:

package main

import (
    "fmt"
    "sort"
)

func heightChecker(heights []int) int {
    expected := make([]int, len(heights))
    copy(expected, heights)
    sort.Ints(expected)
    count := 0
    for i := range heights {
        if heights[i] != expected[i] {
            count++
        }
    }
    return count
}

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

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

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

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

Пример:

Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation:  [5, 3] is also a valid answer.

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

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

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

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

😎 Решение:

func singleNumber(nums []int) []int {
    xor := 0
    for _, num := range nums {
        xor ^= num
    }
    diff := xor & -xor
    res := []int{0, 0}
    for _, num := range nums {
        if num&diff == 0 {
            res[0] ^= num
        } else {
            res[1] ^= num
        }
    }
    return res
}

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

Задача: 1404. Number of Steps to Reduce a Number in Binary Representation to One
Сложность: medium

Дано бинарное представление целого числа в виде строки s. Верните количество шагов, необходимых для его сокращения до 1 по следующим правилам:
Если текущее число четное, его нужно разделить на 2.
Если текущее число нечетное, нужно прибавить к нему 1.
Гарантируется, что для всех тестовых случаев всегда можно достичь единицы.

Пример:

Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14. 
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.  
Step 5) 4 is even, divide by 2 and obtain 2. 
Step 6) 2 is even, divide by 2 and obtain 1.  

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

1⃣Инициализируйте переменную operations значением 0.

2⃣Повторяйте операции, пока длина строки s больше 1:
Если последний бит строки s равен 0, это означает, что число четное; примените операцию деления на 2, удалив последний бит.
В противном случае это означает, что число, представленное строкой, нечетное; добавьте 1 к числу, изменив строку, чтобы выполнить эту операцию.

3⃣Верните количество операций.

😎 Решение:

func numSteps(s string) int {
    str := []byte(s)
    operations := 0

    for len(str) > 1 {
        if str[len(str)-1] == '0' {
            str = str[:len(str)-1]
        } else {
            i := len(str) - 1
            for i >= 0 && str[i] == '1' {
                str[i] = '0'
                i--
            }
            if i < 0 {
                str = append([]byte{'1'}, str...)
            } else {
                str[i] = '1'
            }
        }
        operations++
    }

    return operations
}

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

Задача: 1531. String Compression II
Сложность: hard

Дана строка s и целое число k. Необходимо удалить не более k символов из s так, чтобы длина сжатой версии строки s с использованием RLE была минимальной.

Найдите минимальную длину сжатой версии строки s после удаления не более k символов.

Пример:

Input: s = "aaabcccd", k = 2
Output: 4
Explanation: Compressing s without deleting anything will give us "a3bc3d" of length 6. Deleting any of the characters 'a' or 'c' would at most decrease the length of the compressed string to 5, for instance delete 2 'a' then we will have s = "abcccd" which compressed is abc3d. Therefore, the optimal way is to delete 'b' and 'd', then the compressed version of s will be "a3c3" of length 4.

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

1⃣Обходим символы строки слева направо, решая для каждого символа, включать его в сжатую строку или нет. Это создает состояния (строка, оставшиеся для включения символы), которые можно представить в виде бинарного дерева, где левые потомки означают включение символов, а правые — их пропуск. Многочисленные повторяющиеся подзадачи указывают на необходимость использования динамического программирования.

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

3⃣Связываем состояния друг с другом: удаление нового символа увеличивает i на один и уменьшает k на один; включение нового символа оставляет длину сжатия неизменной (кроме случаев, когда частота последнего символа 1, 9 или 99) или увеличивает длину на один, если новый символ не равен последнему символу сжатия.

😎 Решение

package main

import "math"

type Solution struct {
    memo map[int]int
    add  map[int]struct{}
}

func Constructor() Solution {
    return Solution{memo: make(map[int]int), add: map[int]struct{}{1: {}, 9: {}, 99: {}}}
}

func (this *Solution) GetLengthOfOptimalCompression(s string, k int) int {
    return this.dp(s, 0, byte('a'+26), 0, k)
}

func (this *Solution) dp(s string, idx int, lastChar byte, lastCharCount int, k int) int {
    if k < 0 {
        return math.MaxInt32 / 2
    }

    if idx == len(s) {
        return 0
    }

    key := idx*101*27*101 + int(lastChar-'a')*101*101 + lastCharCount*101 + k

    if res, found := this.memo[key]; found {
        return res
    }

    deleteChar := this.dp(s, idx+1, lastChar, lastCharCount, k-1)
    var keepChar int
    if s[idx] == lastChar {
        keepChar = this.dp(s, idx+1, lastChar, lastCharCount+1, k)
        if _, found := this.add[lastCharCount]; found {
            keepChar++
        }
    } else {
        keepChar = this.dp(s, idx+1, s[idx], 1, k) + 1
    }

    res := min(deleteChar, keepChar)
    this.memo[key] = res

    return res
}

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

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