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

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

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

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