Golang | LeetCode

Задача: 924. Minimize Malware Spread Сложность: hard Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока не останется ни одного узла, который можно было бы заразить таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим из initial ровно один узел. Верните тот узел, удаление которого минимизирует M(initial). Если можно удалить несколько узлов, чтобы минимизировать M(initial), верните такой узел с наименьшим индексом. Обратите внимание, что если узел был удален из начального списка зараженных узлов, он все равно может быть заражен позже из-за распространения вредоносного ПО. Пример:

    
        Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20{}
    

👨‍💻 Алгоритм: 1⃣Определить количество зараженных узлов после распространения вредоносного ПО для исходного списка initial. 2⃣Для каждого узла в initial удалить его и вычислить количество зараженных узлов после распространения вредоносного ПО. 3⃣Найти узел, удаление которого минимизирует количество зараженных узлов. Если есть несколько таких узлов, выбрать узел с наименьшим индексом. 😎 Решение:

    
        package main

func minMalwareSpread(graph [][]int, initial []int) int {
    dfs := func(node int, infected map[int]struct{}) {
        for neighbor := 0; neighbor < len(graph); neighbor++ {
            if graph[node][neighbor] == 1 {
                if _, ok := infected[neighbor]; !ok {
                    infected[neighbor] = struct{}{}
                    dfs(neighbor, infected)
                }
            }
        }
    }
    
    n := len(graph)
    initialSet := make(map[int]struct{})
    for _, v := range initial {
        initialSet[v] = struct{}{}
    }
    sort.Ints(initial)
    minInfected := int(^uint(0) >> 1)
    bestNode := initial[0]
    
    for _, node := range initial {
        infected := make(map[int]struct{})
        for k := range initialSet {
            if k != node {
                infected[k] = struct{}{}
            }
        }
        for i := range initialSet {
            if i != node {
                dfs(i, infected)
            }
        }
        if len(infected) < minInfected {
            minInfected = len(infected)
            bestNode = node
        }
    }
    
    return bestNode
}{}
    

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

Задача: 397. Integer Replacement Сложность: medium К положительному целому числу n можно применить одну из следующих операций: если n четное, замените n на n / 2. если n нечетное, замените n на n + 1 или n - 1. верните минимальное количество операций, необходимых для того, чтобы n стало 1. Пример:

    
        Input: n = 8
Output: 3
Explanation: 8 -> 4 -> 2 -> 1{}
    

👨‍💻 Алгоритм: 1⃣Начните с данного числа n и выполните одну из следующих операций: Если n четное, замените n на n / 2. Если n нечетное, замените n на n + 1 или n - 1. 2⃣Используйте метод динамического программирования или жадный метод, чтобы найти минимальное количество операций, необходимых для достижения n = 1. Определите, какая операция (n + 1 или n - 1) является более эффективной для минимизации количества шагов. 3⃣Продолжайте выполнять выбранные операции, пока n не станет равным 1. Считайте количество выполненных операций и верните это значение как результат. 😎 Решение:

    
        func integerReplacement(n int) int {
    memo := make(map[int]int)
    return helper(n, memo)
}

func helper(n int, memo map[int]int) int {
    if n == 1 {
        return 0
    }
    if val, exists := memo[n]; exists {
        return val
    }
    
    if n % 2 == 0 {
        memo[n] = 1 + helper(n/2, memo)
    } else {
        memo[n] = 1 + min(helper(n+1, memo), helper(n-1, memo))
    }
    
    return memo[n]
}

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

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

Задача: 62. Unique Paths Сложность: medium На сетке размером m на n находится робот. Изначально робот расположен в верхнем левом углу (то есть, в клетке grid[0][0]). Робот пытается добраться до нижнего правого угла (то есть, в клетку grid[m - 1][n - 1]). Робот может двигаться только вниз или вправо в любой момент времени. Даны два целых числа m и n, верните количество возможных уникальных путей, которые робот может пройти, чтобы достичь нижнего правого угла. Тестовые случаи сгенерированы таким образом, что ответ будет меньше или равен 2 * 10^9. Пример:

    
        Input: m = 3, n = 7
Output: 28{}
    

👨‍💻 Алгоритм: 1⃣Инициализировать двумерный массив d[m][n] = количество путей. Сначала установить количество путей равным 1 для первой строки и первого столбца. Для упрощения можно инициализировать весь двумерный массив единицами. 2⃣Проитерировать по всем "внутренним" ячейкам: d[col][row] = d[col - 1][row] + d[col][row - 1]. 3⃣Вернуть d[m - 1][n - 1]. 😎 Решение:

    
        func uniquePaths(m int, n int) int {
    if m == 1 || n == 1 {
        return 1
    }
    return uniquePaths(m-1, n) + uniquePaths(m, n-1)
}{}
    

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

Задача: 320. Generalized Abbreviation Сложность: medium Обобщенная аббревиатура слова может быть построена путем замены любых неперекрывающихся и несмежных подстрок на их соответствующие длины. Например, "abcde" можно сократить следующим образом: "a3e" ("bcd" заменено на "3") "1bcd1" ("a" и "e" заменены на "1") "5" ("abcde" заменено на "5") "abcde" (без замены подстрок) Однако следующие аббревиатуры недействительны: "23" ("ab" заменено на "2" и "cde" заменено на "3") недействительно, так как выбранные подстроки смежные. "22de" ("ab" заменено на "2" и "bc" заменено на "2") недействительно, так как выбранные подстроки перекрываются. Дано слово word, верните список всех возможных обобщенных аббревиатур слова. Верните ответ в любом порядке. Пример:

    
        Input: word = "a"
Output: ["1","a"]{}
    

👨‍💻 Алгоритм: 1⃣Создание битовых масок Каждая аббревиатура имеет одно к одному соответствие с n-битным двоичным числом x, где n - длина слова. Используйте эти числа в качестве чертежей для построения соответствующих аббревиатур. 2⃣Генерация аббревиатур Для числа x просканируйте его бит за битом, чтобы определить, какие символы следует сохранить, а какие - сократить. Если бит равен 1, сохраните соответствующий символ, если 0 - замените его на счетчик. 3⃣Перебор всех комбинаций Для каждого числа от 0 до 2^n - 1 используйте его битовое представление для создания соответствующей аббревиатуры. Сканируйте число x побитово, извлекая его последний бит с помощью b = x & 1 и сдвигая x вправо на один бит x >>= 1. 😎 Решение:

    
        package main

import (
    "fmt"
    "strconv"
)

func generateAbbreviations(word string) []string {
    n := len(word)
    var result []string

    for x := 0; x < (1 << n); x++ {
        result = append(result, abbr(word, x))
    }
    return result
}

func abbr(word string, x int) string {
    var builder []byte
    k := 0

    for i := 0; i < len(word); i, x = i+1, x>>1 {
        if x&1 == 0 {
            if k != 0 {
                builder = append(builder, strconv.Itoa(k)...)
                k = 0
            }
            builder = append(builder, word[i])
        } else {
            k++
        }
    }
    if k != 0 {
        builder = append(builder, strconv.Itoa(k)...)
    }
    return string(builder)
}

func main() {
    word := "word"
    fmt.Println(generateAbbreviations(word))
}{}
    

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

📺 База 1000+ реальных собеседований На программиста, тестировщика, аналитика, проджекта и другие IT профы. Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д. 🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

Задача: 1167. Minimum Cost to Connect Sticks Сложность: medium У вас есть несколько палочек с положительными целыми длинами. Эти длины даны в виде массива sticks, где sticks[i] — длина i-й палочки. Вы можете соединить любые две палочки длиной x и y в одну палочку, заплатив стоимость x + y. Вы должны соединить все палочки, пока не останется только одна палочка. Верните минимальную стоимость соединения всех данных палочек в одну палочку таким образом. Пример:

    
        Input: sticks = [5]
Output: 0
Explanation: There is only one stick, so you don't need to do anything. The total cost is 0.{}
    

👨‍💻 Алгоритм: 1⃣Всегда выбирайте две самые маленькие палочки для соединения и продолжайте делать это, пока не останется только одна палочка. Рассмотрим 4 палочки следующих длин: sticks=[a1, a2, a3, a4]. Попробуем соединить их слева направо. После первого соединения у нас будет: sticks=[(a1 + a2), a3, a4], стоимость=(a1 + a2). После второго соединения у нас будет: sticks=[(a1 + a2 + a3), a4], стоимость=(a1 + a2)+(a1 + a2 + a3). И, наконец, последняя палочка будет выглядеть так: sticks=[(a1 + a2 + a3 + a4)], стоимость=(a1 + a2)+(a1 + a2 + a3)+(a1 + a2 + a3 + a4). 2⃣Итоговая стоимость может быть переписана следующим образом: стоимость=(3a1 + 3a2 + 2a3 + a4). Как видим, палочки, которые соединяются первыми, включаются в итоговую стоимость больше, чем те, которые выбираются позже. Следовательно, оптимально сначала выбирать меньшие палочки, чтобы получить наименьшую стоимость. 3⃣Для выполнения следующих задач будет оптимальна структура данных min heap (которая обычно реализуется как PriorityQueue в большинстве языков): получить две самые маленькие палочки (stick1 и stick2) из массива; добавить одну палочку (stick1 + stick2) обратно в массив. Эта структура данных дает сложность O(logN) для обеих операций. 😎 Решение

    
        import (
    "container/heap"
)

type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}
func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func connectSticks(sticks []int) int {
    pq := &MinHeap{}
    heap.Init(pq)
    for _, stick := range sticks {
        heap.Push(pq, stick)
    }

    totalCost := 0
    for pq.Len() > 1 {
        stick1 := heap.Pop(pq).(int)
        stick2 := heap.Pop(pq).(int)
        cost := stick1 + stick2
        totalCost += cost
        heap.Push(pq, cost)
    }

    return totalCost
}{}
    

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

Задача: 82. Remove Duplicates from Sorted List II Сложность: medium Дана голова отсортированного связного списка. Удалите все узлы, содержащие повторяющиеся числа, оставив только уникальные числа из исходного списка. Верните отсортированный связный список. Пример:

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

👨‍💻 Алгоритм: 1⃣Инициализация "стража" и предшественника: Создается фиктивный начальный узел sentinel, который указывает на начало связного списка. Это делается для удобства управления указателем на начало списка, особенно если первые несколько узлов могут быть удалены. Устанавливаем предшественника pred, который будет последним узлом перед потенциально дублирующимися узлами. Изначально предшественником назначается страж. 2⃣Проход по списку с проверкой на дубликаты: Итерируемся по списку начиная с головы head. На каждом шаге проверяем, есть ли дублирующиеся узлы, сравнивая текущий узел head.val с следующим head.next.val. Если узлы дублируются, то пропускаем все последующие дубликаты, перемещая указатель head до последнего дублированного узла. После этого предшественник pred соединяется с первым узлом после всех дубликатов pred.next = head.next, тем самым пропуская весь блок дублированных узлов. 3⃣Переход к следующему узлу и возврат результата: Если текущий узел не имел дубликатов, просто переводим предшественника pred на следующий узел. Двигаем указатель head на следующий узел в списке. После завершения цикла возвращаем список, начиная с узла, на который указывает sentinel.next, что позволяет исключить все дублирующиеся узлы и вернуть начало нового списка без дубликатов. 😎 Решение:

    
        func deleteDuplicates(head *ListNode) *ListNode {
    sentinel := &ListNode{0, head}
    pred := sentinel
    for head != nil {
        if head.Next != nil && head.Val == head.Next.Val {
            for head.Next != nil && head.Val == head.Next.Val {
                head = head.Next
            }
            pred.Next = head.Next
        } else {
            pred = pred.Next
        }
        head = head.Next
    }
    return sentinel.Next
}{}
    

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

Задача: 658. Find K Closest Elements Сложность: easy Дан отсортированный массив целых чисел arr, два целых числа k и x. Верните k ближайших к x целых чисел в массиве. Результат также должен быть отсортирован в порядке возрастания. Целое число a ближе к x, чем целое число b, если: |a - x| < |b - x|, или |a - x| == |b - x| и a < b. Пример:

    
        Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]{}
    

👨‍💻 Алгоритм: 1⃣Бинарный поиск: Найдите положение числа x или ближайшего к нему числа в массиве arr с помощью бинарного поиска. 2⃣Два указателя: Используйте два указателя, чтобы расширять окно, которое содержит k ближайших к x элементов. Начните с ближайших элементов и расширяйте окно, сравнивая элементы слева и справа от текущего окна. 3⃣Сортировка: Отсортируйте итоговый список, если это необходимо (в данном случае это не нужно, так как массив уже отсортирован). 😎 Решение:

    
        func findClosestElements(arr []int, k int, x int) []int {
    left, right := 0, len(arr) - k

    for left < right {
        mid := (left + right) / 2
        if x - arr[mid] > arr[mid + k] - x {
            left = mid + 1
        } else {
            right = mid
        }
    }

    return arr[left:left + k]
}{}
    

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

Задача: 1380. Lucky Numbers in a Matrix Сложность: easy Дана матрица m x n из различных чисел, верните все счастливые числа в матрице в любом порядке. Счастливое число — это элемент матрицы, который является минимальным элементом в своей строке и максимальным в своем столбце. Пример: Input: matrix = [[3,7,8],[9,11,13],[15,16,17]] Output: [15] Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column. 👨‍💻 Алгоритм: 1⃣Сохраните минимум каждой строки в список rowMin и максимум каждого столбца в список colMax. 2⃣Итерируйте по каждому числу в матрице и проверяйте, равно ли оно rowMin[i] и colMax[j]. 3⃣Если число удовлетворяет условию, добавьте его в список luckyNumbers и верните luckyNumbers. 😎 Решение:

    
        func luckyNumbers(matrix [][]int) []int {
    N := len(matrix)
    M := len(matrix[0])

    rowMin := make([]int, N)
    for i := 0; i < N; i++ {
        rMin := matrix[i][0]
        for j := 1; j < M; j++ {
            if matrix[i][j] < rMin {
                rMin = matrix[i][j]
            }
        }
        rowMin[i] = rMin
    }

    colMax := make([]int, M)
    for i := 0; i < M; i++ {
        cMax := matrix[0][i]
        for j := 1; j < N; j++ {
            if matrix[j][i] > cMax {
                cMax = matrix[j][i]
            }
        }
        colMax[i] = cMax
    }

    var luckyNumbers []int
    for i := 0; i < N; i++ {
        for j := 0; j < M; j++ {
            if matrix[i][j] == rowMin[i] && matrix[i][j] == colMax[j] {
                luckyNumbers = append(luckyNumbers, matrix[i][j])
            }
        }
    }

    return luckyNumbers
}{}
    

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

Задача: 568. Maximum Vacation Days Сложность: hard LeetCode хочет предоставить одному из своих лучших сотрудников возможность путешествовать по n городам для сбора задач по алгоритмам. Однако, как говорится, "делу время, потехе час". Вы можете брать отпуска в некоторых конкретных городах и неделях. Ваша задача — спланировать поездку, чтобы максимально увеличить количество дней отпуска, которые вы сможете взять, соблюдая при этом определенные правила и ограничения. Правила и ограничения: Вы можете путешествовать только между n городами, обозначенными индексами от 0 до n-1. Изначально вы находитесь в городе с индексом 0 в понедельник. Города связаны рейсами. Рейсы представлены матрицей n x n, называемой flights, представляющей статус авиалинии от города i до города j. Если рейса из города i в город j нет, flights[i][j] == 0; иначе flights[i][j] == 1. Также для всех i выполняется flights[i][i] == 0. У вас есть k недель (каждая неделя состоит из семи дней) для путешествий. Вы можете летать не более одного раза в день и можете летать только утром каждого понедельника. Время полета настолько короткое, что его влияние не учитывается. Для каждого города у вас есть ограниченные дни отпуска в разные недели, заданные матрицей n x k, называемой days. Значение days[i][j] представляет максимальное количество дней отпуска, которые вы можете взять в городе i на неделе j. Даны две матрицы flights и days, верните максимальное количество дней отпуска, которые вы можете взять в течение k недель. Пример:

    
        Input: flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]
Output: 12
Explanation:
One of the best strategies is:
1st week : fly from city 0 to city 1 on Monday, and play 6 days and work 1 day.
(Although you start at city 0, we could also fly to and start at other cities since it is Monday.)
2nd week : fly from city 1 to city 2 on Monday, and play 3 days and work 4 days.
3rd week : stay at city 2, and play 3 days and work 4 days.
Ans = 6 + 3 + 3 = 12.{}
    

👨‍💻 Алгоритм: 1⃣Использовать функцию dfs (поиск в глубину), которая возвращает количество отпускных дней, которые можно взять, начиная с текущего города cur_city и текущей недели weekno. В каждом вызове функции проходить по всем городам и находить все города, которые связаны с текущим городом. Такой город обозначен 1 в соответствующей позиции flights[cur_city][i]. 2⃣Для текущего города можно либо остаться в нем, либо поехать в связанный город. Обозначим город, в который меняется расположение, как j. После смены города нужно найти количество отпускных дней, которые можно взять, начиная с нового города и с новой недели. Это количество отпускных дней можно представить как: days[j][weekno] + dfs(flights, days, j, weekno + 1). 3⃣Для текущего города необходимо найти максимальное количество отпускных дней, выбирая различные города в качестве следующего местоположения. Из всех вариантов отпускных дней выбираем максимальное значение, которое и будет возвращено для каждого вызова функции dfs. 😎 Решение:

    
        func maxVacationDays(flights [][]int, days [][]int) int {
    n, k := len(flights), len(days[0])
    memo := make([][]int, n)
    for i := range memo {
        memo[i] = make([]int, k)
        for j := range memo[i] {
            memo[i][j] = -1
        }
    }
    return dfs(flights, days, memo, 0, 0)
}

func dfs(flights [][]int, days [][]int, memo [][]int, curCity, weekNo int) int {
    n, k := len(flights), len(days[0])
    if weekNo == k {
        return 0
    }
    if memo[curCity][weekNo] != -1 {
        return memo[curCity][weekNo]
    }
    maxVac := 0
    for nextCity := 0; nextCity < n; nextCity++ {
        if curCity == nextCity || flights[curCity][nextCity] == 1 {
            maxVac = max(maxVac, days[nextCity][weekNo]+dfs(flights, days, memo, nextCity, weekNo+1))
        }
    }
    memo[curCity][weekNo] = maxVac
    return maxVac
}

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

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