Задача: 109. Convert Sorted List to Binary Search Tree
Сложность: medium

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

Пример:

Input: head = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.

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

1⃣Поскольку нам дан односвязный список, а не массив, у нас нет прямого доступа к элементам списка по индексам. Нам нужно определить средний элемент односвязного списка. Мы можем использовать подход с двумя указателями для нахождения среднего элемента списка. В основном, у нас есть два указателя: slow_ptr и fast_ptr. slow_ptr перемещается на один узел за раз, тогда как fast_ptr перемещается на два узла за раз. К тому времени, как fast_ptr достигнет конца списка, slow_ptr окажется в середине списка. Для списка с четным количеством элементов любой из двух средних элементов может стать корнем BST.

2⃣Как только мы находим средний элемент списка, мы отсоединяем часть списка слева от среднего элемента. Мы делаем это, сохраняя prev_ptr, который указывает на узел перед slow_ptr, т.е. prev_ptr.next = slow_ptr. Для отсоединения левой части мы просто делаем prev_ptr.next = None.

3⃣Для создания сбалансированного по высоте BST нам нужно передать только голову связанного списка в функцию, которая преобразует его в BST. Таким образом, мы рекурсивно работаем с левой половиной списка, передавая оригинальную голову списка, и с правой половиной, передавая slow_ptr.next в качестве головы.

😎 Решение:

class Solution {
    fun findMiddle(head: ListNode?): ListNode? {
        var prevPtr: ListNode? = null
        var slowPtr = head
        var fastPtr = head
        while (fastPtr?.next != null) {
            prevPtr = slowPtr
            slowPtr = slowPtr?.next
            fastPtr = fastPtr.next?.next
        }
        if (prevPtr != null) {
            prevPtr.next = null
        }
        return slowPtr
    }

    fun sortedListToBST(head: ListNode?): TreeNode? {
        if (head == null) {
            return null
        }
        val mid = findMiddle(head)
        if (mid == null) {
            return null
        }
        val node = TreeNode(mid.`val`)
        if (head === mid) {
            return node
        }
        node.left = sortedListToBST(head)
        node.right = sortedListToBST(mid.next)
        return node
    }
}

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

Задача: 1463. Cherry Pickup II
Сложность: hard

Дана матрица grid размером rows x cols, представляющая поле с вишнями, где grid[i][j] обозначает количество вишен, которые можно собрать с клетки (i, j).

У вас есть два робота, которые могут собирать вишни:
Робот №1 находится в левом верхнем углу (0, 0), а
Робот №2 находится в правом верхнем углу (0, cols - 1).

Верните максимальное количество собранных вишен с помощью обоих роботов, следуя приведённым ниже правилам:
Из клетки (i, j) роботы могут перемещаться в клетку (i + 1, j - 1), (i + 1, j) или (i + 1, j + 1).
Когда любой робот проходит через клетку, он подбирает все вишни, и клетка становится пустой.
Когда оба робота находятся в одной клетке, только один из них собирает вишни.
Оба робота не могут выходить за пределы матрицы в любой момент времени.
Оба робота должны достичь нижней строки в матрице grid.

Пример:

Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
Output: 28
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.

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

1⃣Определите трехмерный массив dp, где dp[row][col1][col2] представляет максимальное количество вишен, которые можно собрать, если робот 1 находится в (row, col1), а робот 2 находится в (row, col2).

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

3⃣Верните dp[0][0][n-1], что представляет максимальное количество вишен, которое можно собрать, начиная с верхнего левого и верхнего правого углов.

😎 Решение:

class Solution {
    fun cherryPickup(grid: Array<IntArray>): Int {
        val m = grid.size
        val n = grid[0].size
        val dp = Array(m) { Array(n) { IntArray(n) } }
        
        for (row in m - 1 downTo 0) {
            for (col1 in 0 until n) {
                for (col2 in 0 until n) {
                    var result = grid[row][col1]
                    if (col1 != col2) {
                        result += grid[row][col2]
                    }
                    if (row != m - 1) {
                        var maxCherries = 0
                        for (newCol1 in col1 - 1..col1 + 1) {
                            for (newCol2 in col2 - 1..col2 + 1) {
                                if (newCol1 in 0 until n && newCol2 in 0 until n) {
                                    maxCherries = maxOf(maxCherries, dp[row + 1][newCol1][newCol2])
                                }
                            }
                        }
                        result += maxCherries
                    }
                    dp[row][col1][col2] = result
                }
            }
        }
        return dp[0][0][n - 1]
    }
}

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

Задача: 366. Find Leaves of Binary Tree
Сложность: medium

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

Пример:

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⃣Организовать узлы по высоте и вернуть результат.

😎 Решение:

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    private val pairs = mutableListOf<Pair<Int, Int>>()

    private fun getHeight(node: TreeNode?): Int {
        if (node == null) return -1
        val leftHeight = getHeight(node.left)
        val rightHeight = getHeight(node.right)
        val currHeight = maxOf(leftHeight, rightHeight) + 1
        pairs.add(Pair(currHeight, node.`val`))
        return currHeight
    }

    fun findLeaves(root: TreeNode?): List<List<Int>> {
        getHeight(root)
        pairs.sortBy { it.first }
        val solution = mutableListOf<List<Int>>()
        var currentHeight = -1
        pairs.forEach { (height, value) ->
            if (height != currentHeight) {
                solution.add(mutableListOf())
                currentHeight = height
            }
            (solution.last() as MutableList).add(value)
        }
        return solution
    }
}

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

Задача: 69. Sqrt(x)
Сложность: easy

Дано неотрицательное целое число x. Верните квадратный корень из x, округлённый вниз до ближайшего целого числа. Возвращаемое целое число также должно быть неотрицательным.

Вы не должны использовать встроенные функции или операторы для возведения в степень.

Например, не следует использовать pow(x, 0.5) в C++ или x ** 0.5 в Python.

Пример:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

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

1⃣Если x < 2, верните x. Установите левую границу left = 2 и правую границу right = x / 2.

2⃣Пока left ≤ right:
Возьмите num = (left + right) / 2 в качестве предположения. Вычислите num × num и сравните его с x:
Если num × num > x, переместите правую границу right = pivot − 1.
В противном случае, если num × num < x, переместите левую границу left = pivot + 1.
В противном случае num × num == x, целочисленный квадратный корень найден, давайте вернем его.

3⃣Верните right.

😎 Решение:

class Solution {
    fun mySqrt(x: Int): Int {
        if (x < 2) return x

        var left = 2
        var right = x / 2

        while (left <= right) {
            val pivot = left + (right - left) / 2
            val num = pivot * pivot
            when {
                num > x -> right = pivot - 1
                num < x -> left = pivot + 1
                else -> return pivot
            }
        }
        return right
    }
}

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

Задача: 478. Generate Random Point in a Circle
Сложность: Medium

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

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

- Solution(double radius, double x_center, double y_center) инициализирует объект с радиусом окружности radius и положением центра (x_center, y_center).
- randPoint() возвращает случайную точку внутри окружности. Точка на окружности считается находящейся внутри окружности. Ответ возвращается в виде массива [x, y].

Пример:

Input
["Solution", "randPoint", "randPoint", "randPoint"]
[[1.0, 0.0, 0.0], [], [], []]
Output
[null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]]

Explanation
Solution solution = new Solution(1.0, 0.0, 0.0);
solution.randPoint(); // return [-0.02493, -0.38077]
solution.randPoint(); // return [0.82314, 0.38945]
solution.randPoint(); // return [0.36572, 0.17248]

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

1⃣ Генерируем равномерно случайные точки в квадрате S с длиной стороны 2R.

2⃣ Сохраняем все точки, которые находятся на расстоянии не более R от центра, и отклоняем все, которые дальше этого расстояния.

3⃣ Повторяем процесс до получения нужного количества точек, учитывая, что примерно 78.5% от всех сгенерированных точек будут приемлемыми, и ожидаемое число попыток до получения приемлемой точки составляет примерно 1.274 раза.

😎 Решение:

import kotlin.math.pow
import kotlin.math.sqrt
import kotlin.random.Random

class Solution(private val rad: Double, private val xc: Double, private val yc: Double) {

    fun randPoint(): DoubleArray {
        val x0 = xc - rad
        val y0 = yc - rad

        while (true) {
            val xg = x0 + Random.nextDouble() * rad * 2
            val yg = y0 + Random.nextDouble() * rad * 2
            if (sqrt((xg - xc).pow(2) + (yg - yc).pow(2)) <= rad) {
                return doubleArrayOf(xg, yg)
            }
        }
    }
}

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

Задача: 24. Swap Nodes in Pairs
Сложность: medium

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

Пример:

Input: head = [1,2,3,4]  
Output: [2,1,4,3]  

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

1⃣ Создаем фиктивный узел dummy, который будет указывать на новый измененный список.

2⃣ Используем указатели cur, A и B, чтобы менять местами каждые два соседних узла.

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

😎 Решение:

class Solution {
  fun swapPairs(head: ListNode?): ListNode? {
    val dummy = ListNode(-1)
    var cur: ListNode? = dummy
    var head = head
    while (head?.next != null) {
      val A = head
      val B = head.next
      head = B?.next
      B?.next = A
      A.next = head
      cur?.next = B
      cur = A
    }
    cur?.next = head
    return dummy.next
  }
}

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

Задача: 130. Surrounded Regions
Сложность: Medium

Вам дана матрица размером m на n, которая содержит буквы 'X' и 'O'. Захватите регионы, которые окружены:

Соединение: Ячейка соединена с соседними ячейками по горизонтали или вертикали.
Регион: Для формирования региона соедините каждую ячейку 'O'.
Окружение: Регион окружён ячейками 'X', если можно соединить регион с ячейками 'X', и ни одна из ячеек региона не находится на краю доски.
Окруженный регион захватывается путём замены всех 'O' на 'X' в исходной матрице.

Пример:

Input: board = [["X"]]

Output: [["X"]]

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

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

2⃣Если ячейка на границе оказывается 'O', это означает, что эта ячейка "жива", вместе с другими ячейками 'O', соединёнными с этой граничной ячейкой. Две ячейки считаются соединёнными, если между ними существует путь, состоящий только из букв 'O'.
Цель нашего обхода DFS будет заключаться в том, чтобы отметить все такие связанные ячейки 'O', которые исходят из границы, каким-либо отличительным символом, например, 'E'.

3⃣После обхода всех граничных ячеек мы получаем три типа ячеек:
Ячейки с буквой 'X': эти ячейки можно считать стеной.
Ячейки с буквой 'O': эти ячейки не затрагиваются в нашем обходе DFS, то есть они не имеют соединения с границей, следовательно, они захвачены. Эти ячейки следует заменить на букву 'X'.
Ячейки с буквой 'E': это ячейки, отмеченные в ходе нашего обхода DFS, то есть ячейки, имеющие хотя бы одно соединение с границами, следовательно, они не захвачены. В результате мы должны вернуть этим ячейкам их исходную букву 'O'.

😎 Решение:

class Solution {
    private var rows: Int = 0
    private var cols: Int = 0

    fun solve(board: Array<Array<Char>>) {
        if (board.isEmpty() || board[0].isEmpty()) return

        rows = board.size
        cols = board[0].size

        val borders = mutableListOf<Pair<Int, Int>>()
        for (i in 0 until rows) {
            borders.add(Pair(i, 0))
            borders.add(Pair(i, cols - 1))
        }
        for (j in 0 until cols) {
            borders.add(Pair(0, j))
            borders.add(Pair(rows - 1, j))
        }

        for ((row, col) in borders) {
            dfs(board, row, col)
        }

        for (r in 0 until rows) {
            for (c in 0 until cols) {
                when (board[r][c]) {
                    'O' -> board[r][c] = 'X'
                    'E' -> board[r][c] = 'O'
                }
            }
        }
    }

    private fun dfs(board: Array<Array<Char>>, row: Int, col: Int) {
        if (board[row][col] != 'O') return
        board[row][col] = 'E'
        if (col < cols - 1) dfs(board, row, col + 1)
        if (row < rows - 1) dfs(board, row + 1, col)
        if (col > 0) dfs(board, row, col - 1)
        if (row > 0) dfs(board, row - 1, col)
    }
}

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

Задача: 604. Design Compressed String Iterator
Сложность: easy

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

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

- next(): Возвращает следующий символ, если в оригинальной строке еще остались несжатые символы, в противном случае возвращает пробел.
- hasNext(): Возвращает true, если в оригинальной строке остались символы, которые нужно распаковать, в противном случае возвращает false.

Пример:

Input
["StringIterator", "next", "next", "next", "next", "next", "next", "hasNext", "next", "hasNext"]
[["L1e2t1C1o1d1e1"], [], [], [], [], [], [], [], [], []]
Output
[null, "L", "e", "e", "t", "C", "o", true, "d", true]

Explanation
StringIterator stringIterator = new StringIterator("L1e2t1C1o1d1e1");
stringIterator.next(); // return "L"
stringIterator.next(); // return "e"
stringIterator.next(); // return "e"
stringIterator.next(); // return "t"
stringIterator.next(); // return "C"
stringIterator.next(); // return "o"
stringIterator.hasNext(); // return True
stringIterator.next(); // return "d"
stringIterator.hasNext(); // return True

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

1⃣Предварительная обработка
Мы заранее создаем несжатую строку. Для этого проходим по данному сжатому строковому представлению и добавляем несжатые буквы для каждой сжатой буквы в результирующий строковый строитель res. Чтобы найти количество несжатых букв, мы проходим по данному сжатому строковому представлению. Когда находим букву, определяем следующее за ней число, используя десятичную арифметику. Таким образом, получаем два элемента (букву и количество), необходимые для формирования текущего фрагмента несжатой строки.

2⃣Операция next()
Начинаем с проверки, есть ли еще несжатые буквы в строке. Если нет, hasNext() возвращает False, а next() возвращает пробел (' '). В противном случае возвращаем букву, на которую указывает ptr, указывающий на следующую букву для возврата. Перед возвратом буквы также обновляем ptr, чтобы указывать на следующую букву в res.

3⃣Операция hasNext()
Если указатель ptr выходит за пределы массива res, это указывает на то, что больше несжатых букв нет. В этом случае возвращаем False. В противном случае возвращаем True.

😎 Решение:

class StringIterator(s: String) {
    private val res = StringBuilder()
    private var ptr = 0

    init {
        var i = 0
        while (i < s.length) {
            val ch = s[i++]
            var num = 0
            while (i < s.length && s[i].isDigit()) {
                num = num * 10 + (s[i] - '0')
                i++
            }
            repeat(num) {
                res.append(ch)
            }
        }
    }

    fun next(): Char {
        return if (!hasNext()) ' ' else res[ptr++]
    }

    fun hasNext(): Boolean {
        return ptr != res.length
    }
}

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

Задача: 343. Integer Break
Сложность: medium

Дано целое число n. Верните true, если оно является степенью числа четыре. В противном случае верните false.

Целое число n является степенью числа четыре, если существует целое число x такое, что n == 4^x.

Пример:

Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

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

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

2⃣Вычисление максимального произведения:
Для каждого числа i от 2 до n:
Для каждого числа j от 1 до i // 2:
Обновите dp[i] как максимальное значение между текущим dp[i], произведением j и i - j, и произведением j и dp[i - j].

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

😎 Решение:

class Solution {
    fun integerBreak(n: Int): Int {
        if (n <= 1) return 0
        
        val dp = IntArray(n + 1)
        
        for (i in 2..n) {
            for (j in 1..i / 2) {
                dp[i] = maxOf(dp[i], j * (i - j), j * dp[i - j])
            }
        }
        
        return dp[n]
    }
}

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

Задача: 1229. Meeting Scheduler
Сложность: medium

Даны массивы доступных временных слотов slots1 и slots2 для двух человек и продолжительность встречи duration, верните самый ранний временной слот, который подходит обоим и имеет продолжительность duration.

Если нет общего временного слота, который удовлетворяет требованиям, верните пустой массив.

Формат временного слота — это массив из двух элементов [start, end], представляющий инклюзивный временной диапазон от start до end.

Гарантируется, что никакие два доступных временных слота одного и того же человека не пересекаются друг с другом. То есть для любых двух временных слотов [start1, end1] и [start2, end2] одного и того же человека либо start1 > end2, либо start2 > end1.

Пример:

Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8
Output: [60,68]

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

1⃣Отсортируйте оба массива slots1 и slots2 по времени начала.

2⃣Инициализируйте два указателя, указывающие на начало slots1 и slots2 соответственно.

3⃣Перебирайте, пока указатель1 не достигнет конца slots1 или указатель2 не достигнет конца slots2:
Найдите общий слот между slots1[pointer1] и slots2[pointer2].
Если общий слот больше или равен duration, верните результат.
В противном случае найдите слот, который заканчивается раньше, и передвиньте указатель.
Если общий слот не найден, верните пустой массив.

😎 Решение:

class Solution {
    fun minAvailableDuration(slots1: Array<IntArray>, slots2: Array<IntArray>, duration: Int): List<Int> {
        slots1.sortBy { it[0] }
        slots2.sortBy { it[0] }
        
        var pointer1 = 0
        var pointer2 = 0
        
        while (pointer1 < slots1.size && pointer2 < slots2.size) {
            val intersectLeft = maxOf(slots1[pointer1][0], slots2[pointer2][0])
            val intersectRight = minOf(slots1[pointer1][1], slots2[pointer2][1])
            
            if (intersectRight - intersectLeft >= duration) {
                return listOf(intersectLeft, intersectLeft + duration)
            }
            
            if (slots1[pointer1][1] < slots2[pointer2][1]) {
                pointer1++
            } else {
                pointer2++
            }
        }
        return emptyList()
    }
}

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

Задача: 1338. Reduce Array Size to The Half
Сложность: medium

Дан массив целых чисел arr. Вы можете выбрать набор чисел и удалить все вхождения этих чисел из массива.

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

Пример:

Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has a size greater than half of the size of the old array.

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

1⃣Отсортировать массив и создать список подсчета количества вхождений каждого числа.

2⃣Отсортировать список подсчета в порядке убывания.

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

😎 Решение:

class Solution {
    fun minSetSize(arr: IntArray): Int {
        arr.sort()
        
        val counts = mutableListOf<Int>()
        var currentRun = 1
        for (i in 1 until arr.size) {
            if (arr[i] == arr[i - 1]) {
                currentRun += 1
                continue
            }
            counts.add(currentRun)
            currentRun = 1
        }
        counts.add(currentRun)
        
        counts.sortDescending()
        
        var numbersRemovedFromArr = 0
        var setSize = 0
        for (count in counts) {
            numbersRemovedFromArr += count
            setSize += 1   
            if (numbersRemovedFromArr >= arr.size / 2) {
                break
            }
        }
        
        return setSize
    }
}

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

Задача: 669. Trim a Binary Search Tree
Сложность: medium

Дано корневое дерево двоичного поиска и нижняя и верхняя границы как low и high. Обрежьте дерево так, чтобы все его элементы лежали в диапазоне [low, high]. Обрезка дерева не должна изменять относительную структуру элементов, которые останутся в дереве (то есть любой потомок узла должен оставаться потомком). Можно доказать, что существует единственный ответ.

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

Пример:

Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]

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

1⃣Если node.val > high, то обрезанное двоичное дерево должно находиться слева от узла.

2⃣Если node.val < low, то обрезанное двоичное дерево должно находиться справа от узла.

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

😎 Решение:

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Solution {
    fun trimBST(root: TreeNode?, low: Int, high: Int): TreeNode? {
        root ?: return null
        if (root.`val` > high) return trimBST(root.left, low, high)
        if (root.`val` < low) return trimBST(root.right, low, high)
        root.left = trimBST(root.left, low, high)
        root.right = trimBST(root.right, low, high)
        return root
    }
}

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

Задача: 1256. Encode Number
Сложность: medium

Даны список слов, список отдельных букв (могут повторяться) и оценка каждого символа. Верните максимальную оценку любого правильного набора слов, образованного с помощью заданных букв (words[i] не может быть использовано два или более раз). Не обязательно использовать все символы в буквах, каждая буква может быть использована только один раз. Оценка букв 'a', 'b', 'c', ... , 'z' задаются значениями score[0], score[1], ... , score[25] соответственно.

Пример:

Input: num = 23
Output: "1000"

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

1⃣На основе предоставленной таблицы можно выявить закономерность для преобразования целого числа n в строку f(n)

2⃣Из таблицы видно, что последовательность строк соответствует последовательности чисел в двоичной системе счисления за исключением начального значения n = 0.

3⃣Таким образом, можно вывести, что:
Для каждого значения n > 0, функция f(n) представляет собой двоичное представление числа (n - 1).

😎 Решение:

class Solution {
    fun encode(num: Int): String {
        if (num == 0) return ""
        return Integer.toBinaryString(num - 1)
    }
}

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

Задача: 23. Merge k Sorted Lists
Сложность: hard

Вам дан массив из k списков связанных списков, каждый связанный список отсортирован в порядке возрастания.
Объедините все связанные списки в один отсортированный связанный список и верните его.

Пример:

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

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

1⃣ Используем приоритетную очередь (PriorityQueue) для хранения узлов в порядке возрастания.

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

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

😎 Решение:

class Solution {
  fun mergeKLists(lists: Array<ListNode?>): ListNode? {
    val pq = PriorityQueue<ListNode>(compareBy { it.`val` })
    lists.filterNotNull().forEach { pq.add(it) }
    val res = ListNode(-1)
    var tail = res
    while (pq.isNotEmpty()) {
      val head = pq.poll()
      tail.next = head
      tail = tail.next!!
      head.next?.let { pq.add(it) }
    }
    return res.next
  }
}

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

Задача: 186. Reverse Words in a String II
Сложность: medium

Дан массив символов s, переверните порядок слов.

Слово определяется как последовательность символов, не являющихся пробелами. Слова в s будут разделены одним пробелом.

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

Пример:

Input: s = ["a"]
Output: ["a"]

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

1⃣Перевернуть всю строку: применить функцию reverse, которая переворачивает весь массив символов от начала до конца.

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

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

😎 Решение:

class Solution {
    fun reverseWords(s: CharArray) {
        s.reverse()
        var start = 0
        var end = 0
        val n = s.size

        while (start < n) {
            while (end < n && s[end] != ' ') {
                end++
            }
            s.sliceArray(start until end).reversed().copyInto(s, start)
            end++
            start = end
        }
    }
}

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

Задача: 1328. Break a Palindrome
Сложность: medium

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

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

Строка a лексикографически меньше строки b (одинаковой длины), если в первой позиции, где они отличаются, у строки a символ строго меньше соответствующего символа в строке b. Например, "abcc" лексикографически меньше "abcd", потому что первой различающейся позицией является четвертая, и 'c' меньше, чем 'd'.

Пример:

Input: palindrome = "abccba"
Output: "aaccba"
Explanation: There are many ways to make "abccba" not a palindrome, such as "zbccba", "aaccba", and "abacba".
Of all the ways, "aaccba" is the lexicographically smallest.

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

1⃣Если длина строки равна 1, верните пустую строку, так как невозможно создать непалиндромическую строку в этом случае.

2⃣Итерируйтесь по строке слева до середины строки: если символ не равен 'a', измените его на 'a' и верните строку.

3⃣Если вы прошли всю левую часть строки и все еще не получили непалиндромическую строку, это означает, что строка состоит только из 'a'. Следовательно, измените последний символ на 'b' и верните полученную строку.

😎 Решение:

class Solution {
    fun breakPalindrome(palindrome: String): String {
        val length = palindrome.length
        
        if (length == 1) {
            return ""
        }
        
        val palindromeArray = palindrome.toCharArray()
        for (i in 0 until length / 2) {
            if (palindromeArray[i] != 'a') {
                palindromeArray[i] = 'a'
                return String(palindromeArray)
            }
        }
        
        palindromeArray[length - 1] = 'b'
        return String(palindromeArray)
    }
}

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

Задача: 771. Jewels and Stones
Сложность: medium

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

Буквы чувствительны к регистру, поэтому "a" считается другим типом камня, чем "A".

Пример:

Input: jewels = "aA", stones = "aAAbbbb"
Output: 3

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

1⃣Создайте множество из строки jewels для быстрой проверки, является ли камень драгоценностью. Это позволит эффективно проверять принадлежность каждого камня к драгоценностям.

2⃣Инициализируйте счетчик для подсчета количества камней, которые являются драгоценностями. Пройдите по каждому символу в строке stones и проверьте, содержится ли этот символ в множестве jewels.

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

😎 Решение:

class Solution {
    fun numJewelsInStones(J: String, S: String): Int {
        var ans = 0
        for (s in S) {
            for (j in J) {
                if (j == s) {
                    ans++
                    break
                }
            }
        }
        return ans
    }
}

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

Задача: 1431. Kids With the Greatest Number of Candies
Сложность: easy

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

Вернуть булев массив result длиной n, где result[i] равно true, если, дав i-му ребенку все дополнительные конфеты, он будет иметь наибольшее количество конфет среди всех детей, или false в противном случае.

Обратите внимание, что несколько детей могут иметь наибольшее количество конфет.

Пример:

Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true] 
Explanation: If you give all extraCandies to:
- Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids.
- Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
- Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids.
- Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids.
- Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.

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

1⃣Найдите максимальное количество конфет в массиве candies, сохраняя его в переменной maxCandies.

2⃣Создайте булев список answer и пройдитесь по массиву candies, добавляя в answer значение true, если текущий ребенок с добавленными extraCandies имеет количество конфет больше или равное maxCandies, иначе добавляйте false.

3⃣Верните список answer.

😎 Решение:

class Solution {
    fun kidsWithCandies(candies: IntArray, extraCandies: Int): List<Boolean> {
        val maxCandies = candies.maxOrNull() ?: 0
        return candies.map { it + extraCandies >= maxCandies }
    }
}

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

class Solution {
    fun numBusesToDestination(routes: Array<IntArray>, source: Int, target: Int): Int {
        if (source == target) return 0
        
        val adjList = mutableMapOf<Int, MutableList<Int>>()
        for (route in routes.indices) {
            for (stop in routes[route]) {
                adjList.computeIfAbsent(stop) { mutableListOf() }.add(route)
            }
        }
        
        val q = ArrayDeque<Int>()
        val vis = mutableSetOf<Int>()
        adjList[source]?.forEach { route ->
            q.add(route)
            vis.add(route)
        }
        
        var busCount = 1
        while (q.isNotEmpty()) {
            repeat(q.size) {
                val route = q.removeFirst()
                for (stop in routes[route]) {
                    if (stop == target) return busCount
                    adjList[stop]?.forEach { nextRoute ->
                        if (!vis.contains(nextRoute)) {
                            vis.add(nextRoute)
                            q.add(nextRoute)
                        }
                    }
                }
            }
            busCount++
        }
        return -1
    }
}

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

Задача: 472. Concatenated Words
Сложность: hard

Дан массив строк words (без дубликатов). Верните все составные слова из данного списка слов.

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

Пример:

Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; 
"dogcatsdog" can be concatenated by "dog", "cats" and "dog"; 
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".

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

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

2⃣Использовать поиск в глубину (DFS) для проверки, можно ли достигнуть узел с индексом word.length от узла с индексом 0 в графе.

3⃣Если узел word.length достижим от узла 0, добавить слово в ответ.

😎 Решение:

class Solution {
    private fun dfs(word: String, length: Int, visited: BooleanArray, dictionary: Set<String>): Boolean {
        if (length == word.length) return true
        if (visited[length]) return false
        visited[length] = true
        for (i in word.length - if (length == 0) 1 else 0 downTo length + 1) {
            if (dictionary.contains(word.substring(length, i)) && dfs(word, i, visited, dictionary)) {
                return true
            }
        }
        return false
    }

    fun findAllConcatenatedWordsInADict(words: List<String>): List<String> {
        val dictionary = words.toSet()
        val answer = mutableListOf<String>()
        for (word in words) {
            val visited = BooleanArray(word.length)
            if (dfs(word, 0, visited, dictionary)) {
                answer.add(word)
            }
        }
        return answer
    }
}

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