Задача: 1162. As Far from Land as Possible
Сложность: medium

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

Расстояние, используемое в этой задаче, - это манхэттенское расстояние: расстояние между двумя ячейками (x0, y0) и (x1, y1) равно |x0 - x1| + |y0 - y1|.

Пример:

Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: The cell (1, 1) is as far as possible from all the land with distance 2.

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

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

2⃣Выполните BFS: Обходите текущие элементы в очереди и для каждого элемента проверяйте координаты в четырёх направлениях, являются ли они ячейками с водой (0). Если да, вставьте их в очередь и измените их на ячейки с землёй (1) в матрице visited. После каждого пройденного уровня (внутренний цикл while завершён), увеличьте переменную distance.

3⃣Повторяйте, пока очередь не станет пустой. Верните значение distance. Если оно равно 0, это означает, что не было ячеек с водой и обход завершился после первого шага, поэтому верните -1. Если в матрице не было ячеек с землёй, цикл while вообще не начнётся, и переменная distance останется с начальным значением (-1).

😎 Решение

func maxDistance(grid [][]int) int {
    directions := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    visited := make([][]int, len(grid))
    for i := range grid {
        visited[i] = make([]int, len(grid[i]))
        copy(visited[i], grid[i])
    }
    
    q := [][2]int{}
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[i]); j++ {
            if grid[i][j] == 1 {
                q = append(q, [2]int{i, j})
            }
        }
    }
    
    distance := -1
    for len(q) > 0 {
        qSize := len(q)
        for qSize > 0 {
            landCell := q[0]
            q = q[1:]
            for _, dir := range directions {
                x, y := landCell[0]+dir[0], landCell[1]+dir[1]
                if x >= 0 && y >= 0 && x < len(grid) && y < len(grid[0]) && visited[x][y] == 0 {
                    visited[x][y] = 1
                    q = append(q, [2]int{x, y})
                }
            }
            qSize--
        }
        distance++
    }
    
    if distance == 0 {
        return -1
    }
    return distance
}
func maxDistance(grid [][]int) int {
    directions := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    visited := make([][]int, len(grid))
    for i := range grid {
        visited[i] = make([]int, len(grid[i]))
        copy(visited[i], grid[i])
    }
    
    q := [][2]int{}
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[i]); j++ {
            if grid[i][j] == 1 {
                q = append(q, [2]int{i, j})
            }
        }
    }
    
    distance := -1
    for len(q) > 0 {
        qSize := len(q)
        for qSize > 0 {
            landCell := q[0]
            q = q[1:]
            for _, dir := range directions {
                x, y := landCell[0]+dir[0], landCell[1]+dir[1]
                if x >= 0 && y >= 0 && x < len(grid) && y < len(grid[0]) && visited[x][y] == 0 {
                    visited[x][y] = 1
                    q = append(q, [2]int{x, y})
                }
            }
            qSize--
        }
        distance++
    }
    
    if distance == 0 {
        return -1
    }
    return distance
}

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

Задача: 985. Sum of Even Numbers After Queries
Сложность: medium

Дан целочисленный массив nums и массив queries, где queries[i] = [vali, indexi].

Для каждого запроса i, сначала примените nums[indexi] = nums[indexi] + vali, затем выведите сумму четных значений nums.

Верните целочисленный массив answer, где answer[i] - это ответ на i-й запрос.

Пример:

Input: nums = [1], queries = [[4,0]]
Output: [0]

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

1⃣Инициализация переменных:
Завести переменную evenSum для хранения суммы всех четных чисел в массиве nums.
Пройти по массиву nums и вычислить начальное значение evenSum, сложив все четные числа в nums.

2⃣Обработка запросов:
Создать пустой массив result для хранения ответов на каждый запрос.
Для каждого запроса [val, index] из массива queries выполнить следующие действия:
Если значение nums[index] четное, вычесть его из evenSum.
Обновить nums[index] добавлением val.
Если новое значение nums[index] четное, добавить его к evenSum.
Добавить текущее значение evenSum в массив result.

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

😎 Решение:

func sumEvenAfterQueries(nums []int, queries [][]int) []int {
    evenSum := 0
    for _, num := range nums {
        if num % 2 == 0 {
            evenSum += num
        }
    }

    result := make([]int, len(queries))
    for i, query := range queries {
        val, index := query[0], query[1]
        if nums[index] % 2 == 0 {
            evenSum -= nums[index]
        }
        nums[index] += val
        if nums[index] % 2 == 0 {
            evenSum += nums[index]
        }
        result[i] = evenSum
    }

    return result
}

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

Задача: 561. Array Partition
Сложность: easy

Дан массив целых чисел nums из 2n элементов. Разделите эти числа на n пар (a1, b1), (a2, b2), ..., (an, bn) так, чтобы сумма min(ai, bi) для всех i была максимальной. Верните максимальную сумму.

Пример:

Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.

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

1⃣Отсортируйте массив nums в неубывающем порядке.

2⃣Итерируйте через массив, выбирая каждый второй элемент (начиная с первого).

3⃣Суммируйте выбранные элементы и верните эту сумму.

😎 Решение:

import "sort"

func arrayPairSum(nums []int) int {
    sort.Ints(nums)
    sum := 0
    for i := 0; i < len(nums); i += 2 {
        sum += nums[i]
    }
    return sum
}

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

Задача: 1229. Meeting Scheduler
Сложность: medium

Даны массивы доступных временных слотов slots1 и slots2 для двух человек и продолжительность встречи duration, верните самый ранний временной слот, который подходит обоим и имеет продолжительность duration.

Если нет общего временного слота, который удовлетворяет требованиям, верните пустой массив.

Формат временного слота — это массив из двух элементов [start, end], представляющий инклюзивный временной диапазон от start до end.

Гарантируется, что никакие два доступных временных слота одного и того же человека не пересекаются друг с другом. То есть для любых двух временных слотов [start1, end1] и [start2, end2] одного и того же человека либо start1 > end2, либо start2 > end1.

Пример:

Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8
Output: [60,68]

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

1⃣Отсортируйте оба массива slots1 и slots2 по времени начала.

2⃣Инициализируйте два указателя, указывающие на начало slots1 и slots2 соответственно.

3⃣Перебирайте, пока указатель1 не достигнет конца slots1 или указатель2 не достигнет конца slots2:
Найдите общий слот между slots1[pointer1] и slots2[pointer2].
Если общий слот больше или равен duration, верните результат.
В противном случае найдите слот, который заканчивается раньше, и передвиньте указатель.
Если общий слот не найден, верните пустой массив.

😎 Решение:

func minAvailableDuration(slots1 [][]int, slots2 [][]int, duration int) []int {
    sort.Slice(slots1, func(i, j int) bool {
        return slots1[i][0] < slots1[j][0]
    })
    sort.Slice(slots2, func(i, j int) bool {
        return slots2[i][0] < slots2[j][0]
    })
    
    pointer1, pointer2 := 0, 0
    
    for pointer1 < len(slots1) && pointer2 < len(slots2) {
        intersectLeft := max(slots1[pointer1][0], slots2[pointer2][0])
        intersectRight := min(slots1[pointer1][1], slots2[pointer2][1])
        
        if intersectRight - intersectLeft >= duration {
            return []int{intersectLeft, intersectLeft + duration}
        }
        
        if slots1[pointer1][1] < slots2[pointer2][1] {
            pointer1++
        } else {
            pointer2++
        }
    }
    return []int{}
}

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

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

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

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

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

Тестовые случаи сгенерированы так, что ответ помещается в 32-битное целое число.

Пример:

Input: nums = [9], target = 3
Output: 0

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

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

2⃣Из-за рекурсивной природы формулы мы можем напрямую перевести формулу в рекурсивную функцию.

3⃣Здесь, соответственно, мы определяем рекурсивную функцию под названием combs(remain), которая возвращает количество комбинаций, где каждая комбинация в сумме дает значение remain.

😎 Решение:

package main

func combinationSum4(nums []int, target int) int {
    memo := make(map[int]int)
    return combs(nums, target, memo)
}

func combs(nums []int, remain int, memo map[int]int) int {
    if remain == 0 {
        return 1
    }
    if val, found := memo[remain]; found {
        return val
    }

    result := 0
    for _, num := range nums {
        if remain - num >= 0 {
            result += combs(nums, remain - num, memo)
        }
    }
    memo[remain] = result
    return result
}

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

Задача: 1351. Count Negative Numbers in a Sorted Matrix
Сложность: easy

Дана матрица m x n grid, которая отсортирована по убыванию как по строкам, так и по столбцам. Вернуть количество отрицательных чисел в grid.

Пример:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.

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

1⃣Инициализировать переменную count = 0 для подсчета общего числа отрицательных элементов в матрице.

2⃣Использовать два вложенных цикла для итерации по каждому элементу матрицы grid, и если элемент отрицательный, увеличить count на 1.

3⃣Вернуть count.

😎 Решение:

func countNegatives(grid [][]int) int {
    count := 0
    for _, row := range grid {
        for _, element := range row {
            if element < 0 {
                count++
            }
        }
    }
    return count
}

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

Задача: 902. Numbers At Most N Given Digit Set
Сложность: hard

Дан массив цифр, отсортированный в неубывающем порядке. Вы можете записывать числа, используя каждый digits[i] столько раз, сколько захотите. Например, если digits = ['1','3','5'], мы можем записать такие числа, как '13', '551' и '1351315'. Возвращает количество положительных целых чисел, которые могут быть сгенерированы и которые меньше или равны заданному целому числу n.

Пример:

Input: digits = ["1","3","5","7"], n = 100
Output: 20

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

1⃣Преобразовать заданное число n в строку для удобного доступа к каждой цифре.

2⃣Реализовать рекурсивную функцию для генерации всех возможных чисел с использованием цифр из массива digits и сравнения с n.

3⃣Начать с каждой цифры в digits и рекурсивно строить числа, отслеживая количество подходящих чисел.

😎 Решение:

package main

import (
    "math"
    "strconv"
)

func atMostNGivenDigitSet(digits []string, n int) int {
    s := strconv.Itoa(n)
    K := len(s)
    dp := make([]int, K+1)
    dp[K] = 1

    for i := K - 1; i >= 0; i-- {
        for _, d := range digits {
            if d[0] < s[i] {
                dp[i] += int(math.Pow(float64(len(digits)), float64(K-i-1)))
            } else if d[0] == s[i] {
                dp[i] += dp[i+1]
            }
        }
    }

    for i := 1; i < K; i++ {
        dp[0] += int(math.Pow(float64(len(digits)), float64(i)))
    }

    return dp[0]
}

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

Задача: 234. Palindrome Linked List
Сложность: easy

Дан головной элемент односвязного списка. Верните true, если список является палиндромом, и false в противном случае.

Пример:

Input: head = [1,2,2,1]
Output: true

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

1⃣Копирование односвязного списка в массив: Итеративно пройдите по односвязному списку, добавляя каждое значение в массив. Для этого используйте переменную currentNode, указывающую на текущий узел. На каждой итерации добавляйте currentNode.val в массив и обновляйте currentNode, чтобы он указывал на currentNode.next. Остановите цикл, когда currentNode укажет на null.

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

3⃣Сравнение значений: Помните, что необходимо сравнивать значения узлов, а не сами узлы. Используйте node_1.val == node_2.val для сравнения значений узлов. Сравнение узлов как объектов node_1 == node_2 не даст ожидаемого результата.

😎 Решение:

func isPalindrome(head *ListNode) bool {
    vals := []int{}
    currentNode := head

    for currentNode != nil {
        vals = append(vals, currentNode.Val)
        currentNode = currentNode.Next
    }

    front := 0
    back := len(vals) - 1
    for front < back {
        if vals[front] != vals[back] {
            return false
        }
        front++
        back--
    }
    return true
}

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

Задача: 986. Interval List Intersections
Сложность: medium

Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным.

Верните пересечение этих двух списков интервалов.

Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b.

Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3].

Пример:

Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

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

1⃣Инициализация указателей:
Завести два указателя i и j, указывающие на начало firstList и secondList соответственно.

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

3⃣Возврат результата:
Вернуть список пересечений.

😎 Решение:

func intervalIntersection(firstList [][]int, secondList [][]int) [][]int {
    i, j := 0, 0
    var result [][]int

    for i < len(firstList) && j < len(secondList) {
        start := max(firstList[i][0], secondList[j][0])
        end := min(firstList[i][1], secondList[j][1])
        
        if start <= end {
            result = append(result, []int{start, end})
        }
        
        if firstList[i][1] < secondList[j][1] {
            i++
        } else {
            j++
        }
    }
    
    return result
}

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

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

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

Задача: 978. Longest Turbulent Subarray
Сложность: medium

Дан целочисленный массив arr, верните длину максимального турбулентного подмассива массива arr.

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

Более формально, подмассив [arr[i], arr[i + 1], ..., arr[j]] массива arr считается турбулентным тогда и только тогда, когда:

Для всех i <= k < j:
arr[k] > arr[k + 1], когда k нечетное, и
arr[k] < arr[k + 1], когда k четное.
Или, для всех i <= k < j:
arr[k] > arr[k + 1], когда k четное, и
arr[k] < arr[k + 1], когда k нечетное.

Пример:

Input: arr = [9,4,2,10,7,8,8,1,9]
Output: 5
Explanation: arr[1] > arr[2] < arr[3] > arr[4] < arr[5]

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

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

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

3⃣Повторяйте шаг 2 до конца массива и верните максимальную длину турбулентного подмассива.

😎 Решение:

func maxTurbulenceSize(A []int) int {
    N := len(A)
    ans := 1
    anchor := 0

    for i := 1; i < N; i++ {
        c := compare(A[i-1], A[i])
        if c == 0 {
            anchor = i
        } else if i == N-1 || c*compare(A[i], A[i+1]) != -1 {
            if i-anchor+1 > ans {
                ans = i - anchor + 1
            }
            anchor = i
        }
    }

    return ans
}

func compare(a, b int) int {
    if a > b {
        return 1
    }
    if a < b {
        return -1
    }
    return 0
}

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

Задача: 959. Regions Cut By Slashes
Сложность: medium

n x n сетка состоит из квадратов размером 1 x 1, где каждый квадрат 1 x 1 содержит '/', '', или пустое пространство ' '. Эти символы делят квадрат на смежные области.

Дана сетка grid, представленная в виде строкового массива. Верните количество областей.

Обратите внимание, что обратные слеши экранированы, поэтому '' представлен как '\'.

Пример:

Input: grid = [" /","/ "]
Output: 2

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

1⃣Создайте 4*N*N узлов для каждой ячейки сетки и соедините их в соответствии с описанием.

2⃣Используйте структуру объединения-поиска (DSU), чтобы найти количество связанных компонентов.

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

😎 Решение:

type DSU struct {
    parent []int
}

func NewDSU(N int) *DSU {
    dsu := &DSU{parent: make([]int, N)}
    for i := range dsu.parent {
        dsu.parent[i] = i
    }
    return dsu
}

func (dsu *DSU) find(x int) int {
    if dsu.parent[x] != x {
        dsu.parent[x] = dsu.find(dsu.parent[x])
    }
    return dsu.parent[x]
}

func (dsu *DSU) union(x, y int) {
    dsu.parent[dsu.find(x)] = dsu.find(y)
}

func regionsBySlashes(grid []string) int {
    N := len(grid)
    dsu := NewDSU(4 * N * N)
    
    for r := 0; r < N; r++ {
        for c := 0; c < N; c++ {
            root := 4 * (r * N + c)
            val := grid[r][c]
            
            if val != '\\' {
                dsu.union(root + 0, root + 1)
                dsu.union(root + 2, root + 3)
            }
            if val != '/' {
                dsu.union(root + 0, root + 2)
                dsu.union(root + 1, root + 3)
            }
            
            if r + 1 < N {
                dsu.union(root + 3, (root + 4 * N) + 0)
            }
            if r - 1 >= 0 {
                dsu.union(root + 0, (root - 4 * N) + 3)
            }
            if c + 1 < N {
                dsu.union(root + 2, (root + 4) + 1)
            }
            if c - 1 >= 0 {
                dsu.union(root + 1, (root - 4) + 2)
            }
        }
    }
    
    ans := 0
    for x := 0; x < 4 * N * N; x++ {
        if dsu.find(x) == x {
            ans++
        }
    }
    
    return ans
}

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

Задача: 992. Subarrays with K Different Integers
Сложность: hard

Дан целочисленный массив nums и целое число k, верните количество "хороших" подмассивов в nums.

"Хороший" массив - это массив, в котором количество различных целых чисел равно k.

Например, в массиве [1,2,3,1,2] есть 3 различных целых числа: 1, 2 и 3.
Подмассив - это непрерывная часть массива.

Пример:

Input: nums = [1,2,1,2,3], k = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]

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

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

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

3⃣Возврат результата:
Верните общее количество "хороших" подмассивов.

😎 Решение:

func countGoodSubarrays(nums []int, k int) int {
    count := 0
    left := 0
    right := 0
    distinctCount := 0
    freq := make(map[int]int)
    
    for right < len(nums) {
        freq[nums[right]]++
        if freq[nums[right]] == 1 {
            distinctCount++
        }
        right++
        
        for distinctCount > k {
            freq[nums[left]]--
            if freq[nums[left]] == 0 {
                distinctCount--
            }
            left++
        }
        
        if distinctCount == k {
            count++
        }
    }
    
    return count
}

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

Задача: 1335. Minimum Difficulty of a Job Schedule
Сложность: hard

Вы хотите составить расписание списка заданий на d дней. Задания зависят друг от друга (т.е. чтобы выполнить задание i, вы должны закончить все задания j, где 0 <= j < i).

Вы должны выполнять как минимум одно задание каждый день. Сложность расписания заданий — это сумма сложностей каждого дня из d дней. Сложность дня — это максимальная сложность задания, выполненного в этот день.

Вам дан массив целых чисел jobDifficulty и целое число d. Сложность i-го задания равна jobDifficulty[i].

Верните минимальную сложность расписания заданий. Если вы не можете найти расписание для заданий, верните -1.

Пример:

Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7 

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

1⃣Определение состояния:
Индекс i (индекс первой задачи на сегодняшний день в массиве jobDifficulty) и день d (количество оставшихся дней) будут определять состояние динамического программирования. min_diff(i, d) обозначает минимальную сложность при начале с i-й задачи с оставшимися d днями. min_diff(0, d) будет окончательным ответом, так как он представляет начало с начала массива задач и завершение всех задач за ровно d дней.

2⃣Функция перехода состояния:
Задача с индексом j будет первой задачей на следующий день, следовательно, задачи, которые должны быть завершены сегодня, это все задачи с индексами между i и j, то есть jobDifficulty[i
]. Поскольку сложность дня — это максимальная сложность выполненной в этот день задачи, к сумме сложностей задач будет добавляться максимум из jobDifficulty[i
]. Формулируем функцию перехода состояния следующим образом: min_diff(i, d) = min_diff(j, d - 1) + max(jobDifficulty[i
]) для всех j > i.

3⃣Базовый случай:
Когда остается только 1 день, необходимо завершить все незавершенные задачи в этот день и увеличить сложность расписания задач на максимальную сложность этих задач.

😎 Решение

func minDifficulty(jobDifficulty []int, d int) int {
    n := len(jobDifficulty)
    if n < d {
        return -1
    }

    mem := make([][]int, n)
    for i := range mem {
        mem[i] = make([]int, d+1)
        for j := range mem[i] {
            mem[i][j] = -1
        }
    }

    return minDiff(0, d, jobDifficulty, mem)
}

func minDiff(i, daysRemaining int, jobDifficulty []int, mem [][]int) int {
    if mem[i][daysRemaining] != -1 {
        return mem[i][daysRemaining]
    }

    if daysRemaining == 1 {
        res := 0
        for j := i; j < len(jobDifficulty); j++ {
            if jobDifficulty[j] > res {
                res = jobDifficulty[j]
            }
        }
        return res
    }

    res := int(^uint(0) >> 1)
    dailyMaxJobDiff := 0
    for j := i; j < len(jobDifficulty)-daysRemaining+1; j++ {
        if jobDifficulty[j] > dailyMaxJobDiff {
            dailyMaxJobDiff = jobDifficulty[j]
        }
        next := minDiff(j+1, daysRemaining-1, jobDifficulty, mem)
        if res > dailyMaxJobDiff+next {
            res = dailyMaxJobDiff + next
        }
    }
    mem[i][daysRemaining] = res
    return res
}

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

Задача: №67. Add Binary
Сложность: easy

Даны две двоичные строки a и b. Верните их сумму в виде двоичной строки.

Пример:

Input: a = "11", b = "1"
Output: "100"

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

1⃣Начните с переноса carry = 0. Если в числе a наименьший бит равен 1, добавьте 1 к carry. То же самое относится к числу b: если в числе b наименьший бит равен 1, добавьте 1 к carry. В этот момент carry для наименьшего бита может быть равен 0 (00), 1 (01) или 2 (10).

2⃣Теперь добавьте наименьший бит carry к ответу и перенесите старший бит carry на следующий порядковый бит.

3⃣Повторяйте те же шаги снова и снова, пока не будут использованы все биты в a и b. Если остаётся ненулевой carry, добавьте его. Теперь переверните строку ответа, и задача выполнена.

😎 Решение:

func addBinary(a string, b string) string {
    n, m := len(a), len(b)
    if n < m {
        return addBinary(b, a)
    }

    var result strings.Builder
    carry, j := 0, m-1
    for i := n - 1; i >= 0; i-- {
        if a[i] == '1' {
            carry++
        }
        if j >= 0 && b[j] == '1' {
            carry++
        }
        j--
        result.WriteByte('0' + byte(carry%2))
        carry /= 2
    }
    if carry == 1 {
        result.WriteByte('1')
    }
    s := result.String()
    runes := []rune(s)
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
    return string(runes)
}

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

Задача: 733. Flood Fill
Сложность: easy

Изображение представлено в виде целочисленной сетки m x n, где image[i][j] - значение пикселя изображения. Вам также даны три целых числа sr, sc и color. Вы должны выполнить заливку изображения, начиная с пикселя image[sr][sc]. Чтобы выполнить заливку, рассмотрите начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с начальным пикселем, того же цвета, что и начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с этими пикселями (также того же цвета), и так далее. Замените цвет всех вышеупомянутых пикселей на цвет. Верните измененное изображение после выполнения заливки.

Пример:

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

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

1⃣Получите цвет начального пикселя.

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

3⃣Обновите изображение и верните его.

😎 Решение:

package main

func floodFill(image [][]int, sr int, sc int, color int) [][]int {
    originalColor := image[sr][sc]
    if originalColor == color {
        return image
    }

    var dfs func(x, y int)
    dfs = func(x, y int) {
        if x < 0 || x >= len(image) || y < 0 || y >= len(image[0]) || image[x][y] != originalColor {
            return
        }
        image[x][y] = color
        dfs(x+1, y)
        dfs(x-1, y)
        dfs(x, y+1)
        dfs(x, y-1)
    }

    dfs(sr, sc)
    return image
}

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

Задача: 528. Random Pick with Weight
Сложность: medium

Вам дан массив положительных целых чисел w, где w[i] описывает вес индекса i.
Вам нужно реализовать функцию pickIndex(), которая случайным образом выбирает индекс в диапазоне [0, w.length - 1] (включительно) и возвращает его. Вероятность выбора индекса i равна w[i] / sum(w).

Например, если w = [1, 3], вероятность выбора индекса 0 составляет 1 / (1 + 3) = 0.25 (т.е. 25%), а вероятность выбора индекса 1 составляет 3 / (1 + 3) = 0.75 (т.е. 75%).

Пример:

Input
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]

Explanation
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.

Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
and so on.

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

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

2⃣ Генерация случайного числа и выбор индекса:
В функции pickIndex() сгенерируйте случайное число в диапазоне от 0 до общей суммы весов totalSum.
Используйте линейный поиск, чтобы найти первый индекс в prefixSums, который больше или равен сгенерированному числу.

3⃣ Возврат результата:
Верните найденный индекс.

😎 Решение:

import (
    "math/rand"
    "time"
)

type Solution struct {
    prefixSums []int
    totalSum   int
}

func Constructor(w []int) Solution {
    prefixSums := make([]int, len(w))
    prefixSum := 0
    for i, weight := range w {
        prefixSum += weight
        prefixSums[i] = prefixSum
    }
    return Solution{prefixSums, prefixSum}
}

func (this *Solution) PickIndex() int {
    rand.Seed(time.Now().UnixNano())
    target := float64(this.totalSum) * rand.Float64()
    for i, prefixSum := range this.prefixSums {
        if target < float64(prefixSum) {
            return i
        }
    }
    return len(this.prefixSums) - 1
}

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

Задача: 644. Maximum Average Subarray II
Сложность: hard

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

Пример:

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

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

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

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

3⃣Следите за максимальным средним значением и верните его после проверки всех возможных окон.

😎 Решение:

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

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

Задача: 747. Largest Number At Least Twice of Others
Сложность: easy

Вам дан целочисленный массив nums, в котором наибольшее целое число уникально. Определите, является ли наибольший элемент массива по крайней мере в два раза больше всех остальных чисел в массиве. Если да, то верните индекс самого большого элемента, в противном случае верните -1.

Пример:

Input: nums = [3,6,1,0]
Output: 1

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

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

2⃣Проверьте, является ли этот максимальный элемент по крайней мере в два раза больше всех остальных элементов массива.

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

😎 Решение:

package main

func minCostClimbingStairs(cost []int) int {
    n := len(cost)
    dp := make([]int, n)
    copy(dp, cost)
    for i := 2; i < n; i++ {
        dp[i] += min(dp[i-1], dp[i-2])
    }
    return min(dp[n-1], dp[n-2])
}

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

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

Задача: 542. 01 Matrix
Сложность: medium

Дана бинарная матрица размера m x n, верните расстояние до ближайшего нуля для каждой ячейки.
Расстояние между двумя соседними ячейками равно 1.

Пример:

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

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

1⃣Создайте копию матрицы mat, назовем её matrix. Используйте структуру данных seen для пометки уже посещенных узлов и очередь для выполнения BFS. Поместите все узлы с 0 в очередь и отметьте их в seen.

2⃣Выполните BFS:
Пока очередь не пуста, извлекайте текущие row, col, steps из очереди.
Итеративно пройдите по четырем направлениям. Для каждой nextRow, nextCol проверьте, находятся ли они в пределах границ и не были ли они уже посещены в seen.

3⃣Если так, установите matrix[nextRow][nextCol] = steps + 1 и поместите nextRow, nextCol, steps + 1 в очередь. Также отметьте nextRow, nextCol в seen. Верните matrix.

😎 Решение:

package main

import (
    "container/list"
)

type Solution struct {
    m, n      int
    directions [4][2]int
}

func Constructor() Solution {
    return Solution{
        directions: [4][2]int{
            {0, 1},
            {1, 0},
            {0, -1},
            {-1, 0},
        },
    }
}

func (s *Solution) updateMatrix(mat [][]int) [][]int {
    s.m = len(mat)
    s.n = len(mat[0])
    matrix := make([][]int, s.m)
    seen := make([][]bool, s.m)
    queue := list.New()

    for i := 0; i < s.m; i++ {
        matrix[i] = make([]int, s.n)
        seen[i] = make([]bool, s.n)
        for j := 0; j < s.n; j++ {
            matrix[i][j] = mat[i][j]
            if matrix[i][j] == 0 {
                queue.PushBack([3]int{i, j, 0})
                seen[i][j] = true
            }
        }
    }

    for queue.Len() > 0 {
        curr := queue.Remove(queue.Front()).([3]int)
        row, col, steps := curr[0], curr[1], curr[2]

        for _, direction := range s.directions {
            nextRow, nextCol := row+direction[0], col+direction[1]
            if s.isValid(nextRow, nextCol) && !seen[nextRow][nextCol] {
                seen[nextRow][nextCol] = true
                queue.PushBack([3]int{nextRow, nextCol, steps + 1})
                matrix[nextRow][nextCol] = steps + 1
            }
        }
    }

    return matrix
}

func (s *Solution) isValid(row, col int) bool {
    return 0 <= row && row < s.m && 0 <= col && col < s.n
}

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

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

Дан массив nums, содержащий n различных чисел в диапазоне [0, n]. Верните единственное число в этом диапазоне, которого нет в массиве.

Пример:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

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

1⃣Сначала отсортируйте массив nums.

2⃣Проверьте особые случаи: убедитесь, что число 0 находится в начале массива, а число n — в конце.

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

😎 Решение:

func missingNumber(nums []int) int {
    sort.Ints(nums)
    if nums[len(nums)-1] != len(nums) {
        return len(nums)
    } else if nums[0] != 0 {
        return 0
    }
    for i := 1; i < len(nums); i++ {
        expectedNum := nums[i-1] + 1
        if nums[i] != expectedNum {
            return expectedNum
        }
    }
    return -1
}

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