Задача: 1485. Clone Binary Tree With Random Pointer
Сложность: medium

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

Дерево представлено в том же формате ввода/вывода, что и обычные бинарные деревья, где каждый узел представлен в виде пары [val, random_index], где:
- val: целое число, представляющее Node.val
- random_index: индекс узла (во входных данных), на который указывает случайный указатель, или null, если он не указывает ни на один узел.

Вам будет дано дерево в классе Node, и вы должны вернуть клонированное дерево в классе NodeCopy. Класс NodeCopy является клоном класса Node с такими же атрибутами и конструкторами.

Пример:

Input: root = [[1,null],null,[4,3],[7,0]]
Output: [[1,null],null,[4,3],[7,0]]
Explanation: The original binary tree is [1,null,4,7].
The random pointer of node one is null, so it is represented as [1, null].
The random pointer of node 4 is node 7, so it is represented as [4, 3] where 3 is the index of node 7 in the array representing the tree.
The random pointer of node 7 is node 1, so it is represented as [7, 0] where 0 is the index of node 1 in the array representing the tree.

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

1⃣Глубокое копирование дерева:
Инициализируйте хэш-таблицу newOldPairs, которая сопоставляет узлы старого дерева с узлами нового дерева.
Создайте функцию deepCopy(root), которая принимает корень данного дерева и возвращает корень нового дерева. Эта функция создаёт новый узел с теми же значениями, что и корневой узел, и рекурсивно копирует левое и правое поддеревья. Затем она сохраняет пару старого и нового узлов в хэш-таблицу и возвращает новый корень.

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

3⃣Возвращение клонированного дерева:
Создайте глубокую копию дерева, используя функцию deepCopy(root), и сопоставьте все случайные указатели нового дерева с помощью функции mapRandomPointers(root). Верните новый корень.

😎 Решение:

type Node struct {
    Val int
    Left *Node
    Right *Node
    Random *Node
}

type NodeCopy struct {
    Val int
    Left *NodeCopy
    Right *NodeCopy
    Random *NodeCopy
}

func deepCopy(root *Node, newOldPairs map[*Node]*NodeCopy) *NodeCopy {
    if root == nil {
        return nil
    }
    newRoot := &NodeCopy{Val: root.Val}
    newRoot.Left = deepCopy(root.Left, newOldPairs)
    newRoot.Right = deepCopy(root.Right, newOldPairs)
    newOldPairs[root] = newRoot
    return newRoot
}

func mapRandomPointers(oldNode *Node, newOldPairs map[*Node]*NodeCopy) {
    if oldNode == nil {
        return
    }
    if newNode, found := newOldPairs[oldNode]; found {
        newNode.Random = newOldPairs[oldNode.Random]
        mapRandomPointers(oldNode.Left, newOldPairs)
        mapRandomPointers(oldNode.Right, newOldPairs)
    }
}

func copyRandomBinaryTree(root *Node) *NodeCopy {
    newOldPairs := make(map[*Node]*NodeCopy)
    newRoot := deepCopy(root, newOldPairs)
    mapRandomPointers(root, newOldPairs)
    return newRoot
}

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

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

Строка со скобками допустима тогда и только тогда, когда: это пустая строка, ее можно записать как AB (A, совмещенное с B), где A и B - допустимые строки, или ее можно записать как (A), где A - допустимая строка. Вам дана строка s со скобками. За один ход вы можете вставить скобку в любую позицию строки. Например, если s = "()))", вы можете вставить открывающую скобку в виде "(()))" или закрывающую скобку в виде "())))". Верните минимальное количество ходов, необходимое для того, чтобы сделать s допустимой.

Пример:

Input: n = 3, goal = 3, k = 1
Output: 6

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

1⃣Инициализировать два счетчика open_needed и close_needed.

2⃣Пройти по строке s символ за символом:
Если текущий символ - открывающая скобка (, увеличьте open_needed.
Если текущий символ - закрывающая скобка ), проверьте:
Если open_needed больше 0, уменьшите open_needed.
Иначе увеличьте close_needed.

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

😎 Решение:

package main

func minAddToMakeValid(s string) int {
    openNeeded := 0
    closeNeeded := 0
    
    for _, char := range s {
        if char == '(' {
            openNeeded++
        } else if char == ')' {
            if openNeeded > 0 {
                openNeeded--
            } else {
                closeNeeded++
            }
        }
    }
    
    return openNeeded + closeNeeded
}

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

Задача: 1237. Find Positive Integer Solution for a Given Equation
Сложность: medium

Если дана вызываемая функция f(x, y) со скрытой формулой и значением z, выполните обратную разработку формулы и верните все пары целых положительных чисел x и y, в которых f(x,y) == z. Пары можно возвращать в любом порядке. Хотя точная формула скрыта, функция является монотонно возрастающей, т.е.Например: f(x, y) < f(x + 1, y) f(x, y) < f(x, y + 1) Интерфейс функции определяется следующим образом: interface CustomFunction { public: // Возвращает некоторое положительное целое число f(x, y) для двух положительных целых чисел x и y на основе формулы.
int f(int x, int y); }; Мы будем оценивать ваше решение следующим образом: у судьи есть список из 9 скрытых реализаций CustomFunction, а также способ сгенерировать ключ ответа из всех допустимых пар для определенного z. Судья получит два входа: function_id (чтобы определить, с какой реализацией тестировать ваш код) и целевое z. Судья вызовет ваш findSolution и сравнит ваши результаты с ключом ответа. Если ваши результаты совпадут с ключом ответа, ваше решение будет принято.

Пример:

Input: function_id = 1, z = 5
Output: [[1,4],[2,3],[3,2],[4,1]]

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

1⃣Начнем с =1 x=1 и 𝑦=1000 y=1000 (предполагаем максимальное значение y).

2⃣Перемещение указателей:
Если 𝑓(𝑥,𝑦)=𝑧
f(x,y)=z, добавляем пару (𝑥,𝑦)(x,y) в результат и увеличиваем x.

3⃣Повторяем шаги до тех пор, пока
𝑥≤1000 x≤1000 и 𝑦≥1y≥1.

😎 Решение:

type CustomFunction struct {}

func (cf CustomFunction) f(x, y int) int {}

func findSolution(customfunction CustomFunction, z int) [][]int {
    result := [][]int{}
    x, y := 1, 1000
    
    for x <= 1000 && y >= 1 {
        value := customfunction.f(x, y)
        if value == z {
            result = append(result, []int{x, y})
            x++
        } else if value < z {
            x++
        } else {
            y--
        }
    }
    
    return result
}

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

Задача: 1217. Minimum Cost to Move Chips to The Same Position
Сложность: easy

У нас есть n фишек, где позиция i-й фишки равна position[i].

Нам нужно переместить все фишки в одну и ту же позицию. За один шаг мы можем изменить позицию i-й фишки с position[i] на:
position[i] + 2 или position[i] - 2 с затратами = 0.
position[i] + 1 или position[i] - 1 с затратами = 1.
Верните минимальные затраты, необходимые для перемещения всех фишек в одну и ту же позицию.

Пример:

Input: position = [2,2,2,3,3]
Output: 2
Explanation: We can move the two chips at position  3 to position 2. Each move has cost = 1. The total cost = 2.

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

1⃣Посчитать количество фишек на четных и нечетных позициях.

2⃣Сравнить количество фишек на четных и нечетных позициях.

3⃣Вернуть минимальное количество фишек как минимальную стоимость для перемещения всех фишек в одну позицию.

😎 Решение:

func minCostToMoveChips(position []int) int {
    evenCount, oddCount := 0, 0
    
    for _, pos := range position {
        if pos % 2 == 0 {
            evenCount++
        } else {
            oddCount++
        }
    }
    
    if evenCount < oddCount {
        return evenCount
    }
    return oddCount
}

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

Задача: 653. Two Sum IV - Input is a BST
Сложность: easy

Вам дан целочисленный массив nums без дубликатов. Из nums можно рекурсивно построить максимальное двоичное дерево, используя следующий алгоритм: создайте корневой узел, значение которого равно максимальному значению в nums. Рекурсивно постройте левое поддерево по префиксу подмассива слева от максимального значения. Рекурсивно постройте правое поддерево по суффиксу подмассива справа от максимального значения. Верните максимальное двоичное дерево, построенное из nums.

Пример:

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

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

1⃣Выполните обход BST и сохраните все значения узлов в набор.

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

3⃣Если найдена такая пара, верните true. Если обход завершен и пары не найдены, верните false.

😎 Решение:

package main

import "fmt"

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

func findTarget(root *TreeNode, k int) bool {
    seen := make(map[int]bool)
    return find(root, k, seen)
}

func find(node *TreeNode, k int, seen map[int]bool) bool {
    if node == nil {
        return false
    }
    if seen[k-node.Val] {
        return true
    }
    seen[node.Val] = true
    return find(node.Left, k, seen) || find(node.Right, k, seen)
}

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

Задача: 403. Frog Jump
Сложность: hard

Если задана строка num, представляющая неотрицательное целое число num, и целое число k, верните наименьшее возможное целое число после удаления k цифр из num.

Пример:

Input: stones = [0,1,3,5,6,8,12,17]
Output: true

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

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

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

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

😎 Решение:

func canCross(stones []int) bool {
    dp := make(map[int]map[int]bool)
    for _, stone := range stones {
        dp[stone] = make(map[int]bool)
    }
    dp[0][0] = true
    
    for _, stone := range stones {
        for jump := range dp[stone] {
            for step := jump - 1; step <= jump + 1; step++ {
                if step > 0 && dp[stone + step] != nil {
                    dp[stone + step][step] = true
                }
            }
        }
    }
    
    return len(dp[stones[len(stones) - 1]]) > 0
}

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

Задача: 227. Basic Calculator II
Сложность: medium

Дана строка s, представляющая выражение. Вычислите это выражение и верните его значение.

Целочисленное деление должно округляться к нулю.

Вы можете предположить, что данное выражение всегда является допустимым. Все промежуточные результаты будут находиться в диапазоне [-2^31, 2^31 - 1].

Примечание: Запрещено использовать какие-либо встроенные функции, которые вычисляют строки как математические выражения, такие как eval().

Пример:

Input: s = "3+2*2"
Output: 7

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

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

2⃣Если операция сложения (+) или вычитания (-), добавляем lastNumber к результату вместо того, чтобы помещать его в стек. Текущее значение currentNumber будет обновлено на lastNumber для следующей итерации.

3⃣Если операция умножения (*) или деления (/), вычисляем выражение lastNumber * currentNumber и обновляем lastNumber с результатом выражения. Это значение будет добавлено к результату после сканирования всей строки.

😎 Решение:

package main

import (
    "strconv"
    "unicode"
)

func calculate(s string) int {
    length := len(s)
    if length == 0 {
        return 0
    }
    currentNumber, lastNumber, result := 0, 0, 0
    sign := '+'
    
    for i := 0; i < length; i++ {
        currentChar := rune(s[i])
        if unicode.IsDigit(currentChar) {
            num, _ := strconv.Atoi(string(currentChar))
            currentNumber = (currentNumber * 10) + num
        }
        if !unicode.IsDigit(currentChar) && !unicode.IsSpace(currentChar) || i == length-1 {
            if sign == '+' || sign == '-' {
                result += lastNumber
                lastNumber = currentNumber
                if sign == '-' {
                    lastNumber = -currentNumber
                }
            } else if sign == '*' {
                lastNumber *= currentNumber
            } else if sign == '/' {
                lastNumber /= currentNumber
            }
            sign = currentChar
            currentNumber = 0
        }
    }
    result += lastNumber
    return result
}

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

Задача: 999. Available Captures for Rook
Сложность: easy

Вам дана матрица 8 x 8, изображающая шахматную доску. На ней есть ровно одна белая ладья, представленная символом "R", некоторое количество белых слонов "B" и некоторое количество черных пешек "p". Пустые клетки обозначаются символом '.'. Ладья может перемещаться на любое количество клеток по горизонтали или вертикали (вверх, вниз, влево, вправо), пока не достигнет другой фигуры или края доски. Ладья атакует пешку, если она может переместиться на ее клетку за один ход. Примечание: Ладья не может перемещаться через другие фигуры, такие как слоны или пешки. Это означает, что ладья не может атаковать пешку, если путь ей преграждает другая фигура. Верните количество пешек, которые атакует белая ладья.

Пример:

Input: board = [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]

Output: 3

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

1⃣Поиск ладьи:
Найдите координаты белой ладьи "R" на шахматной доске.

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

3⃣Подсчет атакованных пешек:
Если встреченная фигура - черная пешка "p", увеличьте счетчик атакованных пешек.
Если встреченная фигура - белый слон "B" или край доски, остановитесь в этом направлении.

😎 Решение:

func numRookCaptures(board [][]byte) int {
    countPawns := func(x, y, dx, dy int) int {
        for x >= 0 && x < 8 && y >= 0 && y < 8 {
            if board[x][y] == 'B' {
                break
            }
            if board[x][y] == 'p' {
                return 1
            }
            x += dx
            y += dy
        }
        return 0
    }

    for i := 0; i < 8; i++ {
        for j := 0; j < 8; j++ {
            if board[i][j] == 'R' {
                return countPawns(i, j, -1, 0) + countPawns(i, j, 1, 0) +
                       countPawns(i, j, 0, -1) + countPawns(i, j, 0, 1)
            }
        }
    }
    return 0
}

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

Задача: 73. Set Matrix Zeroes
Сложность: medium

Дана матрица размером m×n, состоящая из целых чисел. Если элемент матрицы равен 0, установите в 0 все элементы его строки и столбца.

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

Пример:

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

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

1⃣Мы перебираем матрицу и отмечаем первую ячейку строки i и первую ячейку столбца j, если условие в приведенном выше псевдокоде выполняется, т.е. если cell[i][j] == 0.

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

3⃣Теперь мы перебираем исходную матрицу, начиная со второй строки и второго столбца, т.е. с matrix[1][1]. Для каждой ячейки мы проверяем, были ли ранее отмечены строка r или столбец c, проверяя соответствующую первую ячейку строки или первую ячейку столбца. Если любая из них была отмечена, мы устанавливаем значение в ячейке на 0. Обратите внимание, что первая строка и первый столбец служат как row_set и column_set, которые мы использовали в первом подходе. Затем мы проверяем, равна ли cell[0][0] нулю, если это так, мы отмечаем первую строку как ноль. И, наконец, если первый столбец был отмечен, мы делаем все записи в нем нулевыми.

😎 Решение:

func setZeroes(matrix [][]int) {
    isCol := false
    R := len(matrix)
    C := len(matrix[0])
    for i := 0; i < R; i++ {
        if matrix[i][0] == 0 {
            isCol = true
        }
        for j := 1; j < C; j++ {
            if matrix[i][j] == 0 {
                matrix[0][j] = 0
                matrix[i][0] = 0
            }
        }
    }
    for i := 1; i < R; i++ {
        for j := 1; j < C; j++ {
            if matrix[i][0] == 0 || matrix[0][j] == 0 {
                matrix[i][j] = 0
            }
        }
    }
    if matrix[0][0] == 0 {
        for j := 0; j < C; j++ {
            matrix[0][j] = 0
        }
    }
    if isCol {
        for i := 0; i < R; i++ {
            matrix[i][0] = 0
        }
    }
}

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

Задача: 1161. Maximum Level Sum of a Binary Tree
Сложность: medium

Дано корневое дерево, уровень корня которого равен 1, уровень его детей равен 2 и так далее.

Верните наименьший уровень x, такой что сумма всех значений узлов на уровне x максимальна.

Пример:

Input: root = [1,7,0,7,-8,null,null]
Output: 2
Explanation: 
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.

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

1⃣Создайте целочисленную переменную maxSum для отслеживания максимальной суммы значений узлов на любом уровне, начав с большого отрицательного значения. Создайте переменную ans для хранения ответа на задачу. Создайте переменную level для хранения текущего уровня, через который мы проходим, и инициализируйте её значением 0. Инициализируйте очередь q типа TreeNode и добавьте в неё корень.

2⃣Выполните обход в ширину (BFS) до тех пор, пока очередь не станет пустой: увеличьте level на 1 и инициализируйте sumAtCurrentLevel = 0 для вычисления суммы всех значений узлов на этом уровне. Проходите через все узлы на уровне, используя только q.size() количество узлов. Внутри этого внутреннего цикла извлекайте все узлы на текущем уровне один за другим, добавляя их значения к sumAtCurrentLevel и добавляя левых и правых детей (если они существуют) в очередь. Поймите, что после прохождения всех узлов на уровне в очереди остаются только узлы уровня +1.

3⃣После прохождения всех узлов на уровне проверьте, больше ли sumAtCurrentLevel, чем maxSum. Если maxSum < sumAtCurrentLevel, обновите переменную ответа на ans = level и установите maxSum = sumAtCurrentLevel. Верните ans.

😎 Решение

func maxLevelSum(root *TreeNode) int {
    maxSum := math.MinInt32
    ans := 0
    level := 0
    q := []*TreeNode{root}
    
    for len(q) > 0 {
        level++
        sumAtCurrentLevel := 0
        nextQ := []*TreeNode{}
        for _, node := range q {
            sumAtCurrentLevel += node.Val
            if node.Left != nil {
                nextQ = append(nextQ, node.Left)
            }
            if node.Right != nil {
                nextQ = append(nextQ, node.Right)
            }
        }
        q = nextQ
        
        if maxSum < sumAtCurrentLevel {
            maxSum = sumAtCurrentLevel
            ans = level
        }
    }
    
    return ans
}

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

Задача: 1018. Binary Prefix Divisible By 5
Сложность: easy

Вам дан двоичный массив nums (индексированный 0). Мы определяем xi как число, двоичным представлением которого является подмассив nums[0..i] (от старшего бита к младшему). Например, если nums = [1,0,1], то x0 = 1, x1 = 2 и x2 = 5. Верните массив булевых чисел answer, где answer[i] истинно, если xi делится на 5.

Пример:

Input: nums = [0,1,1]
Output: [true,false,false]

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

1⃣Инициализация и вычисление:
Создайте переменную x для хранения текущего числа в десятичной системе.
Создайте пустой массив answer для хранения результатов делимости на 5.

2⃣Итерация по массиву:
Пройдите по всем элементам массива nums. Для каждого элемента:
Обновите значение x, учитывая текущий бит.
Проверяйте, делится ли x на 5, и добавьте результат (true или false) в массив answer.
Чтобы избежать переполнения, используйте модуль 5 для переменной x.

3⃣Возврат результата:
Верните массив answer с результатами проверки делимости на 5.

😎 Решение:

func prefixesDivBy5(nums []int) []bool {
    x := 0
    answer := make([]bool, len(nums))
    for i, num := range nums {
        x = (x * 2 + num) % 5
        answer[i] = x == 0
    }
    return answer
}

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

Задача: 90. Subsets II
Сложность: medium

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

Пример:

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

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

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

2⃣Создайте множество seen для хранения уникальных хешей подмножеств. Итерируйте от 0 до 2^n - 1, используя биты в числе как индикатор включения элементов.

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

😎 Решение:

func subsetsWithDup(nums []int) [][]int {
    n := len(nums)
    sort.Ints(nums)
    subsets := make([][]int, 0)
    maxNumberOfSubsets := 1 << n
    seen := make(map[string]bool)
    for subsetIndex := 0; subsetIndex < maxNumberOfSubsets; subsetIndex++ {
        currentSubset := make([]int, 0)
        hashcode := ""
        for j := 0; j < n; j++ {
            if (subsetIndex>>j)&1 == 1 {
                currentSubset = append(currentSubset, nums[j])
                hashcode += strconv.Itoa(nums[j]) + ","
            }
        }
        if !seen[hashcode] {
            subsets = append(subsets, currentSubset)
            seen[hashcode] = true
        }
    }
    return subsets
}

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

Задача: 1014. Best Sightseeing Pair
Сложность: medium

Вам дан целочисленный массив values, в котором values[i] представляет собой значение i-й достопримечательности. Две достопримечательности i и j имеют расстояние j - i между собой. Оценка пары (i < j) достопримечательностей равна values[i] + values[j] + i - j: сумма значений достопримечательностей минус расстояние между ними. Возвращается максимальная оценка пары достопримечательностей.

Пример:

Input: values = [8,1,5,2,6]
Output: 11

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

1⃣Инициализация переменных:
Инициализируйте переменную max_score для хранения максимальной оценки пары.
Инициализируйте переменную max_i_plus_value для хранения максимального значения выражения values[i] + i при проходе по массиву.

2⃣Проход по массиву:
Пройдитесь по массиву начиная с первого элемента и для каждого элемента values[j] вычислите текущую оценку пары как values[j] - j + max_i_plus_value.
Обновите значение max_score, если текущая оценка больше.
Обновите значение max_i_plus_value, если текущий элемент values[j] + j больше предыдущего max_i_plus_value.

3⃣Возврат результата:
Верните значение max_score как максимальную оценку пары достопримечательностей.

😎 Решение:

func maxScoreSightseeingPair(values []int) int {
    maxScore := 0
    maxIPlusValue := values[0]
    
    for j := 1; j < len(values); j++ {
        maxScore = max(maxScore, maxIPlusValue + values[j] - j)
        maxIPlusValue = max(maxIPlusValue, values[j] + j)
    }
    
    return maxScore
}

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

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

Задача: 624. Maximum Distance in Arrays
Сложность: medium

Вам дано m массивов, где каждый массив отсортирован по возрастанию. Вы можете взять два целых числа из двух разных массивов (каждый массив выбирает одно) и вычислить расстояние. Мы определяем расстояние между двумя целыми числами a и b как их абсолютную разность |a - b|. Верните максимальное расстояние.

Пример:

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

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

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

2⃣Рассчитайте максимальное расстояние между минимальным и максимальным элементами.

3⃣Верните это максимальное расстояние.

😎 Решение:

package main

import (
    "math"
)

func maxDistance(arrays [][]int) int {
    minVal := arrays[0][0]
    maxVal := arrays[0][len(arrays[0])-1]
    maxDistance := 0
    
    for i := 1; i < len(arrays); i++ {
        maxDistance = int(math.Max(float64(maxDistance), math.Max(float64(abs(arrays[i][len(arrays[i])-1]-minVal)), float64(abs(arrays[i][0]-maxVal)))))
        minVal = int(math.Min(float64(minVal), float64(arrays[i][0])))
        maxVal = int(math.Max(float64(maxVal), float64(arrays[i][len(arrays[i])-1])))
    }
    
    return maxDistance
}

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

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

Задача: 413. Arithmetic Slices
Сложность: medium

Целочисленный массив называется арифметическим, если он состоит не менее чем из трех элементов и если разность между любыми двумя последовательными элементами одинакова. Например, [1,3,5,7,9], [7,7,7] и [3,-1,-5,-9] являются арифметическими последовательностями. Если задан целочисленный массив nums, верните количество арифметических подмассивов массива nums. Подмассив - это непрерывная подпоследовательность массива.

Пример:

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

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

1⃣Пройдите по массиву, инициализируя два указателя: начальный и текущий. Начните с первой пары элементов.

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

3⃣Суммируйте количество найденных арифметических подмассивов, учитывая, что для каждого арифметического подмассива длины len, количество таких подмассивов равно (len - 2).

😎 Решение:

package main

func numberOfArithmeticSlices(nums []int) int {
    count := 0
    currentLength := 0
    for i := 2; i < len(nums); i++ {
        if nums[i]-nums[i-1] == nums[i-1]-nums[i-2] {
            currentLength++
            count += currentLength
        } else {
            currentLength = 0
        }
    }
    return count
}

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

Задача: 1273. Delete Tree Nodes
Сложность: medium

Дерево, укорененное в узле 0, задано следующим образом: количество узлов - nodes; значение i-го узла - value[i]; родитель i-го узла - parent[i]. Удалите все поддеревья, сумма значений узлов которых равна нулю. Верните количество оставшихся узлов в дереве.

Пример:
Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]
Output: 2

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

1⃣Постройте дерево из заданных узлов, значений и родителей.

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

3⃣Удалите отмеченные узлы и их поддеревья и верните количество оставшихся узлов.

😎 Решение:

func deleteTreeNodes(nodes int, parent []int, value []int) int {
    tree := make(map[int][]int)
    for i := 0; i < nodes; i++ {
        tree[parent[i]] = append(tree[parent[i]], i)
    }

    var dfs func(node int) (int, int)
    dfs = func(node int) (int, int) {
        totalSum := value[node]
        totalCount := 1
        for _, child := range tree[node] {
            childSum, childCount := dfs(child)
            totalSum += childSum
            totalCount += childCount
        }
        if totalSum == 0 {
            return 0, 0
        }
        return totalSum, totalCount
    }

    _, count := dfs(0)
    return count
}

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

Задача: 1413. Minimum Value to Get Positive Step by Step Sum
Сложность: easy

Дан массив целых чисел nums, вы начинаете с начального положительного значения startValue.

На каждой итерации вы вычисляете поэтапную сумму startValue плюс элементы из nums (слева направо).

Верните минимальное положительное значение startValue, такое что поэтапная сумма никогда не будет меньше 1.

Пример:

Input: nums = [-3,2,-3,4,2]
Output: 5
Explanation: If you choose startValue = 4, in the third iteration your step by step sum is less than 1.
step by step sum
startValue = 4 | startValue = 5 | nums
  (4 -3 ) = 1  | (5 -3 ) = 2    |  -3
  (1 +2 ) = 3  | (2 +2 ) = 4    |   2
  (3 -3 ) = 0  | (4 -3 ) = 1    |  -3
  (0 +4 ) = 4  | (1 +4 ) = 5    |   4
  (4 +2 ) = 6  | (5 +2 ) = 7    |   2

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

1⃣Инициализируйте переменные startValue со значением 1 и total со значением startValue.

2⃣Итеративно добавляйте каждый элемент массива nums к total и проверяйте, не опускается ли total ниже 1.

3⃣Если total падает ниже 1, увеличьте startValue на 1 и повторите шаги 2-3. Если total остается не менее 1, верните текущее значение startValue.

😎 Решение:

func minStartValue(nums []int) int {
    startValue := 1
    for {
        total := startValue
        isValid := true
        for _, num := range nums {
            total += num
            if total < 1 {
                isValid = false
                break
            }
        }
        if isValid {
            return startValue
        }
        startValue++
    }
}

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

Задача: 119. Pascal's Triangle ll
Сложность: easy

Для данного целого числа rowIndex верните rowIndex-ю строку (нумерация с нуля) треугольника Паскаля.

Пример:

Input: rowIndex = 3  
Output: [1,3,3,1]  

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

1⃣Рекурсивная формула:
- Используем формулу треугольника Паскаля:
getNum(row, col) = getNum(row-1, col-1) + getNum(row-1, col)

2⃣Базовые случаи:
- Все граничные значения равны 1:
- getNum(0, _) = 1
- getNum(k, 0) = 1, getNum(k, k) = 1

3⃣Формирование строки:
- Для каждого col от 0 до rowIndex, вычисляем getNum(rowIndex, col)
- Добавляем в результирующий срез.

😎 Решение:

func getNum(row int, col int) int {
    if row == 0 || col == 0 || row == col {
        return 1
    }
    return getNum(row-1, col-1) + getNum(row-1, col)
}

func getRow(rowIndex int) []int {
    ans := make([]int, rowIndex+1)
    for i := 0; i <= rowIndex; i++ {
        ans[i] = getNum(rowIndex, i)
    }
    return ans
}

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

Задача: 538. Convert BST to Greater Tree
Сложность: medium

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

Пример:

Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

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

1⃣Поддерживаем глобальную переменную sum, чтобы хранить накопленную сумму всех уже посещённых узлов.

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

3⃣Обновляем текущий узел: root.Val = root.Val + sum, затем обновляем sum.

😎 Решение:

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

type Solution struct {
    sum int
}

func (s *Solution) ConvertBST(root *TreeNode) *TreeNode {
    if root != nil {
        s.ConvertBST(root.Right)
        s.sum += root.Val
        root.Val = s.sum
        s.ConvertBST(root.Left)
    }
    return root
}

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

Задача: №18. 4Sum
Сложность: medium

Учитывая массив nums из n целых чисел, верните массив всех уникальных четверок [nums[a], nums[b], nums[c], nums[d]], таких что:
- 0 <= a, b, c, d < n,
- a, b, c и d — различны,
- nums[a] + nums[b] + nums[c] + nums[d] == target.

Пример:

Input: nums = [1,0,-1,0,-2,2], target = 0  
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]  

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

1⃣Сортировка и фиксирование первых двух чисел:
- Отсортируйте массив.
- Пройдитесь по массиву двумя вложенными циклами: первый фиксирует i, второй — j.
- Пропускайте дубликаты, чтобы избежать повторяющихся комбинаций.

2⃣Два указателя для поиска оставшейся пары:
- Установите start = j + 1, end = len(nums) - 1.
- Пока start < end, вычисляйте сумму четырех чисел.
- Если сумма меньше target — двигайте start.
- Если больше — двигайте end.
- Если равна target — добавьте комбинацию в результат и сдвиньте оба указателя, пропуская дубликаты.

3⃣Возврат результата:
- После завершения всех итераций верните массив уникальных четверок, сумма которых равна target.

😎 Решение:

func fourSum(nums []int, target int) [][]int {
    sort.Ints(nums)
    res := [][]int{}

    for i := 0; i < len(nums)-3; i++ {
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        for j := i + 1; j < len(nums)-2; j++ {
            if j > i+1 && nums[j] == nums[j-1] {
                continue
            }

            start := j + 1
            end := len(nums) - 1

            for start < end {
                sum := nums[i] + nums[j] + nums[start] + nums[end]
                if sum < target {
                    start++
                } else if sum > target {
                    end--
                } else {
                    res = append(res, []int{nums[i], nums[j], nums[start], nums[end]})
                    start++
                    end--
                    for start < end && nums[start] == nums[start-1] {
                        start++
                    }
                    for start < end && nums[end] == nums[end+1] {
                        end--
                    }
                }
            }
        }
    }
    return res
}

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

Задача: 841. Keys and Rooms
Сложность: medium

Есть n комнат, пронумерованных от 0 до n - 1, и все комнаты закрыты, кроме комнаты 0. Ваша цель — посетить все комнаты. Однако вы не можете войти в закрытую комнату, не имея ключа от нее.
Когда вы посещаете комнату, вы можете найти в ней набор различных ключей. Каждый ключ имеет номер, указывающий, какую комнату он открывает, и вы можете взять их все с собой, чтобы открыть другие комнаты.

Дан массив rooms, где rooms[i] — это набор ключей, которые вы можете получить, если посетите комнату i. Верните true, если вы можете посетить все комнаты, или false в противном случае.

Пример:

Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation: 
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.

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

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

2⃣Поместите ключ от комнаты 0 в стек и отметьте комнату 0 как посещенную.

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

😎 Решение:

func canVisitAllRooms(rooms [][]int) bool {
    seen := make([]bool, len(rooms))
    seen[0] = true
    stack := []int{0}

    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        for _, nei := range rooms[node] {
            if !seen[nei] {
                seen[nei] = true
                stack = append(stack, nei)
            }
        }
    }

    for _, v := range seen {
        if !v {
            return false
        }
    }
    return true
}

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