#easy
Задача: 359. Logger Rate Limiter

Создайте систему логирования, которая получает поток сообщений вместе с их временными метками. Каждое уникальное сообщение должно печататься не чаще, чем раз в 10 секунд (то есть, сообщение, напечатанное во временной метке t, предотвратит печать других идентичных сообщений до временной метки t + 10).
Все сообщения будут приходить в хронологическом порядке. Несколько сообщений могут поступить в одно и то же время.

Реализуйте класс Logger:
Logger() Инициализирует объект логгера.
bool shouldPrintMessage(int timestamp, string message) Возвращает true, если сообщение должно быть напечатано в данной временной метке, в противном случае возвращает false.

Пример:

Input
["Logger", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage", "shouldPrintMessage"]
[[], [1, "foo"], [2, "bar"], [3, "foo"], [8, "bar"], [10, "foo"], [11, "foo"]]
Output
[null, true, true, false, false, false, true]

Explanation
Logger logger = new Logger();
logger.shouldPrintMessage(1, "foo");  // return true, next allowed timestamp for "foo" is 1 + 10 = 11
logger.shouldPrintMessage(2, "bar");  // return true, next allowed timestamp for "bar" is 2 + 10 = 12
logger.shouldPrintMessage(3, "foo");  // 3 < 11, return false
logger.shouldPrintMessage(8, "bar");  // 8 < 12, return false
logger.shouldPrintMessage(10, "foo"); // 10 < 11, return false
logger.shouldPrintMessage(11, "foo"); // 11 >= 11, return true, next allowed timestamp for "foo" is 11 + 10 = 21

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

1⃣Инициализируем хеш-таблицу/словарь для хранения сообщений вместе с временной меткой.

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

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

😎 Решение:

type Logger struct {
    msgDict map[string]int
}

func Constructor() Logger {
    return Logger{msgDict: make(map[string]int)}
}

func (this *Logger) ShouldPrintMessage(timestamp int, message string) bool {
    if oldTimestamp, exists := this.msgDict[message]; !exists || timestamp-oldTimestamp >= 10 {
        this.msgDict[message] = timestamp
        return true
    }
    return false
}

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

#medium
Задача: 436. Find Right Interval

Дан массив интервалов, где intervals[i] = [starti, endi] и каждый starti уникален.

Правый интервал для интервала i - это интервал j, такой что startj >= endi и startj минимален. Обратите внимание, что i может быть равен j.

Верните массив индексов правых интервалов для каждого интервала i. Если правого интервала для интервала i не существует, то поставьте -1 в индекс i.

Пример:

Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.

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

1⃣Интуиция за этим подходом такова: если мы будем поддерживать два массива - intervals, который отсортирован по начальным точкам, и endIntervals, который отсортирован по конечным точкам. Когда мы выбираем первый интервал (или, скажем, i-ый интервал) из массива endIntervals, мы можем определить подходящий интервал, удовлетворяющий критериям правого интервала, просматривая интервалы в массиве intervals слева направо, так как массив intervals отсортирован по начальным точкам. Допустим, индекс выбранного элемента из массива intervals окажется j.

2⃣Теперь, когда мы выбираем следующий интервал (скажем, (i+1)-ый интервал) из массива endIntervals, нам не нужно начинать сканирование массива intervals с первого индекса. Вместо этого мы можем начать прямо с индекса j, где мы остановились в последний раз в массиве intervals. Это потому, что конечная точка, соответствующая endIntervals[i+1], больше, чем та, которая соответствует endIntervals[i], и ни один из интервалов из intervals[k], таких что 0 < k < j, не удовлетворяет критериям правого соседа с endIntervals[i], а значит, и с endIntervals[i+1] тоже.

3⃣Если в какой-то момент мы достигнем конца массива, т.е. j = intervals.length, и ни один элемент, удовлетворяющий критериям правого интервала, не будет доступен в массиве intervals, мы ставим -1 в соответствующую запись res. То же самое касается всех оставшихся элементов массива endIntervals, конечные точки которых даже больше, чем у предыдущего интервала. Также мы используем хеш-таблицу hash изначально, чтобы сохранить индексы, соответствующие интервалам, даже после сортировки.

😎 Решение:

func findRightInterval(intervals [][]int) []int {
    endIntervals := make([][]int, len(intervals))
    copy(endIntervals, intervals)
    hash := make(map[[2]int]int)
    for i, interval := range intervals {
        hash[[2]int{interval[0], interval[1]}] = i
    }
    sort.Slice(intervals, func(a, b int) bool { return intervals[a][0] < intervals[b][0] })
    sort.Slice(endIntervals, func(a, b int) bool { return endIntervals[a][1] < endIntervals[b][1] })
    j := 0
    res := make([]int, len(intervals))
    for i := 0; i < len(endIntervals); i++ {
        for j < len(intervals) && intervals[j][0] < endIntervals[i][1] {
            j++
        }
        if j == len(intervals) {
            res[hash[[2]int{endIntervals[i][0], endIntervals[i][1]}]] = -1
        } else {
            res[hash[[2]int{endIntervals[i][0], endIntervals[i][1]}]] = hash[[2]int{intervals[j][0], intervals[j][1]}]
        }
    }
    return res
}

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

#medium
Задача: 437. Path Sum III

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

Путь не обязательно должен начинаться или заканчиваться в корне или на листе, но он должен идти вниз (т.е. перемещаться только от родительских узлов к дочерним).

Пример:

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

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

1⃣Инициализируем счетчик путей в дереве count = 0 и хеш-таблицу h, где ключ - это префиксная сумма, а значение - сколько раз она встречалась. Выполним рекурсивный обход дерева в порядке preorder: узел -> левый -> правый. Функция preorder(node: TreeNode, curr_sum: int) принимает два аргумента: узел дерева и префиксную сумму перед этим узлом. Чтобы запустить рекурсию, вызовем preorder(root, 0).

2⃣Сначала обновим текущую префиксную сумму, добавив значение текущего узла: curr_sum += node.val. Теперь можно обновить счетчик. Рассмотрим две ситуации. В первой ситуации путь в дереве с целевой суммой начинается с корня. Это означает, что текущая префиксная сумма равна целевой сумме curr_sum == k, поэтому увеличиваем счетчик на 1: count += 1. Во второй ситуации путь с целевой суммой начинается где-то ниже. Это означает, что нужно добавить к счетчику количество раз, когда мы видели префиксную сумму curr_sum - target: count += h[curr_sum - target].

3⃣Логика проста: текущая префиксная сумма - это curr_sum, а несколько элементов назад префиксная сумма была curr_sum - target. Все элементы между ними суммируются до curr_sum - (curr_sum - target) = target. Теперь обновим хеш-таблицу: h[curr_sum] += 1. Проанализируем левое и правое поддеревья: preorder(node.left, curr_sum), preorder(node.right, curr_sum). После обработки текущего поддерева удалим текущую префиксную сумму из хеш-таблицы, чтобы не смешивать параллельные поддеревья: h[curr_sum] -= 1. Когда обход в порядке preorder завершен, счетчик обновлен. Вернем его.

😎 Решение:

func pathSum(root *TreeNode, sum int) int {
    count := 0
    k := sum
    h := make(map[int]int)
    var preorder func(*TreeNode, int)
    preorder = func(node *TreeNode, curr_sum int) {
        if node == nil {
            return
        }
        curr_sum += node.Val
        if curr_sum == k {
            count++
        }
        count += h[curr_sum - k]
        h[curr_sum]++
        preorder(node.Left, curr_sum)
        preorder(node.Right, curr_sum)
        h[curr_sum]--
    }
    preorder(root, 0)
    return count
}

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

#medium
Задача: 360. Sort Transformed Array

Дан отсортированный массив целых чисел nums и три целых числа a, b и c. Примените квадратичную функцию вида f(x) = ax^2 + bx + c к каждому элементу nums[i] в массиве и верните массив в отсортированном порядке.

Пример:

Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]

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

1⃣Преобразование и сортировка
Преобразуем каждый элемент массива nums по квадратичной функции f(x) = ax^2 + bx + c и сохраняем результаты в массив transformed. Используем алгоритм поразрядной сортировки для сортировки массива transformed.

2⃣Поразрядная сортировка
Находим максимальное значение по модулю в массиве для определения количества цифр. Применяем поразрядную сортировку к массиву transformed.

3⃣Сортировка по цифре
Для каждой цифры (разряда) используем подсчет для сортировки массива.

😎 Решение:

package main

import (
    "sort"
    "math"
)

func sortTransformedArray(nums []int, a int, b int, c int) []int {
    transformed := make([]int, len(nums))
    for i, x := range nums {
        transformed[i] = a*x*x + b*x + c
    }

    radixSort(transformed)
    return transformed
}

func radixSort(array []int) {
    maxElement := int(math.Abs(float64(array[0])))
    for _, num := range array {
        maxElement = int(math.Max(float64(maxElement), math.Abs(float64(num))))
    }

    for placeValue := 1; maxElement/placeValue > 0; placeValue *= 10 {
        countingSortByDigit(array, placeValue)
    }

    negatives := []int{}
    positives := []int{}
    for _, num := range array {
        if num < 0 {
            negatives = append(negatives, num)
        } else {
            positives = append(positives, num)
        }
    }

    sort.Ints(negatives)
    sort.Ints(positives)
    array = append(negatives, positives...)
}

func countingSortByDigit(array []int, placeValue int) {
    n := len(array)
    output := make([]int, n)
    count := make([]int, 10)

    for _, num := range array {
        digit := (int(math.Abs(float64(num))) / placeValue) % 10
        count[digit]++
    }

    for i := 1; i < 10; i++ {
        count[i] += count[i-1]
    }

    for i := n - 1; i >= 0; i-- {
        num := array[i]
        digit := (int(math.Abs(float64(num))) / placeValue) % 10
        output[count[digit]-1] = num
        count[digit]--
    }

    copy(array, output)
}

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

#medium
Задача: 438. Find All Anagrams in a String
Даны две строки s и p, вернуть массив всех начальных индексов анаграмм строки p в строке s. Ответ можно вернуть в любом порядке.

Анаграмма - это слово или фраза, образованные перестановкой букв другого слова или фразы, обычно с использованием всех исходных букв ровно один раз.

Пример:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

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

1⃣Построить эталонный счетчик pCount для строки p.

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

3⃣Если sCount == pCount, обновить выходной список. Вернуть выходной список.

😎 Решение:

func findAnagrams(s string, p string) []int {
    ns, np := len(s), len(p)
    if ns < np {
        return []int{}
    }

    pCount := make(map[rune]int)
    sCount := make(map[rune]int)

    for _, ch := range p {
        pCount[ch]++
    }

    output := []int{}

    for i, ch := range s {
        sCount[ch]++
        if i >= np {
            leftChar := rune(s[i-np])
            if sCount[leftChar] == 1 {
                delete(sCount, leftChar)
            } else {
                sCount[leftChar]--
            }
        }

        if reflect.DeepEqual(pCount, sCount) {
            output = append(output, i-np+1)
        }
    }
    return output
}

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

#medium
Задача: 439. Ternary Expression Parser

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

Можно всегда считать, что данное выражение является корректным и содержит только цифры, '?', ':', 'T' и 'F', где 'T' означает истину, а 'F' - ложь. Все числа в выражении являются однозначными числами (т.е. в диапазоне от 0 до 9).

Условные выражения группируются справа налево (как обычно в большинстве языков), и результат выражения всегда будет либо цифрой, либо 'T', либо 'F'.

Пример:

Input: expression = "T?2:3"
Output: "2"
Explanation: If true, then result is 2; otherwise result is 3.

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

1⃣Определите вспомогательную функцию isValidAtomic(s), которая принимает строку s и возвращает True, если s является допустимым атомарным выражением. В противном случае функция возвращает False. Функция будет вызываться только с пятисимвольными строками. Если все следующие условия выполнены, функция возвращает True, иначе - False: s[0] является T или F. s[1] является ?. s[2] является T, F или цифрой от 0 до 9. s[3] является :. s[4] является T, F или цифрой от 0 до 9.

2⃣Определите вспомогательную функцию solveAtomic(s), которая принимает строку s и возвращает значение атомарного выражения. Значение атомарного выражения равно E1, если B - это T, иначе значение равно E2. Функция будет вызываться только с пятисимвольными строками и возвращать один символ:.

3⃣Если s[0] является T, функция возвращает s[2], иначе возвращает s[4]. В функции parseTernary(expression) уменьшайте выражение до тех пор, пока не останется односимвольная строка. Инициализируйте j как expression.size() - 1 (это будет самый правый индекс окна). Пока самое правое окно длиной 5 не является допустимым атомарным выражением, уменьшайте j на 1. Когда будет найдено самое правое допустимое атомарное выражение, решите его и уменьшите до одного символа. Замените самое правое допустимое атомарное выражение одним символом, после чего длина выражения уменьшится на 4. В итоге останется односимвольная строка, которую и верните.

😎 Решение:

func parseTernary(expression string) string {
    isValidAtomic := func(s string) bool {
        return (s[0] == 'T' || s[0] == 'F') &&
               s[1] == '?' &&
               (strings.Contains("TF0123456789", string(s[2]))) &&
               s[3] == ':' &&
               (strings.Contains("TF0123456789", string(s[4])))
    }

    solveAtomic := func(s string) byte {
        if s[0] == 'T' {
            return s[2]
        }
        return s[4]
    }

    for len(expression) != 1 {
        j := len(expression) - 1
        for !isValidAtomic(expression[j-4:j+1]) {
            j -= 1
        }
        expression = expression[:j-4] + string(solveAtomic(expression[j-4:j+1])) + expression[j+1:]
    }

    return expression
}

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

#medium
Задача: 361. Bomb Enemy

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

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

Пример:

Input: grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
Output: 3

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

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

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

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

😎 Решение:

package main

func maxKilledEnemies(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }

    rows := len(grid)
    cols := len(grid[0])
    maxCount := 0

    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            if grid[row][col] == '0' {
                hits := killEnemies(row, col, grid)
                if hits > maxCount {
                    maxCount = hits
                }
            }
        }
    }

    return maxCount
}

func killEnemies(row, col int, grid [][]byte) int {
    enemyCount := 0
    directions := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

    for _, dir := range directions {
        r, c := row + dir[0], col + dir[1]

        for r >= 0 && r < len(grid) && c >= 0 && c < len(grid[0]) {
            if grid[r][c] == 'W' {
                break
            }
            if grid[r][c] == 'E' {
                enemyCount++
            }
            r += dir[0]
            c += dir[1]
        }
    }

    return enemyCount
}

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

#medium
Задача: 361. Bomb Enemy

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

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

Пример:

Input: grid = [["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]
Output: 3

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

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

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

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

😎 Решение:

package main

import "fmt"

type Solution struct{}

func (s *Solution) maxKilledEnemies(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }

    rows := len(grid)
    cols := len(grid[0])
    maxCount := 0

    for row := 0; row < rows; row++ {
        for col := 0; col < cols; col++ {
            if grid[row][col] == '0' {
                hits := s.killEnemies(row, col, grid)
                if hits > maxCount {
                    maxCount = hits
                }
            }
        }
    }

    return maxCount
}

func (s *Solution) killEnemies(row, col int, grid [][]byte) int {
    enemyCount := 0
    directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

    for _, dir := range directions {
        r, c := row+dir[0], col+dir[1]

        for r >= 0 && r < len(grid) && c >= 0 && c < len(grid[0]) {
            if grid[r][c] == 'W' {
                break
            }
            if grid[r][c] == 'E' {
                enemyCount++
            }
            r += dir[0]
            c += dir[1]
        }
    }

    return enemyCount
}

func main() {
    grid := [][]byte{
        {'0', 'E', '0', '0'},
        {'E', '0', 'W', 'E'},
        {'0', 'E', '0', '0'},
    }

    sol := Solution{}
    fmt.Println(sol.maxKilledEnemies(grid)) 
}

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

#easy
Задача: 441. Arranging Coins

У вас есть n монет, и вы хотите построить лестницу из этих монет. Лестница состоит из k рядов, где i-й ряд содержит ровно i монет. Последний ряд лестницы может быть неполным.

Дано целое число n, верните количество полных рядов лестницы, которые вы сможете построить.

Пример:

Input: n = 5
Output: 2
Explanation: Because the 3rd row is incomplete, we return 2.

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

1⃣Если мы глубже посмотрим на формулу задачи, мы можем решить её с помощью математики, без использования итераций.

2⃣Напомним, что условие задачи можно выразить следующим образом: k(k + 1) ≤ 2N.

3⃣Это можно решить методом выделения полного квадрата, (k + 1/2)² - 1/4 ≤ 2N. Что приводит к следующему ответу: k = [sqrt(2N + 1/4) - 1/2].

😎 Решение:

import "math"

func arrangeCoins(n int) int {
    return int(math.Sqrt(float64(2 * n) + 0.25) - 0.5)
}

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

#medium
Задача: 442. Find All Duplicates in an Array


Дан целочисленный массив nums длины n, где все целые числа nums находятся в диапазоне [1, n], и каждое число появляется один или два раза. Верните массив всех чисел, которые появляются дважды.

Вы должны написать алгоритм, который работает за время O(n) и использует только постоянное дополнительное пространство.

Пример:

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

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

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

2⃣Поскольку элемент может появляться только один или два раза, нам не нужно беспокоиться о получении дубликатов элементов, которые появляются дважды: Случай I: Если элемент встречается в массиве только один раз, при поиске его в остальной части массива ничего не найдется. Случай II: Если элемент встречается дважды, вы найдете второе вхождение элемента в оставшейся части массива. Когда вы наткнетесь на второе вхождение в более поздней итерации, это будет аналогично случаю I (поскольку больше вхождений этого элемента в оставшейся части массива не будет).

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

😎 Решение:

func findDuplicates(nums []int) []int {
    ans := []int{}
    
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[j] == nums[i] {
                ans = append(ans, nums[i])
                break
            }
        }
    }
    
    return ans
}

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

#medium
Задача: 362. Design Hit Counter

Дана матрица размером 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)
}

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

#medium
Задача: 443. String Compression


Дан массив символов chars, сжать его, используя следующий алгоритм:

Начните с пустой строки s. Для каждой группы последовательных повторяющихся символов в chars:

Если длина группы равна 1, добавьте символ к строке s.
В противном случае добавьте символ, а за ним длину группы.
Сжатая строка s не должна возвращаться отдельно, а вместо этого должна быть сохранена в входном массиве символов chars. Обратите внимание, что длины групп, которые равны 10 или более, будут разделены на несколько символов в chars.

После того как вы закончите модификацию входного массива, верните новую длину массива.

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

Пример:

Input: chars = ["a","a","b","b","c","c","c"]
Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".

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

1⃣Объявите переменные i – первый индекс текущей группы, и res – длина ответа (сжатой строки). Инициализируйте i = 0, res = 0.

2⃣Пока i меньше длины chars: Найдите длину текущей группы последовательных повторяющихся символов groupLength. Добавьте chars[i] к ответу (chars[res++] = chars[i]). Если groupLength > 1, добавьте строковое представление groupLength к ответу и увеличьте res соответственно. Увеличьте i на groupLength и перейдите к следующей группе.

3⃣Верните res.

😎 Решение:

func compress(chars []byte) int {
    i, res := 0, 0
    for i < len(chars) {
        groupLength := 1
        for i+groupLength < len(chars) && chars[i+groupLength] == chars[i] {
            groupLength++
        }
        chars[res] = chars[i]
        res++
        if groupLength > 1 {
            strRepr := strconv.Itoa(groupLength)
            for j := 0; j < len(strRepr); j++ {
                chars[res] = strRepr[j]
                res++
            }
        }
        i += groupLength
    }
    return res
}

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

#hard
Задача: 363. Max Sum of Rectangle No Larger Than K

Дана матрица размером m x n и целое число k, вернуть максимальную сумму прямоугольника в матрице, такая что его сумма не превышает k.

Гарантируется, что будет прямоугольник с суммой, не превышающей k.

Пример:

Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation: Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).

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

1⃣Создать вспомогательную функцию updateResult, которая будет находить максимальную сумму подмассива в одномерном массиве, не превышающую k.

2⃣Преобразовать каждую подматрицу в одномерный массив и применить к ней функцию updateResult.

3⃣Вернуть максимальную найденную сумму.

😎 Решение:

package main

import (
  "math"
  "sort"
)

type Solution struct {
  result int
}

func Constructor() Solution {
  return Solution{result: math.MinInt32}
}

func (this *Solution) updateResult(nums []int, k int) {
  sum := 0
  sortedSum := []int{0}

  for _, num := range nums {
    sum += num
    idx := sort.Search(len(sortedSum), func(i int) bool { return sortedSum[i] >= sum-k })
    if idx < len(sortedSum) {
      this.result = int(math.Max(float64(this.result), float64(sum-sortedSum[idx])))
    }
    sortedSum = append(sortedSum, sum)
    sort.Ints(sortedSum)
  }
}

func (this *Solution) maxSumSubmatrix(matrix [][]int, k int) int {
  rows := len(matrix)
  cols := len(matrix[0])

  for i := 0; i < rows; i++ {
    rowSum := make([]int, cols)
    for row := i; row < rows; row++ {
      for col := 0; col < cols; col++ {
        rowSum[col] += matrix[row][col]
      }
      this.updateResult(rowSum, k)
      if this.result == k {
        return this.result
      }
    }
  }
  return this.result
}

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

#medium
Задача: 445. Add Two Numbers II


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

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

Пример:

Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]

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

1⃣Создайте два связанных списка r1 и r2, чтобы хранить перевернутые связанные списки l1 и l2 соответственно. Создайте два целых числа totalSum и carry для хранения суммы и переноса текущих цифр. Создайте новый ListNode, ans, который будет хранить сумму текущих цифр. Мы будем складывать два числа, используя перевернутый список, добавляя цифры по одной. Продолжаем, пока не пройдем все узлы в r1 и r2.

2⃣Если r1 не равен null, добавляем r1.val к totalSum. Если r2 не равен null, добавляем r2.val к totalSum. Устанавливаем ans.val = totalSum % 10. Сохраняем перенос как totalSum / 10. Создаем новый ListNode, newNode, который будет иметь значение как перенос. Устанавливаем next для newNode как ans. Обновляем ans = newNode, чтобы использовать ту же переменную ans для следующей итерации. Обновляем totalSum = carry.

3⃣Если carry == 0, это означает, что newNode, созданный в финальной итерации цикла while, имеет значение 0. Поскольку мы выполняем ans = newNode в конце каждой итерации цикла while, чтобы избежать возврата связанного списка с головой, равной 0 (начальный ноль), возвращаем следующий элемент, т.е. возвращаем ans.next. В противном случае, если перенос не равен 0, значение ans не равно нулю. Следовательно, просто возвращаем ans.

😎 Решение:

type ListNode struct {
    Val  int
    Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    var temp *ListNode
    for head != nil {
        temp = head.Next
        head.Next = prev
        prev = head
        head = temp
    }
    return prev
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    r1 := reverseList(l1)
    r2 := reverseList(l2)

    totalSum := 0
    carry := 0
    ans := &ListNode{}
    for r1 != nil || r2 != nil {
        if r1 != nil {
            totalSum += r1.Val
            r1 = r1.Next
        }
        if r2 != nil {
            totalSum += r2.Val
            r2 = r2.Next
        }

        ans.Val = totalSum % 10
        carry = totalSum / 10
        head := &ListNode{Val: carry}
        head.Next = ans
        ans = head
        totalSum = carry
    }

    if carry == 0 {
        return ans.Next
    }
    return ans
}

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

#hard
Задача: 446. Arithmetic Slices II - Subsequence


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

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

Например, [1, 3, 5, 7, 9], [7, 7, 7, 7] и [3, -1, -5, -9] являются арифметическими последовательностями.
Например, [1, 1, 2, 5, 7] не является арифметической последовательностью.
Подпоследовательность массива - это последовательность, которая может быть образована путем удаления некоторых элементов (возможно, ни одного) из массива.

Например, [2, 5, 10] является подпоследовательностью [1, 2, 1, 2, 4, 1, 5, 10].
Тестовые случаи сгенерированы таким образом, что ответ помещается в 32-битное целое число.

Пример:

Input: nums = [2,4,6,8,10]
Output: 7
Explanation: All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

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

1⃣Мы можем использовать поиск в глубину (DFS) для генерации всех подпоследовательностей.

2⃣Мы можем проверить, является ли подпоследовательность арифметической, согласно ее определению.

3⃣Возвращаем количество всех арифметических подпоследовательностей.

😎 Решение:

type Solution struct {
    n   int
    ans int
}

func (sol *Solution) dfs(dep int, A []int, cur []int64) {
    if dep == sol.n {
        if len(cur) < 3 {
            return
        }
        for i := 1; i < len(cur); i++ {
            if cur[i]-cur[i-1] != cur[1]-cur[0] {
                return
            }
        }
        sol.ans++
        return
    }
    sol.dfs(dep+1, A, cur)
    cur = append(cur, int64(A[dep]))
    sol.dfs(dep+1, A, cur)
    cur = cur[:len(cur)-1]
}

func numberOfArithmeticSlices(A []int) int {
    sol := Solution{n: len(A), ans: 0}
    sol.dfs(0, A, []int64{})
    return sol.ans
}

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

#medium
Задача: 364. Nested List Weight Sum II

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

Глубина целого числа — это количество списков, внутри которых оно находится. Например, вложенный список [1,[2,2],[[3],2],1] имеет значение каждого целого числа, установленное равным его глубине. Пусть maxDepth будет максимальной глубиной любого целого числа.
Вес целого числа определяется как maxDepth - (глубина целого числа) + 1.

Верните сумму каждого целого числа в nestedList, умноженную на его вес.

Пример:

Input: nestedList = [[1,1],2,[1,1]]
Output: 8
Explanation: Four 1's with a weight of 1, one 2 with a weight of 2.
1*1 + 1*1 + 2*2 + 1*1 + 1*1 = 8

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

1⃣Инициализировать первый уровень BFS-дерева, добавив все элементы из входного nestedList в очередь.

2⃣Для каждого уровня извлекать передний элемент из очереди. Если это список, то добавить его элементы в очередь. В противном случае обновить значения sumOfElements, maxDepth и sumOfProducts.

3⃣Когда очередь станет пустой, вернуть значение (maxDepth + 1) * sumOfElements - sumOfProducts.

😎 Решение:

package main

type NestedInteger struct {
    // This is a placeholder structure for the NestedInteger implementation
}

func (ni NestedInteger) IsInteger() bool {
    // Placeholder method
    return false
}

func (ni NestedInteger) GetInteger() int {
    // Placeholder method
    return 0
}

func (ni NestedInteger) GetList() []*NestedInteger {
    // Placeholder method
    return nil
}

func depthSumInverse(nestedList []*NestedInteger) int {
    queue := append([]*NestedInteger(nil), nestedList...)
    depth, maxDepth, sumOfElements, sumOfProducts := 1, 0, 0, 0

    for len(queue) > 0 {
        size := len(queue)
        if depth > maxDepth {
            maxDepth = depth
        }

        for i := 0; i < size; i++ {
            nested := queue[0]
            queue = queue[1:]

            if nested.IsInteger() {
                value := nested.GetInteger()
                sumOfElements += value
                sumOfProducts += value * depth
            } else {
                queue = append(queue, nested.GetList()...)
            }
        }
        depth++
    }
    return (maxDepth + 1) * sumOfElements - sumOfProducts
}

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

#medium
Задача: 366. Find Leaves of Binary Tree

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

Пример:

Input: root = [1,2,3,4,5]
Output: [[4,5,3],[2],[1]]
Explanation:
[[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.

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

1⃣Реализовать функцию getHeight(node), которая будет вычислять высоту каждого узла в дереве с использованием рекурсивного обхода в глубину (post-order). Если узел является null, вернуть -1.

2⃣Сохранить пары (высота, значение) для всех узлов и отсортировать их по высоте.

3⃣Организовать узлы по высоте и вернуть результат.

😎 Решение:

package main

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

type pair struct {
    height, value int
}

type Solution struct {
    pairs []pair
}

func (s *Solution) getHeight(node *TreeNode) int {
    if node == nil {
        return -1
    }
    leftHeight := s.getHeight(node.Left)
    rightHeight := s.getHeight(node.Right)
    currHeight := max(leftHeight, rightHeight) + 1
    s.pairs = append(s.pairs, pair{currHeight, node.Val})
    return currHeight
}

func (s *Solution) findLeaves(root *TreeNode) [][]int {
    s.getHeight(root)
    sort.Slice(s.pairs, func(i, j int) bool {
        return s.pairs[i].height < s.pairs[j].height
    })
    var solution [][]int
    currentHeight := -1
    for _, p := range s.pairs {
        if p.height != currentHeight {
            solution = append(solution, []int{})
            currentHeight = p.height
        }
        solution[len(solution)-1] = append(solution[len(solution)-1], p.value)
    }
    return solution
}

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

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

#hard
Задача: 591. Tag Validator

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

Фрагмент кода считается корректным, если соблюдаются все следующие правила:
Код должен быть заключен в корректный закрытый тег. В противном случае код некорректен.
Закрытый тег (не обязательно корректный) имеет точно следующий формат: <TAG_NAME>TAG_CONTENT</TAG_NAME>. Среди них <TAG_NAME> — это начальный тег, а </TAG_NAME> — конечный тег. TAG_NAME в начальном и конечном тегах должен быть одинаковым. Закрытый тег корректен, если и только если TAG_NAME и TAG_CONTENT корректны.
Корректное TAG_NAME содержит только заглавные буквы и имеет длину в диапазоне [1, 9]. В противном случае TAG_NAME некорректен.
Корректное TAG_CONTENT может содержать другие корректные закрытые теги, cdata и любые символы (см. примечание 1), КРОМЕ неподходящих <, неподходящих начальных и конечных тегов, и неподходящих или закрытых тегов с некорректным TAG_NAME. В противном случае TAG_CONTENT некорректен.
Начальный тег неподходящий, если нет конечного тега с тем же TAG_NAME, и наоборот. Однако нужно также учитывать проблему несбалансированных тегов, когда они вложены.
< неподходящий, если не удается найти последующий >. И когда вы находите < или </, все последующие символы до следующего > должны быть разобраны как TAG_NAME (не обязательно корректный).
cdata имеет следующий формат: <![CDATA[CDATA_CONTENT]]>. Диапазон CDATA_CONTENT определяется как символы между <![CDATA[ и первым последующим ]]>.
CDATA_CONTENT может содержать любые символы. Функция cdata заключается в том, чтобы запретить валидатору разбирать CDATA_CONTENT, поэтому даже если в нем есть символы, которые могут быть разобраны как тег (корректный или некорректный), вы должны рассматривать их как обычные символы.

Пример:

Input: code = "<DIV>This is the first line <![CDATA[<div>]]></DIV>"
Output: true

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

1⃣Инициализируйте стек для отслеживания открытых тегов и флаг для определения наличия тегов. Используйте регулярное выражение для проверки корректности TAG_NAME, TAG_CONTENT и CDATA.

2⃣Пройдитесь по строке, проверяя каждый символ. Если встретите <, определите тип тега (начальный, конечный или CDATA). Обновите стек и индексы в зависимости от найденного типа.

3⃣В конце проверьте, что стек пуст (все теги корректно закрыты) и верните результат.

😎 Решение:

package main

import (
    "regexp"
    "strings"
)

type Solution struct {
    stack       []string
    containsTag bool
}

func (s *Solution) isValidTagName(tag string, ending bool) bool {
    if ending {
        if len(s.stack) > 0 && s.stack[len(s.stack)-1] == tag {
            s.stack = s.stack[:len(s.stack)-1]
        } else {
            return false
        }
    } else {
        s.containsTag = true
        s.stack = append(s.stack, tag)
    }
    return true
}

func (s *Solution) IsValid(code string) bool {
    regex := "<[A-Z]{0,9}>([^<]*(<((\\/?[A-Z]{1,9}>)|(!\\[CDATA\\[(.*?)]]>)))?)*"
    matched, _ := regexp.MatchString(regex, code)
    if !matched {
        return false
    }

    for i := 0; i < len(code); i++ {
        ending := false
        if len(s.stack) == 0 && s.containsTag {
            return false
        }
        if code[i] == '<' {
            if code[i+1] == '!' {
                i = strings.Index(code[i+1:], "]]>") + i + 2
                if i == -1 {
                    return false
                }
                continue
            }
            if code[i+1] == '/' {
                i++
                ending = true
            }
            closeIndex := strings.Index(code[i+1:], ">") + i + 1
            if closeIndex == -1 || !s.isValidTagName(code[i+1:closeIndex], ending) {
                return false
            }
            i = closeIndex
        }
    }
    return len(s.stack) == 0
}

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

#medium
Задача: 764. Largest Plus Sign

Вам дано целое число n. У вас есть бинарная сетка размером n x n, в которой все значения изначально равны 1, за исключением некоторых индексов, указанных в массиве mines. Элемент массива mines с индексом i определяется как mines[i] = [xi, yi], где grid[xi][yi] == 0.

Верните порядок самого большого крестообразного знака из 1, выровненного по осям, который содержится в сетке. Если такого знака нет, верните 0.

Крестообразный знак из 1 порядка k имеет некоторый центр grid[r][c] == 1, а также четыре луча длиной k - 1, идущих вверх, вниз, влево и вправо, состоящие из 1. Обратите внимание, что за пределами лучей креста могут быть 0 или 1, проверяется только соответствующая область крестообразного знака на наличие 1.

Пример:

Input: n = 5, mines = [[4,2]]
Output: 2
Explanation: In the above grid, the largest plus sign can only be of order 2. One of them is shown.

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

1⃣Создайте сетку размером n x n, заполненную единицами. Затем используйте массив mines, чтобы установить значения нулей в соответствующих ячейках сетки.

2⃣Для каждой ячейки в сетке создайте четыре дополнительных сетки: left, right, up и down, которые будут хранить длину непрерывных единиц, простирающихся в соответствующем направлении от каждой ячейки.

3⃣Пройдите по всей сетке и для каждой ячейки определите минимальную длину луча среди четырех направлений. Эта минимальная длина будет определять порядок крестообразного знака с центром в данной ячейке. Обновите максимальный порядок крестообразного знака и верните его после завершения обхода всей сетки. Если такого знака нет, верните 0.

😎 Решение:

func orderOfLargestPlusSign(N int, mines [][]int) int {
    banned := make(map[int]bool)
    for _, mine := range mines {
        banned[mine[0]*N + mine[1]] = true
    }
    
    ans := 0
    for r := 0; r < N; r++ {
        for c := 0; c < N; c++ {
            k := 0
            for k <= r && r < N - k && k <= c && c < N - k &&
                  !banned[(r - k) * N + c] &&
                  !banned[(r + k) * N + c] &&
                  !banned[r * N + c - k] &&
                  !banned[r * N + c + k] {
                k++
            }
            if k > ans {
                ans = k
            }
        }
    }
    return ans
}

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