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

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

Задача: 1247. Minimum Swaps to Make Strings Equal
Сложность: hard

Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать.

Пример:
Input: arr = [1,2]
Output: 2

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

1⃣Подсчет несоответствующих пар:
Пройдите по строкам s1 и s2, чтобы подсчитать количество пар xy и yx. Пара xy возникает, когда s1[i] равно 'x', а s2[i] равно 'y'. Пара yx возникает, когда s1[i] равно 'y', а s2[i] равно 'x'.

2⃣Проверка четности:
Если сумма количества пар xy и yx нечетная, то невозможно сделать строки равными, поскольку каждая замена уменьшает сумму несоответствующих пар на 2. В этом случае верните -1.

3⃣Вычисление минимального количества замен:
Если количество пар xy четное и количество пар yx четное, то каждые две пары xy и каждые две пары yx можно обменять за один ход. Поэтому минимальное количество замен равно xy // 2 + yx // 2.
Если количество пар xy нечетное и количество пар yx нечетное, то мы можем обменять одну пару xy и одну пару yx за два хода. Поэтому минимальное количество замен равно xy // 2 + yx // 2 + 2.

😎 Решение:

func minimumSwap(s1 string, s2 string) int {
    xy, yx := 0, 0
    for i := 0; i < len(s1); i++ {
        if s1[i] == 'x' && s2[i] == 'y' {
            xy++
        } else if s1[i] == 'y' && s2[i] == 'x' {
            yx++
        }
    }
    if (xy+yx)%2 != 0 {
        return -1
    }
    return xy/2 + yx/2 + (xy%2)*2
}

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

Задача: 1365. How Many Numbers Are Smaller Than the Current Number
Сложность: easy

Дан массив nums. Для каждого элемента nums[i] определите, сколько чисел в массиве меньше его. То есть, для каждого nums[i] вам нужно посчитать количество допустимых j, таких что j != i и nums[j] < nums[i].

Верните ответ в виде массива.

Пример:

Input: nums = [6,5,4,8]
Output: [2,1,0,3]

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

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

2⃣Поиск индекса каждого элемента:
Для каждого элемента nums[i] найдите его индекс в отсортированной копии массива. Этот индекс указывает количество элементов, меньших nums[i].

3⃣Формирование ответа:
Сформируйте массив ответов, где каждый элемент будет соответствовать количеству чисел, меньших текущего.

😎 Решение:

import "sort"

func smallerNumbersThanCurrent(nums []int) []int {
    sortedNums := append([]int(nil), nums...)
    sort.Ints(sortedNums)
    result := make([]int, len(nums))
    
    for i, num := range nums {
        result[i] = indexOf(sortedNums, num)
    }
    
    return result
}

func indexOf(nums []int, target int) int {
    for i, num := range nums {
        if num == target {
            return i
        }
    }
    return -1
}

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

Задача: 954. Array of Doubled Pairs
Сложность: easy

Если задан целочисленный массив четной длины arr, верните true, если можно переупорядочить arr так, чтобы arr[2 * i + 1] = 2 * arr[2 * i] для каждого 0 <= i < len(arr) / 2, или false в противном случае.

Пример:

Input: arr = [3,1,3,6]
Output: false

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

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

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

3⃣Если для каждого элемента можно найти пару, вернуть true, иначе вернуть false.

😎 Решение:

package main

import (
    "sort"
)

func canReorderDoubled(arr []int) bool {
    count := make(map[int]int)
    for _, num := range arr {
        count[num]++
    }
    sort.Slice(arr, func(i, j int) bool {
        return abs(arr[i]) < abs(arr[j])
    })
    for _, num := range arr {
        if count[num] == 0 {
            continue
        }
        if count[2*num] == 0 {
            return false
        }
        count[num]--
        count[2*num]--
    }
    return true
}

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

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

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

Даны корни двух бинарных деревьев p и q. Напишите функцию, чтобы проверить, одинаковы ли они.

Два бинарных дерева считаются одинаковыми, если они структурно идентичны и узлы имеют одинаковые значения.

Пример:

Input: p = [1,2,3], q = [1,2,3]  
Output: true  

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

1⃣Проверка на nil:
- Если оба узла nil, они равны.
- Если один nil, а другой — нет, деревья разные.

2⃣Проверка значений:
- Если значения узлов различаются, деревья разные.

3⃣Рекурсивная проверка:
- Повторяем ту же проверку для левых и правых поддеревьев.

😎 Решение:

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

func isSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    }
    if p == nil || q == nil {
        return false
    }
    if p.Val != q.Val {
        return false
    }
    return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

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

Задача: 238. Product of Array Except Self
Сложность: medium

Дан массив целых чисел nums, верните массив answer такой, что answer[i] равен произведению всех элементов массива nums, кроме nums[i].

Произведение любого префикса или суффикса массива nums гарантированно помещается в 32-битное целое число.

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

Пример:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

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

1⃣Инициализация массивов L и R: Инициализируйте два пустых массива L и R. Массив L будет содержать произведение всех чисел слева от i, а массив R будет содержать произведение всех чисел справа от i. Заполните массив L, установив L[0] равным 1, а для остальных элементов используйте формулу L[i] = L[i-1] * nums[i-1]. Заполните массив R, установив R[length-1] равным 1, а для остальных элементов используйте формулу R[i] = R[i+1] * nums[i+1].

2⃣Заполнение массивов L и R: Пройдите два цикла для заполнения массивов L и R. В первом цикле заполните массив L, начиная с L[0] и двигаясь вправо. Во втором цикле заполните массив R, начиная с R[length-1] и двигаясь влево.

3⃣Формирование результата: Пройдите по исходному массиву и для каждого элемента i вычислите произведение всех элементов, кроме nums[i], используя L[i] * R[i]. Сохраните результат в массиве answer и верните его.

😎 Решение:

func productExceptSelf(nums []int) []int {
    length := len(nums)
    L := make([]int, length)
    R := make([]int, length)
    answer := make([]int, length)

    L[0] = 1
    for i := 1; i < length; i++ {
        L[i] = nums[i-1] * L[i-1]
    }

    R[length-1] = 1
    for i := length - 2; i >= 0; i-- {
        R[i] = nums[i+1] * R[i+1]
    }

    for i := 0; i < length; i++ {
        answer[i] = L[i] * R[i]
    }

    return answer
}

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

Задача: 666. Path Sum IV
Сложность: medium

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

Сотни представляют глубину d этого узла, где 1 <= d <= 4.
Десятки представляют позицию p этого узла на уровне, которому он принадлежит, где 1 <= p <= 8. Позиция соответствует позиции в полном бинарном дереве.
Единицы представляют значение v этого узла, где 0 <= v <= 9.
Дан массив возрастающих трехзначных чисел nums, представляющих бинарное дерево с глубиной меньше 5. Верните сумму всех путей от корня к листьям.

Гарантируется, что данный массив представляет собой валидное связанное бинарное дерево.

Пример:

Input: nums = [113,215,221]
Output: 12
Explanation: The tree that the list represents is shown.
The path sum is (3 + 5) + (3 + 1) = 12.

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

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

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

3⃣Подсчет суммы путей:
Выполните обход дерева (например, используя DFS) и подсчитайте сумму всех путей от корня к листьям.

😎 Решение:

func pathSum(nums []int) int {
    tree := make(map[int]int)
    
    for _, num := range nums {
        depth := num / 100
        pos := (num / 10) % 10
        val := num % 10
        tree[depth*10+pos] = val
    }
    
    return dfs(tree, 1, 1, 0)
}

func dfs(tree map[int]int, depth, pos, currentSum int) int {
    key := depth*10 + pos
    if _, exists := tree[key]; !exists {
        return 0
    }
    currentSum += tree[key]
    leftChild := (depth + 1) * 10 + 2*pos - 1
    rightChild := (depth + 1) * 10 + 2*pos
    if _, leftExists := tree[leftChild]; !leftExists && !tree[rightChild] {
        return currentSum
    }
    return dfs(tree, depth+1, 2*pos-1, currentSum) + dfs(tree, depth+1, 2*pos, currentSum)
}

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

Задача: 484. Find Permutation
Сложность: medium

Перестановка perm из n целых чисел всех чисел в диапазоне [1, n] может быть представлена в виде строки s длиной n - 1, где:

- s[i] == 'I', если perm[i] < perm[i + 1]
- s[i] == 'D', если perm[i] > perm[i + 1]

Дана строка s, восстановите лексикографически наименьшую перестановку perm и верните её.

Пример:

Input: s = "I" 
Output: [1,2]
Explanation: [1,2] is the only legal permutation that can be represented by s, where the number 1 and 2 construct an increasing relationship.

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

1⃣Инициализация
Создайте пустой стек stack. Создайте пустой список result для хранения конечной перестановки.

2⃣Для каждого числа i
Если текущий символ в строке s равен 'D', добавьте i в стек.
Если текущий символ равен 'I', добавьте i в стек, затем извлеките все элементы из стека и добавьте их в result.

3⃣Завершение
Добавьте n в стек и извлеките все элементы из стека, добавив их в result.
Верните список result, который представляет лексикографически наименьшую перестановку.

😎 Решение:

func findPermutation(s string) []int {
    res := make([]int, len(s)+1)
    stack := []int{}
    j := 0
    for i := 1; i <= len(s); i++ {
        if s[i-1] == 'I' {
            stack = append(stack, i)
            for len(stack) > 0 {
                res[j] = stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                j++
            }
        } else {
            stack = append(stack, i)
        }
    }
    stack = append(stack, len(s)+1)
    for len(stack) > 0 {
        res[j] = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        j++
    }
    return res
}

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

Задача: 1519. Number of Nodes in the Sub-Tree With the Same Label
Сложность: medium

Дано дерево с n вершинами и строка labels, в которой labels[i] — метка вершины i.
Нужно вернуть массив ans, где ans[i] — количество узлов в поддереве вершины i с такой же меткой, как у самой вершины.

Пример:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"  
Output: [2,1,1,1,1,1,1]

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

1⃣Построение графа
С помощью списка смежности adj строим дерево, где adj[node] содержит всех соседей node.

2⃣Обход в глубину (DFS)
Стартуем DFS от корня 0. Для каждого узла:
- создаём массив nodeCounts[26] — счётчики меток 'a'..'z'
- проходим по детям, исключая родителя
- агрегируем метки детей в текущий массив
- сохраняем ans[node] = nodeCounts[метка узла]

3⃣Возврат результата
После DFS возвращаем итоговый массив ans.

😎 Решение:

func dfs(node, parent int, adj map[int][]int, labels string, ans []int) []int {
    nodeCounts := make([]int, 26)
    nodeCounts[labels[node]-'a'] = 1

    for _, child := range adj[node] {
        if child == parent {
            continue
        }
        childCounts := dfs(child, node, adj, labels, ans)
        for i := 0; i < 26; i++ {
            nodeCounts[i] += childCounts[i]
        }
    }

    ans[node] = nodeCounts[labels[node]-'a']
    return nodeCounts
}

func countSubTrees(n int, edges [][]int, labels string) []int {
    adj := make(map[int][]int)
    for _, edge := range edges {
        adj[edge[0]] = append(adj[edge[0]], edge[1])
        adj[edge[1]] = append(adj[edge[1]], edge[0])
    }

    ans := make([]int, n)
    dfs(0, -1, adj, labels, ans)
    return ans
}

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

Задача: 556. Next Greater Element III
Сложность: medium

Мы можем перемешать строку s, чтобы получить строку t, используя следующий алгоритм:

Дано положительное целое число n. Найдите наименьшее целое число, которое имеет точно такие же цифры, как и число n, и больше самого числа n по значению. Если такого положительного целого числа не существует, верните -1.

Учтите, что возвращенное число должно помещаться в 32-битное целое число. Если существует допустимый ответ, но он не помещается в 32-битное целое число, верните -1.

Пример:

Input: n = 12
Output: 21

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

1⃣Нахождение и перестановка цифр
Преобразуйте число n в массив цифр. Найдите первую цифру, которая нарушает убывающий порядок (с конца массива). Назовем её индексом i. Найдите первую цифру, которая больше digits[i-1] (с конца массива). Назовем её индексом j. Поменяйте местами цифры на позициях i-1 и j.

2⃣Обратный порядок оставшихся цифр
Обратный порядок части массива от индекса i до конца, чтобы получить наименьшую перестановку, которая больше исходной.

3⃣Проверка результата и преобразование обратно в число
Преобразуйте массив цифр обратно в число. Если число превышает 32-битный предел, верните -1. В противном случае верните полученное число.

😎 Решение:

package main

import (
    "fmt"
    "sort"
    "strconv"
)

func swap(s string, i0, i1 int) string {
    if i0 == i1 {
        return s
    }
    runes := []rune(s)
    runes[i0], runes[i1] = runes[i1], runes[i0]
    return string(runes)
}

var list []string

func permute(a string, l, r int) {
    if l == r {
        list = append(list, a)
    } else {
        for i := l; i <= r; i++ {
            a = swap(a, l, i)
            permute(a, l+1, r)
            a = swap(a, l, i)
        }
    }
}

func nextGreaterElement(n int) int {
    s := strconv.Itoa(n)
    list = []string{}
    permute(s, 0, len(s)-1)
    sort.Strings(list)
    for i := range list {
        if list[i] == s {
            if i < len(list)-1 {
                result, _ := strconv.Atoi(list[i+1])
                if result <= 2147483647 {
                    return result
                }
            }
        }
    }
    return -1
}

func main() {
    n := 12345
    fmt.Println(nextGreaterElement(n)) // Output: 12354
}

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

Задача: 554. Brick Wall
Сложность: medium

Перед вами находится прямоугольная кирпичная стена с n рядами кирпичей. В i-м ряду находится несколько кирпичей одинаковой высоты (то есть один юнит), но они могут быть разной ширины. Общая ширина каждого ряда одинакова.

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

Дан двумерный массив wall, содержащий информацию о стене, верните минимальное количество пересеченных кирпичей после проведения такой вертикальной линии.

Пример:

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

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

1⃣Определите общую ширину стены, сложив ширины кирпичей в первом ряду. Создайте массив pos, где pos[i] указывает на текущую позицию в i-ом ряду.

2⃣Пройдите по каждой возможной позиции для вертикальной линии (от 1 до общей ширины стены - 1). Для каждой позиции обновите массив pos, проверяя, пересекает ли линия границу кирпича. Если пересекает, увеличьте значение pos[i].

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

😎 Решение:

package main

import (
    "math"
)

func leastBricks(wall [][]int) int {
    pos := make([]int, len(wall))
    sum := 0
    res := math.MaxInt32

    for _, el := range wall[0] {
        sum += el
    }

    for sum != 0 {
        count := 0
        for i := 0; i < len(wall); i++ {
            if wall[i][pos[i]] != 0 {
                count++
            } else {
                pos[i]++
            }
            wall[i][pos[i]]--
        }
        sum--
        res = min(res, count)
    }

    return res
}

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

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

Задача: 336. Palindrome Pairs
Сложность: hard

Вам дан массив уникальных строк words, индексируемый с 0.

Пара палиндромов — это пара целых чисел (i, j), таких что:
0 <= i, j < words.length,
i != j, и
words[i] + words[j] (конкатенация двух строк) является палиндромом.
Верните массив всех пар палиндромов из слов.

Вы должны написать алгоритм с временной сложностью O(сумма длин всех слов в words).

Пример:

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]

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

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

2⃣Итерация по всем парам слов и проверка:
Пройдите по всем парам слов в массиве words, используя два вложенных цикла.
Для каждой пары слов проверяйте, образуют ли они палиндром при конкатенации. Это делается путем объединения строк и проверки, равна ли объединенная строка своей обратной версии.

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

😎 Решение:

func palindromePairs(words []string) [][]int {
    var pairs [][]int
    
    for i := 0; i < len(words); i++ {
        for j := 0; j < len(words); j++ {
            if i == j {
                continue
            }
            combined := words[i] + words[j]
            if combined == reverseString(combined) {
                pairs = append(pairs, []int{i, j})
            }
        }
    }
    
    return pairs
}

func reverseString(s string) string {
    runes := []rune(s)
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
    return string(runes)
}

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

Задача: 300. Longest Increasing Subsequence
Сложность: medium

Дан массив целых чисел nums, верните длину самой длинной строго возрастающей подпоследовательности.

Пример:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

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

1⃣Инициализируйте массив dp длиной nums.length, все элементы которого равны 1. dp[i] представляет длину самой длинной возрастающей подпоследовательности, которая заканчивается элементом с индексом i.


2⃣Итерируйтесь от i = 1 до i = nums.length - 1. В каждой итерации используйте второй цикл for для итерации от j = 0 до j = i - 1 (все элементы перед i). Для каждого элемента перед i, проверьте, меньше ли этот элемент, чем nums[i]. Если да, установите dp[i] = max(dp[i], dp[j] + 1).


3⃣Верните максимальное значение из dp.

😎 Решение:

package main

import (
  "fmt"
  "math"
)

func lengthOfLIS(nums []int) int {
  if len(nums) == 0 {
    return 0
  }

  dp := make([]int, len(nums))
  for i := range dp {
    dp[i] = 1
  }

  for i := 1; i < len(nums); i++ {
    for j := 0; j < i; j++ {
      if nums[i] > nums[j] {
        dp[i] = int(math.Max(float64(dp[i]), float64(dp[j]+1)))
      }
    }
  }

  maxLength := 0
  for _, length := range dp {
    if length > maxLength {
      maxLength = length
    }
  }

  return maxLength
}

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

Задача: 946. Validate Stack Sequences
Сложность: medium

Учитывая, что два целочисленных массива pushed и popped имеют разные значения, верните true, если это могло быть результатом последовательности операций push и pop на изначально пустом стеке, или false в противном случае.

Пример:

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

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

1⃣Инициализировать пустой стек.
Использовать указатель j для отслеживания текущей позиции в массиве popped.

2⃣Пройти по каждому элементу в массиве pushed:
Добавить элемент в стек.
Проверить верхний элемент стека:
Если он совпадает с текущим элементом в popped, удалить элемент из стека и увеличить указатель j.

3⃣В конце вернуть true, если указатель j достиг конца массива popped, иначе вернуть false.

😎 Решение:

package main

func validateStackSequences(pushed []int, popped []int) bool {
    stack := []int{}
    j := 0
    for _, x := range pushed {
        stack = append(stack, x)
        for len(stack) > 0 && j < len(popped) && stack[len(stack)-1] == popped[j] {
            stack = stack[:len(stack)-1]
            j++
        }
    }
    return j == len(popped)
}

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

Задача: 996. Number of Squareful Arrays
Сложность: hard

Массив является квадратным, если сумма каждой пары соседних элементов является совершенным квадратом. Если задан целочисленный массив nums, верните количество перестановок nums, которые являются квадратными. Две перестановки perm1 и perm2 различны, если существует некоторый индекс i такой, что perm1[i] != perm2[i].

Пример:

Input: nums = [1,17,8]
Output: 2

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

1⃣Генерация перестановок:
Сгенерируйте все возможные перестановки массива nums.
Для каждой перестановки проверьте, является ли она квадратной.

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

3⃣Подсчет квадратных перестановок:
Подсчитайте количество перестановок, которые являются квадратными, и верните это значение.

😎 Решение:

import (
    "math"
    "sort"
)

func numSquarefulPerms(nums []int) int {
    sort.Ints(nums)
    used := make([]bool, len(nums))
    result := make(map[string]bool)
    path := []int{}
    backtrack(nums, used, path, result)
    return len(result)
}

func backtrack(nums []int, used []bool, path []int, result map[string]bool) {
    if len(path) == len(nums) {
        if isSquareful(path) {
            key := makeKey(path)
            result[key] = true
        }
        return
    }
    
    for i := 0; i < len(nums); i++ {
        if used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
            continue
        }
        path = append(path, nums[i])
        used[i] = true
        backtrack(nums, used, path, result)
        path = path[:len(path)-1]
        used[i] = false
    }
}

func isSquareful(perm []int) bool {
    for i := 0; i < len(perm)-1; i++ {
        sum := perm[i] + perm[i+1]
        root := int(math.Sqrt(float64(sum)))
        if root*root != sum {
            return false
        }
    }
    return true
}

func makeKey(path []int) string {
    key := ""
    for _, num := range path {
        key += string(num) + ","
    }
    return key
}

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

Задача: 616. Add Bold Tag in String
Сложность: medium

Вам дана строка s и массив строк words. Вы должны добавить закрытую пару полужирных тегов <b> и </b>, чтобы обернуть подстроки в s, которые существуют в words. Если две такие подстроки пересекаются, вы должны обернуть их вместе только одной парой закрытых полужирных тегов. Если две подстроки, обернутые полужирными тегами, идут подряд, вы должны объединить их. Верните s после добавления полужирных тегов.

Пример:

Input: s = "abcxyz123", words = ["abc","123"]
Output: "<b>abc</b>xyz<b>123</b>"

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

1⃣Найдите все позиции вхождений подстрок из words в строку s и пометьте эти позиции для выделения тегами <b> и </b>.

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

3⃣Постройте новую строку s, добавляя теги <b> и </b> в определенные позиции.

😎 Решение:

package main

import (
    "strings"
)

func addBoldTag(s string, words []string) string {
    n := len(s)
    bold := make([]bool, n)
    
    for _, word := range words {
        start := strings.Index(s, word)
        for start != -1 {
            for i := start; i < start+len(word); i++ {
                bold[i] = true
            }
            start = strings.Index(s, word, start+1)
        }
    }
    
    var result strings.Builder
    i := 0
    for i < n {
        if bold[i] {
            result.WriteString("<b>")
            for i < n && bold[i] {
                result.WriteByte(s[i])
                i++
            }
            result.WriteString("</b>")
        } else {
            result.WriteByte(s[i])
            i++
        }
    }
    
    return result.String()
}

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

Задача: 951. Flip Equivalent Binary Trees
Сложность: medium

Для бинарного дерева T мы можем определить операцию переворота следующим образом: выбираем любой узел и меняем местами левое и правое дочерние поддеревья. Бинарное дерево X эквивалентно бинарному дереву Y тогда и только тогда, когда мы можем сделать X равным Y после некоторого количества операций переворота. Учитывая корни двух бинарных деревьев root1 и root2, верните true, если эти два дерева эквивалентны перевороту, или false в противном случае.

Пример:

Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
Output: true

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

1⃣Если оба дерева пусты, они эквивалентны, вернуть true. Если одно дерево пустое, а другое нет, они не эквивалентны, вернуть false.

2⃣Если значения корней деревьев не совпадают, вернуть false.
Проверить два условия:
Левое поддерево первого дерева эквивалентно левому поддереву второго дерева и правое поддерево первого дерева эквивалентно правому поддереву второго дерева.
Левое поддерево первого дерева эквивалентно правому поддереву второго дерева и правое поддерево первого дерева эквивалентно левому поддереву второго дерева.

3⃣Вернуть true, если выполняется хотя бы одно из этих условий.

😎 Решение:

package main

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

func flipEquiv(root1 *TreeNode, root2 *TreeNode) bool {
    if root1 == nil && root2 == nil {
        return true
    }
    if root1 == nil || root2 == nil {
        return false
    }
    if root1.Val != root2.Val {
        return false
    }
    
    return (flipEquiv(root1.Left, root2.Left) && flipEquiv(root1.Right, root2.Right)) ||
           (flipEquiv(root1.Left, root2.Right) && flipEquiv(root1.Right, root2.Left))
}

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

Задача: 726. Number of Atoms
Сложность: hard

Если задана строковая формула, представляющая химическую формулу, верните количество атомов. Атомный элемент всегда начинается с прописного символа, затем ноль или более строчных букв, представляющих его название. Если количество больше 1, за ним может следовать одна или более цифр, представляющих количество элементов. Например, "H2O" и "H2O2" возможны, а "H1O2" невозможен. Две формулы объединяются вместе, чтобы получить другую формулу. Например, "H2O2He3Mg4" также является формулой.
Формула, заключенная в круглые скобки, и счет (по желанию) также являются формулами. Например, "(H2O2)" и "(H2O2)3" являются формулами.
Возвращает количество всех элементов в виде строки в следующем виде: первое имя (в отсортированном порядке), затем его количество (если это количество больше 1), затем второе имя (в отсортированном порядке), затем его количество (если это количество больше 1) и т. д. Тестовые примеры генерируются таким образом, чтобы все значения в выводе помещались в 32-битное целое число.

Пример:

Input: formula = "H2O"
Output: "H2O"

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

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

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

3⃣После завершения обработки строки, объедините все словари из стека и отсортируйте результат.

😎 Решение:

package main

import (
    "fmt"
    "sort"
    "strconv"
    "unicode"
)

func countOfAtoms(formula string) string {
    stack := []map[string]int{{}}
    n := len(formula)
    i := 0

    for i < n {
        if formula[i] == '(' {
            stack = append(stack, map[string]int{})
            i++
        } else if formula[i] == ')' {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            i++
            iStart := i
            for i < n && unicode.IsDigit(rune(formula[i])) {
                i++
            }
            multiplicity, _ := strconv.Atoi(formula[iStart:i])
            if multiplicity == 0 {
                multiplicity = 1
            }
            for name, count := range top {
                stack[len(stack)-1][name] += count * multiplicity
            }
        } else {
            iStart := i
            i++
            for i < n && unicode.IsLower(rune(formula[i])) {
                i++
            }
            name := formula[iStart:i]
            iStart = i
            for i < n && unicode.IsDigit(rune(formula[i])) {
                i++
            }
            multiplicity, _ := strconv.Atoi(formula[iStart:i])
            if multiplicity == 0 {
                multiplicity = 1
            }
            stack[len(stack)-1][name] += multiplicity
        }
    }

    countMap := stack[0]
    keys := make([]string, 0, len(countMap))
    for key := range countMap {
        keys = append(keys, key)
    }
    sort.Strings(keys)
    result := ""
    for _, name := range keys {
        result += name
        if countMap[name] > 1 {
            result += strconv.Itoa(countMap[name])
        }
    }
    return result
}

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

Задача: 187. Repeated DNA Sequences
Сложность: medium

ДНК состоит из серии нуклеотидов, обозначаемых как 'A', 'C', 'G' и 'T'.

Например, "ACGAATTCCG" — это последовательность ДНК.
При изучении ДНК полезно определять повторяющиеся последовательности внутри молекулы ДНК.

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

Пример:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]

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

1⃣Перебираем начальные позиции последовательности от 1 до 𝑁−𝐿, где 𝑁 — длина строки, а 𝐿 — длина подстроки (в данном случае 10):
Если начальная позиция 𝑠𝑡𝑎𝑟𝑡==0, вычисляем хеш первой последовательности 𝑠[0:𝐿].
В противном случае вычисляем скользящий хеш из предыдущего значения хеша.

2⃣Проверяем хеш в хешсете:
Если хеш уже существует в хешсете, значит, мы нашли повторяющуюся последовательность, и пора обновить вывод.
В противном случае добавляем хеш в хешсет.

3⃣Возвращаем список вывода, содержащий все повторяющиеся последовательности.

😎 Решение:

type MyCircularQueue struct {
    queue     []int
    tailIndex int
    capacity  int
}

func CreateMyCircularQueue(capacity int) MyCircularQueue {
    return MyCircularQueue{make([]int, capacity), 0, capacity}
}

func (q *MyCircularQueue) enQueue(value int) {
    q.queue[q.tailIndex] = value
    q.tailIndex = (q.tailIndex + 1) % q.capacity
}

func (q *MyCircularQueue) get(index int) int

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

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

Дана двумерная бинарная сетка размером m x n, представляющая карту из '1' (земля) и '0' (вода). Верните количество островов.

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

Пример:

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

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

1⃣Обход всей сетки:
- Если найден '1', запускаем поиск в глубину (DFS).

2⃣DFS для пометки острова:
- Заменяем '1' на '0', чтобы избежать повторного посещения.
- Рекурсивно вызываем DFS для всех четырёх направлений.

3⃣Подсчет островов:
- Каждый запуск DFS означает новый остров.
- Увеличиваем счетчик островов.

😎 Решение:

package main

func numIslands(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }

    numIslands := 0
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] == '1' {
                dfs(grid, i, j)
                numIslands++
            }
        }
    }
    return numIslands
}

func dfs(grid [][]byte, r, c int) {
    if r < 0 || c < 0 || r >= len(grid) || c >= len(grid[0]) || grid[r][c] != '1' {
        return
    }

    grid[r][c] = '0'
    dfs(grid, r-1, c)
    dfs(grid, r+1, c)
    dfs(grid, r, c-1)
    dfs(grid, r, c+1)
}

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

Задача: 387. First Unique Character in a String
Сложность: easy

Дана строка s, найдите первый неповторяющийся символ в ней и верните его индекс. Если такого символа не существует, верните -1.

Пример:

Input: s = "leetcode"
Output: 0

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

1⃣Постройте хеш-таблицу, где ключами являются символы строки, а значениями — количество их появлений. Для этого пройдите по строке и для каждого символа увеличивайте его счетчик в хеш-таблице.

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

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

😎 Решение:

package main

import (
  "math/rand"
  "time"
)

type Solution struct {
  original []int
  array    []int
}

func Constructor(nums []int) Solution {
  original := make([]int, len(nums))
  copy(original, nums)
  return Solution{
    original: original,
    array:    append([]int(nil), nums...),
  }
}

func (this *Solution) Reset() []int {
  this.array = append([]int(nil), this.original...)
  return this.original
}

func (this *Solution) Shuffle() []int {
  rand.Seed(time.Now().UnixNano())
  for i := range this.array {
    randIndex := rand.Intn(len(this.array)-i) + i
    this.array[i], this.array[randIndex] = this.array[randIndex], this.array[i]
  }
  return this.array
}

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