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

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

Задача: 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons
Сложность: hard

Вам даны три целых числа n, m и k. Рассмотрим следующий алгоритм для нахождения максимального элемента в массиве положительных целых чисел:

maximum_value = -1
maximum_index = -1
search_cost = 0
n = arr.length
for (i = 0; i < n; i++){
      if (maximum_value  < arr[i]){
           maximum_value  = arr[i]
           maximum_index = i
           search_cost = search_cost + 1
      }
}
return maximum_index

Вам необходимо построить массив arr, который имеет следующие свойства:
arr содержит ровно n целых чисел.
1 <= arr[i] <= m, где (0 <= i < n).
После применения указанного алгоритма к arr, значение search_cost равно k.
Верните количество способов построить массив arr с учетом указанных условий. Так как ответ может быть очень большим, ответ должен быть вычислен по модулю 10^9 + 7.

Пример:

Input: n = 2, m = 3, k = 1
Output: 6
Explanation: The possible arrays are [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]

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

1⃣Инициализация и базовые случаи: Инициализируем 3D массив dp размером [n+1][m+1][k+1]. Устанавливаем базовые случаи: dp[n][...][0] = 1.

2⃣Итерация и обновление массива dp: Проходим в обратном порядке по индексам i от n-1 до 0, по maxSoFar от m до 0 и по remain от 0 до k. Для каждого из этих значений обновляем dp массив, используя предыдущие результаты для вычисления текущих значений.

3⃣Возврат результата: Возвращаем значение dp[0][0][k], которое является решением исходной задачи.

😎 Решение:

package main

func numOfArrays(n int, m int, k int) int {
    const MOD = 1_000_000_007
    dp := make([][][]int, n+1)
    for i := range dp {
        dp[i] = make([][]int, m+1)
        for j := range dp[i] {
            dp[i][j] = make([]int, k+1)
        }
    }

    for num := 0; num <= m; num++ {
        dp[n][num][0] = 1
    }

    for i := n - 1; i >= 0; i-- {
        for maxSoFar := m; maxSoFar >= 0; maxSoFar-- {
            for remain := 0; remain <= k; remain++ {
                ans := 0
                for num := 1; num <= maxSoFar; num++ {
                    ans = (ans + dp[i+1][maxSoFar][remain]) % MOD
                }

                if remain > 0 {
                    for num := maxSoFar + 1; num <= m; num++ {
                        ans = (ans + dp[i+1][num][remain-1]) % MOD
                    }
                }

                dp[i][maxSoFar][remain] = ans
            }
        }
    }

    return dp[0][0][k]
}

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

Задача: 969. Pancake Sorting
Сложность: medium

Дан массив целых чисел arr, отсортируйте массив, выполняя серию переворотов блинов.

При одном перевороте блина мы выполняем следующие шаги:

Выбираем целое число k, где 1 <= k <= arr.length.
Переворачиваем подмассив arr[0...k-1] (индексация с 0).
Например, если arr = [3,2,1,4] и мы выполнили переворот блина, выбрав k = 3, мы переворачиваем подмассив [3,2,1], так что arr = [1,2,3,4] после переворота блина при k = 3.

Верните массив значений k, соответствующих последовательности переворотов блинов, которая сортирует arr. Любой допустимый ответ, который сортирует массив за количество переворотов не более чем 10 * arr.length, будет считаться правильным.

Пример:

Input: arr = [3,2,4,1]
Output: [4,2,4,3]
Explanation: 
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: arr = [3, 2, 4, 1]
After 1st flip (k = 4): arr = [1, 4, 2, 3]
After 2nd flip (k = 2): arr = [4, 1, 2, 3]
After 3rd flip (k = 4): arr = [3, 2, 1, 4]
After 4th flip (k = 3): arr = [1, 2, 3, 4], which is sorted.

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

1⃣Вдохновляясь пузырьковой сортировкой, начнем с реализации функции flip(list, k), которая выполняет переворот блина на префиксе list[0
] (в Python).

2⃣Основной алгоритм выполняет цикл по значениям списка, начиная с наибольшего.

3⃣На каждом этапе определяем значение для сортировки (назовем его value_to_sort), которое является числом, которое мы будем ставить на место на этом этапе. Затем находим индекс value_to_sort. Если value_to_sort еще не на своем месте, выполняем максимум два переворота блинов, как объяснено в интуиции. В конце этапа value_to_sort будет на своем месте.

😎 Решение:

package main

func pancakeSort(A []int) []int {
    var ans []int

    for valueToSort := len(A); valueToSort > 0; valueToSort-- {
        index := find(A, valueToSort)
        if index == valueToSort-1 {
            continue
        }
        if index != 0 {
            ans = append(ans, index+1)
            flip(A, index+1)
        }
        ans = append(ans, valueToSort)
        flip(A, valueToSort)
    }

    return ans
}

func flip(sublist []int, k int) {
    i := 0
    for i < k/2 {
        sublist[i], sublist[k-i-1] = sublist[k-i-1], sublist[i]
        i++
    }
}

func find(a []int, target int) int {
    for i, v := range a {
        if v == target {
            return i
        }
    }
    return -1
}

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

Задача: 1009. Complement of Base 10 Integer
Сложность: easy

Дополнение целого числа - это целое число, которое получается, если перевернуть все 0 в 1 и все 1 в 0 в его двоичном представлении. Например, целое число 5 - это "101" в двоичном представлении, а его дополнение - "010", то есть целое число 2. Если задано целое число n, верните его дополнение.

Пример:

Input: n = 5
Output: 2

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

1⃣Определение длины двоичного представления:
Найдите длину двоичного представления числа n.

2⃣Создание маски:
Создайте маску, которая состоит из всех единиц и имеет ту же длину, что и двоичное представление числа n.

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

😎 Решение:

func findComplement(num int) int {
    length := 0
    for i := num; i > 0; i >>= 1 {
        length++
    }
    mask := (1 << length) - 1
    return num ^ mask
}

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