#medium
Задача: 274. H-Index

Дан массив целых чисел citations, где citations[i] — количество цитирований, которое исследователь получил за свою i-ю статью. Верните h-индекс исследователя.
Согласно определению h-индекса на Википедии: h-индекс определяется как максимальное значение h, такое что данный исследователь опубликовал по крайней мере h статей, каждая из которых была процитирована как минимум h раз.

Пример:

Input: citations = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

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

1️⃣Отсортировать массив цитирований по убыванию:
Отсортировать массив citations в порядке убывания, чтобы наибольшее количество цитирований было в начале массива.

2️⃣Найти наибольшее значение i, для которого citations[i] > i:
Пройтись по отсортированному массиву и найти наибольшее значение i, для которого выполняется условие citations[i] > i.
Это значение будет индексом, при котором количество цитирований статьи больше индекса.

3️⃣Рассчитать h-индекс:
h-индекс будет равен i + 1, где i - наибольшее значение, найденное на предыдущем шаге.

😎 Решение:

func hIndex(citations []int) int {
    n := len(citations)
    papers := make([]int, n+1)
    for _, c := range citations {
        if c >= n {
            papers[n]++
        } else {
            papers[c]++
        }
    }
    k := n
    s := papers[n]
    for k > s {
        k--
        s += papers[k]
    }
    return k
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 216. Combination Sum III

Найдите все допустимые комбинации k чисел, которые в сумме дают n, при условии, что:

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

Пример:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

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

1️⃣ Инициализация и запуск рекурсивной функции:
Создайте вспомогательную функцию backtrack, которая принимает текущую оставшуюся сумму, размер комбинации k, текущую комбинацию, индекс следующего элемента для добавления и список результатов.
Инициализируйте пустые векторы для хранения текущей комбинации и всех возможных результатов.
Запустите функцию backtrack с начальными значениями: полной суммой n, размером комбинации k, пустой комбинацией, начальным индексом 0 и пустым списком результатов.

2️⃣ Рекурсивная обработка:
В функции backtrack проверьте, если текущая сумма равна нулю и размер комбинации равен k, добавьте копию текущей комбинации в список результатов.
Если текущая сумма меньше нуля или размер комбинации равен k, прекратите текущую ветвь обработки.
Иначе, итерируйтесь по оставшимся кандидатам, начиная с текущего индекса. Для каждого кандидата добавьте его в текущую комбинацию, обновите оставшуюся сумму и вызовите backtrack с обновленными параметрами. После возвращения из рекурсивного вызова удалите последний элемент из комбинации для рассмотрения следующего кандидата.

3️⃣ Возвращение результатов:
По завершении всех рекурсивных вызовов функция combinationSum3 возвращает список всех найденных комбинаций.

😎 Решение:

package main

func backtrack(remain int, k int, comb []int, nextStart int, results *[][]int) {
    if remain == 0 && len(comb) == k {
        temp := make([]int, len(comb))
        copy(temp, comb)
        *results = append(*results, temp)
        return
    } else if remain < 0 || len(comb) == k {
        return
    }

    for i := nextStart; i < 9; i++ {
        comb = append(comb, i+1)
        backtrack(remain-i-1, k, comb, i+1, results)
        comb = comb[:len(comb)-1]
    }
}

func combinationSum3(k int, n int) [][]int {
    var results [][]int
    var comb []int
    backtrack(n, k, comb, 0, &results)
    return results
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 275. H-Index II

Дан массив целых чисел citations, где citations[i] — количество цитирований, которое исследователь получил за свою i-ю статью, и массив отсортирован в порядке возрастания. Верните h-индекс исследователя.
Согласно определению h-индекса на Википедии: h-индекс определяется как максимальное значение h, такое что данный исследователь опубликовал по крайней мере h статей, каждая из которых была процитирована как минимум h раз.
Вы должны написать алгоритм, который работает за логарифмическое время.

Пример:

Input: citations = [0,1,3,5,6]
Output: 3
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

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

1️⃣Найти середину массива:
Определить средний элемент массива, чтобы разделить его на две подмножества: citations[0: mid - 1] и citations[mid + 1: n].

2️⃣Сравнить количество статей с цитированиями больше или равными citations[mid]:
Если citations[mid] == n - mid, то найден h-индекс и его можно вернуть.
Если citations[mid] < n - mid, то необходимо искать в правой подмножности citations[mid + 1: n].
Если citations[mid] > n - mid, то необходимо искать в левой подмножности citations[0: mid - 1].

3️⃣Возвращение результата:
Продолжать процесс, пока не будет найден h-индекс.
Возвратить n - mid, что является количеством статей с цитированиями больше или равными citations[mid].

😎 Решение:

func hIndex(citations []int) int {
    n := len(citations)
    left, right := 0, n - 1
    
    for left <= right {
        mid := left + (right - left) / 2
        if citations[mid] == n - mid {
            return n - mid
        } else if citations[mid] < n - mid {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return n - left
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 217. Contains Duplicate

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

Пример:

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

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

1️⃣ Отсортируйте массив nums по возрастанию.

2️⃣ Итерируйте по отсортированному массиву и сравнивайте каждое число с следующим.

3️⃣ Если любое число совпадает с следующим, верните true. Если цикл завершится без совпадений, верните false.

😎 Решение:

import "sort"

func containsDuplicate(nums []int) bool {
    sort.Ints(nums)
    for i := 0; i < len(nums)-1; i++ {
        if nums[i] == nums[i+1] {
            return true
        }
    }
    return false
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 218. The Skyline Problem

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

Геометрическая информация о каждом здании задана в массиве buildings, где buildings[i] = [lefti, righti, heighti]:

lefti — это координата x левого края i-го здания.
righti — это координата x правого края i-го здания.
heighti — это высота i-го здания.
Вы можете предположить, что все здания — это идеальные прямоугольники, стоящие на абсолютно плоской поверхности на высоте 0.

Пример:

Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
Explanation:
Figure A shows the buildings of the input.
Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.

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

1️⃣ Соберите все уникальные позиции для левых и правых краев зданий в массиве buildings и сохраните их в список edgeSet. Инициализируйте хэш-таблицу edgeIndexMap для хранения соответствующих индексов и значений элементов из heights.

2️⃣ Пройдитесь по всем зданиям в массиве buildings, найдите индексы их левого и правого краев, а также их высоту. Для каждого здания обновите максимальную высоту в диапазоне [leftIndex, rightIndex).

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

😎 Решение:

func getSkyline(buildings [][]int) [][]int {
    edgeSet := make(map[int]struct{})
    for _, building := range buildings {
        edgeSet[building[0]] = struct{}{}
        edgeSet[building[1]] = struct{}{}
    }
    edges := make([]int, 0, len(edgeSet))
    for edge := range edgeSet {
        edges = append(edges, edge)
    }
    sort.Ints(edges)
    edgeIndexMap := make(map[int]int)
    for i, edge := range edges {
        edgeIndexMap[edge] = i
    }
    heights := make([]int, len(edges))
    for _, building := range buildings {
        left, right, height := building[0], building[1], building[2]
        leftIndex, rightIndex := edgeIndexMap[left], edgeIndexMap[right]
        for idx := leftIndex; idx < rightIndex; idx++ {
            if heights[idx] < height {
                heights[idx] = height
            }
        }
    }
    var answer [][]int
    for i, currHeight := range heights {
        currPos := edges[i]
        if len(answer) == 0 || answer[len(answer)-1][1] != currHeight {
            answer = append(answer, []int{currPos, currHeight})
        }
    }
    return answer
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 276. Paint Fence

Вы красите забор из n столбцов, используя k различных цветов. Вы должны красить столбы, следуя этим правилам:
Каждый столб должен быть окрашен в один цвет.
Не может быть трех или более подряд идущих столбцов одного цвета.
Учитывая два целых числа n и k, верните количество способов покрасить забор.

Пример:

Input: n = 3, k = 2
Output: 6
Explanation: All the possibilities are shown.
Note that painting all the posts red or all the posts green is invalid because there cannot be three posts in a row with the same color.

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

1️⃣Инициализация и определение вспомогательной функции:
Определить хеш-таблицу memo, где memo[i] представляет количество способов покрасить i столбцов.
Определить функцию totalWays, которая будет определять количество способов покрасить i столбцов.

2️⃣Реализация базы и проверка кэша:
В функции totalWays проверить базовые случаи: вернуть k, если i == 1, и вернуть k * k, если i == 2.
Проверить, рассчитан ли аргумент i и сохранен ли в memo. Если да, вернуть memo[i].

3️⃣Расчет с использованием рекуррентного соотношения:
В противном случае использовать рекуррентное соотношение для вычисления memo[i], сохранить результат в memo[i] и вернуть его.
Вызвать и вернуть totalWays(n).

😎 Решение:

func numWays(n int, k int) int {
    if n == 1 {
        return k
    }
    
    twoPostsBack := k
    onePostBack := k * k
    
    for i := 3; i <= n; i++ {
        curr := (k - 1) * (onePostBack + twoPostsBack)
        twoPostsBack = onePostBack
        onePostBack = curr
    }
    
    return onePostBack
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 219. Contains Duplicate II

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

Пример:

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

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

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

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

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

😎 Решение:

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

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 314. Binary Tree Vertical Order Traversal

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

Если два узла находятся в одной строке и столбце, порядок должен быть слева направо.

Пример:

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

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

1️⃣Создайте хэш-таблицу с именем columnTable для отслеживания результатов.

2️⃣Инициализируйте очередь, поместив в нее корневой узел вместе с его индексом столбца (0). Выполните обход в ширину (BFS), извлекая элементы из очереди. На каждой итерации извлекайте элемент, состоящий из узла и соответствующего индекса столбца. Если узел не пуст, добавьте его значение в columnTable. Затем поместите дочерние узлы с их индексами столбцов (т.е. column-1 и column+1) в очередь.

3️⃣После завершения BFS обхода получите хэш-таблицу, содержащую значения узлов, сгруппированные по индексам столбцов. Для каждой группы значений отсортируйте их по индексам строк. Отсортируйте хэш-таблицу по ключам (индексам столбцов) в порядке возрастания и верните результаты по столбцам.

😎 Решение:

package main

import (
    "sort"
    "container/list"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func verticalOrder(root *TreeNode) [][]int {
    var output [][]int
    if root == nil {
        return output
    }

    columnTable := map[int][]int{}
    queue := list.New()
    queue.PushBack([2]interface{}{root, 0})

    for queue.Len() > 0 {
        element := queue.Front()
        queue.Remove(element)
        pair := element.Value.([2]interface{})
        node := pair[0].(*TreeNode)
        column := pair[1].(int)

        if node != nil {
            columnTable[column] = append(columnTable[column], node.Val)

            if node.Left != nil {
                queue.PushBack([2]interface{}{node.Left, column - 1})
            }
            if node.Right != nil {
                queue.PushBack([2]interface{}{node.Right, column + 1})
            }
        }
    }

    var sortedKeys []int
    for key := range columnTable {
        sortedKeys = append(sortedKeys, key)
    }
    sort.Ints(sortedKeys)

    for _, key := range sortedKeys {
        output = append(output, columnTable[key])
    }

    return output
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 315. Count of Smaller Numbers After Self

Дан целочисленный массив nums, верните целочисленный массив counts, где counts[i] - это количество элементов справа от nums[i], которые меньше nums[i].

Пример:

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

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

1️⃣Реализуйте дерево отрезков (segment tree). Поскольку дерево инициализируется нулями, нужно реализовать только операции обновления и запроса. Установите смещение offset = 10^4.

2️⃣Итерация по каждому числу в nums в обратном порядке. Для каждого числа выполните следующие действия:
Смещайте число на num + offset.
Запросите количество элементов в дереве отрезков, которые меньше текущего числа.
Обновите счетчик текущего числа в дереве отрезков.

3️⃣Верните результат.

😎 Решение:

package main

import (
    "fmt"
    "sort"
)

func countSmaller(nums []int) []int {
    offset := 10000
    size := 2 * 10000 + 1
    tree := make([]int, size * 2)
    result := make([]int, len(nums))

    for i := len(nums) - 1; i >= 0; i-- {
        smallerCount := query(0, nums[i] + offset, tree, size)
        result[i] = smallerCount
        update(nums[i] + offset, 1, tree, size)
    }
    return result
}

func update(index, value int, tree []int, size int) {
    index += size
    tree[index] += value
    for index > 1 {
        index /= 2
        tree[index] = tree[index * 2] + tree[index * 2 + 1]
    }
}

func query(left, right int, tree []int, size int) int {
    result := 0
    left += size
    right += size
    for left < right {
        if left % 2 == 1 {
            result += tree[left]
            left++
        }
        left /= 2
        if right % 2 == 1 {
            right--
            result += tree[right]
        }
        right /= 2
    }
    return result
}

func main() {
    nums := []int{5, 2, 6, 1}
    fmt.Println(countSmaller(nums)) 
}

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 220. Contains Duplicate III

Вам дан массив целых чисел nums и два целых числа indexDiff и valueDiff.

Найдите пару индексов (i, j) таких, что:
i != j,
abs(i - j) <= indexDiff,
abs(nums[i] - nums[j]) <= valueDiff.

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

Пример:

Input: nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
Output: true
Explanation: We can choose (i, j) = (0, 3).
We satisfy the three conditions:
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0

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

1️⃣ Инициализация и вычисление корзин:
Рассчитать ширину корзины w = t + 1.
Инициализировать пустой хэш-таблицей buckets.
Определить функцию getID, которая возвращает идентификатор корзины для элемента x и ширины корзины w.

2️⃣ Итерация и проверка корзин:
Перебрать все элементы массива nums.
Для каждого элемента nums[i]:
Определить его корзину с помощью getID.
Проверить, есть ли в текущей корзине элемент. Если есть, вернуть true.
Проверить соседние корзины на наличие "почти дубликатов". Если есть, вернуть true.
Если текущая корзина пуста и в соседних корзинах нет "почти дубликатов", добавить текущий элемент в соответствующую корзину.
Если текущий индекс превышает k, удалить элемент из корзины, которая вышла за пределы окна.

3️⃣ Завершение:
Если ни одна пара "почти дубликатов" не найдена, вернуть false.

😎 Решение:

func getID(x, w int) int {
    if x < 0 {
        return (x + 1) / w - 1
    }
    return x / w
}

func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool {
    if t < 0 {
        return false
    }
    buckets := make(map[int]int)
    w := t + 1

    for i, num := range nums {
        bucket := getID(num, w)
        if _, ok := buckets[bucket]; ok {
            return true
        }
        if val, ok := buckets[bucket-1]; ok && abs(num-val) < w {
            return true
        }
        if val, ok := buckets[bucket+1]; ok && abs(num-val) < w {
            return true
        }
        buckets[bucket] = num
        if i >= k {
            delete(buckets, getID(nums[i-k], w))
        }
    }
    return false
}

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

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
🤔 Задача: 221. Maximal Square

Дана бинарная матрица размером m x n, заполненная 0 и 1. Найдите наибольший квадрат, содержащий только 1, и верните его площадь.

Пример:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

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

1⃣Инициализировать 1D массив dp с нулями, чтобы хранить промежуточные результаты для каждого столбца, а также переменные maxsqlen для максимальной длины квадрата и prev для предыдущего значения.

2⃣Пройти по каждому элементу матрицы. Если текущий элемент равен '1', обновить dp[j] по формуле dp[j]=min(dp[j−1],prev,dp[j])+1 и обновить maxsqlen. Если текущий элемент равен '0', установить dp[j] в 0. Обновить prev на значение dp[j] перед его изменением.

3⃣По завершении пройти по всем строкам и столбцам, вернуть квадрат maxsqlen как площадь наибольшего квадрата.

😎 Решение:

func maximalSquare(matrix [][]byte) int {
    rows := len(matrix)
    cols := 0
    if rows > 0 {
        cols = len(matrix[0])
    }
    dp := make([]int, cols+1)
    maxsqlen := 0
    prev := 0
    
    for i := 1; i <= rows; i++ {
        for j := 1; j <= cols; j++ {
            temp := dp[j]
            if matrix[i-1][j-1] == '1' {
                dp[j] = min(dp[j-1], min(prev, dp[j])) + 1
                maxsqlen = max(maxsqlen, dp[j])
            } else {
                dp[j] = 0
            }
            prev = temp
        }
    }
    
    return maxsqlen * maxsqlen
}

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
}

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

#easy
🤔 Задача: 222. Count Complete Tree Nodes

Учитывая корень полного двоичного дерева, верните количество узлов в дереве. Согласно Википедии, в полном двоичном дереве каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы на последнем уровне расположены как можно левее. Он может содержать от 1 до 2 в степени n узлов включительно на последнем уровне n. Разработайте алгоритм, который выполняется за время, меньшее, чем O(n).

Привет:

Input: root = [1,2,3,4,5,6]
Output: 6

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

1⃣Инициализация и проверка пустоты дерева
Если дерево пустое, вернуть 0.
Рассчитать глубину дерева d.

2⃣Поиск узлов на последнем уровне
Использовать двоичный поиск, чтобы найти количество узлов на последнем уровне. Функция exists используется для проверки наличия узла по индексу.

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

😎 Решение:

import (
    "math"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func computeDepth(node *TreeNode) int {
    d := 0
    for node.Left != nil {
        node = node.Left
        d++
    }
    return d
}

func exists(idx, d int, node *TreeNode) bool {
    left, right := 0, int(math.Pow(2, float64(d)))-1
    for i := 0; i < d; i++ {
        pivot := left + (right-left)/2
        if idx <= pivot {
            node = node.Left
            right = pivot
        } else {
            node = node.Right
            left = pivot + 1
        }
    }
    return node != nil
}

func countNodes(root *TreeNode) int {
    if root == nil {
        return 0
    }

    d := computeDepth(root)
    if d == 0 {
        return 1
    }

    left, right := 1, int(math.Pow(2, float64(d)))-1
    for left <= right {
        pivot := left + (right-left)/2
        if exists(pivot, d, root) {
            left = pivot + 1
        } else {
            right = pivot - 1
        }
    }

    return int(math.Pow(2, float64(d)) - 1 + float64(left))
}

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

#medium
Задача: 277. Find the Celebrity

Предположим, вы находитесь на вечеринке с n людьми, обозначенными от 0 до n - 1, и среди них может быть один знаменитость. Определение знаменитости: все остальные n - 1 человек знают знаменитость, но знаменитость не знает никого из них.
Теперь вы хотите выяснить, кто является знаменитостью, или убедиться, что ее нет. Вам разрешено задавать вопросы типа: "Привет, A. Ты знаешь B?", чтобы получить информацию о том, знает ли A B. Вам нужно найти знаменитость (или убедиться, что ее нет), задав как можно меньше вопросов (в асимптотическом смысле).
Вам предоставлена вспомогательная функция bool knows(a, b), которая сообщает, знает ли a b. Реализуйте функцию int findCelebrity(n). На вечеринке будет ровно одна знаменитость, если она есть.
Верните метку знаменитости, если она есть на вечеринке. Если знаменитости нет, верните -1.

Пример:

Input: graph = [[1,1,0],[0,1,0],[1,1,1]]
Output: 1
Explanation: There are three persons labeled with 0, 1 and 2. graph[i][j] = 1 means person i knows person j, otherwise graph[i][j] = 0 means person i does not know person j. The celebrity is the person labeled as 1 because both 0 and 2 know him but 1 does not know anybody.

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

1⃣Найти потенциального кандидата на знаменитость:
Использовать один проход через всех людей, чтобы определить возможного кандидата.
Если человек a знает человека b, то a не может быть знаменитостью, и переключаем кандидата на b.

2⃣Реализовать функцию isCelebrity(candidate):
Проверить, знает ли кандидат кого-либо из людей (исключая самих себя).
Проверить, знают ли все остальные кандидата (исключая самого кандидата).
Если кандидат знает кого-то, или кто-то не знает кандидата, то кандидат не является знаменитостью.

3⃣Возвращение результата:
Если кандидат проходит все проверки в isCelebrity(candidate), вернуть его метку.
В противном случае вернуть -1.

😎 Решение:

type Solution struct {
    n     int
    cache map[pair]bool
}

type pair struct {
    a, b int
}

func (s *Solution) findCelebrity(n int) int {
    s.n = n
    s.cache = make(map[pair]bool)
    celebrityCandidate := 0
    for i := 1; i < n; i++ {
        if s.cachedKnows(celebrityCandidate, i) {
            celebrityCandidate = i
        }
    }
    if s.isCelebrity(celebrityCandidate) {
        return celebrityCandidate
    }
    return -1
}

func (s *Solution) isCelebrity(i int) bool {
    for j := 0; j < s.n; j++ {
        if i == j {
            continue
        }
        if s.cachedKnows(i, j) || !s.cachedKnows(j, i) {
            return false
        }
    }
    return true
}

func (s *Solution) cachedKnows(a, b int) bool {
    key := pair{a, b}
    if _, exists := s.cache[key]; !exists {
        s.cache[key] = knows(a, b)
    }
    return s.cache[key]
}

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

#medium
Задача: 223. Rectangle Area

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

Первый прямоугольник определяется его нижним левым углом (ax1, ay1) и верхним правым углом (ax2, ay2).

Второй прямоугольник определяется его нижним левым углом (bx1, by1) и верхним правым углом (bx2, by2).

Пример:

Input: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
Output: 45

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

1⃣Вычислить площади двух прямоугольников:
Рассчитайте площади прямоугольников A и B, умножив их ширину на высоту.

2⃣Вычислить перекрытие:
Найдите перекрытие по оси X и оси Y. Если перекрытие существует, вычислите площадь перекрытия.

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

😎 Решение:

func computeArea(ax1 int, ay1 int, ax2 int, ay2 int, bx1 int, by1 int, bx2 int, by2 int) int {
    areaOfA := (ay2 - ay1) * (ax2 - ax1)
    areaOfB := (by2 - by1) * (bx2 - bx1)

    left := max(ax1, bx1)
    right := min(ax2, bx2)
    xOverlap := right - left

    top := min(ay2, by2)
    bottom := max(ay1, by1)
    yOverlap := top - bottom

    areaOfOverlap := 0
    if xOverlap > 0 && yOverlap > 0 {
        areaOfOverlap = xOverlap * yOverlap
    }

    totalArea := areaOfA + areaOfB - areaOfOverlap
    return totalArea
}

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

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

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

#hard
Задача: 224. Basic Calculator

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

Примечание: нельзя использовать встроенные функции, которые оценивают строки как математические выражения, такие как eval().

Пример:

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

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

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

2⃣Обработка выражения внутри скобок:
Когда встречаем открывающую скобку '(', оцениваем выражение, удаляя операнды и операторы из стека до соответствующей закрывающей скобки.
Результат выражения помещаем обратно в стек.

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

😎 Решение:

package main

import (
  "fmt"
  "math"
  "strconv"
  "unicode"
)

type Solution struct{}

func (s Solution) evaluateExpr(stack *[]interface{}) int {
  if len(*stack) == 0 || !isInt((*stack)[len(*stack)-1]) {
    *stack = append(*stack, 0)
  }

  res := pop(stack).(int)

  for len(*stack) != 0 && (*stack)[len(*stack)-1].(rune) != ')' {
    sign := pop(stack).(rune)

    if sign == '+' {
      res += pop(stack).(int)
    } else {
      res -= pop(stack).(int)
    }
  }
  return res
}

func (s Solution) calculate(expr string) int {
  operand := 0
  n := 0
  stack := []interface{}{}

  for i := len(expr) - 1; i >= 0; i-- {
    ch := expr[i]

    if unicode.IsDigit(rune(ch)) {
      operand = int(math.Pow(10, float64(n))) * (int(ch-'0')) + operand
      n += 1
    } else if ch != ' ' {
      if n != 0 {
        stack = append(stack, operand)
        n = 0
        operand = 0
      }
      if ch == '(' {
        res := s.evaluateExpr(&stack)
        pop(&stack)
        stack = append(stack, res)
      } else {
        stack = append(stack, rune(ch))
      }
    }
  }

  if n != 0 {
    stack = append(stack, operand)
  }

  return s.evaluateExpr(&stack)
}

func pop(stack *[]interface{}) interface{} {
  if len(*stack) == 0 {
    return nil
  }
  res := (*stack)[len(*stack)-1]
  *stack = (*stack)[:len(*stack)-1]
  return res
}

func isInt(value interface{}) bool {
  _, ok := value.(int)
  return ok
}

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

#easy
Задача: 225. Implement Stack using Queues

Реализуйте стек (последним пришел - первым вышел, LIFO) с использованием только двух очередей. Реализованный стек должен поддерживать все функции обычного стека (push, top, pop и empty).

Реализуйте класс MyStack:
void push(int x): Добавляет элемент x на вершину стека.
int pop(): Удаляет элемент с вершины стека и возвращает его.
int top(): Возвращает элемент на вершине стека.
boolean empty(): Возвращает true, если стек пуст, иначе false.

Примечания:
Вы должны использовать только стандартные операции очереди, что означает, что допустимы только операции добавления в конец, просмотр/удаление из начала, определение размера и проверка на пустоту.

Пример:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

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

1⃣Реализация методов push и pop:
Метод push добавляет элемент x в очередь q2, затем перемещает все элементы из q1 в q2 и меняет местами q1 и q2.
Метод pop удаляет элемент из q1 и обновляет значение top.

2⃣Реализация методов top и empty:
Метод top возвращает верхний элемент стека.
Метод empty проверяет, пуста ли очередь q1, и возвращает соответствующее значение.

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

😎 Решение:

package main

import "fmt"

type MyStack struct {
    q1 []int
    q2 []int
    topElement int
}

func Constructor() MyStack {
    return MyStack{
        q1: []int{},
        q2: []int{},
    }
}

func (this *MyStack) Push(x int)  {
    this.q2 = append(this.q2, x)
    this.topElement = x
    for len(this.q1) > 0 {
        this.q2 = append(this.q2, this.q1[0])
        this.q1 = this.q1[1:]
    }
    this.q1, this.q2 = this.q2, this.q1
}

func (this *MyStack) Pop() int {
    res := this.q1[0]
    this.q1 = this.q1[1:]
    if len(this.q1) > 0 {
        this.topElement = this.q1[0]
    }
    return res
}

func (this *MyStack) Top() int {
    return this.topElement
}

func (this *MyStack) Empty() bool {
    return len(this.q1) == 0
}

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

#easy
Задача: 226. Invert Binary Tree

Дан корень бинарного дерева, инвертируйте дерево и верните его корень.

Пример:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

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

1⃣Рекурсивная инверсия поддеревьев:
Если текущий узел (root) пустой, возвращаем null.
Рекурсивно инвертируем правое поддерево и сохраняем результат в переменную right.
Рекурсивно инвертируем левое поддерево и сохраняем результат в переменную left.

2⃣Обмен поддеревьев:
Устанавливаем левое поддерево текущего узла равным правому поддереву.
Устанавливаем правое поддерево текущего узла равным левому поддереву.

3⃣Возврат корня:
Возвращаем текущий узел (root) как новый корень инвертированного дерева.

😎 Решение:

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    right := invertTree(root.Right)
    left := invertTree(root.Left)
    root.Left = right
    root.Right = left
    return root
}

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

#easy
Задача: 278. First Bad Version

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

Предположим, у вас есть n версий [1, 2, ..., n], и вы хотите выяснить первую плохую версию, которая вызывает все последующие версии быть плохими.

Вам предоставлен API bool isBadVersion(version), который возвращает, является ли версия плохой. Реализуйте функцию для нахождения первой плохой версии. Вы должны минимизировать количество вызовов API.

Пример:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

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

1⃣Инициализация границ поиска:
Устанавливаем начальные значения левой и правой границ поиска: left = 1 и right = n.

2⃣Бинарный поиск:
Пока левая граница меньше правой, находим среднюю точку mid и проверяем, является ли она плохой версией с помощью isBadVersion(mid).
Если текущая версия mid плохая, смещаем правую границу к mid, иначе смещаем левую границу на mid + 1.

3⃣Возврат результата:
Когда левая граница станет равной правой, возвращаем left как индекс первой плохой версии.

😎 Решение:

package main

func firstBadVersion(n int) int {
    left, right := 1, n
    for left < right {
        mid := left + (right-left)/2
        if isBadVersion(mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

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

#medium
Задача: 279. Perfect Squares

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

Совершенный квадрат — это целое число, являющееся квадратом целого числа; другими словами, это произведение некоторого целого числа на самого себя. Например, 1, 4, 9 и 16 являются совершенными квадратами, тогда как 3 и 11 не являются.

Пример:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

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

1⃣Инициализация:
Создайте массив dp размером n + 1 и заполните его значениями Integer.MAX_VALUE, кроме dp[0], которое установите в 0.
Предварительно вычислите все совершенные квадраты, которые меньше или равны n, и сохраните их в массиве square_nums.

2⃣Заполнение массива dp:
Для каждого числа i от 1 до n:
Для каждого совершенного квадрата s из массива square_nums:
Если i меньше текущего совершенного квадрата s, прервите внутренний цикл.
Обновите dp[i], чтобы он содержал минимальное количество чисел, сумма которых равна i.

3⃣Возврат результата:
Верните значение dp[n], которое будет содержать наименьшее количество совершенных квадратов, сумма которых равна n.

😎 Решение:

import (
    "math"
    "fmt"
)

func numSquares(n int) int {
    dp := make([]int, n+1)
    for i := range dp {
        dp[i] = math.MaxInt32
    }
    dp[0] = 0
    
    maxSquareIndex := int(math.Sqrt(float64(n))) + 1
    squareNums := make([]int, maxSquareIndex)
    for i := 1; i < maxSquareIndex; i++ {
        squareNums[i] = i * i
    }
    
    for i := 1; i <= n; i++ {
        for s := 1; s < maxSquareIndex; s++ {
            if i < squareNums[s] {
                break
            }
            dp[i] = min(dp[i], dp[i-squareNums[s]]+1)
        }
    }
    
    return dp[n]
}

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

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

#medium
Задача: 382. Linked List Random Node

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

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

Solution(ListNode head) Инициализирует объект с головой односвязного списка head.
int getRandom() Выбирает узел случайным образом из списка и возвращает его значение. Все узлы списка должны иметь равные шансы быть выбранными.

Пример:

Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.

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

1⃣Реализуйте интерфейс init(head), который будет вызываться при создании объекта. Преобразуйте связанный список в массив для дальнейшего использования.

2⃣В интерфейсе init(head) преобразуйте переданный связанный список в массив, чтобы его можно было использовать позже.

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

😎 Решение:

package main

import (
  "math/rand"
  "time"
)

type ListNode struct {
  Val  int
  Next *ListNode
}

type Solution struct {
  rangeVals []int
}

func Constructor(head *ListNode) Solution {
  var rangeVals []int
  for head != nil {
    rangeVals = append(rangeVals, head.Val)
    head = head.Next
  }
  rand.Seed(time.Now().UnixNano())
  return Solution{rangeVals: rangeVals}
}

func (this *Solution) GetRandom() int {
  pick := rand.Intn(len(this.rangeVals))
  return this.rangeVals[pick]
}

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