Golang | LeetCode

Задача: 336. Palindrome Pairs
Сложность: hard

Вам дан массив уникальных строк words, индексируемый с 0.

Пара палиндромов — это пара целых чисел (i, j), таких что:
0 <= i, j < words.length,
i != j, и
words[i] + words[j] (конкатенация двух строк) является палиндромом.
Верните массив всех пар палиндромов из слов.

Вы должны написать алгоритм с временной сложностью O(сумма длин всех слов в words).

Пример:

Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]

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

1⃣Инициализация и подготовка данных:
Создайте структуру для хранения результатов (список пар индексов).
Создайте словарь для хранения слов и их индексов, чтобы ускорить поиск.

2⃣Итерация по всем парам слов и проверка:
Пройдите по всем парам слов в массиве words, используя два вложенных цикла.
Для каждой пары слов проверяйте, образуют ли они палиндром при конкатенации. Это делается путем объединения строк и проверки, равна ли объединенная строка своей обратной версии.

3⃣Добавление найденных пар в результат:
Если проверка на палиндром проходит, добавьте текущую пару индексов в список результатов.
Верните итоговый список всех найденных пар.

😎 Решение:

func palindromePairs(words []string) [][]int {
    var pairs [][]int
    
    for i := 0; i < len(words); i++ {
        for j := 0; j < len(words); j++ {
            if i == j {
                continue
            }
            combined := words[i] + words[j]
            if combined == reverseString(combined) {
                pairs = append(pairs, []int{i, j})
            }
        }
    }
    
    return pairs
}

func reverseString(s string) 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)
}

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

🔥 Скрытые вакансии с удаленной работой для Golang разработчика, которые нигде больше не публикуются. Напрямую от компаний, с контактами рекрутеров.

🔹 Golang Go Jobs | Вакансии

🔸 Все каналы с вакансиями

Задача: 897. Increasing Order Search Tree
Сложность: easy

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

Пример:

Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

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

1⃣Выполнить обход дерева в порядке in-order, чтобы получить список узлов.

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

3⃣Вернуть новый корень дерева (первый элемент списка).

😎 Решение:

package main

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

func increasingBST(root *TreeNode) *TreeNode {
    nodes := []*TreeNode{}
    
    var inorder func(node *TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        inorder(node.Left)
        nodes = append(nodes, node)
        inorder(node.Right)
    }
    
    inorder(root)
    
    for i := 0; i < len(nodes)-1; i++ {
        nodes[i].Left = nil
        nodes[i].Right = nodes[i+1]
    }
    
    nodes[len(nodes)-1].Left = nil
    nodes[len(nodes)-1].Right = nil
    return nodes[0]
}

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

Задача: 200. Number of Islands
Сложность: medium

Дана двумерная бинарная сетка размером m x n, представляющая карту из '1' (земля) и '0' (вода). Верните количество островов.

Остров окружён водой и образуется путём соединения соседних земель горизонтально или вертикально. Можно предположить, что все четыре края сетки окружены водой.

Пример:

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

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

1⃣Обход всей сетки:
- Если найден '1', запускаем поиск в глубину (DFS).

2⃣DFS для пометки острова:
- Заменяем '1' на '0', чтобы избежать повторного посещения.
- Рекурсивно вызываем DFS для всех четырёх направлений.

3⃣Подсчет островов:
- Каждый запуск DFS означает новый остров.
- Увеличиваем счетчик островов.

😎 Решение:

package main

func numIslands(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }

    numIslands := 0
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            if grid[i][j] == '1' {
                dfs(grid, i, j)
                numIslands++
            }
        }
    }
    return numIslands
}

func dfs(grid [][]byte, r, c int) {
    if r < 0 || c < 0 || r >= len(grid) || c >= len(grid[0]) || grid[r][c] != '1' {
        return
    }

    grid[r][c] = '0'
    dfs(grid, r-1, c)
    dfs(grid, r+1, c)
    dfs(grid, r, c-1)
    dfs(grid, r, c+1)
}

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

Задача: 313. Super Ugly Number
Сложность: medium

Супер некрасивое число — это положительное целое число, простые множители которого находятся в массиве primes.

Дано целое число n и массив целых чисел primes. Верните n-е супер некрасивое число.

Гарантируется, что n-е супер некрасивое число помещается в 32-битное знаковое целое число.

Пример:

Input: n = 12, primes = [2,7,13,19]
Output: 32
Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 super ugly numbers given primes = [2,7,13,19].

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

1⃣Инициализация
Создайте массив ugly_numbers длиной n для хранения супер некрасивых чисел. Создайте массив indices длиной primes для отслеживания позиций в массиве ugly_numbers. Создайте массив next_ugly длиной primes для хранения следующего возможного супер некрасивого числа для каждого простого числа из primes.

2⃣Генерация супер некрасивых чисел
Установите первое значение в ugly_numbers как 1. Повторяйте до тех пор, пока не заполните массив ugly_numbers: Найдите минимальное значение в массиве next_ugly и добавьте его в ugly_numbers. Обновите соответствующий индекс в indices и пересчитайте значение в next_ugly.

3⃣Возврат результата
Верните последнее значение в массиве ugly_numbers, которое будет n-м супер некрасивым числом.

😎 Решение:

func nthSuperUglyNumber(n int, primes []int) int {
    ugly_numbers := make([]int, n)
    ugly_numbers[0] = 1
    indices := make([]int, len(primes))
    next_ugly := append([]int(nil), primes...)
    
    for i := 1; i < n; i++ {
        next_val := min(next_ugly)
        ugly_numbers[i] = next_val
        
        for j := 0; j < len(primes); j++ {
            if next_val == next_ugly[j] {
                indices[j]++
                next_ugly[j] = ugly_numbers[indices[j]] * primes[j]
            }
        }
    }
    
    return ugly_numbers[n-1]
}

func min(arr []int) int {
    minVal := arr[0]
    for _, val := range arr {
        if val < minVal {
            minVal = val
        }
    }
    return minVal
}

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

Задача: 1166. Design File System
Сложность: medium

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

Формат пути - это одна или несколько конкатенированных строк в форме: /, за которой следует одна или несколько строчных английских букв. Например, "/leetcode" и "/leetcode/problems" - допустимые пути, в то время как пустая строка "" и "/" не допустимы.

Реализуйте класс FileSystem:

- bool createPath(string path, int value) создает новый путь и связывает с ним значение, если это возможно, и возвращает true. Возвращает false, если путь уже существует или его родительский путь не существует.
- int get(string path) возвращает значение, связанное с путем, или возвращает -1, если путь не существует.

Пример:

Input: 
["FileSystem","createPath","get"]
[[],["/a",1],["/a"]]
Output: 
[null,true,1]
Explanation: 
FileSystem fileSystem = new FileSystem();

fileSystem.createPath("/a", 1); // return true
fileSystem.get("/a"); // return 1

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

1⃣Инициализируйте словарь или HashMap под названием paths, который будет использовать ключ в виде пути, переданного в нашу функцию create, и значение, переданное этой функции.

2⃣Для функции create выполняем три шага. Сначала выполняем базовую проверку валидности пути. Проверяем, является ли путь пустым, "/" или если путь уже существует в нашем словаре. Если любое из этих условий выполнено, просто возвращаем false. Затем получаем родительский путь предоставленного пути и проверяем его наличие в словаре. Если родительский путь не существует, возвращаем false, иначе продолжаем.

3⃣Наконец, вставляем предоставленный путь и значение в словарь и возвращаем true. Для функции get просто возвращаем значение по умолчанию -1, если путь не существует в словаре. В противном случае возвращаем фактическое значение.

😎 Решение

type FileSystem struct {
    paths map[string]int
}

func Constructor() FileSystem {
    return FileSystem{paths: make(map[string]int)}
}

func (this *FileSystem) CreatePath(path string, value int) bool {
    if path == "" || (len(path) == 1 && path == "/") || this.paths[path] != 0 {
        return false
    }

    delimIndex := strings.LastIndex(path, "/")
    parent := path[:delimIndex]

    if len(parent) > 1 && this.paths[parent] == 0 {
        return false
    }

    this.paths[path] = value
    return true
}

func (this *FileSystem) Get(path string) int {
    if val, ok := this.paths[path]; ok {
        return val
    }
    return -1
}

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

Задача: 947. Most Stones Removed with Same Row or Column
Сложность: medium

Учитывая массив stones длины n, где stones[i] = [xi, yi] представляет местоположение i-го камня, верните наибольшее возможное количество камней, которые могут быть удалены.

Пример:

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5

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

1⃣Представить каждую строку и столбец как узлы в графе.

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

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

😎 Решение:

package main

func removeStones(stones [][]int) int {
    parent := make(map[int]int)
    
    var find func(int) int
    find = func(x int) int {
        if parent[x] == 0 {
            parent[x] = x
        }
        if parent[x] != x {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }
    
    union := func(x, y int) {
        parent[find(x)] = find(y)
    }
    
    for _, stone := range stones {
        union(stone[0], ^stone[1])
    }
    
    uniqueRoots := make(map[int]bool)
    for k := range parent {
        uniqueRoots[find(k)] = true
    }
    
    return len(stones) - len(uniqueRoots)
}

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

Задача: 1064. Fixed Point
Сложность: medium

Дан массив различных целых чисел arr, отсортированный в порядке возрастания. Верните наименьший индекс i, который удовлетворяет условию arr[i] == i. Если такого индекса нет, верните -1.

Пример:

Input: arr = [-10,-5,0,3,7]
Output: 3
Explanation: For the given array, arr[0] = -10, arr[1] = -5, arr[2] = 0, arr[3] = 3, thus the output is 3.

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

1⃣Инициализируйте значение left как 0, right как N - 1 и answer как -1.

2⃣Пока размер области поиска не равен нулю, то есть left <= right, выполните следующие шаги: найдите mid как mid = (left + right) / 2. Сравните arr[mid] и mid: если arr[mid] = mid, сохраните mid в answer и перейдите в левую часть, изменив right на mid - 1; если arr[mid] < mid, перейдите в правую часть, изменив left на mid + 1; если arr[mid] > mid, перейдите в левую часть, изменив right на mid - 1.

3⃣Верните answer.

😎 Решение:

func fixedPoint(arr []int) int {
    left, right := 0, len(arr) - 1
    answer := -1
    
    for left <= right {
        mid := (left + right) / 2
        
        if arr[mid] == mid {
            answer = mid
            right = mid - 1
        } else if arr[mid] < mid {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    return answer
}

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

Задача: 1413. Minimum Value to Get Positive Step by Step Sum
Сложность: easy

Дан массив целых чисел nums, вы начинаете с начального положительного значения startValue.

На каждой итерации вы вычисляете поэтапную сумму startValue плюс элементы из nums (слева направо).

Верните минимальное положительное значение startValue, такое что поэтапная сумма никогда не будет меньше 1.

Пример:

Input: nums = [-3,2,-3,4,2]
Output: 5
Explanation: If you choose startValue = 4, in the third iteration your step by step sum is less than 1.
step by step sum
startValue = 4 | startValue = 5 | nums
  (4 -3 ) = 1  | (5 -3 ) = 2    |  -3
  (1 +2 ) = 3  | (2 +2 ) = 4    |   2
  (3 -3 ) = 0  | (4 -3 ) = 1    |  -3
  (0 +4 ) = 4  | (1 +4 ) = 5    |   4
  (4 +2 ) = 6  | (5 +2 ) = 7    |   2

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

1⃣Инициализируйте переменные startValue со значением 1 и total со значением startValue.

2⃣Итеративно добавляйте каждый элемент массива nums к total и проверяйте, не опускается ли total ниже 1.

3⃣Если total падает ниже 1, увеличьте startValue на 1 и повторите шаги 2-3. Если total остается не менее 1, верните текущее значение startValue.

😎 Решение:

func minStartValue(nums []int) int {
    startValue := 1
    for {
        total := startValue
        isValid := true
        for _, num := range nums {
            total += num
            if total < 1 {
                isValid = false
                break
            }
        }
        if isValid {
            return startValue
        }
        startValue++
    }
}

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

Задача: 231. Power of Two
Сложность: easy

Дано целое число n, верните true, если оно является степенью двойки. В противном случае верните false.

Целое число n является степенью двойки, если существует целое число x, такое что n == 2^x.

Пример:

Input: n = 1
Output: true
Explanation: 2^0 = 1

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

1⃣Проверка на ноль: Если n равно нулю, верните false, так как ноль не является степенью двойки.

2⃣Преобразование к длинному типу: Преобразуйте n к типу long, чтобы избежать переполнения при выполнении побитовых операций.

3⃣Побитовая проверка: Используйте побитовую операцию, чтобы проверить, является ли число степенью двойки. Число является степенью двойки, если результат выражения (x & (-x)) равен x.

😎 Решение:

func isPowerOfTwo(n int) bool {
    if n == 0 {
        return false
    }
    x := int64(n)
    return (x & -x) == x
}

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

Задача: 441. Arranging Coins
Сложность: easy

У вас есть n монет, и вы хотите построить лестницу из этих монет. Лестница состоит из k рядов, где i-й ряд содержит ровно i монет. Последний ряд лестницы может быть неполным.

Дано целое число n, верните количество полных рядов лестницы, которые вы сможете построить.

Пример:

Input: n = 5
Output: 2
Explanation: Because the 3rd row is incomplete, we return 2.

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

1⃣Если мы глубже посмотрим на формулу задачи, мы можем решить её с помощью математики, без использования итераций.

2⃣Напомним, что условие задачи можно выразить следующим образом: k(k + 1) ≤ 2N.

3⃣Это можно решить методом выделения полного квадрата, (k + 1/2)² - 1/4 ≤ 2N. Что приводит к следующему ответу: k = [sqrt(2N + 1/4) - 1/2].

😎 Решение:

import "math"

func arrangeCoins(n int) int {
    return int(math.Sqrt(float64(2 * n) + 0.25) - 0.5)
}

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

Задача: 647. Palindromic Substrings
Сложность: medium

Реализуйте структуру данных MapSum, поддерживающую:

- Insert(key string, val int) — вставляет или обновляет значение по ключу.
- Sum(prefix string) — возвращает сумму значений всех ключей, начинающихся с указанного префикса.

Пример:

mapSum := Constructor()
mapSum.Insert("apple", 3)
mapSum.Sum("ap")      // 3
mapSum.Insert("app", 2)
mapSum.Sum("ap")      // 5 (3 + 2)

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

1⃣Хранение данных
Используем map[string]int для хранения всех ключей и их значений.

2⃣Операция Insert
Если ключ уже существует — просто перезаписываем новое значение.

3⃣Операция Sum
Проходим по всем ключам. Если ключ начинается с prefix, прибавляем его значение к результату.

😎 Решение:

package main

import "strings"

type MapSum struct {
    mapData map[string]int
}

func Constructor() MapSum {
    return MapSum{mapData: make(map[string]int)}
}

func (this *MapSum) Insert(key string, val int) {
    this.mapData[key] = val
}

func (this *MapSum) Sum(prefix string) int {
    ans := 0
    for key, val := range this.mapData {
        if strings.HasPrefix(key, prefix) {
            ans += val
        }
    }
    return ans
}

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

Задача: 315. Count of Smaller Numbers After Self
Сложность: hard

Дан целочисленный массив nums, верните целочисленный массив counts, где counts[i] - это количество элементов справа от nums[i], которые меньше nums[i].

Пример:

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

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

1⃣Реализуйте дерево отрезков (segment tree). Поскольку дерево инициализируется нулями, нужно реализовать только операции обновления и запроса. Установите смещение offset = 10^4.

2⃣Итерация по каждому числу в nums в обратном порядке. Для каждого числа выполните следующие действия:
Смещайте число на num + offset.
Запросите количество элементов в дереве отрезков, которые меньше текущего числа.
Обновите счетчик текущего числа в дереве отрезков.

3⃣Верните результат.

😎 Решение:

package main

import (
    "fmt"
    "sort"
)

func countSmaller(nums []int) []int {
    offset := 10000
    size := 2 * 10000 + 1
    tree := make([]int, size * 2)
    result := make([]int, len(nums))

    for i := len(nums) - 1; i >= 0; i-- {
        smallerCount := query(0, nums[i] + offset, tree, size)
        result[i] = smallerCount
        update(nums[i] + offset, 1, tree, size)
    }
    return result
}

func update(index, value int, tree []int, size int) {
    index += size
    tree[index] += value
    for index > 1 {
        index /= 2
        tree[index] = tree[index * 2] + tree[index * 2 + 1]
    }
}

func query(left, right int, tree []int, size int) int {
    result := 0
    left += size
    right += size
    for left < right {
        if left % 2 == 1 {
            result += tree[left]
            left++
        }
        left /= 2
        if right % 2 == 1 {
            right--
            result += tree[right]
        }
        right /= 2
    }
    return result
}

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

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

Задача: 283. Move Zeroes
Сложность: easy

Дан целочисленный массив nums. Переместите все нули в конец массива, сохраняя относительный порядок ненулевых элементов.

Обратите внимание, что вы должны сделать это на месте, не создавая копию массива.

Пример:

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

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

1⃣Инициализация указателей:
Инициализируйте два указателя: lastNonZeroFoundAt для отслеживания позиции последнего ненулевого элемента и cur для итерации по массиву.

2⃣Итерация и обмен элементами:
Итерируйтесь по массиву с помощью указателя cur.
Если текущий элемент ненулевой, поменяйте его местами с элементом, на который указывает lastNonZeroFoundAt, и продвиньте указатель lastNonZeroFoundAt.

3⃣Завершение итерации:
Повторяйте шаг 2 до конца массива. В итоге все нули будут перемещены в конец массива, сохраняя относительный порядок ненулевых элементов.

😎 Решение:

func moveZeroes(nums []int) {
    lastNonZeroFoundAt := 0
    for cur := 0; cur < len(nums); cur++ {
        if nums[cur] != 0 {
            nums[lastNonZeroFoundAt], nums[cur] = nums[cur], nums[lastNonZeroFoundAt]
            lastNonZeroFoundAt++
        }
    }
}

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

Задача: №28. Find the Index of the First Occurrence in a String
Сложность: easy

Учитывая две строки, needle и haystack, верните индекс первого вхождения needle в haystack, или -1, если needle не является частью haystack.

Пример:

Input: haystack = "sadbutsad", needle = "sad"  
Output: 0  

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

1⃣Обработка граничного случая:
- Если needle — пустая строка, вернуть 0 (по определению).

2⃣Итерация по возможным позициям:
- Проходим по всем индексам i от 0 до len(haystack) - len(needle),
- На каждой итерации сравниваем срез haystack[i:i+len(needle)] с needle.

3⃣Проверка совпадений:
- Если подстроки совпали — возвращаем текущий индекс i.
- Если не нашли ни одного совпадения — возвращаем -1.

😎 Решение:

func strStr(haystack string, needle string) int {
    n := len(needle)
    if n == 0 {
        return 0
    }
    for i := 0; i <= len(haystack)-n; i++ {
        if haystack[i:i+n] == needle {
            return i
        }
    }
    return -1
}

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

Задача: 943. Find the Shortest Superstring
Сложность: hard

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

Пример:

Input: words = ["alex","loves","leetcode"]
Output: "alexlovesleetcode"

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

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

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

3⃣Вернуть результат.

😎 Решение:

package main

func shortestSuperstring(words []string) string {
    for len(words) > 1 {
        maxOverlap := -1
        l, r := 0, 0
        merged := ""
        for i := 0; i < len(words); i++ {
            for j := 0; j < len(words); j++ {
                if i != j {
                    ovlp := overlap(words[i], words[j])
                    if ovlp > maxOverlap {
                        maxOverlap = ovlp
                        l = i
                        r = j
                        merged = merge(words[i], words[j], ovlp)
                    }
                }
            }
        }
        words[l] = merged
        words = append(words[:r], words[r+1:]...)
    }
    return words[0]
}

func overlap(a, b string) int {
    maxOverlap := 0
    for i := 1; i <= min(len(a), len(b)); i++ {
        if a[len(a)-i:] == b[:i] {
            maxOverlap = i
        }
    }
    return maxOverlap
}

func merge(a, b string, overlapLen int) string {
    return a + b[overlapLen:]
}

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

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

Задача: 164. Maximum Gap
Сложность: medium

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

Необходимо написать алгоритм, который работает за линейное время и использует линейное дополнительное пространство.

Пример:

Input: nums = [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.

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

1⃣Инициализация:
Определите минимальное и максимальное значения в массиве для расчета возможного максимального интервала (разрыва) между элементами в идеально распределенном массиве.
Вычислите размер ведра (bucket size), необходимый для размещения всех элементов массива так, чтобы если массив был равномерно распределен, каждый ведер должен содержать хотя бы один элемент. Размер ведра = (max_value - min_value) / (количество элементов - 1).

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

3⃣Вычисление максимального интервала:
Пройдите через ведра и вычислите максимальный интервал, сравнивая минимальное значение текущего непустого ведра с максимальным значением предыдущего непустого ведра.
Максимальный интервал будет наибольшей разницей между "минимальными" и "максимальными" значениями последовательных непустых ведер.

😎 Решение:

func maximumGap(nums []int) int {
    if len(nums) < 2 { 
        return 0
    }

    sort.Ints(nums)
    maxGap := 0

    for i := 0; i < len(nums)-1; i++ {
        diff := nums[i+1] - nums[i]
        if diff > maxGap {
            maxGap = diff
        }
    }

    return maxGap
}

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

Задача: 999. Available Captures for Rook
Сложность: easy

Вам дана матрица 8 x 8, изображающая шахматную доску. На ней есть ровно одна белая ладья, представленная символом "R", некоторое количество белых слонов "B" и некоторое количество черных пешек "p". Пустые клетки обозначаются символом '.'. Ладья может перемещаться на любое количество клеток по горизонтали или вертикали (вверх, вниз, влево, вправо), пока не достигнет другой фигуры или края доски. Ладья атакует пешку, если она может переместиться на ее клетку за один ход. Примечание: Ладья не может перемещаться через другие фигуры, такие как слоны или пешки. Это означает, что ладья не может атаковать пешку, если путь ей преграждает другая фигура. Верните количество пешек, которые атакует белая ладья.

Пример:

Input: board = [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]

Output: 3

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

1⃣Поиск ладьи:
Найдите координаты белой ладьи "R" на шахматной доске.

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

3⃣Подсчет атакованных пешек:
Если встреченная фигура - черная пешка "p", увеличьте счетчик атакованных пешек.
Если встреченная фигура - белый слон "B" или край доски, остановитесь в этом направлении.

😎 Решение:

func numRookCaptures(board [][]byte) int {
    countPawns := func(x, y, dx, dy int) int {
        for x >= 0 && x < 8 && y >= 0 && y < 8 {
            if board[x][y] == 'B' {
                break
            }
            if board[x][y] == 'p' {
                return 1
            }
            x += dx
            y += dy
        }
        return 0
    }

    for i := 0; i < 8; i++ {
        for j := 0; j < 8; j++ {
            if board[i][j] == 'R' {
                return countPawns(i, j, -1, 0) + countPawns(i, j, 1, 0) +
                       countPawns(i, j, 0, -1) + countPawns(i, j, 0, 1)
            }
        }
    }
    return 0
}

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

Задача: 1230. Toss Strange Coins
Сложность: medium

У вас есть несколько монет. Вероятность выпадения орла для i-й монеты равна prob[i].

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

Пример:

Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0
Output: 0.03125

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

1⃣Инициализация:
Создайте переменную n и инициализируйте её размером массива prob.
Создайте 2D массив dp размером n + 1 строк и target + 1 столбцов, где dp[i][j] хранит вероятность получить j орлов, используя первые i монет.
Установите базовый случай dp[0][0] = 1.

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

3⃣Возврат результата:
Верните значение dp[n][target], которое содержит искомую вероятность.

😎 Решение:

func probabilityOfHeads(prob []float64, target int) float64 {
    n := len(prob)
    dp := make([][]float64, n+1)
    for i := range dp {
        dp[i] = make([]float64, target+1)
    }
    dp[0][0] = 1.0

    for i := 1; i <= n; i++ {
        dp[i][0] = dp[i-1][0] * (1 - prob[i-1])
        for j := 1; j <= target; j++ {
            if j <= i {
                dp[i][j] = dp[i-1][j-1] * prob[i-1] + dp[i-1][j] * (1 - prob[i-1])
            }
        }
    }

    return dp[n][target]
}

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

Задача: 287. Find the Duplicate Number
Сложность: medium

Дан массив целых чисел nums, содержащий n + 1 целых чисел, где каждое число находится в диапазоне [1, n] включительно.
В массиве есть только одно повторяющееся число, верните это повторяющееся число.
Вы должны решить задачу, не изменяя массив nums и используя только постоянное дополнительное пространство.

Пример:

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

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

1⃣Определение дубликата:
Итерируйте по массиву, оценивая каждый элемент (назовем его cur). Используйте абсолютное значение текущего элемента, чтобы получить индекс.
Если элемент по индексу cur отрицательный, значит, мы уже встречали этот элемент ранее, и cur является дубликатом. Сохраните cur как дубликат и выйдите из цикла.
Если элемент по индексу cur положительный, инвертируйте знак этого элемента, чтобы пометить его как встреченный, и перейдите к следующему элементу.

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

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

😎 Решение:

func findDuplicate(nums []int) int {
    duplicate := -1
    for i := 0; i < len(nums); i++ {
        cur := abs(nums[i])
        if nums[cur] < 0 {
            duplicate = cur
            break
        }
        nums[cur] *= -1
    }
    for i := 0; i < len(nums); i++ {
        nums[i] = abs(nums[i])
    }
    return duplicate
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

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