#easy
Задача: 405. Convert a Number to Hexadecimal

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

Пример:

Input: num = 26
Output: "1a"

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

1⃣Определите, является ли число отрицательным. Если да, преобразуйте его в положительное число с помощью метода дополнения до двух. Для этого прибавьте к числу 2^32 и используйте битовую операцию И с маской 0xFFFFFFFF.

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

3⃣Переверните строку результата и удалите ведущие нули, если они есть. Если строка пустая, верните "0".

😎 Решение:

package main

import (
    "fmt"
    "strings"
)

func toHex(num int) string {
    if num == 0 {
        return "0"
    }
    hexChars := "0123456789abcdef"
    if num < 0 {
        num += 1 << 32
    }
    result := []byte{}
    for num > 0 {
        result = append(result, hexChars[num%16])
        num /= 16
    }
    for i, j := 0, len(result)-1; i < j; i, j = i+1, j-1 {
        result[i], result[j] = result[j], result[i]
    }
    return string(result)
}

func main() {
    fmt.Println(toHex(26))
    fmt.Println(toHex(-1))
}

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

#medium
Задача: 322. Coin Change

Дан целочисленный массив coins, представляющий монеты разных номиналов, и целое число amount, представляющее общую сумму денег.

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

Вы можете предположить, что у вас есть неограниченное количество монет каждого типа.

Пример:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

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

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

2⃣Функция backtracking
Внутри функции backtracking для каждой монеты из массива coins:
Проверьте все возможные количества монет данного номинала (от 0 до максимального количества, которое можно использовать без превышения amount). Для каждой комбинации монет обновите сумму и вызовите функцию рекурсивно для проверки оставшейся суммы. Если текущая комбинация дает меньшую сумму монет, обновите минимальное количество монет.

3⃣Возврат результата
Если комбинация, дающая сумму amount, найдена, верните минимальное количество монет, иначе верните -1.

😎 Решение:

package main

import (
    "fmt"
    "math"
)

func coinChange(coins []int, amount int) int {
    return coinChangeHelper(0, coins, amount)
}

func coinChangeHelper(idxCoin int, coins []int, amount int

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

#medium
Задача: 406. Queue Reconstruction by Height

Вам дан массив людей, people, которые являются атрибутами некоторых людей в очереди (не обязательно по порядку). Каждый people[i] = [hi, ki] представляет собой человека ростом hi, перед которым стоят ровно ki других людей, чей рост больше или равен hi. Реконструируйте и верните очередь, представленную входным массивом people. Возвращаемая очередь должна быть отформатирована как массив queue, где queue[j] = [hj, kj] - это атрибуты j-го человека в очереди (queue[0] - человек, находящийся в начале очереди).

Пример:

Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

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

1⃣Отсортируйте массив people по убыванию роста hi. Если два человека имеют одинаковый рост, отсортируйте их по возрастанию значения ki.

2⃣Создайте пустой список для результата. Вставляйте каждого человека из отсортированного массива в список на позицию, соответствующую значению ki.

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

😎 Решение:

package main

import (
    "sort"
)

func reconstructQueue(people [][]int) [][]int {
    sort.Slice(people, func(i, j int) bool {
        if people[i][0] == people[j][0] {
            return people[i][1] < people[j][1]
        }
        return people[i][0] > people[j][0]
    })
    result := [][]int{}
    for _, person := range people {
        result = append(result[:person[1]], append([][]int{person}, result[person[1]:]...)...)
    }
    return result
}

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

#medium
Задача: 323. Number of Connected Components in an Undirected Graph

У вас есть граф из n узлов. Вам дано целое число n и массив edges, где edges[i] = [ai, bi] указывает на наличие ребра между ai и bi в графе.

Верните количество связных компонентов в графе.

Пример:

Input: n = 5, edges = [[0,1],[1,2],[3,4]]
Output: 2

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

1⃣Создание списка смежности
Создайте список смежности, такой что adj[v] содержит все смежные вершины вершины v.

2⃣Инициализация посещенных узлов
Инициализируйте хэш-карту или массив visited для отслеживания посещенных вершин.

3⃣Подсчет компонентов
Определите счетчик и инициализируйте его нулем.
Итерируйте по каждой вершине в edges, и если вершина еще не была посещена, начните DFS с этой вершины. Добавляйте каждую вершину, посещенную во время DFS, в visited. Каждый раз, когда начинается новый DFS, увеличивайте счетчик на один. В конце, счетчик будет содержать количество связных компонентов в неориентированном графе.

😎 Решение:

package main

func countComponents(n int, edges [][]int) int {
    adj := make(map[int][]int)
    for _, edge := range edges {
        adj[edge[0]] = append(adj[edge[0]], edge[1])
        adj[edge[1]] = append(adj[edge[1]], edge[0])
    }

    visited := make(map[int]bool)
    count := 0

    var dfs func(int)
    dfs = func(node int) {
        stack := []int{node}
        for len(stack) > 0 {
            current := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            if !visited[current] {
                visited[current] = true
                for _, neighbor := range adj[current] {
                    if !visited[neighbor] {
                        stack = append(stack, neighbor)
                    }
                }
            }
        }
    }

    for i := 0; i < n; i++ {
        if !visited[i] {
            dfs(i)
            count++
        }
    }

    return count
}

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

#medium
Задача: 325. Maximum Size Subarray Sum Equals k

Дан целочисленный массив nums и целое число k. Верните максимальную длину подмассива, сумма которого равна k. Если такого подмассива не существует, верните 0.

Пример:

Input: nums = [1,-1,5,-2,3], k = 3
Output: 4
Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.

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

1⃣Инициализация переменных
Инициализируйте prefixSum как 0 для отслеживания префиксной суммы nums. Инициализируйте longestSubarray как 0 для отслеживания самой длинной подмассы с суммой k. Инициализируйте хеш-карту indices для хранения префиксных сумм и их индексов.

2⃣Итерация по массиву
На каждом индексе i, добавляйте nums[i] к prefixSum. Проверьте следующие условия: Если prefixSum == k, обновите longestSubarray как i + 1. Если prefixSum - k существует в indices, обновите longestSubarray, если текущая длина подмассива больше. Если текущий prefixSum еще не существует в indices, добавьте indices[prefixSum] = i.

3⃣Возврат результата
Верните значение longestSubarray.

😎 Решение:

package main

func maxSubArrayLen(nums []int, k int) int {
    prefixSum := 0
    longestSubarray := 0
    indices := make(map[int]int)
    
    for i, num := range nums {
        prefixSum += num
        
        if prefixSum == k {
            longestSubarray = i + 1
        }
        if idx, found := indices[prefixSum - k]; found {
            longestSubarray = max(longestSubarray, i - idx)
        }
        if _, found := indices[prefixSum]; !found {
            indices[prefixSum] = i
        }
    }
    
    return longestSubarray
}

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

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

#easy
Задача: 326. Power of Three

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

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

Пример:

Input: n = 27
Output: true
Explanation: 27 = 3^3

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

1⃣Проверка начального значения
Если n меньше или равно нулю, вернуть false, так как степени тройки всегда положительны.

2⃣Цикл деления на 3
Пока n делится на 3 без остатка, делите n на 3. Повторяйте этот процесс до тех пор, пока n делится на 3.

3⃣Проверка конечного значения
Если после всех делений значение n стало равно 1, значит исходное число является степенью тройки, вернуть true. В противном случае вернуть false.

😎 Решение:

func isPowerOfThree(n int) bool {
    if n <= 0 {
        return false
    }
    for n % 3 == 0 {
        n /= 3
    }
    return n == 1
}

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

#easy
Задача: 589. N-ary Tree Preorder Traversal

Дан корень N-арного дерева, верните значения его узлов в порядке предварительного (preorder) обхода.

Сериализация ввода N-арного дерева представлена в их обходе уровнями. Каждая группа детей разделена значением null (См. примеры).

Пример:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10]

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

1⃣Инициализация
Создайте два списка: stack для хранения узлов и output для хранения значений узлов в порядке обхода. Добавьте корневой узел в stack.

2⃣Итеративный обход
Пока stack не пуст, извлекайте узел из stack и добавляйте его значение в output. Разверните список дочерних узлов текущего узла и добавьте их в stack.

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

😎 Решение:

type Node struct {
    Val      int
    Children []*Node
}

func preorder(root *Node) []int {
    if root == nil {
        return nil
    }
    stack := []*Node{root}
    output := []int{}
    
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        output = append(output, node.Val)
        for i := len(node.Children) - 1; i >= 0; i-- {
            stack = append(stack, node.Children[i])
        }
    }
    
    return output
}

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

#Medium
Задача: 478. Generate Random Point in a Circle

Дан радиус и положение центра окружности, реализуйте функцию randPoint, которая генерирует равномерно случайную точку внутри окружности.

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

- Solution(double radius, double x_center, double y_center) инициализирует объект с радиусом окружности radius и положением центра (x_center, y_center).
- randPoint() возвращает случайную точку внутри окружности. Точка на окружности считается находящейся внутри окружности. Ответ возвращается в виде массива [x, y].

Пример:

Input
["Solution", "randPoint", "randPoint", "randPoint"]
[[1.0, 0.0, 0.0], [], [], []]
Output
[null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]]

Explanation
Solution solution = new Solution(1.0, 0.0, 0.0);
solution.randPoint(); // return [-0.02493, -0.38077]
solution.randPoint(); // return [0.82314, 0.38945]
solution.randPoint(); // return [0.36572, 0.17248]

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

1⃣ Генерируем равномерно случайные точки в квадрате S с длиной стороны 2R.

2⃣ Сохраняем все точки, которые находятся на расстоянии не более R от центра, и отклоняем все, которые дальше этого расстояния.

3⃣ Повторяем процесс до получения нужного количества точек, учитывая, что примерно 78.5% от всех сгенерированных точек будут приемлемыми, и ожидаемое число попыток до получения приемлемой точки составляет примерно 1.274 раза.

😎 Решение:

package main

import (
    "math"
    "math/rand"
    "time"
)

type Solution struct {
    rad, xc, yc float64
}

func Constructor(radius float64, x_center float64, y_center float64) Solution {
    rand.Seed(time.Now().UnixNano())
    return Solution{rad: radius, xc: x_center, yc: y_center}
}

func (s *Solution) RandPoint() []float64 {
    x0 := s.xc - s.rad
    y0 := s.yc - s.rad

    for {
        xg := x0 + rand.Float64()*s.rad*2
        yg := y0 + rand.Float64()*s.rad*2
        if math.Sqrt(math.Pow(xg-s.xc, 2)+math.Pow(yg-s.yc, 2)) <= s.rad {
            return []float64{xg, yg}
        }
    }
}

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

#Hard
Задача: 480. Sliding Window Median

Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, среднего значения не существует, поэтому медианой считается среднее значение двух средних чисел.

Например, если arr = [2, 3, 4], медиана равна 3.
Например, если arr = [1, 2, 3, 4], медиана равна (2 + 3) / 2 = 2.5.

Вам дан целочисленный массив nums и целое число k. Существует скользящее окно размера k, которое перемещается от самого левого края массива до самого правого. Вы можете видеть только k чисел в окне. Каждый раз скользящее окно перемещается вправо на одну позицию.

Верните массив медиан для каждого окна в исходном массиве. Ответы с точностью до 10^-5 будут приниматься.

Пример:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]
Explanation: 
Window position                Median
---------------                -----
[1  3  -1] -3  5  3  6  7        1
 1 [3  -1  -3] 5  3  6  7       -1
 1  3 [-1  -3  5] 3  6  7       -1
 1  3  -1 [-3  5  3] 6  7        3
 1  3  -1  -3 [5  3  6] 7        5
 1  3  -1  -3  5 [3  6  7]       6

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

1⃣Сохраняйте числа в контейнере окна размера k, выполняя следующие операции: Вставка входящего элемента. Удаление выходящего элемента.

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

3⃣ Поддерживайте окно в отсортированном состоянии до и после операций вставки и удаления.

😎 Решение:

package main

import (
    "sort"
)

func medianSlidingWindow(nums []int, k int) []float64 {
    var medians []float64

    for i := 0; i + k <= len(nums); i++ {
        window := append([]int(nil), nums[i:i+k]...)
        sort.Ints(window)

        if k % 2 == 1 {
            medians = append(medians, float64(window[k/2]))
        } else {
            medians = append(medians, float64(window[k/2-1]+window[k/2])/2.0)
        }
    }

    return medians
}

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

#Easy
Задача: 482. License Key Formatting

Вам дан лицензионный ключ, представленный в виде строки s, которая состоит только из буквенно-цифровых символов и тире. Строка разделена на n + 1 групп с помощью n тире. Вам также дано целое число k.

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

Верните переформатированный лицензионный ключ.

Пример:

Input: s = "5F3Z-2e-9-w", k = 4
Output: "5F3Z-2E9W"
Explanation: The string s has been split into two parts, each part has 4 characters.
Note that the two extra dashes are not needed and can be removed.

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

1⃣Инициализация
Установите count в 0 для подсчета символов в текущей группе. Установите ans в пустую строку для хранения конечного результата.

2⃣Итерация по входной строке в обратном порядке
Пропускайте символы '-'. Если текущий символ не '-', добавьте его в ans и увеличьте count на 1. Если count достигает k, добавьте '-' в ans и сбросьте count.

3⃣Завершение
Проверьте, есть ли в конце строки ans тире, и удалите его, если оно есть. Переверните строку ans и верните её.

😎 Решение:

package main

import (
    "strings"
    "unicode"
)

func licenseKeyFormatting(s string, k int) string {
    count := 0
    var ans strings.Builder

    for i := len(s) - 1; i >= 0; i-- {
        if s[i] != '-' {
            ans.WriteByte(byte(unicode.ToUpper(rune(s[i]))))
            count++
            if count == k {
                ans.WriteByte('-')
                count = 0
            }
        }
    }

    res := ans.String()
    if len(res) > 0 && res[len(res)-1] == '-' {
        res = res[:len(res)-1]
    }

    runes := []rune(res)
    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)
}

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

#Medium
Задача: 484. Find Permutation

Перестановка perm из n целых чисел всех чисел в диапазоне [1, n] может быть представлена в виде строки s длиной n - 1, где:

s[i] == 'I', если perm[i] < perm[i + 1], и
s[i] == 'D', если perm[i] > perm[i + 1].
Дана строка s, восстановите лексикографически наименьшую перестановку perm и верните её.

Пример:

Input: s = "I"
Output: [1,2]
Explanation: [1,2] is the only legal permutation that can represented by s, where the number 1 and 2 construct an increasing relationship.

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

1⃣Инициализация
Создайте пустой стек stack. Создайте пустой список result для хранения конечной перестановки.

2⃣Для каждого числа i
Если текущий символ в строке s равен 'D', добавьте i в стек. Если текущий символ в строке s равен 'I', добавьте i в стек, затем извлеките все элементы из стека и добавьте их в result.

3⃣Завершение
Добавьте n в стек и извлеките все элементы из стека, добавив их в result. Верните список result, который представляет лексикографически наименьшую перестановку.

😎 Решение:

func findPermutation(s string) []int {
    res := make([]int, len(s)+1)
    stack := []int{}
    j := 0
    for i := 1; i <= len(s); i++ {
        if s[i-1] == 'I' {
            stack = append(stack, i)
            for len(stack) > 0 {
                res[j] = stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                j++
            }
        } else {
            stack = append(stack, i)
        }
    }
    stack = append(stack, len(s)+1)
    for len(stack) > 0 {
        res[j] = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        j++
    }
    return res
}

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

#Easy
Задача: 485. Max Consecutive Ones

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

Пример:

Input: nums = [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s. The maximum number of consecutive 1s is 3.

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

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

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

3⃣В конце верните максимальное значение.

😎 Решение:

func findMaxConsecutiveOnes(nums []int) int {
    count := 0
    maxCount := 0
    for _, num := range nums {
        if num == 1 {
            count++
        } else {
            if count > maxCount {
                maxCount = count
            }
            count = 0
        }
    }
    if count > maxCount {
        maxCount = count
    }
    return maxCount
}

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

#Medium
Задача: 486. Predict the Winner

Дан целочисленный массив nums. Два игрока играют в игру с этим массивом: игрок 1 и игрок 2.

Игрок 1 и игрок 2 ходят по очереди, начиная с игрока 1. Оба игрока начинают игру с нулевым счетом. В каждый ход игрок берет одно из чисел с любого конца массива (то есть nums[0] или nums[nums.length - 1]), что уменьшает размер массива на 1. Игрок добавляет выбранное число к своему счету. Игра заканчивается, когда в массиве не останется элементов.

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

Пример:

Input: nums = [1,5,2]
Output: false
Explanation: Initially, player 1 can choose between 1 and 2. 
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2). 
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5. 
Hence, player 1 will never be the winner and you need to return 

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

1⃣Определите maxDiff(left, right) как максимальную разницу в счете, которую текущий игрок может достичь. Если left = right, верните nums[left].

2⃣В противном случае текущий игрок может выбрать nums[left] или nums[right]. Максимальная разница в счете, которую он может получить, равна большему из значений nums[left] - maxDiff(left + 1, right) и nums[right] - maxDiff(left, right - 1).

3⃣Верните true, если maxDiff(0, n - 1) >= 0. Этот вызов сделан с точки зрения первого игрока, и первый игрок является победителем, если у игроков одинаковый счет (разница 0).

😎 Решение:

func maxDiff(nums []int, left int, right int) int {
    if left == right {
        return nums[left]
    }

    scoreByLeft := nums[left] - maxDiff(nums, left+1, right)
    scoreByRight := nums[right] - maxDiff(nums, left, right-1)

    if scoreByLeft > scoreByRight {
        return scoreByLeft
    }
    return scoreByRight
}

func predictTheWinner(nums []int) bool {
    return maxDiff(nums, 0, len(nums)-1) >= 0
}

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

#hard
Задача: 407. Trapping Rain Water II

Задав целочисленную матрицу heightMap размером m x n, представляющую высоту каждой ячейки на двумерной карте рельефа, верните объем воды, который она может задержать после дождя.

Пример:

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

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

1⃣Используйте приоритетную очередь для хранения всех ячеек по периметру матрицы.

2⃣Постепенно извлекайте ячейки из очереди, рассматривая их соседей. Если соседняя ячейка ниже текущей, добавьте разницу в высоте к общему объему воды и обновите её высоту.

3⃣Повторите процесс, пока все ячейки не будут обработаны.

😎 Решение:

package main

import (
    "container/heap"
)

type cell struct {
    height, x, y int
}

type minHeap []cell

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

func trapRainWater(heightMap [][]int) int {
    if len(heightMap) == 0 || len(heightMap[0]) == 0 {
        return 0
    }
    m, n := len(heightMap), len(heightMap[0])
    visited := make([][]bool, m)
    for i := range visited {
        visited[i] = make([]bool, n)
    }
    h := &minHeap{}
    heap.Init(h)
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if i == 0 || i == m-1 || j == 0 || j == n-1 {
                heap.Push(h, cell{heightMap[i][j], i, j})
                visited[i][j] = true
            }
        }
    }
    directions := []struct{ x, y int }{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
    water := 0
    for h.Len() > 0 {
        c := heap.Pop(h).(cell)
        for _, dir := range directions {
            nx, ny := c.x+dir.x, c.y+dir.y
            if nx >= 0 && ny >= 0 && nx < m && ny < n && !visited[nx][ny] {
                visited[nx][ny] = true
                if c.height > heightMap[nx][ny] {
                    water += c.height - heightMap[nx][ny]
                }
                heap.Push(h, cell{max(c.height, heightMap[nx][ny]), nx, ny})
            }
        }
    }
    return water
}

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

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

#easy
Задача: 408. Valid Word Abbreviation

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

Например, строка "замена" может быть сокращена следующим образом (но не ограничивается этим): "s10n" ("s ubstitutio n") "sub4u4" ("sub stit u tion") "12" ("замена") "su3i1u2on" ("su bst i t u ti on") "substitution" (без замены подстрок) Следующие сокращения не являются допустимыми:

"s55n" ("s ubsti tutio n", заменяемые подстроки смежные) "s010n" (содержит ведущие нули) "s0ubstitution" (заменяет пустую подстроку) Если задано строковое слово и аббревиатура abbr, верните, соответствует ли строка заданной аббревиатуре.

Подстрока - это непрерывная непустая последовательность символов в строке.

Пример:

Input: word = "internationalization", abbr = "i12iz4n"
Output: true

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

1⃣Инициализируйте два указателя: один для строки word и один для аббревиатуры abbr. Начните сравнение символов строки и аббревиатуры с начала.

2⃣Если символ аббревиатуры - это цифра, вычислите полное число и переместите указатель строки word на это количество символов. Если символ аббревиатуры - это буква, убедитесь, что он совпадает с текущим символом строки.

3⃣Повторяйте шаг 2, пока оба указателя не достигнут конца строки и аббревиатуры соответственно. Если это так, верните true, иначе false.

😎 Решение:

package main

import (
    "strconv"
    "unicode"
)

func validWordAbbreviation(word string, abbr string) bool {
    i, j := 0, 0
    for i < len(word) && j < len(abbr) {
        if unicode.IsDigit(rune(abbr[j])) {
            if abbr[j] == '0' {
                return false
            }
            num := 0
            for j < len(abbr) && unicode.IsDigit(rune(abbr[j])) {
                n, _ := strconv.Atoi(string(abbr[j]))
                num = num*10 + n
                j++
            }
            i += num
        } else {
            if word[i] != abbr[j] {
                return false
            }
            i++
            j++
        }
    }
    return i == len(word) && j == len(abbr)
}

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

#easy
Задача: 409. Longest Palindrome

Если задана строка s, состоящая из строчных или прописных букв, верните длину самого длинного палиндрома, который можно построить из этих букв. Буквы чувствительны к регистру, например, "Aa" не считается палиндромом.

Пример:

Input: s = "abccccdd"
Output: 7

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

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

2⃣Пройдитесь по словарю и добавьте четное количество каждого символа к длине палиндрома. Если встречается нечетное количество символа, добавьте (count - 1) к длине палиндрома.

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

😎 Решение:

package main

func longestPalindrome(s string) int {
    charCount := make(map[rune]int)
    for _, char := range s {
        charCount[char]++
    }
    length := 0
    oddFound := false
    for _, count := range charCount {
        if count % 2 == 0 {
            length += count
        } else {
            length += count - 1
            oddFound = true
        }
    }
    if oddFound {
        return length + 1
    }
    return length
}

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

#easy
Задача: 410. Split Array Largest Sum

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

Пример:

Input: nums = [7,2,5,10,8], k = 2
Output: 18

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

1⃣Определите границы для бинарного поиска: минимальная сумма равна максимальному элементу массива, максимальная сумма равна сумме всех элементов массива.

2⃣Выполните бинарный поиск по этим границам. Для каждой средней суммы проверьте, можно ли разбить массив на k подмассивов, чтобы максимальная сумма подмассива не превышала эту среднюю сумму.

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

😎 Решение:

package main

func splitArray(nums []int, k int) int {
    left, right := max(nums), sum(nums)
    for left < right {
        mid := (left + right) / 2
        if canSplit(nums, k, mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

func canSplit(nums []int, k int, maxSum int) bool {
    currentSum, subarrays := 0, 1
    for _, num := range nums {
        if currentSum + num > maxSum {
            currentSum = num
            subarrays++
            if subarrays > k {
                return false
            }
        } else {
            currentSum += num
        }
    }
    return true
}

func max(nums []int) int {
    maxNum := nums[0]
    for _, num := range nums {
        if num > maxNum {
            maxNum = num
        }
    }
    return maxNum
}

func sum(nums []int) int {
    total := 0
    for _, num := range nums {
        total += num
    }
    return total
}

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

#hard
Задача: 411. Minimum Unique Word Abbreviation

Строку можно сократить, заменив любое количество не смежных подстрок их длинами. Например, строка "substitution" может быть сокращена как (но не ограничиваясь этим):

"s10n" ("s ubstitutio n") "sub4u4" ("sub stit u tion") "12" ("substitution") "su3i1u2on" ("su bst i t u ti on") "substitution" (без замен подстрок) Обратите внимание, что "s55n" ("s ubsti tutio n") не является правильным сокращением "substitution", поскольку замененные подстроки являются смежными.

Длина аббревиатуры - это количество букв, которые не были заменены, плюс количество подстрок, которые были заменены. Например, аббревиатура "s10n" имеет длину 3 (2 буквы + 1 подстрока), а "su3i1u2on" - 9 (6 букв + 3 подстроки). Учитывая целевую строку target и массив строк dictionary, верните аббревиатуру target с наименьшей возможной длиной, которая не является аббревиатурой ни одной строки в словаре. Если существует несколько самых коротких аббревиатур, верните любую из них.

Пример:

Input: target = "apple", dictionary = ["blade"]
Output: "a4"

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

1⃣Создайте множество всех аббревиатур из словаря, вычислив их все возможные аббревиатуры.

2⃣Сгенерируйте все возможные аббревиатуры для строки target.

3⃣Найдите самую короткую аббревиатуру для target, которая отсутствует в множестве аббревиатур словаря.

😎 Решение:

package main

import (
    "sort"
    "strconv"
)

func generateAbbreviations(word string) map[string]struct{} {
    result := make(map[string]struct{})
    helper(word, "", 0, 0, result)
    return result
}

func helper(word, current string, pos, count int, result map[string]struct{}) {
    if pos == len(word) {
        if count > 0 {
            current += strconv.Itoa(count)
        }
        result[current] = struct{}{}
        return
    }
    helper(word, current, pos+1, count+1, result)
    if count > 0 {
        current += strconv.Itoa(count)
    }
    helper(word, current+string(word[pos]), pos+1, 0, result)
}

func minAbbreviation(target string, dictionary []string) string {
    targetAbbrs := generateAbbreviations(target)
    dictAbbrs := make(map[string]struct{})
    for _, word := range dictionary {
        for abbr := range generateAbbreviations(word) {
            dictAbbrs[abbr] = struct{}{}
        }
    }
    validAbbrs := make([]string, 0)
    for abbr := range targetAbbrs {
        if _, exists := dictAbbrs[abbr]; !exists {
            validAbbrs = append(validAbbrs, abbr)
        }
    }
    sort.Slice(validAbbrs, func(i, j int) bool {
        return len(validAbbrs[i]) < len(validAbbrs[j])
    })
    return validAbbrs[0]
}

// Пример использования
func main() {
    target := "substitution"
    dictionary := []string{"substitution", "subtitution", "substitutio"}
    println(minAbbreviation(target, dictionary))
}

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

#easy
Задача: 412. Fizz Buzz

Учитывая целое число n, верните строковый массив answer (с индексом 1), где: answer[i] == "FizzBuzz", если i делится на 3 и 5. answer[i] == "Fizz", если i делится на 3. answer[i] == "Buzz", если i делится на 5. answer[i] == i (как строка), если ни одно из перечисленных условий не верно.

Пример:

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

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

1⃣Создайте пустой список для хранения результата.

2⃣Пройдите по всем числам от 1 до n и для каждого числа выполните проверку: Если число делится на 3 и на 5, добавьте "FizzBuzz". Если число делится на 3, добавьте "Fizz". Если число делится на 5, добавьте "Buzz". Если ни одно из условий не выполнено, добавьте само число как строку.

3⃣Верните полученный список.

😎 Решение:

package main

import (
    "strconv"
)

func fizzBuzz(n int) []string {
    answer := make([]string, n)
    for i := 1; i <= n; i++ {
        switch {
        case i % 3 == 0 && i % 5 == 0:
            answer[i-1] = "FizzBuzz"
        case i % 3 == 0:
            answer[i-1] = "Fizz"
        case i % 5 == 0:
            answer[i-1] = "Buzz"
        default:
            answer[i-1] = strconv.Itoa(i)
        }
    }
    return answer
}

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

#medium
Задача: 413. Arithmetic Slices

Целочисленный массив называется арифметическим, если он состоит не менее чем из трех элементов и если разность между любыми двумя последовательными элементами одинакова. Например, [1,3,5,7,9], [7,7,7] и [3,-1,-5,-9] являются арифметическими последовательностями. Если задан целочисленный массив nums, верните количество арифметических подмассивов массива nums. Подмассив - это непрерывная подпоследовательность массива.

Пример:

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

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

1⃣Пройдите по массиву, инициализируя два указателя: начальный и текущий. Начните с первой пары элементов.

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

3⃣Суммируйте количество найденных арифметических подмассивов, учитывая, что для каждого арифметического подмассива длины len, количество таких подмассивов равно (len - 2).

😎 Решение:

package main

func numberOfArithmeticSlices(nums []int) int {
    count := 0
    currentLength := 0
    for i := 2; i < len(nums); i++ {
        if nums[i]-nums[i-1] == nums[i-1]-nums[i-2] {
            currentLength++
            count += currentLength
        } else {
            currentLength = 0
        }
    }
    return count
}

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