На easyoffer 2.0 появится:
База тестовых заданий

🟠Тестовые задания для разных грейдов
🟠Фильтрация тестовых заданий по технологиям и компаниям

Когда я только начинал учиться на программиста, я постоянно выдумывал себе задачи для практики и тратил на это много времени. Но только в момент поиска работы я столкнулся с тестовыми заданиями, и понял насколько круто они прокачивают навыки. Нужно было еще на этапе обучения пробовать их делать. Все компании стараются составить тестовое задание "под себя", это дает большой выбор в тематике задач и технологий. На easyoffer 2.0 вы сможете отфильтровать тестовые задания по навыкам/грейдам и найти те, что подходят лично вам для практики.

В течение 1-2 дней я объявлю о краудфандинг кампании, чтобы ускорить разработку easyoffer 2.0. Все кто, поддержал проект на этом этапе смогу получить 1 год доступа к сайту по цене месячной подписки и смогут попасть на закрытое бета-тестирование. А первые 150 донатеров получать особо-выгодную цену и бонус.

🚀 Следите за стартом 👉 в этом телеграм канале, в нем информация о старте будет опубликована за 6 часов до официального начала.

Задача: 1055. Shortest Way to Form String
Сложность: medium

Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (например, "ace" является подпоследовательностью "abcde", а "aec" - нет). Если даны две строки source и target, верните минимальное количество подпоследовательностей source, чтобы их объединение равнялось target. Если задача невыполнима, верните -1.

Пример:

Input: source = "abc", target = "abcbc"
Output: 2

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

1⃣Используй два указателя для отслеживания текущих позиций в строках source и target.

2⃣Перебирай символы строки source, пока не найдешь совпадающий символ в target.
Если ты прошел всю строку source и не нашел все символы target, увеличь счетчик количества подпоследовательностей и начни снова с начала source.

3⃣Повтори шаги 2 и 3 до тех пор, пока не пройдешь всю строку target.

😎 Решение:

package main

func minSubsequences(source, target string) int {
    subsequencesCount := 0
    targetIndex := 0

    for targetIndex < len(target) {
        sourceIndex := 0
        subsequencesCount++
        startIndex := targetIndex

        for sourceIndex < len(source) && targetIndex < len(target) {
            if source[sourceIndex] == target[targetIndex] {
                targetIndex++
            }
            sourceIndex++
        }

        if targetIndex == startIndex {
            return -1
        }
    }

    return subsequencesCount
}

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

Задача: 1054. Distant Barcodes
Сложность: medium

На складе имеется ряд штрих-кодов, где i-й штрих-код - barcodes[i]. Переставьте штрих-коды так, чтобы два соседних штрих-кода не были одинаковыми. Вы можете вернуть любой ответ, и гарантируется, что ответ существует.

Пример:

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

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

1⃣Подсчитай частоту каждого штрих-кода.
Помести все штрих-коды в максимальную кучу на основе их частоты.

2⃣Извлекай штрих-коды из кучи, чередуя их, чтобы два соседних штрих-кода не были одинаковыми.

3⃣Если куча становится пустой, помести временно сохранённый штрих-код обратно в кучу.

😎 Решение:

package main

func prevPermOpt1(arr []int) []int {
    n := len(arr)
    var i int
    for i = n - 2; i >= 0; i-- {
        if arr[i] > arr[i+1] {
            break
        }
    }
    if i == -1 {
        return arr
    }

    var j int
    for j = n - 1; j > i; j-- {
        if arr[j] < arr[i] && (j == n-1 || arr[j] != arr[j+1]) {
            break
        }
    }

    arr[i], arr[j] = arr[j], arr[i]
    
    return arr
}

func main() {
    arr := []int{3, 2, 1}
    result := prevPermOpt1(arr)
    fmt.Println(result)
}

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

Задача: 1024. Video Stitching
Сложность: medium

Вам дана серия видеоклипов со спортивного соревнования, длительность которых составляет несколько секунд. Эти видеоклипы могут накладываться друг на друга и иметь различную длину. Каждый видеоклип описывается массивом clips, где clips[i] = [starti, endi] указывает, что i-й клип начинается в starti и заканчивается в endi. Мы можем произвольно разрезать эти клипы на сегменты. Например, клип [0, 7] может быть разрезан на сегменты [0, 1] + [1, 3] + [3, 7]. Верните минимальное количество клипов, необходимое для того, чтобы мы могли разрезать клипы на сегменты, охватывающие все спортивное событие [0, время]. Если задача невыполнима, верните -1.

Пример:

Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
Output: 3

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

1⃣Сортировка клипов:
Отсортируйте клипы по начальным значениям. Если начальные значения равны, отсортируйте по конечным значениям в убывающем порядке.

2⃣Выбор клипов:
Используйте жадный алгоритм для выбора клипов. Начните с начальной точки 0 и двигайтесь вперед, выбирая клип, который может покрыть наибольший диапазон.
Если обнаруживается, что начальная точка текущего клипа больше текущей позиции, это означает, что клипы не могут покрыть промежуток, и нужно вернуть -1.

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

😎 Решение:

import "sort"

func videoStitching(clips [][]int, T int) int {
    sort.Slice(clips, func(i, j int) bool {
        return clips[i][0] < clips[j][0] || (clips[i][0] == clips[j][0] && clips[i][1] > clips[j][1])
    })
    end, end2, res := -1, 0, 0
    for _, clip := range clips {
        if end2 >= T || clip[0] > end2 {
            break
        }
        if end < clip[0] && clip[0] <= end2 {
            res++
            end = end2
        }
        end2 = max(end2, clip[1])
    }
    if end2 >= T {
        return res
    }
    return -1
}

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

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

Задача: 88. Merge Sorted Array
Сложность: easy

Вам даны два массива целых чисел nums1 и nums2, отсортированных в порядке неубывания, а также два целых числа m и n, представляющих количество элементов в nums1 и nums2 соответственно.

Слейте nums1 и nums2 в один массив, отсортированный в порядке неубывания.

Итоговый отсортированный массив не должен возвращаться функцией, а должен храниться внутри массива nums1. Чтобы это обеспечить, длина nums1 составляет m + n, где первые m элементов обозначают элементы, которые должны быть объединены, а последние n элементов установлены в 0 и должны быть проигнорированы. Длина nums2 составляет n.

Пример:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

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

1⃣Самая простая реализация заключалась бы в создании копии значений в nums1, называемой nums1Copy, а затем использовании двух указателей для чтения и одного указателя для записи для чтения значений из nums1Copy и nums2 и записи их в nums1.

2⃣Инициализируйте nums1Copy новым массивом, содержащим первые m значений nums1.
Инициализируйте указатель для чтения p1 в начале nums1Copy.
Инициализируйте указатель для чтения p2 в начале nums2.

3⃣Инициализируйте указатель для записи p в начале nums1.
Пока p все еще находится внутри nums1:
Если nums1Copy[p1] существует и меньше или равно nums2[p2]:
Запишите nums1Copy[p1] в nums1[p], и увеличьте p1 на 1.
Иначе
Запишите nums2[p2] в nums1[p], и увеличьте p2 на 1.
Увеличьте p на 1.

😎 Решение:

func merge(nums1 []int, m int, nums2 []int, n int) {
    nums1Copy := append([]int(nil), nums1[:m]...)
    p1 := 0
    p2 := 0
    for p := 0; p < m+n; p++ {
        if p2 >= n || (p1 < m && nums1Copy[p1] < nums2[p2]) {
            nums1[p] = nums1Copy[p1]
            p1++
        } else {
            nums1[p] = nums2[p2]
            p2++
        }
    }
}

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

Задача: 785. Is Graph Bipartite?
Сложность: medium

Есть неориентированный граф с n узлами, где каждый узел пронумерован от 0 до n - 1. Вам дан двумерный массив graph, где graph[u] — это массив узлов, смежных с узлом u. Более формально, для каждого v в graph[u] существует неориентированное ребро между узлом u и узлом v. Граф обладает следующими свойствами:

Нет петель (graph[u] не содержит u).
Нет параллельных ребер (graph[u] не содержит дублирующихся значений).
Если v есть в graph[u], то u есть в graph[v] (граф неориентированный).
Граф может быть несвязным, то есть могут существовать два узла u и v, между которыми нет пути.
Граф является двудольным, если узлы можно разделить на два независимых множества A и B так, что каждое ребро в графе соединяет узел из множества A с узлом из множества B.

Верните true, если и только если граф является двудольным.

Пример:

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

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

1⃣Мы будем хранить массив (или hashmap) для поиска цвета каждого узла: color[node]. Цвета могут быть 0, 1 или неокрашенные (-1 или null).

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

3⃣Для выполнения поиска в глубину мы используем стек. Для каждого неокрашенного соседа в graph[node] мы будем его окрашивать и добавлять в наш стек, который действует как своего рода "список дел" для узлов, которые нужно посетить дальше. Наш внешний цикл для start... гарантирует, что мы окрасим каждый узел.

😎 Решение:

func isBipartite(graph [][]int) bool {
    color := make(map[int]int)
    for node := 0; node < len(graph); node++ {
        if _, found := color[node]; !found {
            stack := []int{node}
            color[node] = 0
            for len(stack) > 0 {
                currentNode := stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                for _, neighbor := range graph[currentNode] {
                    if _, found := color[neighbor]; !found {
                        stack = append(stack, neighbor)
                        color[neighbor] = color[currentNode] ^ 1
                    } else if color[neighbor] == color[currentNode] {
                        return false
                    }
                }
            }
        }
    }
    return true
}

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

Задача: 121. Best Time to Buy and Sell Stock
Сложность: easy

Вам дан массив prices, где prices[i] — цена акции в i-й день.

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

Верните максимальную прибыль. Если прибыли получить нельзя — верните 0.

Пример:

Input: prices = [7,1,5,3,6,4]  
Output: 5  
Explanation: Buy on day 2 (price = 1), sell on day 5 (price = 6), profit = 5  

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

1⃣Инициализация:
- minprice — минимальная цена, наблюдавшаяся до текущего дня.
- maxprofit — максимальная прибыль, вычисленная как price[i] - minprice.

2⃣Проход по массиву:
- Если текущая цена < minprice, обновляем minprice.
- Иначе считаем прибыль prices[i] - minprice и обновляем maxprofit, если она больше текущего значения.

3⃣Результат:
- Возвращаем maxprofit после полного прохода по массиву.

😎 Решение:

func maxProfit(prices []int) int {
    minprice := int(^uint(0) >> 1) // инициализация максимальным int
    maxprofit := 0
    for i := 0; i < len(prices); i++ {
        if prices[i] < minprice {
            minprice = prices[i]
        } else if prices[i]-minprice > maxprofit {
            maxprofit = prices[i] - minprice
        }
    }
    return maxprofit
}

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

Задача: №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
}

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

Задача: 1140. Stone Game II
Сложность: medium

Алиса и Боб продолжают свои игры с кучами камней. Есть несколько куч, расположенных в ряд, и в каждой куче положительное количество камней piles[i]. Цель игры - закончить с наибольшим количеством камней.
Алиса и Боб ходят по очереди, начиная с Алисы. Изначально M = 1.
В свой ход каждый игрок может взять все камни из первых X оставшихся куч, где 1 <= X <= 2M. Затем, мы устанавливаем M = max(M, X).
Игра продолжается до тех пор, пока все камни не будут взяты.
Предполагая, что Алиса и Боб играют оптимально, верните максимальное количество камней, которые может получить Алиса.

Пример:

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. 
Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. 
In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger. 

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

1⃣Создать рекурсивную функцию f, которая принимает три параметра: p (игрок), i (индекс текущей кучи),
и m (максимальное количество куч, которые можно взять за ход).
Если i равен длине массива кучи, вернуть 0 (базовый случай рекурсии). Если значение уже вычислено ранее (dp[p][i][m] != -1), вернуть его.

2⃣Инициализировать переменную s как количество камней, взятых текущим игроком за ход, и переменную res для хранения результата текущего состояния.
Если ход Боба, инициализировать res большим числом, так как Боб хочет минимизировать результат.
Если ход Алисы, инициализировать res маленьким числом, так как Алиса хочет максимизировать результат.

3⃣Итеративно обновлять значение res в зависимости от того, чей ход, и обновлять значения в dp[p][i][m]. В конце вернуть res.

😎 Решение:

func stoneGameII(piles []int) int {
    dp := make([][][]int, 2)
    for i := range dp {
        dp[i] = make([][]int, len(piles) + 1)
        for j := range dp[i] {
            dp[i][j] = make([]int, len(piles) + 1)
            for k := range dp[i][j] {
                dp[i][j][k] = -1
            }
        }
    }
    
    var f func(p, i, m int) int
    f = func(p, i, m int) int {
        if i == len(piles) {
            return 0
        }
        if dp[p][i][m] != -1 {
            return dp[p][i][m]
        }
        res := 1000000
        if p == 0 {
            res = -1
        }
        s := 0
        for x := 1; x <= min(2 * m, len(piles) - i); x++ {
            s += piles[i + x - 1]
            if p == 0 {
                res = max(res, s + f(1, i + x, max(m, x)))
            } else {
                res = min(res, f(0, i + x, max(m, x)))
            }
        }
        dp[p][i][m] = res
        return res
    }
    
    return f(0, 0, 1)
}

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

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

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

Задача: 1461. Check If a String Contains All Binary Codes of Size K
Сложность: medium

Дана бинарная строка s и целое число k, верните true, если каждый бинарный код длины k является подстрокой s. В противном случае верните false.

Пример:

Input: s = "00110110", k = 2
Output: true
Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indices 0, 1, 3 and 2 respectively.

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

1⃣Определите количество возможных двоичных кодов длины k.

2⃣Создайте массив для отслеживания, какие коды были найдены. Итерируйте по строке s, вычисляя хэш для текущего окна длины k и обновляя массив отслеживания.

3⃣Возвращайте true, если все возможные коды найдены, иначе false.

😎 Решение:

func hasAllCodes(s string, k int) bool {
    need := 1 << k
    got := make([]bool, need)
    allOne := need - 1
    hashVal := 0
    
    for i := 0; i < len(s); i++ {
        hashVal = ((hashVal << 1) & allOne) | int(s[i]-'0')
        if i >= k-1 && !got[hashVal] {
            got[hashVal] = true
            need--
            if need == 0 {
                return true
            }
        }
    }
    return false
}

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

Задача: 1539. Kth Missing Positive Number
Сложность: easy

Дан массив arr из положительных целых чисел, отсортированных в строго возрастающем порядке, и целое число k.

Верните k-й положительный целочисленный элемент, который отсутствует в этом массиве.

Пример:

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

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

1⃣Проверьте, является ли k-й отсутствующий номер меньше первого элемента массива. Если это так, верните k. Уменьшите k на количество положительных чисел, отсутствующих до начала массива: k -= arr[0] - 1.

2⃣Итерируйтесь по элементам массива. На каждом шаге вычисляйте количество отсутствующих положительных чисел между i+1-м и i-м элементами: currMissing = arr[i + 1] - arr[i] - 1. Сравните k с currMissing. Если k <= currMissing, то число для возврата находится между arr[i + 1] и arr[i], и вы можете его вернуть: arr[i] + k. В противном случае уменьшите k на currMissing и продолжайте.

3⃣Если элемент, который нужно вернуть, больше последнего элемента массива, верните его: arr[n - 1] + k.

😎 Решение

func findKthPositive(arr []int, k int) int {
    if k <= arr[0] - 1 {
        return k
    }
    k -= arr[0] - 1
    n := len(arr)
    for i := 0; i < n - 1; i++ {
        currMissing := arr[i + 1] - arr[i] - 1
        if k <= currMissing {
            return arr[i] + k
        }
        k -= currMissing
    }
    return arr[n - 1] + k
}

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

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

Вам дан целочисленный массив arr. За один ход вы можете выбрать палиндромный подмассив arr[i], arr[i + 1], ..., arr[j], где i <= j, и удалить этот подмассив из данного массива. Обратите внимание, что после удаления подмассива элементы слева и справа от него перемещаются, чтобы заполнить пробел, образовавшийся в результате удаления. Верните минимальное количество ходов, необходимое для удаления всех чисел из массива.

Пример:
Input: arr = [1,2]
Output: 2

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

1⃣Базовый случай:
Если подмассив состоит из одного элемента, то его удаление займет 1 ход, поэтому dp[i][i] = 1.

2⃣Рекурсивный случай:
Если arr[i] == arr[j], то мы можем удалить их в одном ходе, если подмассив arr[i+1...j-1] можно удалить за dp[i+1][j-1] ходов, тогда dp[i][j] = dp[i+1][j-1] (если удалим подмассив arr[i+1...j-1] и затем удалим arr[i] и arr[j]).

3⃣В противном случае, минимальное количество ходов для удаления подмассива arr[i...j] будет равно 1 + минимум ходов для удаления каждого из подмассивов arr[i...k] и arr[k+1...j], где i <= k < j. То есть, dp[i][j] = min(dp[i][k] + dp[k+1][j]) для всех k от i до j-1.

😎 Решение:

package main

import (
    "fmt"
    "math"
)

func minMovesToDelete(arr []int) int {
    n := len(arr)
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
        dp[i][i] = 1
    }

    for length := 2; length <= n; length++ {
        for i := 0; i <= n-length; i++ {
            j := i + length - 1
            if arr[i] == arr[j] {
                if length > 2 {
                    dp[i][j] = dp[i+1][j-1]
                } else {
                    dp[i][j] = 1
                }
            } else {
                dp[i][j] = math.MaxInt32
                for k := i; k < j; k++ {
                    dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j])
                }
            }
        }
    }
    return dp[0][n-1]
}

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

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

Задача: 910. Smallest Range II
Сложность: medium

Вам дан целочисленный массив nums и целое число k. Для каждого индекса i, где 0 <= i < nums.length, измените nums[i] на nums[i] + k или nums[i] - k. Оценка nums - это разница между максимальным и минимальным элементами в nums. Верните минимальную оценку nums после изменения значений в каждом индексе.

Пример:

Input: nums = [1], k = 0
Output: 0

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

1⃣Отсортировать массив nums.

2⃣Рассчитать начальную разницу между максимальным и минимальным элементами.

3⃣Пройтись по всем элементам массива, пытаясь минимизировать разницу, изменяя текущий элемент на +k и -k и вычисляя новые максимальные и минимальные значения массива.

😎 Решение:

package main

import (
    "sort"
)

func smallestRangeII(nums []int, k int) int {
    sort.Ints(nums)
    n := len(nums)
    result := nums[n-1] - nums[0]

    for i := 0; i < n-1; i++ {
        high := max(nums[n-1]-k, nums[i]+k)
        low := min(nums[0]+k, nums[i+1]-k)
        if high-low < result {
            result = high - low
        }
    }

    return result
}

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

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

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

Задача: №22. Generate Parentheses
Сложность: medium

Учитывая n пар круглых скобок, напишите функцию, которая генерирует все комбинации правильных круглых скобок.

Пример:

Input: n = 3  
Output: ["((()))","(()())","(())()","()(())","()()()"]  

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

1⃣Использовать рекурсивный backtracking, добавляя (, если их количество меньше n, и ), если их меньше, чем (.

2⃣Если открывающих и закрывающих скобок уже n, добавить текущую строку в результат.

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

😎 Решение:

func generateParenthesis(n int) []string {
    res := make([]string, 0)
    backtrack(&res, n, 0, 0, "")
    return res
}

func backtrack(res *[]string, n, openN, closedN int, val string) {
    if openN == n && closedN == n {
        *res = append(*res, val)
        return
    }
    if openN < n {
        backtrack(res, n, openN+1, closedN, val+"(")
    }
    if closedN < openN {
        backtrack(res, n, openN, closedN+1, val+")")
    }
}

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

Задача: 1059. All Paths from Source Lead to Destination
Сложность: medium

Учитывая ребра направленного графа, где edges[i] = [ai, bi] указывает на наличие ребра между вершинами ai и bi, и две вершины source и destination этого графа, определите, все ли пути, начинающиеся из source, заканчиваются в destination, то есть: существует ли хотя бы один путь из source в destination Если существует путь из source в node без исходящих ребер, то этот node равен destination. Количество возможных путей из source в destination - конечное число. Верните true тогда и только тогда, когда все пути из source ведут в destination.

Пример:

Input: n = 3, edges = [[0,1],[0,2]], source = 0, destination = 2
Output: false

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

1⃣Построение графа и проверка путей:
Построить граф на основе входных данных.
Использовать поиск в глубину (DFS) для проверки наличия всех путей от вершины source до вершины destination.

2⃣Проверка конечности путей:
Проверить, что из всех вершин, достижимых от source, либо исходят ребра, либо они являются вершиной destination.
Убедиться, что из любой вершины, не являющейся destination, исходят хотя бы одно ребро.

3⃣Рекурсивная проверка конечности путей:
Рекурсивно проверять, что все пути из source заканчиваются в destination, избегая циклов и проверяя конечность всех путей.

😎 Решение:

func leadsToDestination(n int, edges [][]int, source int, destination int) bool {
    graph := make(map[int][]int)
    for _, edge := range edges {
        graph[edge[0]] = append(graph[edge[0]], edge[1])
    }
    
    visited := make([]int, n)
    
    var dfs func(node int) bool
    dfs = func(node int) bool {
        if visited[node] != 0 {
            return visited[node] == 2
        }
        if len(graph[node]) == 0 {
            return node == destination
        }
        visited[node] = 1
        for _, neighbor := range graph[node] {
            if !dfs(neighbor) {
                return false
            }
        }
        visited[node] = 2
        return true
    }

    return dfs(source)
}

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

Задача: 1057. Campus Bikes
Сложность: medium

В городке, изображенном на плоскости X-Y, есть n рабочих и m велосипедов, причем n <= m. Вам дан массив workers длины n, где workers[i] = [xi, yi] - положение i-го рабочего. Вам также дан массив bikes длины m, где bikes[j] = [xj, yj] - позиция j-го велосипеда. Все заданные позиции уникальны. Назначаем велосипед каждому работнику. Среди доступных велосипедов и работников мы выбираем пару (workeri, bikej) с наименьшим манхэттенским расстоянием между ними и назначаем велосипед этому работнику. Если существует несколько пар (workeri, bikej) с одинаковым наименьшим манхэттенским расстоянием, мы выбираем пару с наименьшим индексом работника. Если существует несколько способов сделать это, мы выбираем пару с наименьшим индексом велосипеда. Повторяем этот процесс до тех пор, пока не останется свободных работников. Возвращаем массив answer длины n, где answer[i] - индекс (с индексом 0) велосипеда, на который назначен i-й работник. Манхэттенское расстояние между двумя точками p1 и p2 равно Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Пример:

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: [1,0]

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

1⃣Для каждой пары (работник, велосипед) вычисли Манхэттенское расстояние и сохрани все пары вместе с расстоянием в список.

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

3⃣Заполни и верни массив назначений.

😎 Решение:

package main

import (
    "fmt"
    "sort"
    "math"
)

type Pair struct {
    distance int
    workerIdx int
    bikeIdx int
}

func assignBikes(workers [][]int, bikes [][]int) []int {
    var pairs []Pair
    
    for i := 0; i < len(workers); i++ {
        for j := 0; j < len(bikes); j++ {
            distance := int(math.Abs(float64(workers[i][0] - bikes[j][0])) + math.Abs(float64(workers[i][1] - bikes[j][1])))
            pairs = append(pairs, Pair{distance, i, j})
        }
    }
    
    sort.Slice(pairs, func(a, b int) bool {
        if pairs[a].distance != pairs[b].distance {
            return pairs[a].distance < pairs[b].distance
        }
        if pairs[a].workerIdx != pairs[b].workerIdx {
            return pairs[a].workerIdx < pairs[b].workerIdx
        }
        return pairs[a].bikeIdx < pairs[b].bikeIdx
    })
    
    result := make([]int, len(workers))
    for i := range result {
        result[i] = -1
    }
    bikeTaken := make([]bool, len(bikes))
    workerAssigned := make([]bool, len(workers))
    
    for _, pair := range pairs {
        if !workerAssigned[pair.workerIdx] && !bikeTaken[pair.bikeIdx] {
            result[pair.workerIdx] = pair.bikeIdx
            bikeTaken[pair.bikeIdx] = true
            workerAssigned[pair.workerIdx] = true
        }
    }
    
    return result
}

func main() {
    workers := [][]int{{0, 0}, {2, 1}}
    bikes := [][]int{{1, 2}, {3, 3}}
    fmt.Println(assignBikes(workers, bikes)) // Output: [1, 0]
}

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

Задача: 665. Non-decreasing Array
Сложность: medium

Дан массив nums из n целых чисел. Ваша задача - проверить, можно ли сделать его неубывающим, изменив не более одного элемента.

Мы определяем массив как неубывающий, если для каждого i (индексация с 0), такого что 0 <= i <= n - 2, выполняется условие nums[i] <= nums[i + 1].

Пример:

Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

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

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

2⃣Проверка условий:
Если nums[i] > nums[i + 1], то увеличиваем count.
Если count превышает 1, возвращаем false, так как больше одного изменения недопустимо.
Если nums[i - 1] > nums[i + 1] и nums[i] > nums[i + 2], то возвращаем false.

3⃣Возврат результата:
Если количество изменений не превышает 1, вернуть true.

😎 Решение:

func checkPossibility(nums []int) bool {
    count := 0
    
    for i := 1; i < len(nums); i++ {
        if nums[i] < nums[i-1] {
            if count > 0 {
                return false
            }
            count++
            if i == 1 || nums[i] >= nums[i-2] {
                nums[i-1] = nums[i]
            } else {
                nums[i] = nums[i-1]
            }
        }
    }
    
    return true
}

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

Задача: 251. Flatten 2D Vector
Сложность: medium

Разработайте итератор для разворачивания двумерного вектора. Он должен поддерживать операции next и hasNext.

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

Vector2D(int[][] vec) инициализирует объект двумерным вектором vec.
next() возвращает следующий элемент из двумерного вектора и перемещает указатель на один шаг вперед. Вы можете предположить, что все вызовы next допустимы.
hasNext() возвращает true, если в векторе еще остались элементы, и false в противном случае.

Пример:

Input
["Vector2D", "next", "next", "next", "hasNext", "hasNext", "next", "hasNext"]
[[[[1, 2], [3], [4]]], [], [], [], [], [], [], []]
Output
[null, 1, 2, 3, true, true, 4, false]

Explanation
Vector2D vector2D = new Vector2D([[1, 2], [3], [4]]);
vector2D.next();    // return 1
vector2D.next();    // return 2
vector2D.next();    // return 3
vector2D.hasNext(); // return True
vector2D.hasNext(); // return True
vector2D.next();    // return 4
vector2D.hasNext(); // return False

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

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

2⃣Проверка доступности: Реализуйте метод hasNext(), который просто проверяет, находится ли индекс position в пределах допустимых индексов массива nums. Этот метод вернет true, если position указывает на действительный индекс, и false в противном случае.

3⃣Получение следующего элемента: Метод next() возвращает элемент в текущей позиции position и продвигает указатель position на следующий индекс. Эта операция обеспечивает, что после вызова next(), position обновляется и указывает на следующий элемент, готовый к следующему вызову next().

😎 Решение:

type Vector2D struct {
    nums    []int
    position int
}

func Constructor(v [][]int) Vector2D {
    nums := make([]int, 0)
    for _, innerList := range v {
        nums = append(nums, innerList...)
    }
    return Vector2D{nums, -1}
}

func (this *Vector2D) Next() int {
    this.position++
    return this.nums[this.position]
}

func (this *Vector2D) HasNext() bool {
    return this.position + 1 < len(this.nums)
}

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

Задача: 1436. Destination City
Сложность: easy

Дан массив paths, где paths[i] = [cityAi, cityBi] означает, что существует прямой путь из cityAi в cityBi. Вернуть конечный город, то есть город, из которого нет пути в другой город.

Гарантируется, что граф путей образует линию без циклов, поэтому будет ровно один конечный город.

Пример:

Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output: "Sao Paulo" 
Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".

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

1⃣Для каждого города cityBi в paths проверьте, является ли он кандидатом на конечный город.

2⃣Для каждого кандидата проверьте, нет ли пути, ведущего из него (cityAi == candidate).

3⃣Верните город, который не имеет исходящих путей.

😎 Решение:

func destCity(paths [][]string) string {
    for _, path := range paths {
        candidate := path[1]
        good := true
        for _, p := range paths {
            if p[0] == candidate {
                good = false
                break
            }
        }
        if good {
            return candidate
        }
    }
    return ""
}

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