Задача: 930. Binary Subarrays With Sum
Сложность: medium

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

Пример:

Input: nums = [1,0,1,0,1], goal = 2
Output: 4

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

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

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

3⃣Вернуть счетчик подмассивов.

😎 Решение:

package main

func numSubarraysWithSum(nums []int, goal int) int {
    prefixSumCount := map[int]int{0: 1}
    currentSum := 0
    count := 0
    
    for _, num := range nums {
        currentSum += num
        count += prefixSumCount[currentSum - goal]
        prefixSumCount[currentSum]++
    }
    
    return count
}

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

Задача: 219. Contains Duplicate II
Сложность: easy

Дан массив целых чисел nums и целое число k. Верните true, если в массиве существуют два различных индекса i и j, такие что nums[i] == nums[j] и abs(i - j) <= k.

Пример:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

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

1⃣Создайте пустое множество set.

2⃣Пройдитесь по массиву nums:
Если текущий элемент уже есть в множестве, верните true.
Добавьте текущий элемент в множество.
Если размер множества больше k, удалите элемент, который был добавлен k шагов назад.

3⃣Если не найдены дублирующиеся элементы на расстоянии k или менее, верните false.

😎 Решение:

func containsNearbyDuplicate(nums []int, k int) bool {
    set := make(map[int]struct{})
    for i, num := range nums {
        if _, exists := set[num]; exists {
            return true
        }
        set[num] = struct{}{}
        if len(set) > k {
            delete(set, nums[i-k])
        }
    }
    return false
}

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

Задача: 720. Longest Word in Dictionary
Сложность: medium

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

Пример:

Input: words = ["w","wo","wor","worl","world"]
Output: "world"

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

1⃣Отсортируйте массив слов по длине и лексикографическому порядку.

2⃣Используйте множество для отслеживания слов, которые можно построить.

3⃣Пройдите по каждому слову в отсортированном массиве и добавьте его в множество, если все его префиксы уже существуют в множестве.

😎 Решение:

package main

import (
    "sort"
)

func longestWord(words []string) string {
    sort.Strings(words)
    validWords := map[string]struct{}{ "": {} }
    longest := ""
    for _, word := range words {
        if _, ok := validWords[word[:len(word)-1]]; ok {
            validWords[word] = struct{}{}
            if len(word) > len(longest) {
                longest = word
            }
        }
    }
    return longest
}

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

Задача: 477. Total Hamming Distance
Сложность: medium

Хэммингово расстояние между двумя целыми числами — это количество позиций, в которых соответствующие биты отличаются.
Дан массив nums, нужно вернуть сумму Хэмминговых расстояний между всеми парами чисел в nums.

Пример:

Input: nums = [4,14,2] 
Output: 6

Explanation:

4  = 0100  
14 = 1110  
2  = 0010  

(4,14): 2 различия  
(4,2):  2 различия  
(14,2): 2 различия  
Итого: 2+2+2 = 6

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

1⃣Перебираем все уникальные пары чисел из массива.

2⃣Для каждой пары считаем XOR, чтобы выявить, на каких позициях биты различаются. Затем считаем количество единиц в этом числе — это и есть Хэммингово расстояние.

3⃣Суммируем результат по всем парам и возвращаем общую сумму.

😎 Решение:

package main

func totalHammingDistance(nums []int) int {
    ans := 0
    if len(nums) == 0 {
        return ans
    }
    for i := 0; i < len(nums)-1; i++ {
        for j := i + 1; j < len(nums); j++ {
            ans += countBits(nums[i] ^ nums[j])
        }
    }
    return ans
}

func countBits(n int) int {
    count := 0
    for n > 0 {
        count += n & 1
        n >>= 1
    }
    return count
}

func main() {}

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

Задача: №24. Swap Nodes in Pairs
Сложность: medium

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

Пример:

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

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

1⃣Создать фиктивный (dummy) узел перед head для удобства обработки начала списка.

2⃣Использовать указатели prev, first и second для перестановки пары узлов.

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

😎 Решение:

func swapPairs(head *ListNode) *ListNode {
    dummy := &ListNode{Next: head}
    prev := dummy

    for head != nil && head.Next != nil {
        first, second := head, head.Next

        prev.Next = second
        first.Next = second.Next
        second.Next = first

        prev = first
        head = first.Next
    }

    return dummy.Next
}

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

Задача: 1426. Counting Elements
Сложность: easy

Дан целочисленный массив arr, посчитайте, сколько элементов x в нем есть таких, что x + 1 также находится в arr. Если в arr есть дубликаты, считайте их отдельно.

Пример:

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

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

1⃣Создайте вспомогательную функцию для проверки, содержится ли элемент в массиве.

2⃣Итерируйте по каждому элементу массива и используйте вспомогательную функцию для проверки, содержится ли элемент x + 1 в массиве.

3⃣Увеличьте счетчик, если x + 1 найден, и верните значение счетчика.

😎 Решение:

package main

func countElements(arr []int) int {
    count := 0
    for _, x := range arr {
        if integerInArray(arr, x+1) {
            count++
        }
    }
    return count
}

func integerInArray(arr []int, target int) bool {
    for _, x := range arr {
        if x == target {
            return true
        }
    }
    return false
}

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

Задача: №65. Valid Number
Сложность: hard

Учитывая строку s, определите, является ли s валидным числом.

Например, все следующие строки являются действительными числами: "2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789". В то время как следующие строки не являются валидными числами: "abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53".

Формально, валидное число определяется с использованием одного из следующих определений:

Целое число с необязательным показателем степени.
Десятичное число с необязательным показателем степени.
Целое число определяется необязательным знаком '-' или '+' за которым следуют цифры.

Десятичное число определяется необязательным знаком '-' или '+' и одним из следующих определений:

Цифры, за которыми следует точка '.'.
Цифры, за которыми следует точка '.', за которой следуют цифры.
Точка '.', за которой следуют цифры.
Показатель степени определяется с помощью обозначения показателя степени 'e' или 'E', за которым следует целое число.

Цифры определяются как одна или более цифр.

Пример:

Input: s = "0"

Output: true

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

1⃣Объявите три переменные: seenDigit, seenExponent и seenDot, установив их все в false. Перебирайте символы входной строки. Если символ является цифрой, установите seenDigit в true.

2⃣Если символ является знаком (+ или -), проверьте, является ли он первым символом ввода или предшествует ли он показателю степени (экспоненте). Если нет, верните false. Если символ является экспонентой (e или E), сначала проверьте, была ли уже видна экспонента или еще не было увидено ни одной цифры. Если что-то из этого верно, верните false. В противном случае установите seenExponent в true и сбросьте seenDigit, потому что после экспоненты должно следовать новое целое число.

3⃣Если символ — точка (.), проверьте, были ли уже видны точка или экспонента. Если да, верните false. Иначе установите seenDot в true. Если символ чему-то иначе, верните false. В конце верните значение seenDigit, потому что, например, ввод вида "21e" должен быть признан недействительным, если после e не следуют цифры.

😎 Решение:

func isNumber(s string) bool {
    seenDigit := false
    seenExponent := false
    seenDot := false
    for i := 0; i < len(s); i++ {
        curr := s[i]
        if '0' <= curr && curr <= '9' {
            seenDigit = true
        } else if curr == '+' || curr == '-' {
            if i > 0 && s[i-1] != 'e' && s[i-1] != 'E' {
                return false
            }
        } else if curr == 'e' || curr == 'E' {
            if seenExponent || !seenDigit {
                return false
            }
            seenExponent = true
            seenDigit = false
        } else if curr == '.' {
            if seenDot || seenExponent {
                return false
            }
            seenDot = true
        } else {
            return false
        }
    }
    return seenDigit
}

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

Задача: 674. Longest Continuous Increasing Subsequence
Сложность: easy

Дан неотсортированный массив nums. Нужно найти длину самой длинной непрерывной строго возрастающей подпоследовательности (подмассива).

Пример:

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

Пояснение: [1,3,5] — самая длинная возрастающая подпоследовательность подряд. [1,3,5,7] — не считается, потому что 4 нарушает последовательность.

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

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

2⃣Проход по массиву
На каждой итерации проверяем: если текущий элемент не больше предыдущего (nums[i-1] >= nums[i]), значит возрастающая последовательность прерывается, и anchor сбрасывается на текущий индекс.

3⃣Обновление результата
На каждом шаге считаем длину текущей последовательности как i - anchor + 1 и обновляем ans, если она больше текущего значения.

😎 Решение:

func findLengthOfLCIS(nums []int) int {
    ans, anchor := 0, 0
    for i := 0; i < len(nums); i++ {
        if i > 0 && nums[i-1] >= nums[i] {
            anchor = i
        }
        if i-anchor+1 > ans {
            ans = i - anchor + 1
        }
    }
    return ans
}

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

Задача: 258. Add Digits
Сложность: easy

Дано целое число num. Повторно складывайте все его цифры, пока результат не станет однозначным, и верните его.

Пример:

Input: num = 38
Output: 2
Explanation: The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2 
Since 2 has only one digit, return it.

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

1⃣Инициализируйте переменную digital_root значением 0.

2⃣В цикле, пока num больше 0:
Добавьте к digital_root последнюю цифру num.
Уменьшите num, удалив последнюю цифру.
Если num равно 0 и digital_root больше 9, присвойте num значение digital_root и сбросьте digital_root в 0.

3⃣Верните значение digital_root.

😎 Решение:

func addDigits(num int) int {
    digital_root := 0
    for num > 0 {
        digital_root += num % 10
        num /= 10
        if num == 0 && digital_root > 9 {
            num = digital_root
            digital_root = 0
        }
    }
    return digital_root
}

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

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

Дан указатель на начало связанного списка. Верните список после его сортировки в порядке возрастания.

Пример:

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

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

1⃣Разделение списка (Фаза разделения):
Рекурсивно разделяйте исходный список на две половины. Процесс разделения продолжается до тех пор, пока в связанном списке не останется только один узел. Для разделения списка на две части используется подход с быстрым и медленным указателями, как упоминается в методе поиска середины связанного списка.

2⃣Сортировка подсписков и их объединение (Фаза слияния):
Рекурсивно сортируйте каждый подсписок и объединяйте их в один отсортированный список. Это аналогично задаче слияния двух отсортированных связанных списков.

3⃣Иллюстрация процесса сортировки:
Процесс продолжается до тех пор, пока не будет получен исходный список в отсортированном порядке. Например, для связанного списка [10,1,60,30,5] описан процесс сортировки слиянием с использованием подхода сверху вниз. Если у нас есть отсортированные списки list1 = [1,10] и list2 = [5,30,60], следующая анимация иллюстрирует процесс слияния обоих списков в один отсортированный список.

😎 Решение:

func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    mid := getMid(head)
    left := sortList(head)
    right := sortList(mid)
    return merge(left, right)
}

func merge(list1, list2 *ListNode) *ListNode {
    dummyHead := &ListNode{}
    tail := dummyHead
    for list1 != nil && list2 != nil {
        if list1.Val < list2.Val {
            tail.Next = list1
            list1 = list1.Next
        } else {
            tail.Next = list2
            list2 = list2.Next
        }
        tail = tail.Next
    }
    if list1 != nil {
        tail.Next = list1
    } else {
        tail.Next = list2
    }
    return dummyHead.Next
}

func getMid(head *ListNode) *ListNode {
    midPrev := (*ListNode)(nil)
    for head != nil && head.Next != nil {
        if midPrev == nil {
            midPrev = head
        } else {
            midPrev = midPrev.Next
        }
        head = head.Next.Next
    }
    mid := midPrev.Next
    midPrev.Next = nil
    return mid
}

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

Задача: 973. K Closest Points to Origin
Сложность: medium

Дан массив точек, где points[i] = [xi, yi] представляет собой точку на плоскости X-Y, и целое число k. Верните k точек, ближайших к началу координат (0, 0).

Расстояние между двумя точками на плоскости X-Y является евклидовым расстоянием (то есть √((x1 - x2)² + (y1 - y2)²)).

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

Пример:

Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].

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

1⃣Отсортируйте массив с помощью функции компаратора.

2⃣Функция компаратора будет использовать уравнение квадратного евклидова расстояния для сравнения двух точек.

3⃣Верните первые k элементов массива.

😎 Решение:

import (
    "sort"
)

func kClosest(points [][]int, k int) [][]int {
    sort.Slice(points, func(i, j int) bool {
        return squaredDistance(points[i]) < squaredDistance(points[j])
    })
    return points[:k]
}

func squaredDistance(point []int) int {
    return point[0]*point[0] + point[1]*point[1]
}

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

Задача: 233. Number of Digit One
Сложность: hard

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

Пример:

Input: n = 13
Output: 6

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

1⃣Итерация по степеням 10: Итеративно увеличивайте значение i от 1 до n, увеличивая i в 10 раз на каждом шаге. Это позволяет анализировать каждую цифру числа n.

2⃣Подсчет групповых единиц: Для каждой итерации добавляйте (n / (i * 10)) * i к счетчику countr, что представляет собой количество единиц, встречающихся в группах размера i после каждого интервала (i * 10).

3⃣Добавление дополнительных единиц: Для каждой итерации добавляйте min(max((n % (i * 10)) - i + 1, 0), i) к счетчику countr, что представляет собой дополнительные единицы, зависящие от цифры на позиции i.

😎 Решение:

func countDigitOne(n int) int {
    countr := 0
    for i := int64(1); i <= int64(n); i *= 10 {
        divider := i * 10
        countr += int(int64(n)/divider)*int(i) + int(min(max(int64(n)%divider-i+1, 0), i))
    }
    return countr
}

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

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

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

Задача: 752. Open the Lock
Сложность: medium

Перед вами замок с 4 круглыми колесами. Каждое колесо имеет 10 слотов: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. Колеса могут свободно вращаться и оборачиваться: например, мы можем повернуть "9" так, чтобы получился "0", или "0" так, чтобы получился "9". Каждый ход состоит из поворота одного колеса на один слот. Изначально замок начинается с '0000', строки, представляющей состояние 4 колес. Вам дан список тупиков, то есть если замок отобразит любой из этих кодов, колеса замка перестанут вращаться, и вы не сможете его открыть. Учитывая цель, представляющую значение колес, которое позволит отпереть замок, верните минимальное общее количество оборотов, необходимое для открытия замка, или -1, если это невозможно.

Пример:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6

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

1⃣Используйте алгоритм BFS для поиска кратчайшего пути от начального состояния '0000' до целевого состояния, избегая тупиков. Инициализируйте очередь с начальным состоянием '0000' и начальным шагом 0. Используйте множество для отслеживания посещенных состояний, чтобы избежать повторного посещения одного и того же состояния.

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

3⃣Если очередь пуста и целевое состояние не найдено, верните -1.

😎 Решение:

package main

import (
    "fmt"
)

func openLock(deadends []string, target string) int {
    neighbors := func(node string) []string {
        res := []string{}
        for i := 0; i < 4; i++ {
            x := node[i] - '0'
            for _, d := range []int{-1, 1} {
                y := (x + byte(d) + 10) % 10
                res = append(res, node[:i]+string(y+'0')+node[i+1:])
            }
        }
        return res
    }

    dead := make(map[string]bool)
    for _, d := range deadends {
        dead[d] = true
    }

    queue := []string{"0000"}
    steps := 0
    visited := make(map[string]bool)
    visited["0000"] = true

    for len(queue) > 0 {
        size := len(queue)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            if node == target {
                return steps
            }
            if dead[node] {
                continue
            }
            for _, neighbor := range neighbors(node) {
                if !visited[neighbor] {
                    visited[neighbor] = true
                    queue = append(queue, neighbor)
                }
            }
        }
        steps++
    }

    return -1
}

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

Задача: №55. Jump Game
Сложность: medium

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

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

Пример:

Input: nums = [2,3,1,1,4]  
Output: true  
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.  

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

1⃣Инициализация таблицы памяти:
- Изначально все элементы таблицы памяти имеют статус UNKNOWN, за исключением последнего, который является (тривиально) GOOD (может достичь сам себя).

2⃣Модификация алгоритма обратного трассирования:
- Измените алгоритм обратного трассирования таким образом, чтобы на рекурсивном шаге сначала проверялось, известен ли индекс (GOOD/BAD).
- Если индекс известен, тогда возвращается True/False.

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

😎 Решение:

type Index int

const (
    GOOD    Index = 1
    BAD     Index = 2
    UNKNOWN Index = 0
)

var memo []Index

func canJumpFromPosition(position int, nums []int) bool {
    if memo[position] != UNKNOWN {
        return memo[position] == GOOD
    }
    furthestJump := position + nums[position]
    if furthestJump > len(nums)-1 {
        furthestJump = len(nums) - 1
    }
    for nextPosition := position + 1; nextPosition <= furthestJump; nextPosition++ {
        if canJumpFromPosition(nextPosition, nums) {
            memo[position] = GOOD
            return true
        }
    }
    memo[position] = BAD
    return false
}

func canJump(nums []int) bool {
    memo = make([]Index, len(nums))
    for i := range memo {
        memo[i] = UNKNOWN
    }
    memo[len(nums)-1] = GOOD
    return canJumpFromPosition(0, nums)
}

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

Задача: 594. Longest Harmonious Subsequence
Сложность: easy

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

Дан целочисленный массив nums, верните длину его самой длинной гармоничной подпоследовательности среди всех возможных подпоследовательностей.

Подпоследовательность массива - это последовательность, которую можно получить из массива, удалив некоторые или никакие элементы, не изменяя порядок оставшихся элементов.

Пример:

Input: nums = [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

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

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

2⃣На каждой итерации проверьте, существуют ли в словаре элементы, отличающиеся на 1 от текущего, и обновите максимальную длину гармоничной подпоследовательности.

3⃣Верните максимальную длину гармоничной подпоследовательности.

😎 Решение:

func findLHS(nums []int) int {
    count := make(map[int]int)
    res := 0
    
    for _, num := range nums {
        count[num]++
        if count[num+1] > 0 {
            res = max(res, count[num]+count[num+1])
        }
        if count[num-1] > 0 {
            res = max(res, count[num]+count[num-1])
        }
    }
    
    return res
}

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

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

Задача: 1207. Unique Number of Occurrences
Сложность: easy

Дан массив целых чисел arr. Верните true, если количество вхождений каждого значения в массиве уникально, или false в противном случае.

Пример:

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

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

1⃣Сохраните частоты элементов массива arr в хэш-таблице freq.

2⃣Итерируйтесь по хэш-таблице freq и вставьте частоты всех уникальных элементов массива arr в хэш-набор freqSet.

3⃣Верните true, если размер хэш-набора freqSet равен размеру хэш-таблицы freq, иначе верните false.

😎 Решение:

func uniqueOccurrences(arr []int) bool {
    freq := make(map[int]int)
    for _, num := range arr {
        freq[num]++
    }
    freqSet := make(map[int]struct{})
    for _, count := range freq {
        freqSet[count] = struct{}{}
    }
    return len(freq) == len(freqSet)
}

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

Задача: 1135. Connecting Cities With Minimum Cost
Сложность: medium

Есть n городов, пронумерованных от 1 до n. Вам даны целое число n и массив connections, где connections[i] = [xi, yi, costi] указывает, что стоимость соединения города xi и города yi (двунаправленное соединение) равна costi.

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

Стоимость - это сумма использованных стоимостей соединений.

Пример:

Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
Output: 6
Explanation: Choosing any 2 edges will connect all cities so we choose the minimum 2.

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

1⃣Сортировка рёбер:
Отсортируйте все соединения (рёбра) в графе по их весам (стоимости) в порядке возрастания.

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

3⃣Проверка соединённости:
Подсчитайте количество рёбер в MST. Если оно меньше n-1, верните -1, так как соединить все города невозможно. Иначе верните суммарную стоимость рёбер в MST.

😎 Решение:

import "sort"

type DisjointSet struct {
    parent []int
}

func NewDisjointSet(n int) *DisjointSet {
    parent := make([]int, n+1)
    for i := 0; i <= n; i++ {
        parent[i] = i
    }
    return &DisjointSet{parent}
}

func (ds *DisjointSet) Find(x int) int {
    if ds.parent[x] != x {
        ds.parent[x] = ds.Find(ds.parent[x])
    }
    return ds.parent[x]
}

func (ds *DisjointSet) Union(x, y int) {
    rootX := ds.Find(x)
    rootY := ds.Find(y)
    if rootX != rootY {
        ds.parent[rootY] = rootX
    }
}

func minimumCost(n int, connections [][]int) int {
    sort.Slice(connections, func(i, j int) bool {
        return connections[i][2] < connections[j][2]
    })

    disjointSet := NewDisjointSet(n)
    totalCost := 0
    edgesUsed := 0

    for _, connection := range connections {
        x, y, cost := connection[0], connection[1], connection[2]
        if disjointSet.Find(x) != disjointSet.Find(y) {
            disjointSet.Union(x, y)
            totalCost += cost
            edgesUsed++
            if edgesUsed == n-1 {
                return totalCost
            }
        }
    }
    return -1
}

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

Задача: 537. Complex Number Multiplication
Сложность: medium

Комплексное число можно представить в виде строки в формате "real+imaginaryi", где:
real — это действительная часть и является целым числом в диапазоне [-100, 100].
imaginary — это мнимая часть и является целым числом в диапазоне [-100, 100].
i^2 == -1.
Даны два комплексных числа num1 и num2 в виде строк, верните строку комплексного числа, представляющую их произведение.

Пример:

Input: num1 = "1+1i", num2 = "1+1i"
Output: "0+2i"
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.

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

1⃣ Извлечение реальной и мнимой частей:
Разделите строки a и b на реальные и мнимые части, используя символы '+' и 'i'.

2⃣ Вычисление произведения:
Переведите извлечённые части в целые числа.
Используйте формулу для умножения комплексных чисел: (a+ib)×(x+iy)=ax−by+i(bx+ay).

3⃣ Формирование строки результата:
Создайте строку в требуемом формате с реальной и мнимой частями произведения и верните её.

😎 Решение:

import (
    "fmt"
    "strconv"
    "strings"
)

func complexNumberMultiply(a string, b string) string {
    x := strings.Split(a, "+")
    y := strings.Split(b, "+")
    a_real, _ := strconv.Atoi(x[0])
    a_img, _ := strconv.Atoi(x[1][:len(x[1])-1])
    b_real, _ := strconv.Atoi(y[0])
    b_img, _ := strconv.Atoi(y[1][:len(y[1])-1])
    realPart := a_real * b_real - a_img * b_img
    imaginaryPart := a_real * b_img + a_img * b_real
    return fmt.Sprintf("%d+%di", realPart, imaginaryPart)
}

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

Задача: 1376. Time Needed to Inform All Employees
Сложность: medium

В компании работает n сотрудников, каждому из которых присвоен уникальный идентификатор от 0 до n - 1. Руководитель компании имеет идентификатор headID.

У каждого сотрудника есть один непосредственный начальник, указанный в массиве manager, где manager[i] — это непосредственный начальник i-го сотрудника, manager[headID] = -1. Также гарантируется, что отношения подчинения образуют древовидную структуру.

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

i-й сотрудник нуждается в informTime[i] минутах, чтобы сообщить всем своим непосредственным подчиненным (т.е. через informTime[i] минут все его непосредственные подчиненные могут начать распространять новость).

Верните количество минут, необходимых для того, чтобы сообщить всем сотрудникам о срочной новости.

Пример:
Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.

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

1⃣Создайте список смежности adjList; индекс i будет хранить смежные узлы для сотрудника с идентификатором i.

2⃣Итерируйте по сотрудникам от 0 до N - 1, и для каждого сотрудника i добавляйте ребро manager[i] -> i, если manager[i] не равен -1.

3⃣Начните выполнение DFS с узла headID и временем 0 для каждого узла как curr. Обновите максимальное время maxTime, сравнив его с текущим временем. Итерируйте по смежным узлам curr и для каждого смежного узла выполните DFS с временем time + informTime[curr]. Когда DFS завершится, верните maxTime.

😎 Решение:

type Solution struct {
    maxTime int
}

func (s *Solution) DFS(adjList [][]int, informTime []int, curr int, time int) {
    if time > s.maxTime {
        s.maxTime = time
    }
    for _, adjacent := range adjList[curr] {
        s.DFS(adjList, informTime, adjacent, time + informTime[curr])
    }
}

func numOfMinutes(n int, headID int, manager []int, informTime []int) int {
    adjList := make([][]int, n)
    for i := 0; i < n; i++ {
        if manager[i] != -1 {
            adjList[manager[i]] = append(adjList[manager[i]], i)
        }
    }
    s := &Solution{maxTime: int(^uint(0) >> 1)}
    s.DFS(adjList, informTime, headID, 0)
    return s.maxTime
}

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

Задача: 380. Insert Delete GetRandom O(1)
Сложность: medium

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

RandomizedSet(): Инициализирует объект RandomizedSet.
bool insert(int val): Вставляет элемент val в множество, если его там нет. Возвращает true, если элемент отсутствовал, и false в противном случае.
bool remove(int val): Удаляет элемент val из множества, если он присутствует. Возвращает true, если элемент присутствовал, и false в противном случае.
int getRandom(): Возвращает случайный элемент из текущего множества элементов (гарантируется, что по крайней мере один элемент существует при вызове этого метода). Каждый элемент должен иметь равную вероятность быть возвращенным.
Вы должны реализовать функции класса таким образом, чтобы каждая функция работала в среднем за O(1) по времени.

Пример:

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

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

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

2⃣Метод insert(val): Проверить наличие значения в словаре. Если отсутствует, добавить значение в список и обновить словарь с новым индексом.
Метод remove(val): Проверить наличие значения в словаре. Если присутствует, заменить удаляемое значение последним элементом списка, обновить его индекс в словаре, удалить последний элемент из списка и удалить значение из словаря.

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

😎 Решение:

package main

import (
    "math/rand"
    "time"
)

type RandomizedSet struct {
    dict map[int]int
    list []int
}

func Constructor() RandomizedSet {
    rand.Seed(time.Now().UnixNano())
    return RandomizedSet{
        dict: make(map[int]int),
        list: make([]int, 0),
    }
}

func (this *RandomizedSet) Insert(val int) bool {
    if _, exists := this.dict[val]; exists {
        return false
    }
    this.dict[val] = len(this.list)
    this.list = append(this.list, val)
    return true
}

func (this *RandomizedSet) Remove(val int) bool {
    index, exists := this.dict[val]
    if !exists {
        return false
    }
    lastElement := this.list[len(this.list)-1]
    this.list[index] = lastElement
    this.dict[lastElement] = index
    this.list = this.list[:len(this.list)-1]
    delete(this.dict, val)
    return true
}

func (this *RandomizedSet) GetRandom() int {
    return this.list[rand.Intn(len(this.list))]
}

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