Golang | LeetCode

Задача: 661. Image Smoother Сложность: easy Дан целочисленный матрица img размером m x n, представляющая градации серого изображения. Верните изображение после применения сглаживания к каждой его ячейке. Пример:

    
        Input: img = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[0,0,0],[0,0,0],[0,0,0]]
Explanation:
For the points (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0
For the points (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0
For the point (1,1): floor(8/9) = floor(0.88888889) = 0{}
    

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

    
        func imageSmoother(img [][]int) [][]int {
    m, n := len(img), len(img[0])
    result := make([][]int, m)
    
    for i := range result {
        result[i] = make([]int, n)
        for j := 0; j < n; j++ {
            count, total := 0, 0
            for ni := max(0, i-1); ni <= min(m-1, i+1); ni++ {
                for nj := max(0, j-1); nj <= min(n-1, j+1); nj++ {
                    total += img[ni][nj]
                    count++
                }
            }
            result[i][j] = total / count
        }
    }
    
    return result
}

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

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

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

Задача: 654. Maximum Binary Tree Сложность: medium Вам дан целочисленный массив nums без дубликатов. Из nums можно рекурсивно построить максимальное двоичное дерево, используя следующий алгоритм: создайте корневой узел, значение которого равно максимальному значению в nums. Рекурсивно постройте левое поддерево по префиксу подмассива слева от максимального значения. Рекурсивно постройте правое поддерево по суффиксу подмассива справа от максимального значения. Верните максимальное двоичное дерево, построенное из nums. Пример:

    
        Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]{}
    

👨‍💻 Алгоритм: 1⃣Найдите максимальное значение в текущем подмассиве и создайте узел с этим значением. 2⃣Рекурсивно постройте левое поддерево для подмассива слева от максимального значения. 3⃣Рекурсивно постройте правое поддерево для подмассива справа от максимального значения. 😎 Решение:

    
        package main

import (
    "fmt"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func constructMaximumBinaryTree(nums []int) *TreeNode {
    return build(nums, 0, len(nums))
}

func build(nums []int, l, r int) *TreeNode {
    if l == r {
        return nil
    }
    maxIndex := max(nums, l, r)
    root := &TreeNode{Val: nums[maxIndex]}
    root.Left = build(nums, l, maxIndex)
    root.Right = build(nums, maxIndex+1, r)
    return root
}

func max(nums []int, l, r int) int {
    maxIndex := l
    for i := l + 1; i < r; i++ {
        if nums[i] > nums[maxIndex] {
            maxIndex = i
        }
    }
    return maxIndex
}

func main() {
    nums := []int{3, 2, 1, 6, 0, 5}
    root := constructMaximumBinaryTree(nums)
    fmt.Println(root)
}{}
    

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

Задача: 1168. Optimize Water Distribution in a Village Сложность: hard В деревне есть n домов. Мы хотим обеспечить все дома водой, строя колодцы и прокладывая трубы. Для каждого дома i мы можем либо построить колодец внутри него непосредственно с затратами wells[i - 1] (обратите внимание на -1 из-за нумерации с нуля), либо провести воду из другого колодца с помощью трубы. Затраты на прокладку труб между домами даны в массиве pipes, где каждый pipes[j] = [house1j, house2j, costj] представляет собой стоимость соединения дома house1j и дома house2j с помощью трубы. Соединения двунаправленные, и между одними и теми же домами могут быть несколько допустимых соединений с разными затратами. Верните минимальные оhttps://leetcode.com/problems/optimize-water-distribution-in-a-village/Figures/1168/PrimAlgDemo.gifбщие затраты на обеспечение всех домов водой. Пример:

    
        Input: n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]
Output: 3
Explanation: The image shows the costs of connecting houses using pipes.
The best strategy is to build a well in the first house with cost 1 and connect the other houses to it with cost 2 so the total cost is 3.{}
    

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

    
        import (
    "container/heap"
)

type Edge struct {
    cost, house int
}

type MinHeap []Edge

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].cost < h[j].cost }
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.(Edge))
}
func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func minCostToSupplyWater(n int, wells []int, pipes [][]int) int {
    graph := make([][]Edge, n+1)
    minHeap := &MinHeap{}
    heap.Init(minHeap)
    
    for i, cost := range wells {
        graph[0] = append(graph[0], Edge{cost, i + 1})
        heap.Push(minHeap, Edge{cost, i + 1})
    }
    
    for _, pipe := range pipes {
        house1, house2, cost := pipe[0], pipe[1], pipe[2]
        graph[house1] = append(graph[house1], Edge{cost, house2})
        graph[house2] = append(graph[house2], Edge{cost, house1})
    }
    
    mstSet := map[int]bool{0: true}
    totalCost := 0
    
    for len(mstSet) < n+1 {
        edge := heap.Pop(minHeap).(Edge)
        cost, nextHouse := edge.cost, edge.house
        if mstSet[nextHouse] {
            continue
        }
        mstSet[nextHouse] = true
        totalCost += cost
        for _, neighborEdge := range graph[nextHouse] {
            if !mstSet[neighborEdge.house] {
                heap.Push(minHeap, neighborEdge)
            }
        }
    }
    
    return totalCost
}{}
    

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

Задача: 935. Knight Dialer Сложность: medium Шахматный конь обладает уникальным движением: он может перемещаться на две клетки по вертикали и одну клетку по горизонтали, или на две клетки по горизонтали и одну клетку по вертикали (при этом обе клетки образуют форму буквы L). Возможные движения шахматного коня показаны на этой диаграмме: Шахматный конь может двигаться так, как показано на шахматной диаграмме ниже: У нас есть шахматный конь и телефонная панель, как показано ниже, конь может стоять только на числовой клетке (то есть на синей клетке). Учитывая целое число n, верните, сколько различных телефонных номеров длины n мы можем набрать. Вам разрешается сначала поставить коня на любую цифровую клетку, а затем выполнить n - 1 прыжков, чтобы набрать номер длины n. Все прыжки должны быть правильными прыжками коня. Поскольку ответ может быть очень большим, верните ответ по модулю 10^9 + 7. Пример:

    
        Input: n = 1
Output: 10{}
    

👨‍💻 Алгоритм: 1⃣Определить возможные движения коня с каждой цифровой клетки. Использовать динамическое программирование для хранения количества способов достижения каждой цифровой клетки на каждом шаге. 2⃣Инициализировать массив DP количеством способов набора телефонного номера длины 1 для каждой цифровой клетки (это просто 1). На каждом шаге обновлять массив DP, переходя по всем возможным движениям коня. 3⃣Вернуть сумму всех значений в массиве DP на последнем шаге. 😎 Решение:

    
        package main

const MOD = 1000000007

func knightDialer(n int) int {
    moves := map[int][]int{
        0: {4, 6},
        1: {6, 8},
        2: {7, 9},
        3: {4, 8},
        4: {0, 3, 9},
        5: {},
        6: {0, 1, 7},
        7: {2, 6},
        8: {1, 3},
        9: {2, 4},
    }
    
    dp := make([]int, 10)
    for i := range dp {
        dp[i] = 1
    }
    
    for step := 1; step < n; step++ {
        newDp := make([]int, 10)
        for i := 0; i < 10; i++ {
            for _, move := range moves[i] {
                newDp[move] = (newDp[move] + dp[i]) % MOD
            }
        }
        dp = newDp
    }
    
    sum := 0
    for _, count := range dp {
        sum = (sum + count) % MOD
    }
    return sum
}{}
    

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

Задача: 334. Increasing Triplet Subsequence Сложность: medium Дан массив целых чисел nums. Верните true, если существуют такие три индекса (i, j, k), что i < j < k и nums[i] < nums[j] < nums[k]. Если таких индексов не существует, верните false. Пример:

    
        Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.{}
    

👨‍💻 Алгоритм: 1⃣Инициализация переменных: Создайте две переменные first_num и second_num и установите их значение на максимальное целое значение (Integer.MAX_VALUE или аналогичный максимум для выбранного языка программирования). Эти переменные будут хранить минимальные значения, необходимые для проверки существования возрастающей тройки. 2⃣Итерация по массиву: Пройдите по каждому элементу массива nums. Для каждого элемента выполните следующие проверки: - если текущий элемент меньше или равен first_num, обновите first_num текущим элементом. - иначе, если текущий элемент меньше или равен second_num, обновите second_num текущим элементом. - иначе, если текущий элемент больше second_num, это означает, что найдена возрастающая тройка, поэтому верните true. 3⃣Возврат результата: Если после завершения итерации по массиву не была найдена возрастающая тройка, верните false. 😎 Решение:

    
        func increasingTriplet(nums []int) bool {
    firstNum := int(^uint(0) >> 1)  // Maximum integer
    secondNum := int(^uint(0) >> 1) // Maximum integer
    
    for _, n := range nums {
        if n <= firstNum {
            firstNum = n
        } else if n <= secondNum {
            secondNum = n
        } else {
            return true
        }
    }
    return false
}{}
    

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

Задача: 834. Sum of Distances in Tree Сложность: hard Есть неориентированное связное дерево с n узлами, пронумерованными от 0 до n - 1, и n - 1 ребрами. Вам даны целое число n и массив edges, где edges[i] = [ai, bi] указывает, что существует ребро между узлами ai и bi в дереве. Верните массив answer длиной n, где answer[i] — это сумма расстояний между i-м узлом в дереве и всеми другими узлами. Пример:

    
        Input: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Output: [8,12,6,10,10,10]
Explanation: The tree is shown above.
We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
equals 1 + 1 + 2 + 2 + 2 = 8.
Hence, answer[0] = 8, and so on.{}
    

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

    
        func sumOfDistancesInTree(N int, edges [][]int) []int {
    graph := make([]map[int]struct{}, N)
    for i := range graph {
        graph[i] = make(map[int]struct{})
    }
    for _, edge := range edges {
        graph[edge[0]][edge[1]] = struct{}{}
        graph[edge[1]][edge[0]] = struct{}{}
    }

    ans := make([]int, N)
    count := make([]int, N)
    for i := range count {
        count[i] = 1
    }

    var dfs func(int, int)
    dfs = func(node, parent int) {
        for child := range graph[node] {
            if child != parent {
                dfs(child, node)
                count[node] += count[child]
                ans[node] += ans[child] + count[child]
            }
        }
    }

    var dfs2 func(int, int)
    dfs2 = func(node, parent int) {
        for child := range graph[node] {
            if child != parent {
                ans[child] = ans[node] - count[child] + N - count[child]
                dfs2(child, node)
            }
        }
    }

    dfs(0, -1)
    dfs2(0, -1)
    return ans
}{}
    

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

🔍Тестовое собеседование с Go ТехЛидом из WildBerries в этот четверг 26 февраля(в четверг!) в 19:00 по мск приходи онлайн на открытое собеседование, чтобы посмотреть на настоящее интервью на Middle Go-разработчика. Как это будет: 📂 Рамиль Мясоутов, ТехЛид из WildBerries, ex-Купер будет задавать реальные вопросы и задачи разработчику-добровольцу 📂 Рамиль будет комментировать каждый ответ респондента, чтобы дать понять, чего от вас ожидает собеседующий на интервью 📂 В конце можно будет задать любой вопрос Рамилю Это бесплатно. Эфир проходит в рамках менторской программы от ШОРТКАТ для Go-разработчиков, которые хотят повысить свой грейд, ЗП и прокачать скиллы. Переходи в нашего бота, чтобы получить ссылку на эфир → @shortcut_go_bot Реклама. О рекламодателе.

Задача: 941. Valid Mountain Array Сложность: easy Задав массив целых чисел arr, верните true тогда и только тогда, когда он является допустимым горным массивом. Напомним, что arr является горным массивом тогда и только тогда, когда: arr.length >= 3 Существует некоторое i с 0 < i < arr.length - 1 такое, что: arr[0] < arr[1] < ... < arr[i - 1] < arr[i] arr[i] > arr[i + 1] > ... > arr[arr.length - 1] Пример:

    
        Input: arr = [2,1]
Output: false{}
    

👨‍💻 Алгоритм: 1⃣Убедиться, что длина массива не меньше 3. 2⃣Найти вершину горы, которая удовлетворяет условиям горного массива. Проверить, что все элементы слева от вершины строго возрастают. Проверить, что все элементы справа от вершины строго убывают. 3⃣Вернуть true, если оба условия выполнены, иначе вернуть false. 😎 Решение:

    
        package main

func validMountainArray(arr []int) bool {
    if len(arr) < 3 {
        return false
    }
    
    i := 1
    for i < len(arr) && arr[i] > arr[i-1] {
        i++
    }
    
    if i == 1 || i == len(arr) {
        return false
    }
    
    for i < len(arr) && arr[i] < arr[i-1] {
        i++
    }
    
    return i == len(arr)
}{}
    

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

Задача: 1146. Snapshot Array Сложность: medium Реализуйте SnapshotArray, который поддерживает следующий интерфейс: SnapshotArray(int length) инициализирует структуру данных, похожую на массив, с заданной длиной. Изначально каждый элемент равен 0. void set(index, val) устанавливает элемент с заданным индексом равным val. int snap() делает снимок массива и возвращает snap_id: общее количество вызовов snap() минус 1. int get(index, snap_id) возвращает значение на заданном индексе в момент, когда мы сделали снимок с указанным snap_id. Пример:

    
        Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation: 
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array[0] = 5
snapshotArr.snap();  // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array[0] with snap_id = 0, return 5{}
    

👨‍💻 Алгоритм: 1⃣Инициализация: Для каждого элемента nums[i] в массиве создайте пустой список для хранения его исторических значений в формате [snap_id, value]. Инициализируйте каждый список, добавив первую запись [0, 0]. 2⃣Метод set: Добавьте историческую запись [snap_id, value] в список записей historyRecords[index]. 3⃣Методы snap и get: Метод snap возвращает snap_id и увеличивает его на 1. Метод get использует бинарный поиск, чтобы найти индекс последней вставки snap_id в данный снимок (целевой индекс будет snap_index - 1). Возвращает historyRecords[index][snap_index - 1][1]. 😎 Решение:

    
        type SnapshotArray struct {
    snapId         int
    historyRecords []map[int]int
}

func Constructor(length int) SnapshotArray {
    historyRecords := make([]map[int]int, length)
    for i := range historyRecords {
        historyRecords[i] = map[int]int{0: 0}
    }
    return SnapshotArray{0, historyRecords}
}

func (this *SnapshotArray) Set(index int, val int) {
    this.historyRecords[index][this.snapId] = val
}

func (this *SnapshotArray) Snap() int {
    this.snapId++
    return this.snapId - 1
}

func (this *SnapshotArray) Get(index int, snapId int) int {
    record := this.historyRecords[index]
    for s := snapId; s >= 0; s-- {
        if val, ok := record[s]; ok {
            return val
        }
    }
    return 0
}{}
    

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

Задача: 645. Set Mismatch Сложность: easy У вас есть набор целых чисел s, который изначально содержит все числа от 1 до n. К сожалению, из-за какой-то ошибки одно из чисел в s продублировалось в другое число в наборе, что привело к повторению одного числа и потере другого. Вам дан целочисленный массив nums, представляющий состояние данных в этом наборе после ошибки. Найдите число, которое встречается дважды, и число, которое отсутствует, и верните их в виде массива. Пример:

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

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

    
        func findErrorNums(nums []int) []int {
    numSet := make(map[int]bool)
    duplicate := -1
    n := len(nums)
    for _, num := range nums {
        if numSet[num] {
            duplicate = num
        }
        numSet[num] = true
    }
    sum := 0
    for num := range numSet {
        sum += num
    }
    missing := (n * (n + 1)) / 2 - sum
    return []int{duplicate, missing}
}{}
    

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