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

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

Задача: 1266. Minimum Time Visiting All Points
Сложность: easy

На двумерной плоскости имеется n точек с целочисленными координатами points[i] = [xi, yi]. Верните минимальное время в секундах для посещения всех точек в порядке, заданном точками. Вы можете перемещаться по следующим правилам: за 1 секунду вы можете либо: переместиться по вертикали на одну единицу, по горизонтали на одну единицу, либо по диагонали sqrt(2) единиц (другими словами, переместиться на одну единицу по вертикали и на одну единицу по горизонтали за 1 секунду). Вы должны посетить точки в том же порядке, в котором они появляются в массиве. Вы можете проходить через точки, которые появляются позже в порядке, но они не считаются за посещение.

Пример:
Input: points = [[1,1],[3,4],[-1,0]]
Output: 7

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

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

2⃣Последовательно проходите по всем точкам и вычисляйте минимальное время для перехода от текущей точки к следующей.

3⃣Суммируйте время переходов для получения общего минимального времени.

😎 Решение:

func minTimeToVisitAllPoints(points [][]int) int {
    time := 0
    for i := 0; i < len(points)-1; i++ {
        time += distance(points[i], points[i+1])
    }
    return time
}

func distance(p1, p2 []int) int {
    return max(abs(p1[0]-p2[0]), abs(p1[1]-p2[1]))
}

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

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

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

Задача: 1023. Camelcase Matching
Сложность: medium

Учитывая массив строк queries и строку pattern, верните булевский массив answer, где answer[i] - true, если queries[i] соответствует pattern, и false в противном случае. Слово запроса queries[i] соответствует pattern, если вы можете вставить строчные английские буквы pattern так, чтобы они были равны запросу. Вы можете вставить каждый символ в любую позицию и не можете вставить ни одного символа.

Пример:

Input: queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"], pattern = "FB"
Output: [true,false,true,true,false]

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

1⃣Инициализация переменных:
Создайте массив answer для хранения результатов соответствия каждого запроса шаблону.

2⃣Проверка каждого запроса:
Для каждого запроса из queries, проверьте, можно ли вставить строчные буквы в pattern, чтобы они соответствовали запросу.
Используйте два указателя, один для query и один для pattern. Перемещайте оба указателя, пока они не достигнут конца строк. Если текущие символы совпадают, переместите оба указателя. Если символы не совпадают и текущий символ в запросе является строчной буквой, переместите только указатель запроса.

3⃣Возврат результата:
Если указатель шаблона достиг конца строки, добавьте true в answer, иначе добавьте false.
Верните массив answer.

😎 Решение:

func camelMatch(queries []string, pattern string) []bool {
    matches := func(query, pattern string) bool {
        i, j := 0, 0
        
        for i < len(query) {
            if j < len(pattern) && query[i] == pattern[j] {
                j++
            } else if query[i] >= 'A' && query[i] <= 'Z' {
                return false
            }
            i++
        }
        
        return j == len(pattern)
    }
    
    answer := make([]bool, len(queries))
    for i, query := range queries {
        answer[i] = matches(query, pattern)
    }
    
    return answer
}

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

Задача: 102. Binary Tree Level Order Traversal
Сложность: medium

Дан корень бинарного дерева. Верните обход узлов дерева по уровням (то есть слева направо, уровень за уровнем).

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

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

1⃣Самый простой способ решения задачи — использование рекурсии. Сначала убедимся, что дерево не пустое, а затем рекурсивно вызовем функцию helper(node, level), которая принимает текущий узел и его уровень в качестве аргументов.

2⃣Эта функция выполняет следующее:
Выходной список здесь называется levels, и, таким образом, текущий уровень — это просто длина этого списка len(levels). Сравниваем номер текущего уровня len(levels) с уровнем узла level. Если вы все еще на предыдущем уровне, добавьте новый, добавив новый список в levels.

3⃣Добавьте значение узла в последний список в levels.
Рекурсивно обработайте дочерние узлы, если они не равны None: helper(node.left / node.right, level + 1).

😎 Решение:

func levelOrder(root *TreeNode) [][]int {
    levels := [][]int{}
    var helper func(*TreeNode, int)
    helper = func(node *TreeNode, level int) {
        if len(levels) == level {
            levels = append(levels, []int{})
        }
        levels[level] = append(levels[level], node.Val)
        if node.Left != nil {
            helper(node.Left, level+1)
        }
        if node.Right != nil {
            helper(node.Right, level+1)
        }
    }
    if root != nil {
        helper(root, 0)
    }
    return levels
}

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

Задача: 520. Detect Capital
Сложность: easy

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

Все буквы в этом слове заглавные, как "USA".
Все буквы в этом слове строчные, как "leetcode".
Только первая буква в этом слове заглавная, как "Google".
Дана строка word. Верните true, если использование заглавных букв в ней правильное.

Пример:

Input: word = "USA"
Output: true

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

1⃣Шаблон для первого случая в регулярном выражении: [A-Z]*, где [A-Z] соответствует одной заглавной букве от 'A' до 'Z', а * означает повторение предыдущего шаблона 0 или более раз. Этот шаблон представляет "Все заглавные буквы".

2⃣Шаблон для второго случая в регулярном выражении: [a-z]*, где [a-z] соответствует одной строчной букве от 'a' до 'z'. Этот шаблон представляет "Все строчные буквы". Шаблон для третьего случая в регулярном выражении: [A-Z][a-z]*, где первая буква заглавная, а остальные строчные.

3⃣Объедините эти три шаблона: [A-Z]*|[a-z]*|[A-Z][a-z]*, где | означает "или". Мы можем объединить второй и третий случай, получив . [a-z]*, где . соответствует любому символу. Итоговый шаблон: [A-Z]*|.[a-z]*.

😎 Решение:

import (
    "regexp"
)

func detectCapitalUse(word string) bool {
    pattern := "^[A-Z]*$|^[a-z]*$|^[A-Z][a-z]*$"
    match, _ := regexp.MatchString(pattern, word)
    return match
}

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

Задача: 1197. Minimum Knight Moves
Сложность: medium

На бесконечной шахматной доске с координатами от -бесконечности до +бесконечности у вас есть конь на клетке [0, 0].
У коня есть 8 возможных ходов. Каждый ход представляет собой два квадрата в кардинальном направлении, затем один квадрат в ортогональном направлении.

Верните минимальное количество шагов, необходимых для перемещения коня на клетку [x, y]. Гарантируется, что ответ существует.

Пример:

Input: x = 5, y = 5
Output: 4
Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]

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

1⃣Инициализация структур данных:
Инициализируйте две очереди для хранения координат и расстояний: одну для движения от начальной точки, другую — от конечной точки.
Инициализируйте две карты для хранения посещенных координат и расстояний: одну для движения от начальной точки, другую — от конечной точки.

2⃣Реализация двунаправленного поиска в ширину (BFS):
Выполняйте шаги из очередей, расширяя круги поиска как от начальной, так и от конечной точки.
Если круги пересекаются, возвращайте сумму расстояний до точки пересечения.

3⃣Расширение кругов поиска:
Для каждой текущей точки из очередей расширяйте круг поиска по всем возможным ходам коня.
Обновляйте расстояния и добавляйте новые точки в очереди, если они еще не были посещены.
Увеличивайте units на значение, извлеченное из кучи.

😎 Решение:

package main

import (
    "container/list"
    "fmt"
)

func minKnightMoves(x int, y int) int {
    offsets := [][]int{{1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}}
    
    originQueue := list.New()
    originQueue.PushBack([]int{0, 0, 0})
    originDistance := map[string]int{"0,0": 0}
    
    targetQueue := list.New()
    targetQueue.PushBack([]int{x, y, 0})
    targetDistance := map[string]int{fmt.Sprintf("%d,%d", x, y): 0}
    
    for {
        origin := originQueue.Remove(originQueue.Front()).([]int)
        originKey := fmt.Sprintf("%d,%d", origin[0], origin[1])
        if targetDistance[originKey] != 0 || originKey == fmt.Sprintf("%d,%d", x, y) {
            return origin[2] + targetDistance[originKey]
        }
        
        target := targetQueue.Remove(targetQueue.Front()).([]int)
        targetKey := fmt.Sprintf("%d,%d", target[0], target[1])
        if originDistance[targetKey] != 0 || targetKey == "0,0" {
            return target[2] + originDistance[targetKey]
        }
        
        for _, offset := range offsets {
            nextOrigin := []int{origin[0] + offset[0], origin[1] + offset[1], origin[2] + 1}
            nextOriginKey := fmt.Sprintf("%d,%d", nextOrigin[0], nextOrigin[1])
            if _, ok := originDistance[nextOriginKey]; !ok {
                originQueue.PushBack(nextOrigin)
                originDistance[nextOriginKey] = nextOrigin[2]
            }
            
            nextTarget := []int{target[0] + offset[0], target[1] + offset[1], target[2] + 1}
            nextTargetKey := fmt.Sprintf("%d,%d", nextTarget[0], nextTarget[1])
            if _, ok := targetDistance[nextTargetKey]; !ok {
                targetQueue.PushBack(nextTarget)
                targetDistance[nextTargetKey] = nextTarget[2]
            }
        }
    }
}

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

Задача: 835. Image Overlap
Сложность: medium

Вам даны два изображения, img1 и img2, представленные как бинарные квадратные матрицы размером n x n. Бинарная матрица содержит только 0 и 1 в качестве значений.
Мы можем сдвигать одно изображение как угодно, перемещая все биты 1 влево, вправо, вверх и/или вниз на любое количество единиц. Затем мы помещаем его поверх другого изображения. После этого мы можем вычислить перекрытие, подсчитав количество позиций, на которых в обоих изображениях есть 1.

Также обратите внимание, что при сдвиге не допускается никакое вращение. Любые биты 1, которые перемещаются за пределы границ матрицы, стираются.

Верните максимальное возможное перекрытие.

Пример:

Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output: 3
Explanation: We translate img1 to right by 1 unit and down by 1 unit.

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

1⃣Определите функцию shiftAndCount(xShift, yShift, M, R), которая смещает матрицу M относительно матрицы R на координаты (xShift, yShift) и подсчитывает количество единиц в зоне перекрытия.

2⃣Организуйте цикл по всем возможным комбинациям координат смещения (xShift, yShift).

3⃣На каждой итерации вызывайте функцию shiftAndCount() дважды для обоих направлений смещения и обновляйте максимальное количество перекрытий.

😎 Решение:

func shiftAndCount(xShift, yShift int, M, R [][]int) int {
    leftShiftCount, rightShiftCount := 0, 0
    rRow := 0
    for mRow := yShift; mRow < len(M); mRow++ {
        rCol := 0
        for mCol := xShift; mCol < len(M); mCol++ {
            if M[mRow][mCol] == 1 && M[mRow][mCol] == R[rRow][rCol] {
                leftShiftCount++
            }
            if M[mRow][rCol] == 1 && M[mRow][rCol] == R[rRow][mCol] {
                rightShiftCount++
            }
            rCol++
        }
        rRow++
    }
    return max(leftShiftCount, rightShiftCount)
}

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

func largestOverlap(A [][]int, B [][]int) int {
    maxOverlaps := 0
    for yShift := 0; yShift < len(A); yShift++ {
        for xShift := 0; xShift < len(A); xShift++ {
            maxOverlaps = max(maxOverlaps, shiftAndCount(xShift, yShift, A, B))
            maxOverlaps = max(maxOverlaps, shiftAndCount(xShift, yShift, B, A))
        }
    }
    return maxOverlaps
}

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

Задача: 141. Linked List Cycle
Сложность: easy

Дана переменная head, которая является началом связного списка. Определите, содержит ли связный список цикл.

Цикл в связном списке существует, если существует узел в списке, до которого можно добраться снова, последовательно следуя по указателю next. Внутренне переменная pos используется для обозначения индекса узла, к которому подключен указатель next последнего узла. Обратите внимание, что pos не передается в качестве параметра.

Верните true, если в связном списке есть цикл. В противном случае верните false.

Пример:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

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

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

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

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

😎 Решение:

func hasCycle(head *ListNode) bool {
    nodesSeen := make(map[*ListNode]bool)
    current := head
    for current != nil {
        if nodesSeen[current] {
            return true
        }
        nodesSeen[current] = true
        current = current.Next
    }
    return false
}

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

Задача: 470. Implement Rand10() Using Rand7()
Сложность: medium

Дано API rand7(), которое генерирует случайное целое число в диапазоне [1, 7].
Нужно реализовать функцию rand10(), которая генерирует случайное число в диапазоне [1, 10].
Вы можете использовать только rand7(), другие источники случайности использовать нельзя.

Пример:

Input: n = 1 
Output: [2]

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

1⃣rand7() генерирует 7 возможных значений. Скомбинируем два вызова rand7() как 7×7 = 49 вариантов, что достаточно для генерации чисел от 1 до 10.

2⃣Представим это как таблицу 7×7: row = rand7(), col = rand7(). Индекс = (row-1)*7 + col даёт значение от 1 до 49.

3⃣Используем только первые 40 значений (1..40) — они равномерно делятся на 10.
Если idx > 40, делаем повторный вызов, чтобы не портить равномерность.

😎 Решение:

func rand10() int {
    var row, col, idx int
    for {
        row = rand7()
        col = rand7()
        idx = col + (row-1) * 7
        if idx <= 40 {
            break
        }
    }
    return 1 + (idx-1) % 10
}

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

Задача: 211. Design Add and Search Words Data Structure
Сложность: medium

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

Реализуйте класс WordDictionary:
WordDictionary() инициализирует объект.
void addWord(word) добавляет слово в структуру данных, оно может быть сопоставлено позже.
bool search(word) возвращает true, если в структуре данных есть строка, которая соответствует слову, или false в противном случае. Слово может содержать точки '.', где точки могут быть сопоставлены с любой буквой.

Пример:

Input
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
Output
[null,null,null,null,false,true,true,true]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

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

1⃣Инициализация и добавление слова:
Создайте класс WordDictionary с конструктором, который инициализирует корневой узел TrieNode.
Метод addWord(String word) добавляет слово в структуру данных. Инициализируйте текущий узел как корневой и пройдите по каждому символу слова. Если символ отсутствует среди дочерних узлов текущего узла, создайте новый узел. Перемещайтесь к следующему узлу. В конце отметьте текущий узел как конец слова.

2⃣Поиск слова в узле:
Метод searchInNode(String word, TrieNode node) ищет слово в переданном узле TrieNode. Пройдите по каждому символу слова. Если символ не найден среди дочерних узлов текущего узла, проверьте, является ли символ точкой '.'. Если да, рекурсивно выполните поиск в каждом дочернем узле текущего узла. Если символ не точка и не найден, верните false. Если символ найден, перейдите к следующему узлу. В конце проверьте, является ли текущий узел концом слова.

3⃣Поиск слова в структуре данных:
Метод search(String word) использует метод searchInNode() для поиска слова, начиная с корневого узла. Верните результат поиска. Если слово найдено, верните true, иначе false.

😎 Решение:

package main

type TrieNode struct {
    children map[rune]*TrieNode
    isWord   bool
}

type WordDictionary struct {
    root *TrieNode
}

func Constructor() WordDictionary {
    return WordDictionary{root: &TrieNode{children: make(map[rune]*TrieNode)}}
}

func (this *WordDictionary) AddWord(word string) {
    node := this.root
    for _, ch := range word {
        if _, ok := node.children[ch]; !ok {
            node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
        }
        node = node.children[ch]
    }
    node.isWord = true
}

func (this *WordDictionary) searchInNode(word string, node *TrieNode) bool {
    for i, ch := range word {
        if nextNode, ok := node.children[ch]; ok {
            node = nextNode
        } else {
            if ch == '.' {
                for _, child := range node.children {
                    if this.searchInNode(word[i+1:], child) {
                        return true
                    }
                }
            }
            return false
        }
    }
    return node.isWord
}

func (this *WordDictionary) Search(word string) bool {
    return this.searchInNode(word, this.root)
}

func main() {
    wordDictionary := Constructor()
    wordDictionary.AddWord("bad")
    wordDictionary.AddWord("dad")
    wordDictionary.AddWord("mad")
    println(wordDictionary.Search("pad")) // Output: false
    println(wordDictionary.Search("bad")) // Output: true
    println(wordDictionary.Search(".ad")) // Output: true
    println(wordDictionary.Search("b..")) // Output: true
}

х

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

Задача: 209. Minimum Size Subarray Sum
Сложность: medium

Дан массив положительных целых чисел nums и положительное целое число target. Верните минимальную длину подмассива, сумма которого больше или равна target. Если такого подмассива нет, верните 0.

Пример:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

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

1⃣Инициализация переменных:
Создайте три целочисленные переменные left, right и sumOfCurrentWindow. Переменные left и right формируют подмассив, указывая на начальные и конечные индексы текущего подмассива (или окна), а sumOfCurrentWindow хранит сумму этого окна. Инициализируйте все их значением 0.
Создайте еще одну переменную res для хранения ответа на задачу. Инициализируйте ее большим целым значением.

2⃣Итерация по массиву:
Итерируйте по массиву nums с помощью right, начиная с right = 0 до nums.length - 1, увеличивая right на 1 после каждой итерации. Выполняйте следующее внутри этой итерации:
Добавьте элемент с индексом right к текущему окну, увеличив sumOfCurrentWindow на nums[right].
Проверьте, если sumOfCurrentWindow >= target. Если да, у нас есть подмассив, который удовлетворяет условию. В результате, попытайтесь обновить переменную ответа res длиной этого подмассива. Выполните res = min(res, right - left + 1). Затем удалите первый элемент из этого окна, уменьшив sumOfCurrentWindow на nums[left] и увеличив left на 1. Этот шаг повторяется во внутреннем цикле, пока sumOfCurrentWindow >= target.

3⃣Возврат результата:
Текущая сумма окна теперь меньше target. Нужно добавить больше элементов в окно. В результате, увеличивается right на 1.
Верните res.

😎 Решение:

func minSubArrayLen(target int, nums []int) int {
    left, sumOfCurrentWindow, res := 0, 0, int(^uint(0) >> 1)

    for right := 0; right < len(nums); right++ {
        sumOfCurrentWindow += nums[right]

        for sumOfCurrentWindow >= target {
            if res > right - left + 1 {
                res = right - left + 1
            }
            sumOfCurrentWindow -= nums[left]
            left++
        }
    }

    if res == int(^uint(0) >> 1) {
        return 0
    }
    return res
}

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

Задача: 135. Candy
Сложность: hard

В очереди стоят n детей. Каждому ребенку присвоено значение рейтинга, указанное в массиве целых чисел ratings.

Вы раздаете конфеты этим детям с соблюдением следующих требований:

Каждый ребенок должен получить как минимум одну конфету.
Дети с более высоким рейтингом должны получать больше конфет, чем их соседи.
Верните минимальное количество конфет, которое вам нужно иметь, чтобы распределить их среди детей.

Пример:

Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

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

1⃣Инициализация и первичное заполнение массивов:
Создайте два массива: left2right для расчета конфет с учетом только левых соседей и right2left для расчета с учетом только правых соседей. Изначально каждому ученику в обоих массивах присваивается по одной конфете.

2⃣Обход и обновление значений в массивах:
Проходите массив ratings слева направо, увеличивая значение в left2right для каждого ученика, чей рейтинг выше рейтинга его левого соседа.
Затем проходите массив справа налево, увеличивая значение в right2left для каждого ученика, чей рейтинг выше рейтинга его правого соседа.

3⃣Расчет минимального количества конфет:
Для каждого ученика определите максимальное значение конфет между left2right[i] и right2left[i], чтобы соответствовать требованиям к распределению конфет.
Суммируйте полученные значения для всех учеников, чтобы найти минимальное количество конфет, необходимое для соблюдения всех правил.

😎 Решение:

func candy(ratings []int) int {
    sum := 0
    n := len(ratings)
    left2right := make([]int, n)
    right2left := make([]int, n)
    for i := range left2right {
        left2right[i] = 1
    }
    for i := range right2left {
        right2left[i] = 1
    }
    for i := 1; i < n; i++ {
        if ratings[i] > ratings[i-1] {
            left2right[i] = left2right[i-1] + 1
        }
    }
    for i := n - 2; i >= 0; i-- {
        if ratings[i] > ratings[i+1] {
            right2left[i] = right2left[i+1] + 1
        }
    }
    for i := 0; i < n; i++ {
        sum += max(left2right[i], right2left[i])
    }
    return sum
}

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

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

Задача: 815. Bus Routes
Сложность: hard

Дан массив routes, представляющий автобусные маршруты, где routes[i] - это автобусный маршрут, который i-й автобус повторяет бесконечно.

Например, если routes[0] = [1, 5, 7], это означает, что 0-й автобус путешествует в последовательности 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... бесконечно.
Вы начинаете на автобусной остановке source (вы изначально не находитесь в автобусе) и хотите добраться до автобусной остановки target. Перемещаться между автобусными остановками можно только на автобусах.

Верните наименьшее количество автобусов, которые вам нужно взять, чтобы доехать от source до target. Верните -1, если это невозможно.

Пример:

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

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

1⃣Верните 0, если source и target совпадают. Инициализируйте пустую карту adjList, чтобы хранить ребра, где ключ - это автобусная остановка, а значение - список целых чисел, обозначающих индексы маршрутов, которые имеют эту остановку. Инициализируйте пустую очередь q и неупорядоченное множество vis, чтобы отслеживать посещенные маршруты. Вставьте начальные маршруты в очередь q и отметьте их посещенными в vis.

2⃣Итерация по очереди, пока она не пуста: извлеките маршрут из очереди, итерируйтесь по остановкам в маршруте. Если остановка равна target, верните busCount. В противном случае, итерируйтесь по маршрутам для этой остановки в карте adjList, добавьте непосещенные маршруты в очередь и отметьте их посещенными.

3⃣Верните -1 после завершения обхода в ширину (BFS).

😎 Решение:

func numBusesToDestination(routes [][]int, source int, target int) int {
    if source == target {
        return 0
    }

    adjList := make(map[int][]int)
    for route, stops := range routes {
        for _, stop := range stops {
            adjList[stop] = append(adjList[stop], route)
        }
    }

    q := []int{}
    vis := make(map[int]bool)
    for _, route := range adjList[source] {
        q = append(q, route)
        vis[route] = true
    }

    busCount := 1
    for len(q) > 0 {
        size := len(q)
        for i := 0; i < size; i++ {
            route := q[0]
            q = q[1:]
            for _, stop := range routes[route] {
                if stop == target {
                    return busCount
                }
                for _, nextRoute := range adjList[stop] {
                    if !vis[nextRoute] {
                        vis[nextRoute] = true
                        q = append(q, nextRoute)
                    }
                }
            }
        }
        busCount++
    }
    return -1
}

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

Задача: 1100. Find K-Length Substrings With No Repeated Characters
Сложность: medium

Дана строка s и целое число k. Верните количество подстрок в s длиной k, которые не содержат повторяющихся символов.

Пример:

Input: s = "havefunonleetcode", k = 5
Output: 6
Explanation: There are 6 substrings they are: 'havef','avefu','vefun','efuno','etcod','tcode'.

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

1⃣Если k > 26, верните 0, так как не может быть строки длиной более 26 символов с уникальными символами. Для остальных случаев, где k <= 26, проверьте каждую подстроку длиной k на наличие повторяющихся символов.

2⃣Итерация по строке s от индекса 0 до n - k (включительно), где n - длина строки s:
Для каждого индекса i:
Инициализируйте флаг isUnique как true и массив частот размером 26 для подсчета частот каждого символа.
Итерируйте следующие k символов и увеличивайте частоту каждого встреченного символа в массиве частот.
Если частота любого символа становится больше 1, установите isUnique в false и прекратите итерацию.
Если после итерации по k символам флаг isUnique все еще равен true, увеличьте счетчик ответов на 1.

3⃣Верните количество подстрок без повторяющихся символов после итерации по всем индексам от 0 до n - k.

😎 Решение:

func numKLenSubstrNoRepeats(s string, k int) int {
    if k > 26 {
        return 0
    }
    
    n := len(s)
    answer := 0
    
    for i := 0; i <= n - k; i++ {
        freq := make([]int, 26)
        isUnique := true
        
        for j := i; j < i + k; j++ {
            freq[s[j] - 'a']++
            
            if freq[s[j] - 'a'] > 1 {
                isUnique = false
                break
            }
        }
        
        if isUnique {
            answer++
        }
    }
    
    return answer
}

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