Задача: №35. Search Insert Position
Сложность: easy

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

Вы должны написать алгоритм со сложностью O(log n).

Пример:

Input: nums = [1,3,5,6], target = 5  
Output: 2  

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

1⃣Инициализировать два указателя: left = 0, right = n - 1.

2⃣Бинарный поиск:
- Вычислить pivot = left + (right - left) / 2.
- Если nums[pivot] == target, вернуть pivot.
- Если target < nums[pivot], искать в левом подмассиве (right = pivot - 1).
- Если target > nums[pivot], искать в правом подмассиве (left = pivot + 1).

3⃣Вернуть `left` – это позиция, где target должен быть вставлен.

😎Решение:

func searchInsert(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        pivot := left + (right-left)/2
        if nums[pivot] == target {
            return pivot
        } else if target < nums[pivot] {
            right = pivot - 1
        } else {
            left = pivot + 1
        }
    }
    return left
}

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

Задача: 1013. Partition Array Into Three Parts With Equal Sum
Сложность: easy

Если задан массив целых чисел arr, верните true, если мы можем разбить массив на три непустые части с равными суммами. Формально, мы можем разбить массив, если можем найти индексы i + 1 < j с (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1])

Пример:

Input: arr = [0,2,1,-6,6,-7,9,1,2,0,1]
Output: true

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

1⃣Вычисление общей суммы:
Вычислите общую сумму всех элементов массива. Если эта сумма не делится на 3 без остатка, вернуть false, так как невозможно разбить массив на три части с равной суммой.

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

3⃣Проверка третьей части:
Убедитесь, что оставшаяся часть массива также имеет ту же сумму, что и две найденные части. Если да, вернуть true, иначе false.

😎 Решение:

func canThreePartsEqualSum(arr []int) bool {
    totalSum := 0
    for _, num := range arr {
        totalSum += num
    }
    if totalSum % 3 != 0 {
        return false
    }
    
    target := totalSum / 3
    partSum, count, n := 0, 0, len(arr)
    
    for i := 0; i < n; i++ {
        partSum += arr[i]
        if partSum == target {
            count++
            partSum = 0
            if count == 2 && i < n - 1 {
                return true
            }
        }
    }
    
    return false
}

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

Задача: 1271. Hexspeak
Сложность: easy

Десятичное число можно преобразовать в его шестнадцатеричное представление, сначала преобразовав его в прописную шестнадцатеричную строку, а затем заменив все вхождения цифры '0' на букву 'O', а цифры '1' - на букву 'I'. Такое представление допустимо тогда и только тогда, когда оно состоит только из букв набора {'A', 'B', 'C', 'D', 'E', 'F', 'I', 'O'}. Получив строку num, представляющую десятичное целое число n, верните шестнадцатеричное представление n, если оно допустимо, иначе верните "ERROR".

Пример:
Input: num = "257"
Output: "IOI"

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

1⃣Преобразуйте десятичное число в шестнадцатеричную строку в верхнем регистре.

2⃣Замените все вхождения цифры '0' на букву 'O', а цифры '1' на букву 'I'

3⃣Проверьте, что преобразованная строка содержит только допустимые символы. Если это так, верните строку, иначе верните "ERROR".

😎 Решение:

import (
    "strconv"
    "strings"
)

func toHexString(num string) string {
    n, _ := strconv.ParseInt(num, 10, 64)
    hexStr := strings.ToUpper(strconv.FormatInt(n, 16))
    hexStr = strings.ReplaceAll(hexStr, "0", "O")
    hexStr = strings.ReplaceAll(hexStr, "1", "I")
    for _, char := range hexStr {
        if !strings.Contains("ABCDEFIO", string(char)) {
            return "ERROR"
        }
    }
    return hexStr
}

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

Задача: 163. Missing Ranges
Сложность: easy

Вам дан диапазон [lower, upper] и отсортированный массив уникальных целых чисел nums, где все элементы находятся в этом диапазоне.

Число x считается пропущенным, если оно находится в диапазоне [lower, upper] и его нет в массиве nums.

Верните кратчайший отсортированный список диапазонов, который точно покрывает все пропущенные числа. То есть ни один элемент из nums не включен в какой-либо из диапазонов, и каждое пропущенное число покрыто одним из диапазонов..

Пример:

Input: nums = [-1], lower = -1, upper = -1
Output: []
Explanation: There are no missing ranges since there are no missing numbers.

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

1⃣Инициализация и проверка начальных условий:
Создайте переменную n и инициализируйте её размером массива nums.
Создайте список missingRanges, который будет содержать решение задачи.
Если массив nums пуст, верните диапазон [lower, upper].
Проверьте, совпадает ли первый элемент массива с lower. Если lower < nums[0], добавьте в missingRanges диапазон [lower, nums[0] - 1].

2⃣Итерация по элементам массива:
Проитерируйте по всем элементам в nums с помощью цикла от i = 0 до n - 2 (до предпоследнего элемента):
Если текущий элемент nums[i] и следующий элемент nums[i + 1] отличаются на 1 или меньше, между этими двумя числами нет пропущенных чисел.
В противном случае, если nums[i + 1] - nums[i] > 1, то пропущены числа от nums[i] + 1 до nums[i + 1] - 1 (включительно). В этом случае диапазон [nums[i] + 1, nums[i + 1] - 1] добавляется в missingRanges.

3⃣Проверка и добавление последнего пропущенного диапазона:
Проверьте, совпадает ли последний элемент массива с upper. Если nums[n - 1] < upper, добавьте в missingRanges диапазон [nums[n - 1] + 1, upper].

😎 Решение:

func findMissingRanges(nums []int, lower int, upper int) [][]int {
    n := len(nums)
    missingRanges := make([][]int, 0)
    if n == 0 {
        missingRanges = append(missingRanges, []int{lower, upper})
        return missingRanges
    
    if lower < nums[0] {
        missingRanges = append(missingRanges, []int{lower, nums[0] - 1})
    }    for i := 0; i < n-1; i++ {
        if nums[i+1]-nums[i] <= 1 {
            continue
        }
        missingRanges = append(missingRanges, []int{nums[i] + 1, nums[i+1] - 1})
    }
    if upper > nums[n-1] {
        missingRanges = append(missingRanges, []int{nums[n-1] + 1, upper})
    }

    return missingRanges
}

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

Задача: №57. Insert Interval
Сложность: medium

Вам дан массив непересекающихся интервалов intervals, где intervals[i] = [starti, endi] представляет начало и конец i-го интервала, и массив intervals отсортирован в порядке возрастания по starti. Вам также дан интервал newInterval = [start, end], представляющий начало и конец другого интервала.

Вставьте newInterval в массив intervals так, чтобы intervals оставался отсортированным в порядке возрастания по starti и в intervals не было бы перекрывающихся интервалов (при необходимости объедините перекрывающиеся интервалы).

Верните массив intervals после вставки.

Обратите внимание, что не обязательно модифицировать массив intervals на месте. Вы можете создать новый массив и вернуть его.

Пример:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

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

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

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

3⃣Обработка интервалов после вставки:
Проходим через оставшиеся интервалы после индекса i и добавляем их в массив res. Это включает интервалы, которые следуют после нового интервала и не перекрываются с ним.
Возвращаем массив res, содержащий все интервалы с корректно вставленным новым интервалом.

😎 Решение:

func insert(intervals [][]int, newInterval []int) [][]int {
    n := len(intervals)
    i := 0
    res := make([][]int, 0)

    for i < n && intervals[i][1] < newInterval[0] {
        res = append(res, intervals[i])
        i++
    }

    for i < n && newInterval[1] >= intervals[i][0] {
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i++
    }
    res = append(res, newInterval)

    for i < n {
        res = append(res, intervals[i])
        i++
    }

    return res
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

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

Задача: 643. Maximum Average Subarray I
Сложность: easy

Вам дан целочисленный массив nums, состоящий из n элементов, и целое число k. Найдите смежный подмассив, длина которого равна k и который имеет максимальное среднее значение, и верните это значение. Принимается любой ответ с погрешностью вычислений менее 10-5.

Пример:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000

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

1⃣Инициализация скользящего окна
Вычислите сумму первых k элементов массива nums. Это будет начальное значение максимальной суммы.

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

3⃣Обновление максимальной суммы
На каждом шаге обновляйте максимальную сумму, если текущая сумма больше, и в конце верните среднее значение этой суммы.

😎 Решение:

package main

func findMaxAverage(nums []int, k int) float64 {
    currentSum := 0
    for i := 0; i < k; i++ {
        currentSum += nums[i]
    }
    maxSum := currentSum
    
    for i := k; i < len(nums); i++ {
        currentSum += nums[i] - nums[i - k]
        if currentSum > maxSum {
            maxSum = currentSum
        }
    }
    
    return float64(maxSum) / float64(k)
}

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

Задача: 717. 1-bit and 2-bit Characters
Сложность: easy

У нас есть два специальных символа: первый символ может быть представлен одним битом 0. Второй символ может быть представлен двумя битами (10 или 11). Если задан двоичный массив bits, который заканчивается 0, верните true, если последний символ должен быть однобитным.

Пример:

Input: bits = [1,0,0]
Output: true

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

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

2⃣Пройдите по массиву, увеличивая индекс на 1, если текущий бит равен 0, и на 2, если текущий бит равен 1.

3⃣Проверьте, достиг ли индекс последнего элемента массива, и верните результат.

😎 Решение:

package main

func isOneBitCharacter(bits []int) bool {
    i := 0
    for i < len(bits) - 1 {
        i += bits[i] + 1
    }
    return i == len(bits) - 1
}

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

Задача: 690. Employee Importance
Сложность: medium

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

Вам дан массив сотрудников employees, где:

employees[i].id — это идентификатор i-го сотрудника.
employees[i].importance — значение важности i-го сотрудника.
employees[i].subordinates — список идентификаторов прямых подчиненных i-го сотрудника.
Дан целочисленный id, представляющий идентификатор сотрудника. Верните суммарное значение важности этого сотрудника и всех его прямых и косвенных подчиненных.

Пример:

Input: employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 1
Output: 11
Explanation: Employee 1 has an importance value of 5 and has two direct subordinates: employee 2 and employee 3.
They both have an importance value of 3.
Thus, the total importance value of employee 1 is 5 + 3 + 3 = 11.

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

1⃣Создайте хеш-таблицу emap для быстрого доступа к сотрудникам по их идентификаторам.

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

3⃣Используйте DFS для вычисления общей важности, начиная с заданного идентификатора сотрудника.

😎 Решение:

type Employee struct {
    Id           int
    Importance   int
    Subordinates []int
}

func getImportance(employees []*Employee, queryid int) int {
    emap := make(map[int]*Employee)
    for _, e := range employees {
        emap[e.Id] = e
    }
    return dfs(queryid, emap)
}

func dfs(eid int, emap map[int]*Employee) int {
    employee := emap[eid]
    ans := employee.Importance
    for _, subid := range employee.Subordinates {
        ans += dfs(subid, emap)
    }
    return ans
}

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

Задача: 518. Coin Change II
Сложность: medium

Вам дан целочисленный массив coins, представляющий монеты разных номиналов, и целое число amount, представляющее общую сумму денег.

Верните количество комбинаций, которые составляют эту сумму. Если эту сумму нельзя составить никакой комбинацией монет, верните 0.

Предположим, что у вас есть бесконечное количество каждой монеты.

Ответ гарантированно вписывается в знаковое 32-битное целое число.

Пример:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

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

1⃣Создайте двумерный массив memo с n строками и amount + 1 столбцами. Инициализируйте значения -1, чтобы указать, что подзадача еще не решена. Реализуйте рекурсивный метод numberOfWays, который принимает два параметра: индекс i текущей рассматриваемой монеты и оставшуюся сумму, которую нужно составить. Он возвращает количество способов составить сумму, используя монеты, начиная с индекса i до последней монеты.

2⃣Если amount == 0, верните 1. Мы можем выбрать один способ, не выбирая ни одной монеты, чтобы составить сумму 0. Если i == n, у нас не осталось монет для составления суммы, верните 0. Если эта подзадача уже решена, т.е. memo[i][amount] != -1, верните memo[i][amount]. Если значение текущей монеты превышает сумму, мы не можем её использовать. Рекурсивно вызовите numberOfWays(i + 1, amount), присвойте результат memo[i][amount] и верните его.

3⃣В противном случае, добавьте общее количество способов составить сумму, как выбирая текущую монету, так и игнорируя её. Сложите значения numberOfWays(i, amount - coins[i]) и numberOfWays(i + 1, amount), сохраните результат в memo[i][amount] и верните его. Верните numberOfWays(0, amount), ответ на исходную задачу.

😎 Решение:

func change(amount int, coins []int) int {
    memo := make([][]int, len(coins))
    for i := range coins {
        memo[i] = make([]int, amount + 1)
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }

    var numberOfWays func(i, amount int) int
    numberOfWays = func(i, amount int) int {
        if amount == 0 {
            return 1
        }
        if i == len(coins) {
            return 0
        }
        if memo[i][amount] != -1 {
            return memo[i][amount]
        }

        if coins[i] > amount {
            memo[i][amount] = numberOfWays(i + 1, amount)
        } else {
            memo[i][amount] = numberOfWays(i, amount - coins[i]) + numberOfWays(i + 1, amount)
        }
        return memo[i][amount]
    }

    return numberOfWays(0, amount)
}

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

Задача: 286. Walls and Gates
Сложность: medium

Вам дана сетка размером m x n, представляющая комнаты, инициализированные следующими значениями:
-1: Стена или препятствие.
0: Ворота.
INF: Бесконечность, обозначающая пустую комнату. Мы используем значение 2^31 - 1 = 2147483647 для представления INF, так как можно предположить, что расстояние до ворот меньше 2147483647.
Заполните каждую пустую комнату расстоянием до ближайших ворот. Если невозможно добраться до ворот, комната должна быть заполнена значением INF.

Пример:

Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

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

1⃣Обход всех комнат:
Пройдите через каждую клетку сетки, инициализируя очередь для BFS. Если клетка содержит ворота (0), добавьте её в очередь.

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

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

😎 Решение:

package main

import "container/list"

func wallsAndGates(rooms [][]int) {
    if len(rooms) == 0 {
        return
    }

    m, n := len(rooms), len(rooms[0])
    q := list.New()
    INF := 2147483647
    directions := [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if rooms[i][j] == 0 {
                q.PushBack([2]int{i, j})
            }
        }
    }

    for q.Len() > 0 {
        front := q.Front()
        q.Remove(front)
        x, y := front.Value.([2]int)[0], front.Value.([2]int)[1]
        for _, dir := range directions {
            nx, ny := x+dir[0], y+dir[1]
            if nx >= 0 && ny >= 0 && nx < m && ny < n && rooms[nx][ny] == INF {
                rooms[nx][ny] = rooms[x][y] + 1
                q.PushBack([2]int{nx, ny})
            }
        }
    }
}

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

Задача: 1091. Shortest Path in Binary Matrix
Сложность: medium

Дан бинарный матричный массив grid размером n x n. Верните длину самого короткого чистого пути в матрице. Если чистого пути не существует, верните -1.

Чистый путь в бинарной матрице — это путь из верхнего левого угла (т.е. (0, 0)) в нижний правый угол (т.е. (n - 1, n - 1)), такой что:

Все посещенные клетки пути равны 0.
Все соседние клетки пути соединены по 8 направлениям (т.е. они различны и имеют общую сторону или угол).
Длина чистого пути — это количество посещенных клеток этого пути.

Пример:

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

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

1⃣Проверить, что начальная и конечная клетки открыты (равны 0). Если нет, вернуть -1.

2⃣Выполнить поиск в ширину (BFS) из начальной клетки, добавляя в очередь соседние клетки, если они открыты и еще не посещены. Обновлять длину пути для каждой клетки.

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

😎 Решение:

package main

import "container/list"

func shortestPathBinaryMatrix(grid [][]int) int {
    if grid[0][0] != 0 || grid[len(grid)-1][len(grid[0])-1] != 0 {
        return -1
    }

    directions := [][]int{
        {-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1},
        {1, -1}, {1, 0}, {1, 1},
    }

    queue := list.New()
    queue.PushBack([]int{0, 0})
    grid[0][0] = 1

    for queue.Len() > 0 {
        cell := queue.Remove(queue.Front()).([]int)
        row, col := cell[0], cell[1]
        distance := grid[row][col]
        if row == len(grid)-1 && col == len(grid[0])-1 {
            return distance
        }
        for _, direction := range directions {
            newRow, newCol := row+direction[0], col+direction[1]
            if newRow >= 0 && newCol >= 0 && newRow < len(grid) && newCol < len(grid[0]) && grid[newRow][newCol] == 0 {
                queue.PushBack([]int{newRow, newCol})
                grid[newRow][newCol] = distance + 1
            }
        }
    }
    return -1
}

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

Задача: 103. Binary Tree Zigzag Level Order Traversal
Сложность: medium

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

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

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

1⃣Мы также можем реализовать поиск в ширину (BFS) с использованием одного цикла. Трюк заключается в том, что мы добавляем узлы для посещения в очередь, а узлы разных уровней разделяем с помощью какого-то разделителя (например, пустого узла). Разделитель отмечает конец уровня, а также начало нового уровня.

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

3⃣Для каждого уровня мы начинаем с пустого контейнера deque, который будет содержать все значения данного уровня. В зависимости от порядка каждого уровня, т.е. либо слева направо, либо справа налево, мы решаем, с какого конца deque добавлять новый элемент.

😎 Решение:

func zigzagLevelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }
    var res [][]int
    nodeQueue := []*TreeNode{root, nil}
    levelList := []int{}
    isOrderLeft := true
    for len(nodeQueue) > 0 {
        currNode := nodeQueue[0]
        nodeQueue = nodeQueue[1:]
        if currNode != nil {
            if isOrderLeft {
                levelList = append(levelList, currNode.Val)
            } else {
                levelList = append([]int{currNode.Val}, levelList...)
            }
            if currNode.Left != nil {
                nodeQueue = append(nodeQueue, currNode.Left)
            }
            if currNode.Right != nil {
                nodeQueue = append(nodeQueue, currNode.Right)
            }
        } else {
            res = append(res, levelList)
            levelList = []int{}
            if len(nodeQueue) > 0 {
                nodeQueue = append(nodeQueue, nil)
            }
            isOrderLeft = !isOrderLeft
        }
    }
    return res
}

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

Задача: 434. Number of Segments in a String
Сложность: easy

Дана строка s, верните количество сегментов в строке.

Сегмент определяется как непрерывная последовательность символов, отличных от пробелов.

Пример:

Input: s = "Hello, my name is John"
Output: 5
Explanation: The five segments are ["Hello,", "my", "name", "is", "John"]

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

1⃣Инициализируйте счетчик сегментов segment_count равным 0.

2⃣Итеративно пройдитесь по строке s. Для каждого индекса i проверьте, начинается ли на этом индексе сегмент: Если символ s[i] не является пробелом, и (либо это первый символ строки, либо предыдущий символ s[i-1] является пробелом), увеличьте segment_count.

3⃣Верните segment_count.

😎 Решение:

func countSegments(s string) int {
    segmentCount := 0

    for i := 0; i < len(s); i++ {
        if (i == 0 || s[i-1] == ' ') && s[i] != ' ' {
            segmentCount++
        }
    }

    return segmentCount
}

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

Задача: 983. Minimum Cost For Tickets
Сложность: medium

Вы запланировали несколько поездок на поезде за год вперёд. Дни года, в которые вы будете путешествовать, заданы в виде целочисленного массива days. Каждый день — это целое число от 1 до 365.

Билеты на поезд продаются тремя различными способами:

однодневный билет продаётся за costs[0] долларов,
семидневный билет продаётся за costs[1] долларов, и
тридцатидневный билет продаётся за costs[2] долларов.
Билеты позволяют путешествовать указанное количество дней подряд.

Например, если мы покупаем семидневный билет на 2-й день, то мы можем путешествовать в течение 7 дней: 2, 3, 4, 5, 6, 7 и 8.
Верните минимальное количество долларов, которое вам нужно, чтобы путешествовать каждый день, указанный в списке days.

Пример:

Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total, you spent $11 and covered all the days of your travel.

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

1⃣Создайте массив dp размером на один больше последнего дня, в который нужно путешествовать. Инициализируйте все значения -1, что означает, что ответ для этого дня ещё не был вычислен. Также создайте хэш-набор isTravelNeeded из days.

2⃣Создайте функцию solve, которая принимает аргумент currDay. Если currDay больше последнего дня, когда нужно путешествовать, просто верните 0, так как все дни уже покрыты. Если currDay отсутствует в isTravelNeeded, перейдите к currDay + 1. Если ответ для currDay в массиве dp не равен -1, это означает, что ответ уже был вычислен, поэтому просто верните его.

3⃣Найдите стоимость трёх билетов, которые можно использовать в этот день, добавьте соответствующую стоимость и обновите dp[currDay] соответственно в рекурсивном вызове. Вызовите solve, передав currDay = 1, и верните ответ.

😎 Решение:

package main

import "math"

type Solution struct {
    isTravelNeeded map[int]bool
}

func (s *Solution) solve(dp []int, days []int, costs []int, currDay int) int {
    if currDay > days[len(days)-1] {
        return 0
    }
    
    if !s.isTravelNeeded[currDay] {
        return s.solve(dp, days, costs, currDay+1)
    }
    
    if dp[currDay] != -1 {
        return dp[currDay]
    }
    
    oneDay := costs[0] + s.solve(dp, days, costs, currDay+1)
    sevenDay := costs[1] + s.solve(dp, days, costs, currDay+7)
    thirtyDay := costs[2] + s.solve(dp, days, costs, currDay+30)
    
    dp[currDay] = int(math.Min(float64(oneDay), math.Min(float64(sevenDay), float64(thirtyDay))))
    return dp[currDay]
}

func (s *Solution) MincostTickets(days []int, costs []int) int {
    lastDay := days[len(days)-1]
    dp := make([]int, lastDay+1)
    for i := range dp {
        dp[i] = -1
    }
    
    s.isTravelNeeded = make(map[int]bool)
    for _, day := range days {
        s.isTravelNeeded[day] = true
    }
    
    return s.solve(dp, days, costs, 1)
}

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

Задача: 920. Number of Music Playlists
Сложность: hard

В вашем плеере есть n разных песен. Во время путешествия вы хотите прослушать goal песен (не обязательно разных). Чтобы избежать скуки, вы создадите плейлист таким образом, чтобы: каждая песня играла хотя бы один раз. Песня может быть проиграна снова только в том случае, если было проиграно k других песен. Учитывая n, цель и k, верните количество возможных плейлистов, которые вы можете создать. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.

Пример:

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

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

1⃣Создать двумерный массив dp, где dp[i][j] представляет количество возможных плейлистов длины i, содержащих j различных песен.

2⃣Инициализировать dp[0][0] = 1, что означает, что существует один способ создать плейлист длины 0 с 0 песнями.
Заполнить массив dp, используя два случая:
Добавление новой песни, которая не была проиграна раньше: dp[i][j] += dp[i-1][j-1] * (n - j + 1)
Повторное проигрывание песни, если было проиграно k других песен: dp[i][j] += dp[i-1][j] * max(j - k, 0)

3⃣Ответ находится в dp[goal][n].

😎 Решение:

package main

func numMusicPlaylists(n int, goal int, k int) int {
    const MOD = 1_000_000_007
    dp := make([][]int, goal+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    dp[0][0] = 1

    for i := 1; i <= goal; i++ {
        for j := 1; j <= n; j++ {
            dp[i][j] = dp[i-1][j-1] * (n - j + 1) % MOD
            if j > k {
                dp[i][j] = (dp[i][j] + dp[i-1][j] * (j - k) % MOD) % MOD
            }
        }
    }

    return dp[goal][n]
}

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

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

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