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

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

Задача: 147. Insertion Sort List
Сложность: medium

Дана голова односвязного списка. Отсортируйте список, используя сортировку вставками, и верните голову отсортированного списка.

Шаги алгоритма сортировки вставками:

1. Сортировка вставками итеративно работает, потребляя один входной элемент за каждую итерацию и формируя отсортированный выходной список.
2. На каждой итерации сортировка вставками удаляет один элемент из входных данных, находит место, куда он принадлежит в отсортированном списке, и вставляет его туда.
3. Процесс повторяется до тех пор, пока не закончатся входные элементы.

Пример:

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

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

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

2⃣Механизм вставки узла:
В односвязном списке каждый узел содержит только один указатель, который указывает на следующий узел. Чтобы вставить новый узел (например, B) перед определенным узлом (например, A), необходимо знать узел (например, C), который находится перед узлом A (т.е. C -> A). Имея ссылку на узел C, можно вставить новый узел так, чтобы получилось C -> B -> A.

3⃣Использование пары указателей для вставки:
Используя пару указателей (prev и next), которые служат местом для вставки нового элемента между ними, вставьте новый элемент в список. Это делается путем установки prev -> new_node -> next. Этот метод позволяет точно и безопасно вставлять новые элементы в список, сохраняя при этом правильный порядок элементов без необходимости перемещения других узлов списка.

😎 Решение:

func insertionSortList(head *ListNode) *ListNode {
    dummy := &ListNode{}
    curr := head
    for curr != nil {
        prev := dummy
        for prev.Next != nil && prev.Next.Val <= curr.Val {
            prev = prev.Next
        }
        next := curr.Next
        curr.Next = prev.Next
        prev.Next = curr
        curr = next
    }
    return dummy.Next
}

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

Задача: 659. Split Array into Consecutive Subsequences
Сложность: medium

Вам дан отсортированный в неубывающем порядке массив целых чисел nums.

Определите, можно ли разделить nums на одну или несколько подпоследовательностей так, чтобы выполнялись оба следующих условия:

Каждая подпоследовательность является последовательностью последовательных возрастающих чисел (то есть каждое целое число на 1 больше предыдущего).
Все подпоследовательности имеют длину 3 или более.
Верните true, если можно разделить nums согласно вышеуказанным условиям, или false в противном случае.

Подпоследовательность массива — это новый массив, который формируется из исходного массива путем удаления некоторых (может быть, ни одного) элементов без нарушения относительных позиций оставшихся элементов. (например, [1,3,5] является подпоследовательностью [1,2,3,4,5], тогда как [1,3,2] не является).

Пример:

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

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

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

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

3⃣Проверка результата:
Верните true, если все элементы успешно распределены по подпоследовательностям.

😎 Решение:

func isPossible(nums []int) bool {
    freq := make(map[int]int)
    need := make(map[int]int)
    
    for _, num := range nums {
        freq[num]++
    }
    
    for _, num := range nums {
        if freq[num] == 0 {
            continue
        }
        if need[num] > 0 {
            need[num]--
            need[num+1]++
        } else if freq[num+1] > 0 && freq[num+2] > 0 {
            freq[num+1]--
            freq[num+2]--
            need[num+3]++
        } else {
            return false
        }
        freq[num]--
    }
    
    return true
}

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

Задача: 684. Redundant Connection
Сложность: medium

В этой задаче дерево — это неориентированный граф, который является связным и не содержит циклов.

Вам дан граф, который изначально был деревом с n узлами, пронумерованными от 1 до n, и к которому добавили одно дополнительное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее. Граф представлен массивом edges длины n, где edges[i] = [ai, bi] указывает на то, что существует ребро между узлами ai и bi в графе.

Верните ребро, которое можно удалить, чтобы результирующий граф стал деревом из n узлов. Если существует несколько ответов, верните тот, который встречается последним в исходных данных.
Пример:

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]

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

1⃣Для каждого ребра (u, v) создайте представление графа с использованием списка смежности. Это позволит легко выполнять обход в глубину (DFS) для проверки соединений между узлами.

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

3⃣Верните дублирующееся ребро, которое встречается последним в исходных данных. Это обеспечит корректность решения, даже если существует несколько ответов.

😎 Решение:

package main

func findRedundantConnection(edges [][]int) []int {
    const MAX_EDGE_VAL = 1000
    graph := make([][]int, MAX_EDGE_VAL+1)
    for i := range graph {
        graph[i] = make([]int, 0)
    }
    seen := make(map[int]bool)

    var dfs func(source, target int) bool
    dfs = func(source, target int) bool {
        if !seen[source] {
            seen[source] = true
            if source == target {
                return true
            }
            for _, nei := range graph[source] {
                if dfs(nei, target) {
                    return true
                }
            }
        }
        return false
    }

    for _, edge := range edges {
        seen = make(map[int]bool)
        if len(graph[edge[0]]) > 0 && len(graph[edge[1]]) > 0 && dfs(edge[0], edge[1]) {
            return edge
        }
        graph[edge[0]] = append(graph[edge[0]], edge[1])
        graph[edge[1]] = append(graph[edge[1]], edge[0])
    }
    return nil
}

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

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

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

Пример:

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

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

1⃣Инициализируйте список вывода levels. Длина этого списка определяет, какой уровень в данный момент обновляется. Вам следует сравнить этот уровень len(levels) с уровнем узла level, чтобы убедиться, что вы добавляете узел на правильный уровень. Если вы все еще находитесь на предыдущем уровне, добавьте новый уровень, вставив новый список в levels.

2⃣Добавьте значение узла в последний уровень в levels.

3⃣Рекурсивно обработайте дочерние узлы, если они не равны None, используя функцию helper(node.left / node.right, level + 1).

😎 Решение:

func levelOrderBottom(root *TreeNode) [][]int {
    levels := make([][]int, 0)
    var helper func(node *TreeNode, level int)
    helper = func(node *TreeNode, level int) {
        if node == nil {
            return
        }
        if len(levels) == level {
            levels = append(levels, []int{})
        }
        levels[level] = append(levels[level], node.Val)
        if node.Left != nil {
            helper(node.Left, level+1)
        }
        if node.Right != nil {
            helper(node.Right, level+1)
        }
    }
    helper(root, 0)
    for i := 0; i < len(levels)/2; i++ {
        levels[i], levels[len(levels)-1-i] = levels[len(levels)-1-i], levels[i]
    }
    return levels
}

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