Задача: 1359. Count All Valid Pickup and Delivery Options
Сложность: hard

Дано n заказов, каждый из которых состоит из услуги забора и доставки.

Посчитайте все возможные допустимые последовательности забора/доставки, такие что доставка(i) всегда идет после забора(i).

Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: n = 1
Output: 1
Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.

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

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

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

3⃣Возвращение результата:
Верните результат для n заказов, применяя модуль 10^9 + 7 для предотвращения переполнения.

😎 Решение:

func countOrders(n int) int {
    MOD := 1_000_000_007
    dp := make([]int, n + 1)
    dp[0] = 1
    
    for i := 1; i <= n; i++ {
        dp[i] = dp[i - 1] * (2 * i - 1) * i % MOD
    }
    
    return dp[n]
}

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

Задача: 111. Minimum Depth of Binary Tree
Сложность: easy

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

Минимальная глубина - это количество узлов вдоль самого короткого пути от корневого узла до ближайшего листового узла.

Пример:

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

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

1⃣Мы будем использовать метод обхода в глубину (dfs) с корнем в качестве аргумента.
Базовое условие рекурсии: это для узла NULL, в этом случае мы должны вернуть 0.

2⃣Если левый ребенок корня является NULL: тогда мы должны вернуть 1 + минимальную глубину для правого ребенка корневого узла, что равно 1 + dfs(root.right).

3⃣Если правый ребенок корня является NULL: тогда мы должны вернуть 1 + минимальную глубину для левого ребенка корневого узла, что равно 1 + dfs(root.left). Если оба ребенка не являются NULL, тогда вернуть 1 + min(dfs(root.left), dfs(root.right)).

😎 Решение:

func minDepth(root *TreeNode) int {
    var dfs func(root *TreeNode) int
    dfs = func(root *TreeNode) int {
        if root == nil {
            return 0
        }
        if root.Left == nil {
            return 1 + dfs(root.Right)
        } else if root.Right == nil {
            return 1 + dfs(root.Left)
        }
        leftDepth := dfs(root.Left)
        rightDepth := dfs(root.Right)
        if leftDepth < rightDepth {
            return 1 + leftDepth
        } else {
            return 1 + rightDepth
        }
    }
    return dfs(root)
}

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

Задача: 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
Сложность: medium

Дан прямоугольный торт размером h x w и два массива целых чисел horizontalCuts и verticalCuts, где:
horizontalCuts[i] — это расстояние от верхнего края прямоугольного торта до i-го горизонтального разреза,
verticalCuts[j] — это расстояние от левого края прямоугольного торта до j-го вертикального разреза.
Верните максимальную площадь кусочка торта после разрезания в каждом горизонтальном и вертикальном положении, указанном в массивах horizontalCuts и verticalCuts. Так как ответ может быть очень большим числом, верните его по модулю 10^9 + 7.

Пример:

Input: h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
Output: 4 
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts.
 After you cut the cake, the green piece of cake has the maximum area.

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

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

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

3⃣Верните произведение максимальной высоты и максимальной ширины, взятое по модулю 10^9+7.

😎 Решение:

func maxArea(h int, w int, horizontalCuts []int, verticalCuts []int) int {
    sort.Ints(horizontalCuts)
    sort.Ints(verticalCuts)
    
    maxHeight := max(horizontalCuts[0], h - horizontalCuts[len(horizontalCuts)-1])
    for i := 1; i < len(horizontalCuts); i++ {
        maxHeight = max(maxHeight, horizontalCuts[i] - horizontalCuts[i-1])
    }
    
    maxWidth := max(verticalCuts[0], w - verticalCuts[len(verticalCuts)-1])
    for i := 1; i < len(verticalCuts); i++ {
        maxWidth = max(maxWidth, verticalCuts[i] - verticalCuts[i-1])
    }
    
    return (maxHeight * maxWidth) % 1000000007
}

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

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

Задача: 237. Delete Node in a Linked List
Сложность: medium

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

Вам дан узел node, который нужно удалить. У вас нет доступа к первому узлу head.

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

Удалите данный узел. Обратите внимание, что под удалением узла мы не подразумеваем его удаление из памяти. Мы имеем в виду:

- Значение данного узла не должно существовать в односвязном списке.
- Количество узлов в односвязном списке должно уменьшиться на один.
- Все значения перед узлом должны оставаться в том же порядке.
- Все значения после узла должны оставаться в том же порядке.

Пример:

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

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

1⃣Копирование данных: Скопируйте значение из следующего узла (node.next) в текущий узел (node). Таким образом, текущий узел будет иметь значение, которое было в следующем узле.

2⃣Обновление указателя: Обновите указатель next текущего узла, чтобы он ссылался на узел, следующий за узлом node.next. Это effectively удалит следующий узел из списка.

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

😎 Решение:

func deleteNode(node *ListNode) {
    node.Val = node.Next.Val
    node.Next = node.Next.Next
}

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

Задача: 990. Satisfiability of Equality Equations
Сложность: medium

Дан массив строк equations, представляющий отношения между переменными, где каждая строка equations[i] имеет длину 4 и принимает одну из двух форм: "xi==yi" или "xi!=yi". Здесь xi и yi - это строчные буквы (не обязательно разные), представляющие имена переменных из одной буквы.

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

Пример:

Input: equations = ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.

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

1⃣Создание графа для уравнений "==":
Создайте структуру данных для объединения (Union-Find) для обработки уравнений равенства.
Пройдите через массив equations и для каждого уравнения типа "xi==yi" объедините соответствующие переменные.

2⃣Проверка уравнений "!=":
Пройдите через массив equations и для каждого уравнения типа "xi!=yi" проверьте, принадлежат ли переменные к одной и той же группе в структуре объединения. Если принадлежат, верните false.

3⃣Возврат результата:
Если после проверки всех уравнений "xi!=yi" не было обнаружено противоречий, верните true.

😎 Решение:

func equationsPossible(equations []string) bool {
    uf := NewUnionFind(26)
    
    for _, eq := range equations {
        if eq[1] == '=' {
            x := int(eq[0] - 'a')
            y := int(eq[3] - 'a')
            uf.Union(x, y)
        }
    }
    
    for _, eq := range equations {
        if eq[1] == '!' {
            x := int(eq[0] - 'a')
            y := int(eq[3] - 'a')
            if uf.Connected(x, y) {
                return false
            }
        }
    }

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

Задача: 43. Multiply Strings
Сложность: hard

Даны два неотрицательных целых числа num1 и num2, представленные в виде строк. Верните произведение num1 и num2, также представленное в виде строки.

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

Пример:

Input: num1 = "2", num2 = "3"
Output: "6"

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

1⃣Переверните оба числа. Инициализируйте массив ans с (N+M) нулями. Для каждой цифры в secondNumber:
Инициализируйте переменную carry, первоначально равную 0.
Инициализируйте массив (currentResult), который начинается с некоторого количества нулей, основываясь на позиции цифры в secondNumber.

2⃣Для каждой цифры в firstNumber:
Умножьте цифру из secondNumber на цифру из firstNumber и добавьте предыдущий carry к умножению.
Возьмите остаток от деления умножения на 10, чтобы получить последнюю цифру.
Добавьте последнюю цифру в массив currentResult.
Разделите умножение на 10, чтобы получить новое значение для carry.

3⃣После итерации по каждой цифре в первом числе, если carry не равен нулю, добавьте carry в currentResult.
Добавьте currentResult к ans.
Если последняя цифра в ans равна нулю, перед тем как перевернуть ans, необходимо удалить ноль из ans. В противном случае в финальном ответе будет ведущий ноль.
Переверните ans и верните его.

😎 Решение:

func addStrings(num1 []int, num2 []int) []int {
    ans := []int{}
    carry := 0

    for i := 0; i < len(num1) || i < len(num2) || carry != 0; i++ {
        digit1, digit2 := 0, 0
        if i < len(num1) {
            digit1 = num1[i]
        }
        if i < len(num2) {
            digit2 = num2[i]
        }

        sum := digit1 + digit2 + carry
        carry = sum / 10
        ans = append(ans, sum%10)
    }

    if carry != 0 {
        ans = append(ans, carry)
    }
    return ans
}

func multiplyOneDigit(firstNumber string, secondNumberDigit rune, numZeros int) []int {
    currentResult := make([]int, numZeros)

    carry := 0
    for i := 0; i < len(firstNumber); i++ {
        firstNumberDigit := firstNumber[i] - '0'
        multiplication := int(secondNumberDigit-'0')*int(firstNumberDigit) + carry
        carry = multiplication / 10
        currentResult = append(currentResult, multiplication%10)
    }

    if carry != 0 {
        currentResult = append(currentResult, carry)
    }
    return currentResult
}

func multiply(num1 string, num2 string) string {
    if num1 == "0" || num2 == "0" {
        return "0"
    }

    firstNumber := reverseString(num1)
    secondNumber := reverseString(num2)

    N := len(firstNumber) + len(secondNumber)
    ans := make([]int, N)

    for i, digit := range secondNumber {
        result := multiplyOneDigit(firstNumber, rune(digit), i)
        ans = addStrings(result, ans)
    }

    if ans[len(ans)-1] == 0 {
        ans = ans[:len(ans)-1]
    }

    var answer strings.Builder
    for i := len(ans) - 1; i >= 0; i-- {
        answer.WriteString(strconv.Itoa(ans[i]))
    }

    return answer.String()
}

func reverseString(s string) string {
    runes := []rune(s)
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
    return string(runes)
}

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

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

Дан двоичный массив nums и целое число goal. Верните количество непустых подмассивов, сумма которых равна goal.

Пример:

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

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

1⃣Создаём хэш-таблицу, где ключ — сумма префикса, а значение — количество её вхождений. Изначально prefixSumCount[0] = 1.

2⃣Проходим по массиву, накапливая currentSum. Если (currentSum - goal) уже есть в хэше, увеличиваем счётчик count на количество таких префиксов.

3⃣Обновляем хэш-таблицу, увеличивая счётчик текущей суммы currentSum.

😎 Решение:

func numSubarraysWithSum(nums []int, goal int) int {
    prefixSumCount := make(map[int]int)
    prefixSumCount[0] = 1

    currentSum, count := 0, 0

    for _, num := range nums {
        currentSum += num
        count += prefixSumCount[currentSum - goal]
        prefixSumCount[currentSum]++
    }

    return count
}

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

Задача: 1257. Smallest Common Region
Сложность: medium

Вам даны списки регионов, в которых первый регион каждого списка включает все остальные регионы этого списка. Естественно, если регион x содержит другой регион y, то x больше y. Также, по определению, регион x содержит сам себя. Даны два региона: region1 и region2, верните наименьший регион, который содержит их оба. Если вам даны регионы r1, r2 и r3 такие, что r1 включает r3, то гарантированно не существует r2 такого, что r2 включает r3. Гарантированно существует наименьший регион.

Пример:
Input:
regions = [["Earth","North America","South America"],
["North America","United States","Canada"],
["United States","New York","Boston"],
["Canada","Ontario","Quebec"],
["South America","Brazil"]],
region1 = "Quebec",
region2 = "New York"
Output: "North America"

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

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

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

3⃣Найдем последний общий регион в путях двух заданных регионов.

😎 Решение:

func findSmallestRegion(regions [][]string, region1 string, region2 string) string {
    parent := make(map[string]string)

    for _, regionList := range regions {
        for i := 1; i < len(regionList); i++ {
            parent[regionList[i]] = regionList[0]
        }
    }

    ancestors1 := make(map[string]bool)
    for region1 != "" {
        ancestors1[region1] = true
        region1 = parent[region1]
    }

    for !ancestors1[region2] {
        region2 = parent[region2]
    }

    return region2
}

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

Задача: 362. Design Hit Counter
Сложность: medium

Дана матрица размером m x n, где каждая ячейка является либо стеной 'W', либо врагом 'E', либо пустой '0'. Верните максимальное количество врагов, которых можно уничтожить, используя одну бомбу. Вы можете разместить бомбу только в пустой ячейке.

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

Пример:

Input
["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]
[[], [1], [2], [3], [4], [300], [300], [301]]
Output
[null, null, null, null, 3, null, 4, 3]

Explanation
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1);       // hit at timestamp 1.
hitCounter.hit(2);       // hit at timestamp 2.
hitCounter.hit(3);       // hit at timestamp 3.
hitCounter.getHits(4);   // get hits at timestamp 4, return 3.
hitCounter.hit(300);     // hit at timestamp 300.
hitCounter.getHits(300); // get hits at timestamp 300, return 4.
hitCounter.getHits(301); // get hits at timestamp 301, return 3.

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

1⃣При вызове метода hit(int timestamp), добавьте временную метку в очередь.

2⃣ При вызове метода getHits(int timestamp), удалите все временные метки из очереди, которые старше 300 секунд от текущей временной метки.

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

😎 Решение:

package main

type HitCounter struct {
    hits []int
}

func Constructor() HitCounter {
    return HitCounter{hits: []int{}}
}

func (this *HitCounter) Hit(timestamp int) {
    this.hits = append(this.hits, timestamp)
}

func (this *HitCounter) GetHits(timestamp int) int {
    start := 0
    for start < len(this.hits) && timestamp - this.hits[start] >= 300 {
        start++
    }
    this.hits = this.hits[start:]
    return len(this.hits)
}

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

Задача: 639. Decode Ways II
Сложность: hard

Сообщение, содержащее буквы от A-Z, может быть закодировано в цифры с помощью следующего отображения: 'A' -> "1" 'B' -> "2" ... 'Z' -> "26" Чтобы декодировать закодированное сообщение, все цифры должны быть сгруппированы, а затем снова преобразованы в буквы с помощью обратного отображения (может быть несколько способов). Например, "11106" может быть преобразовано в: "AAJF" с группировкой (1 1 10 6) "KJF" с группировкой (11 10 6) Обратите внимание, что группировка (1 11 06) недействительна, поскольку "06" не может быть преобразовано в "F", так как "6" отличается от "06". В дополнение к вышеуказанным преобразованиям кодированное сообщение может содержать символ "*", который может представлять любую цифру от "1" до "9" ("0" исключается). Например, кодированное сообщение "1*" может представлять любое из кодированных сообщений "11", "12", "13", "14", "15", "16", "17", "18" или "19". Декодирование "1*" эквивалентно декодированию любого из кодированных сообщений, которые оно может представлять. Если задана строка s, состоящая из цифр и символов '*', верните количество способов ее декодирования. Поскольку ответ может быть очень большим, верните его по модулю 109 + 7.

Пример:

Input: s = "*"
Output: 9

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

1⃣Инициализация
Создайте массив dp, где dp[i] представляет количество способов декодирования подстроки s[0:i]. Установите начальные значения dp[0] = 1 (пустая строка имеет один способ декодирования).

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

3⃣Модульное вычисление
Поскольку количество способов декодирования может быть большим, вычисляйте результаты по модулю 10^9 + 7.

😎 Решение:

package main

import (
  "fmt"
)

func numDecodings(s string) int {
  const MOD = 1000000007
  n := len(s)
  dp := make([]int, n+1)
  dp[0] = 1

  for i := 1; i <= n; i++ {
    if s[i-1] == '*' {
      dp[i] = 9 * dp[i-1]
    } else if s[i-1] != '0' {
      dp[i] = dp[i-1]
    }

    if i > 1 {
      if s[i-2] == '*' {
        if s[i-1] == '*' {
          dp[i] += 15 * dp[i-2]
        } else if s[i-1] >= '0' && s[i-1] <= '6' {
          dp[i] += 2 * dp[i-2]
        } else {
          dp[i] += dp[i-2]
        }
      } else if s[i-2] == '1' {
        if s[i-1] == '*' {
          dp[i] += 9 * dp[i-2]
        } else {
          dp[i] += dp[i-2]
        }
      } else if s[i-2] == '2' {
        if s[i-1] == '*' {
          dp[i] += 6 * dp[i-2]
        } else if s[i-1] >= '0' && s[i-1] <= '6' {
          dp[i] += dp[i-2]
        }
      }
    }

    dp[i] %= MOD
  }

  return dp[n]
}

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

Задача: 84. Largest Rectangle in Histogram
Сложность: hard

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

Пример:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

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

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

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

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

😎 Решение:

func largestRectangleArea(heights []int) int {
    max_area := 0
    inf := int(^uint(0) >> 1)
    for i := 0; i < len(heights); i++ {
        for j := i; j < len(heights); j++ {
            min_height := inf
            for k := i; k <= j; k++ {
                if heights[k] < min_height {
                    min_height = heights[k]
                }
            }
            if min_height*(j-i+1) > max_area {
                max_area = min_height * (j - i + 1)
            }
        }
    }
    return max_area
}

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

Задача: 1238. Circular Permutation in Binary Representation
Сложность: medium

Даны 2 целых числа n и start. Ваша задача - вернуть любую перестановку p из (0,1,2.....,2^n -1) такую, что : p[0] = start p[i] и p[i+1] отличаются только одним битом в их двоичном представлении. p[0] и p[2^n -1] также должны отличаться только одним битом в их двоичном представлении.

Пример:

Input: n = 2, start = 3
Output: [3,2,0,1]

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

1⃣Генерация Грей-кода:
Генерация Грей-кода для чисел от 0 до 2𝑛−1

2⃣Определение начальной позиции:
Находим индекс числа start в последовательности Грей-кода.

3⃣Построение перестановки:
Формируем перестановку, начиная с числа start и следуя по циклическому Грей-коду.

😎 Решение:

func grayCode(n int) []int {
    result := make([]int, 1<<n)
    for i := 0; i < 1<<n; i++ {
        result[i] = i ^ (i >> 1)
    }
    return result
}

func circularPermutation(n int, start int) []int {
    gray := grayCode(n)
    startIndex := 0
    for i, v := range gray {
        if v == start {
            startIndex = i
            break
        }
    }
    return append(gray[startIndex:], gray[:startIndex]...)
}

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

Задача: 297. Serialize and Deserialize Binary Tree
Сложность: hard

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

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

Уточнение: формат ввода/вывода такой же, как в LeetCode для сериализации бинарного дерева. Вам не обязательно придерживаться этого формата, так что будьте креативны и придумайте свои подходы.

Пример:

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

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

1⃣Сериализация дерева:
Используйте рекурсивный обход дерева в порядке root -> left subtree -> right subtree.
Для каждого узла добавляйте его значение в строку сериализации. Если узел пустой, добавляйте "None".

2⃣Пример:
Начните с корня, узел 1, строка сериализации становится "1,".
Переходите к левому поддереву с корнем 2, строка сериализации становится "1,2,".
Для узла 2, посетите его левый узел 3 ("1,2,3,None,None,") и правый узел 4 ("1,2,3,None,None,4,None,None").
Возвращайтесь к корню 1 и посетите его правое поддерево, узел 5 ("1,2,3,None,None,4,None,None,5,None,None,").

3⃣Десериализация строки:
Разделите строку на список значений.
Используйте рекурсивную функцию для создания узлов дерева, извлекая значения из списка и восстанавливая структуру дерева. Если значение "None", узел пустой.

😎 Решение:

package main

import (
    "strconv"
    "strings"
)

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

type Codec struct{}

func (c *Codec) rserialize(root *TreeNode, str *strings.Builder) {
    if root == nil {
        str.WriteString("null,")
    } else {
        str.WriteString(strconv.Itoa(root.Val) + ",")
        c.rserialize(root.Left, str)
        c.rserialize(root.Right, str)
    }
}

func (c *Codec) serialize(root *TreeNode) string {
    var str strings.Builder
    c.rserialize(root, &str)
    return str.String()
}

func (c *Codec) rdeserialize(data *[]string) *TreeNode {
    if (*data)[0] == "null" {
        *data = (*data)[1:]
        return nil
    }

    val, _ := strconv.Atoi((*data)[0])
    root := &TreeNode{Val: val}
    *data = (*data)[1:]
    root.Left = c.rdeserialize(data)
    root.Right = c.rdeserialize(data)
    return root
}

func (c *Codec) deserialize(data string) *TreeNode {
    dataArray := strings.Split(data, ",")
    return c.rdeserialize(&dataArray)
}

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

Задача: 826. Most Profit Assigning Work
Сложность: medium

У вас есть n заданий и m рабочих. Вам даны три массива: difficulty, profit и worker, где:
difficulty[i] и profit[i] — сложность и прибыль i-го задания,
worker[j] — способность j-го рабочего (т.е. j-й рабочий может выполнить задание со сложностью не больше worker[j]).
Каждому рабочему можно назначить не более одного задания, но одно задание может быть выполнено несколько раз.
Например, если три рабочих выполняют одно и то же задание с оплатой $1, общая прибыль составит $3. Если рабочий не может выполнить ни одно задание, его прибыль равна $0.

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

Пример:

Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get a profit of [20,20,30,30] separately.

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

1⃣Создание и сортировка профиля работы
Инициализируйте массив пар jobProfile с {0, 0}. Для каждого задания добавьте {difficulty[i], profit[i]} в jobProfile. Отсортируйте jobProfile по возрастанию сложности.

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

3⃣Вычисление максимальной прибыли
Для каждой способности рабочего используйте бинарный поиск, чтобы найти задание с наибольшей прибылью, которую может выполнить этот рабочий. Суммируйте полученную прибыль для всех рабочих и верните ее.

😎 Решение:

func maxProfitAssignment(difficulty []int, profit []int, worker []int) int {
    type Job struct {
        Difficulty int
        Profit     int
    }
    
    jobProfile := []Job{{0, 0}}
    for i := 0; i < len(difficulty); i++ {
        jobProfile = append(jobProfile, Job{difficulty[i], profit[i]})
    }
    sort.Slice(jobProfile, func(i, j int) bool {
        return jobProfile[i].Difficulty < jobProfile[j].Difficulty
    })
    
    for i := 1; i < len(jobProfile); i++ {
        jobProfile[i].Profit = max(jobProfile[i].Profit, jobProfile[i-1].Profit)
    }
    
    netProfit := 0
    for _, ability := range worker {
        l, r := 0, len(jobProfile)-1
        jobProfit := 0
        for l <= r {
            mid := (l + r) / 2
            if jobProfile[mid].Difficulty <= ability {
                jobProfit = max(jobProfit, jobProfile[mid].Profit)
                l = mid + 1
            } else {
                r = mid - 1
            }
        }
        netProfit += jobProfit
    }
    return netProfit
}

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

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

Задача: 172. Factorial Trailing Zeroes
Сложность: medium

Дано целое число n, верните количество конечных нулей в n!.

Обратите внимание, что n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.

Пример:

Input: n = 3
Output: 0
Explanation: 3! = 6, no trailing zero.

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

1⃣Вычислите факториал n:
Инициализируйте переменную nFactorial значением 1.
Для каждого i от 2 до n включительно умножайте nFactorial на i.

2⃣Подсчитайте количество конечных нулей в nFactorial:
Инициализируйте переменную zeroCount значением 0.
Пока nFactorial делится на 10 без остатка, делите его на 10 и увеличивайте zeroCount на 1.

3⃣Верните значение zeroCount как количество конечных нулей в n!.

😎 Решение:

import (
    "math/big"
)

func trailingZeroes(n int) int {
    nFactorial := big.NewInt(1)
    for i := 2; i <= n; i++ {
        nFactorial.Mul(nFactorial, big.NewInt(int64(i)))
    }

    zeroCount := 0
    ten := big.NewInt(10)
    zero := big.NewInt(0)
    modResult := new(big.Int)

    for {
        modResult.Mod(nFactorial, ten)
        if modResult.Cmp(zero) == 0 {
            nFactorial.Div(nFactorial, ten)
            zeroCount++
        } else {
            break
        }
    }

    return zeroCount
}

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

Задача: 460. LFU Cache
Сложность: hard

Спроектируйте и реализуйте структуру данных для кеша с наименьшим количеством использования (Least Frequently Used, LFU).

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

LFUCache(int capacity): Инициализирует объект с указанной вместимостью структуры данных.
int get(int key): Возвращает значение ключа, если ключ существует в кеше. В противном случае возвращает -1.
void put(int key, int value): Обновляет значение ключа, если он уже присутствует, или вставляет ключ, если его еще нет. Когда кеш достигает своей вместимости, он должен аннулировать и удалить ключ, используемый наименее часто, перед вставкой нового элемента. В этой задаче, если имеется несколько ключей с одинаковой частотой использования, аннулируется наименее недавно использованный ключ.
Чтобы определить наименее часто используемый ключ, для каждого ключа в кеше поддерживается счетчик использования. Ключ с наименьшим счетчиком использования является наименее часто используемым ключом.
Когда ключ впервые вставляется в кеш, его счетчик использования устанавливается на 1 (из-за операции put). Счетчик использования для ключа в кеше увеличивается при вызове операции get или put для этого ключа.

Функции get и put должны иметь среднюю временную сложность O(1).

Пример:

Input
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

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

1⃣insert(int key, int frequency, int value):
Вставить пару частота-значение в cache с заданным ключом.
Получить LinkedHashSet, соответствующий данной частоте (по умолчанию пустой Set), и вставить в него ключ.

2⃣int get(int key):
Если ключа нет в кеше, вернуть -1.
Получить частоту и значение из кеша.
Удалить ключ из LinkedHashSet, связанного с частотой.
Если minf == frequency и LinkedHashSet пуст, увеличить minf на 1 и удалить запись частоты из frequencies.
Вызвать insert(key, frequency + 1, value).
Вернуть значение.

3⃣void put(int key, int value):
Если capacity <= 0, выйти.
Если ключ существует, обновить значение и вызвать get(key).
Если размер кеша равен capacity, удалить первый элемент из LinkedHashSet, связанного с minf, и из кеша.
Установить minf в 1.
Вызвать insert(key, 1, value).

😎 Решение:

package main
type LFUCache struct {
    cache       map[int][2]int
    frequencies map[int][]int
    capacity    int
    minf        int
}
func Constructor(capacity int) LFUCache {
    return LFUCache{
        cache:       make(map[int][2]int),
        frequencies: make(map[int][]int),
        capacity:    capacity,
    }
}
func (c *LFUCache) insert(key, freq, value int) {
    c.frequencies[freq] = append(c.frequencies[freq], key)
    c.cache[key] = [2]int{freq, value}
}
func (c *LFUCache) Get(key int) int {
    if val, found := c.cache[key]; !found {
        return -1
    } else {
        freq, value := val[0], val[1]
        c.frequencies[freq] = removeKey(c.frequencies[freq], key)
        if len(c.frequencies[freq]) == 0 {
            delete(c.frequencies, freq)
            if c.minf == freq {
                c.minf++
            }
        }
        c.insert(key, freq+1, value)
        return value
    }
}
func (c *LFUCache) Put(key int, value int) {
    if c.capacity <= 0 {
        return
    }
    if val, found := c.cache[key]; found {
        c.cache[key] = [2]int{val[0], value}
        c.Get(key)
        return
    }
    if len(c.cache) == c.capacity {
        minFreqKeys := c.frequencies[c.minf]
        delete(c.cache, minFreqKeys[0])
        c.frequencies[c.minf] = minFreqKeys[1:]
        if len(c.frequencies[c.minf]) == 0 {
            delete(c.frequencies, c.minf)
        }
    }
    c.minf = 1
    c.insert(key, 1, value)
}
func removeKey(slice []int, key int) []int {
    for i, v := range slice {
        if v == key {
            return append(slice[:i], slice[i+1:]...)
        }
    }
    return slice
}

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

Задача: 1396. Design Underground System
Сложность: medium

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

Реализуйте класс UndergroundSystem:
- void checkIn(int id, string stationName, int t)
Пассажир с карточкой, идентификатор которой равен id, регистрируется на станции stationName в момент времени t.
Пассажир может быть зарегистрирован только в одном месте в одно и то же время.
- void checkOut(int id, string stationName, int t)
Пассажир с карточкой, идентификатор которой равен id, покидает станцию stationName в момент времени t.
- double getAverageTime(string startStation, string endStation)
Возвращает среднее время, необходимое для поездки от startStation до endStation.
Среднее время рассчитывается на основе всех предыдущих поездок от startStation до endStation, где пассажиры зарегистрировались на startStation и вышли на endStation. Время поездки от startStation до endStation может отличаться от времени поездки от endStation до startStation. Перед вызовом getAverageTime как минимум один пассажир уже совершил поездку от startStation до endStation. Предполагается, что все вызовы методов checkIn и checkOut последовательны и происходят в хронологическом порядке.

Пример:

Input
["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]
[[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]
Output
[null,null,null,5.00000,null,null,5.50000]
Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8); // Customer 10 "Leyton" -> "Paradise" in 8-3 = 5
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000, (5) / 1 = 5
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16); // Customer 5 "Leyton" -> "Paradise" in 16-10 = 6
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000, (5 + 6) / 2 = 5.5

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

1⃣При регистрации на входе сохраняем информацию о начале пути (станция и время) в словаре checkInData.

2⃣При регистрации на выходе извлекаем информацию о начале пути из checkInData, вычисляем время поездки и обновляем статистику для маршрута в journeyData.

3⃣Для получения среднего времени поездки по заданному маршруту извлекаем статистику из journeyData и вычисляем среднее значение.

😎 Решение:

type UndergroundSystem struct {
    journeyData map[string][2]float64
    checkInData map[int][2]interface{}
}

func Constructor() UndergroundSystem {
    return UndergroundSystem{
        journeyData: make(map[string][2]float64),
        checkInData: make(map[int][2]interface{}),
    }
}

func (this *UndergroundSystem) CheckIn(id int, stationName string, t int) {
    this.checkInData[id] = [2]interface{}{stationName, t}
}

func (this *UndergroundSystem) CheckOut(id int, stationName string, t int) {
    checkIn := this.checkInData[id]
    startStation := checkIn[0].(string)
    startTime := checkIn[1].(int)
    delete(this.checkInData, id)
    routeKey := startStation + "->" + stationName
    tripTime := float64(t - startTime)
    if _, exists := this.journeyData[routeKey]; !exists {
        this.journeyData[routeKey] = [2]float64{0, 0}
    }
    this.journeyData[routeKey][0] += tripTime
    this.journeyData[routeKey][1] += 1
}

func (this *UndergroundSystem) GetAverageTime(startStation string, endStation string) float64 {
    stats := this.journeyData[startStation+"->"+endStation]
    return stats[0] / stats[1]
}

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

Задача: 476. Number Complement
Сложность: easy

Дополнение целого числа — это число, которое получается при замене всех 0 на 1 и всех 1 на 0 в его двоичном представлении.
Например, целое число 5 в двоичной системе — "101", и его дополнение — "010", что соответствует целому числу 2. Дано целое число num, верните его дополнение.

Пример:

Input: num = 5 
Output: 2  

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

1⃣Вычислите длину в битах входного числа: l = ⌊log₂(num)⌋ + 1.

2⃣Постройте битовую маску из 1-битов длины l: bitmask = (1 << l) − 1.

3⃣Верните результат операции XOR числа и битовой маски: num ⊕ bitmask.

😎 Решение:

package main

func findComplement(num int) int {
    bitmask := num
    bitmask |= (bitmask >> 1)
    bitmask |= (bitmask >> 2)
    bitmask |= (bitmask >> 4)
    bitmask |= (bitmask >> 8)
    bitmask |= (bitmask >> 16)
    return bitmask ^ num
}

func main() {}

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

Задача: 486. Predict the Winner
Сложность: medium

Дан массив nums. Игроки 1 и 2 поочередно берут по одному числу с любого конца массива.
Оба игрока играют оптимально. Нужно определить, сможет ли игрок 1 выиграть (или хотя бы не проиграть, т.е. равный счёт тоже считается победой).

Пример:

Input: nums = [1,5,2]
Output: false

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

1⃣Определяем рекурсивную функцию maxDiff(left, right), которая возвращает максимальную разницу очков между текущим игроком и соперником при игре на подотрезке массива.

2⃣На каждом шаге игрок может взять число либо с начала (left), либо с конца (right). После выбора число вычитается из результата рекурсивного вызова для оставшегося отрезка. Выбирается максимум из двух стратегий.

3⃣Игра начинается с полного массива: maxDiff(0, len(nums)-1). Если результат больше либо равен 0, игрок 1 может выиграть (или хотя бы не проиграть).

😎 Решение:

func maxDiff(nums []int, left int, right int) int {
    if left == right {
        return nums[left]
    }

    scoreByLeft := nums[left] - maxDiff(nums, left+1, right)
    scoreByRight := nums[right] - maxDiff(nums, left, right-1)

    if scoreByLeft > scoreByRight {
        return scoreByLeft
    }
    return scoreByRight
}

func predictTheWinner(nums []int) bool {
    return maxDiff(nums, 0, len(nums)-1) >= 0
}

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

Задача: 1370. Increasing Decreasing String
Сложность: easy

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

Выберите наименьший символ из s и добавьте его к результату.
Выберите наименьший символ из s, который больше последнего добавленного символа, и добавьте его.
Повторяйте шаг 2, пока не сможете выбрать больше символов.
Выберите наибольший символ из s и добавьте его к результату.
Выберите наибольший символ из s, который меньше последнего добавленного символа, и добавьте его.
Повторяйте шаг 5, пока не сможете выбрать больше символов.
Повторяйте шаги с 1 по 6, пока не выберете все символы из s.
На каждом этапе, если наименьший или наибольший символ появляется более одного раза, вы можете выбрать любое его вхождение и добавить его к результату.

Верните результирующую строку после сортировки s с помощью этого алгоритма.

Пример:
Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

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

1⃣Инициализация и сортировка:
Создайте словарь для подсчета количества каждого символа в строке s. Создайте результирующую строку result.

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

3⃣Проверка завершения:
Повторяйте шаги 2 и 3, пока не будут добавлены все символы из строки s в result.

😎 Решение:

func sortString(s string) string {
    charCount := make([]int, 26)
    for _, c := range s {
        charCount[c - 'a']++
    }
    
    result := make([]byte, 0, len(s))
    for len(result) < len(s) {
        for c := byte('a'); c <= 'z'; c++ {
            if charCount[c - 'a'] > 0 {
                result = append(result, c)
                charCount[c - 'a']--
            }
        }
        for c := byte('z'); c >= 'a'; c-- {
            if charCount[c - 'a'] > 0 {
                result = append(result, c)
                charCount[c - 'a']--
            }
        }
    }
    
    return string(result)
}

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

Задача: 655. Print Binary Tree
Сложность: medium

Учитывая корень двоичного дерева, постройте строковую матрицу res с индексом 0 размером m x n, которая представляет собой форматированную раскладку дерева. Форматированная матрица должна быть построена по следующим правилам: высота дерева равна height, количество строк m должно быть равно height + 1. Количество столбцов n должно быть равно 2height+1 - 1. Поместите корневой узел в середину верхней строки (более формально, в позицию res[0][(n-1)/2]).
Для каждого узла, который был помещен в матрицу в позицию res[r][c], поместите его левого ребенка в res[r+1][c-2height-r-1], а правого - в res[r+1][c+2height-r-1]. Продолжайте этот процесс, пока не будут размещены все узлы дерева. Любые пустые ячейки должны содержать пустую строку "". Верните построенную матрицу res.

Пример:

Input: root = [1,2]
Output: 
[["","1",""],
 ["2","",""]]

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

1⃣Найдите высоту дерева и определите размер матрицы (m x n).

2⃣Рекурсивно разместите узлы в матрице, начиная с корневого узла.

3⃣Верните заполненную матрицу.

😎 Решение:

package main

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

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

func findHeight(root *TreeNode) int {
    if root == nil {
        return -1
    }
    leftHeight := findHeight(root.Left)
    rightHeight := findHeight(root.Right)
    if leftHeight > rightHeight {
        return 1 + leftHeight
    }
    return 1 + rightHeight
}

func fill(res [][]string, root *TreeNode, r, c, height int) {
    if root == nil {
        return
    }
    res[r][c] = strconv.Itoa(root.Val)
    if root.Left != nil {
        fill(res, root.Left, r+1, c-(1<<(height-r-1)), height)
    }
    if root.Right != nil {
        fill(res, root.Right, r+1, c+(1<<(height-r-1)), height)
    }
}

func printTree(root *TreeNode) [][]string {
    height := findHeight(root)
    m := height + 1
    n := (1 << (height + 1)) - 1
    res := make([][]string, m)
    for i := range res {
        res[i] = make([]string, n)
        for j := range res[i] {
            res[i][j] = ""
        }
    }
    fill(res, root, 0, (n-1)/2, height)
    return res
}

func main() {
    root := &TreeNode{Val: 1, Left: &TreeNode{Val: 2}, Right: &TreeNode{Val: 3}}
    result := printTree(root)
    for _, row := range result {
        fmt.Println(strings.Join(row, " "))
    }
}

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