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

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

Задача: 293. Flip Game
Сложность: easy

Вы играете в игру Flip со своим другом.

Вам дана строка currentState, которая содержит только символы '+' и '-'. Вы и ваш друг по очереди переворачиваете две последовательные "++" в "--". Игра заканчивается, когда один из игроков больше не может сделать ход, и, следовательно, другой игрок становится победителем.

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

Пример:

Input: currentState = "++++"
Output: ["--++","+--+","++--"]

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

1⃣Создайте пустой массив nextPossibleStates для хранения всех возможных следующих состояний после одного хода.

2⃣Запустите цикл от index = 0 до currentState.size() - 1. Для каждого индекса:
Если символы на позициях index и index + 1 равны '+':
Создайте новую строку nextState, заменив две последовательные '+' на '--'.
Используйте конкатенацию строк для создания nextState из подстроки до первого '+', "--" и подстроки после второго '+' до конца.
Сохраните созданное nextState в массив nextPossibleStates.

3⃣После цикла верните массив nextPossibleStates, содержащий все возможные следующие состояния.

😎 Решение:

package main

func generatePossibleNextMoves(currentState string) []string {
    var nextPossibleStates []string

    for i := 0; i < len(currentState)-1; i++ {
        if currentState[i] == '+' && currentState[i+1] == '+' {
            nextState := currentState[:i] + "--" + currentState[i+2:]
            nextPossibleStates = append(nextPossibleStates, nextState)
        }
    }

    return nextPossibleStates
}

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

Задача: 651. 4 Keys Keyboard
Сложность: medium

Представьте, что у вас есть специальная клавиатура со следующими клавишами: A: Напечатать одну букву "A" на экране. Ctrl-A: Выделить весь экран. Ctrl-C: Скопировать выделение в буфер. Ctrl-V: Печать буфера на экране с добавлением его после того, что уже было напечатано. Учитывая целое число n, верните максимальное количество букв 'A', которые можно напечатать на экране при нажатии не более n клавиш.

Пример:

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

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

1⃣Используйте динамическое программирование для отслеживания максимального количества букв 'A' на экране после каждого числа нажатий клавиш.

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

3⃣Возвращайте значение из таблицы динамического программирования для n нажатий клавиш.

😎 Решение:

package main

import (
    "fmt"
)

func maxA(n int) int {
    dp := make([]int, n+1)
    for i := 1; i <= n; i++ {
        dp[i] = dp[i-1] + 1
        for j := 2; j < i; j++ {
            dp[i] = max(dp[i], dp[j-2]*(i-j+1))
        }
    }
    return dp[n]
}

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

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

Задача: 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
Сложность: medium

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

Пример:

Input: nums = [8,2,4,7], limit = 4
Output: 2 
Explanation: All subarrays are: 
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4. 
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4. 
Therefore, the size of the longest subarray is 2.

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

1⃣Инициализировать два дека (minDeque и maxDeque) для хранения минимальных и максимальных значений в текущем окне и переменную left для начала окна.

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

3⃣Обновлять maxLength, проверяя максимальную длину текущего окна, и возвращать maxLength как результат.

😎 Решение:

package main

import (
    "container/heap"
)

type IntHeap []int

func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{}   { old := *h; n := len(old); x := old[n-1]; *h = old[0 : n-1]; return x }

type MaxHeap struct{ IntHeap }
func (h MaxHeap) Less(i, j int) bool { return h.IntHeap[i] > h.IntHeap[j] }

func longestSubarray(nums []int, limit int) int {
    maxHeap := &MaxHeap{}
    minHeap := &IntHeap{}
    heap.Init(maxHeap)
    heap.Init(minHeap)

    left, maxLength := 0, 0

    for right, num := range nums {
        heap.Push(maxHeap, num)
        heap.Push(minHeap, num)

        for (*maxHeap)[0]-(*minHeap)[0] > limit {
            if (*maxHeap)[0] == nums[left] {
                heap.Pop(maxHeap)
            }
            if (*minHeap)[0] == nums[left] {
                heap.Pop(minHeap)
            }
            left++
        }

        if maxLength < right-left+1 {
            maxLength = right-left+1
        }
    }

    return maxLength
}

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

Задача: 1258. Synonymous Sentences
Сложность: medium

Вам дан список эквивалентных пар строк synonyms, где synonyms[i] = [si, ti] означает, что si и ti являются эквивалентными строками. Вам также дан текст предложения. Верните все возможные синонимичные предложения, отсортированные лексикографически.

Пример:

Input: synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]], text = "I am happy today but was sad yesterday"
Output: ["I am cheerful today but was sad yesterday","I am cheerful today but was sorrow yesterday","I am happy today but was sad yesterday","I am happy today but was sorrow yesterday","I am joy today but was sad yesterday","I am joy today but was sorrow yesterday"]

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

1⃣Построить граф синонимов, используя структуру данных, такую как Union-Find или просто с использованием DFS/BFS.

2⃣Пройти по каждому слову в предложении и найти все возможные синонимы.
Сгенерировать все возможные комбинации предложений.

3⃣Отсортировать полученные предложения лексикографически.

😎 Решение:

import (
    "sort"
    "strings"
)

func generateSentences(synonyms [][]string, text string) []string {
    graph := make(map[string]map[string]bool)

    for _, pair := range synonyms {
        if _, ok := graph[pair[0]]; !ok {
            graph[pair[0]] = make(map[string]bool)
        }
        if _, ok := graph[pair[1]]; !ok {
            graph[pair[1]] = make(map[string]bool)
        }
        graph[pair[0]][pair[1]] = true
        graph[pair[1]][pair[0]] = true
    }

    words := strings.Split(text, " ")
    synonymGroups := make([][]string, len(words))
    for i, word := range words {
        synonymGroups[i] = findSynonyms(graph, word)
    }

    var sentences []string
    generate(&sentences, synonymGroups, []string{}, 0)
    sort.Strings(sentences)
    return sentences
}

func findSynonyms(graph map[string]map[string]bool, word string) []string {
    synonyms := make(map[string]bool)
    stack := []string{word}
    for len(stack) > 0 {
        w := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if !synonyms[w] {
            synonyms[w] = true
            for neighbor := range graph[w] {
                stack = append(stack, neighbor)
            }
        }
    }
    var result []string
    for synonym := range synonyms {
        result = append(result, synonym)
    }
    sort.Strings(result)
    return result
}

func generate(sentences *[]string, groups [][]string, sentence []string, index int) {
    if index == len(groups) {
        *sentences = append(*sentences, strings.Join(sentence, " "))
        return
    }
    for _, word := range groups[index] {
        generate(sentences, groups, append(sentence, word), index+1)
    }
}

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

Задача: 1000. Minimum Cost to Merge Stones
Сложность: hard

Имеется n кучек камней, расположенных в ряд. В i-й куче находятся камни stones[i]. Ход состоит в объединении ровно k последовательных куч в одну кучу, и стоимость этого хода равна общему количеству камней в этих k кучах. Верните минимальную стоимость объединения всех куч камней в одну кучу. Если это невозможно, верните -1.

Пример:

Input: stones = [3,2,4,1], k = 2
Output: 20

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

1⃣Проверка на возможность объединения:
Проверьте, можно ли объединить все кучи в одну, если количество куч n не равно 1 по модулю k-1. Если нет, верните -1.

2⃣Инициализация и динамическое программирование:
Создайте таблицу dp для хранения минимальных затрат на объединение подмассивов камней.
Используйте таблицу prefix для хранения префиксных сумм камней, чтобы быстро вычислять сумму камней в подмассиве.

3⃣Заполнение таблицы dp:
Заполните таблицу dp минимальными затратами на объединение подмассивов камней, используя динамическое программирование.
Для каждого подмассива длиной от k до n, найдите минимальную стоимость его объединения.

😎 Решение:

func mergeStones(stones []int, k int) int {
    n := len(stones)
    if (n-1)%(k-1) != 0 {
        return -1
    }

    prefix := make([]int, n+1)
    for i := 0; i < n; i++ {
        prefix[i+1] = prefix[i] + stones[i]
    }

    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
    }

    for m := k; m <= n; m++ {
        for i := 0; i <= n-m; i++ {
            j := i + m - 1
            dp[i][j] = int(^uint(0) >> 1) // max int
            for t := i; t < j; t += k - 1 {
                dp[i][j] = min(dp[i][j], dp[i][t]+dp[t+1][j])
            }
            if (j-i)%(k-1) == 0 {
                dp[i][j] += prefix[j+1] - prefix[i]
            }
        }
    }

    return dp[0][n-1]
}

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

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