Задача: 592. Fraction Addition and Subtraction
Сложность: medium

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

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

Пример:

Input: expression = "-1/2+1/2+1/3"
Output: "1/3"

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

1⃣Начните сканирование строки и разделите её на части, содержащие числители и знаменатели, с учетом знаков.

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

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

😎 Решение:

class Solution {
    fun fractionAddition(expression: String): String {
        val sign = mutableListOf<Char>()
        if (expression[0] != '-') sign.add('+')
        for (char in expression) {
            if (char == '+' || char == '-') sign.add(char)
        }

        val fractions = expression.split(Regex("(?=[+-])"))
        var prevNum = 0
        var prevDen = 1
        var i = 0

        for (sub in fractions) {
            if (sub.isEmpty()) continue
            val (num, den) = sub.split('/').map { it.toInt() }
            val g = gcd(prevDen, den)
            if (sign[i] == '+') {
                prevNum = prevNum * den / g + num * prevDen / g
            } else {
                prevNum = prevNum * den / g - num * prevDen / g
            }
            prevDen = prevDen * den / g
            val gcdValue = gcd(Math.abs(prevNum), prevDen)
            prevNum /= gcdValue
            prevDen /= gcdValue
            i++
        }

        return "$prevNum/$prevDen"
    }

    private fun gcd(a: Int, b: Int): Int {
        return if (b == 0) a else gcd(b, a % b)
    }
}

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

Задача: 1196. How Many Apples Can You Put into the Basket
Сложность: easy

У вас есть несколько яблок и корзина, которая может выдержать до 5000 единиц веса.

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

Пример:

Input: weight = [100,200,150,1000]
Output: 4
Explanation: All 4 apples can be carried by the basket since their sum of weights is 1450.

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

1⃣Преобразование массива в мин-кучу:
Преобразуйте массив weight в мин-кучу, чтобы получить минимальные элементы первым.

2⃣Инициализация переменных:
Инициализируйте переменные apples для подсчета количества яблок и units для записи текущего веса корзины.

3⃣Добавление яблок в корзину:
Пока текущий вес корзины меньше 5000 единиц и в куче остаются элементы:
Увеличивайте apples на 1.
Увеличивайте units на значение, извлеченное из кучи.

😎 Решение:

class Solution {
    fun maxNumberOfApples(weight: IntArray): Int {
        val heap = PriorityQueue(weight.asList())
        var apples = 0
        var units = 0

        while (heap.isNotEmpty() && units + heap.peek() <= 5000) {
            units += heap.poll()
            apples++
        }
        return apples
    }
}

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

Задача: 524. Longest Word in Dictionary through Deleting
Сложность: medium

Даны строка s и массив строк dictionary. Верните самую длинную строку из dictionary, которую можно сформировать, удаляя некоторые символы из данной строки s. Если возможных результатов несколько, верните самое длинное слово с наименьшим лексикографическим порядком. Если возможного результата нет, верните пустую строку.

Пример:

Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
Output: "apple"

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

1⃣Инициализируйте переменную для хранения самой длинной строки, соответствующей критериям. Пройдите по каждой строке x в неотсортированном массиве dictionary и проверьте, является ли x подпоследовательностью строки s.

2⃣Если строка x является подпоследовательностью, сравните её с текущей самой длинной строкой по длине. Если длина x больше или равна длине текущей самой длинной строки и она меньше текущей строки в лексикографическом порядке (если равны по длине), обновите текущую самую длинную строку.

3⃣После рассмотрения всех строк в dictionary, верните найденную строку. Если ни одна строка не подошла, верните пустую строку.

😎 Решение:

class Solution {
    fun isSubsequence(x: String, y: String): Boolean {
        var j = 0
        for (i in y.indices) {
            if (j < x.length && x[j] == y[i]) {
                j++
            }
        }
        return j == x.length
    }

    fun findLongestWord(s: String, d: List<String>): String {
        var maxStr = ""
        for (str in d) {
            if (isSubsequence(str, s)) {
                if (str.length > maxStr.length || (str.length == maxStr.length && str < maxStr)) {
                    maxStr = str
                }
            }
        }
        return maxStr
    }
}

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

Задача: 753. Cracking the Safe
Сложность: medium

Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно.
После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода.

Пример:

Input: n = 1, k = 2
Output: "10"

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

1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1].

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

3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры.

😎 Решение:

fun crackSafe(n: Int, k: Int): String {
    val seen = mutableSetOf<String>()
    val result = StringBuilder()

    fun dfs(node: String) {
        for (x in 0 until k) {
            val neighbor = node + x
            if (!seen.contains(neighbor)) {
                seen.add(neighbor)
                dfs(neighbor.drop(1))
                result.append(x)
            }
        }
    }

    val startNode = "0".repeat(n - 1)
    dfs(startNode)

    result.append(startNode)
    return result.toString()
}

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

Задача: 287. Find the Duplicate Number
Сложность: medium

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

Пример:

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

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

1⃣Определение дубликата:
Итерируйте по массиву, оценивая каждый элемент (назовем его cur). Используйте абсолютное значение текущего элемента, чтобы получить индекс.
Если элемент по индексу cur отрицательный, значит, мы уже встречали этот элемент ранее, и cur является дубликатом. Сохраните cur как дубликат и выйдите из цикла.
Если элемент по индексу cur положительный, инвертируйте знак этого элемента, чтобы пометить его как встреченный, и перейдите к следующему элементу.

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

3⃣Возврат результата:
Верните найденный дубликат.

😎 Решение:

class Solution {
    fun findDuplicate(nums: IntArray): Int {
        var duplicate = -1
        for (i in nums.indices) {
            val cur = Math.abs(nums[i])
            if (nums[cur] < 0) {
                duplicate = cur
                break
            }
            nums[cur] = -nums[cur]
        }
        for (i in nums.indices) {
            nums[i] = Math.abs(nums[i])
        }
        return duplicate
    }
}

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

Задача: 378. Kth Smallest Element in a Sorted Matrix
Сложность: medium

Дана матрица размером n x n, где каждая строка и каждый столбец отсортированы в порядке возрастания. Верните k-й наименьший элемент в матрице.

Заметьте, что это k-й наименьший элемент в отсортированном порядке, а не k-й уникальный элемент.

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

Пример:

Input: matrix = [[-5]], k = 1
Output: -5

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

1⃣Инициализировать мин-кучу H. В нашем решении мы будем рассматривать каждую строку как отдельный список. Поскольку столбцы также отсортированы, мы можем рассматривать каждый столбец как отдельный список.

2⃣Взять первые элементы из min(N, K) строк, где N представляет количество строк, и добавить каждый из этих элементов в кучу. Важно знать, к какой строке и столбцу принадлежит элемент, чтобы в дальнейшем перемещаться по соответствующему списку.

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

😎 Решение:

import java.util.PriorityQueue

data class MyHeapNode(val value: Int, val row: Int, val column: Int) : Comparable<MyHeapNode> {
    override fun compareTo(other: MyHeapNode): Int {
        return value - other.value
    }
}

class Solution {
    fun kthSmallest(matrix: Array<IntArray>, k: Int): Int {
        val N = matrix.size
        val minHeap = PriorityQueue<MyHeapNode>()

        for (r in 0 until minOf(N, k)) {
            minHeap.offer(MyHeapNode(matrix[r][0], r, 0))
        }

        var element: MyHeapNode = minHeap.peek()
        var k = k
        while (k > 0) {
            element = minHeap.poll()
            val r = element.row
            val c = element.column

            if (c < N - 1) {
                minHeap.offer(MyHeapNode(matrix[r][c + 1], r, c + 1))
            }
            k -= 1
        }

        return element.value
    }
}

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

Задача: 1315. Sum of Nodes with Even-Valued Grandparent
Сложность: medium

Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0.

A grandparent of a node is the parent of its parent if it exists.

Пример:

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.

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

1⃣Определите метод solve(), который принимает TreeNode root, значение родителя parent и значение бабушки или дедушки gParent. Этот метод возвращает сумму значений узлов с четным значением бабушки и дедушки в поддереве узла root. Если root равен null, верните 0 как сумму.

2⃣Рекурсивно пройдите по левому и правому дочерним узлам, передавая в качестве значения parent root, а в качестве значения gParent parent. Если значение gParent четное, добавьте значение root к ответу.

3⃣Вызовите рекурсивную функцию solve() с корневым узлом и значениями -1 для parent и gParent. Верните сумму для левого и правого дочерних узлов и значение для текущего узла.

😎 Решение:

class Solution {
    private fun solve(root: TreeNode?, parent: Int, gParent: Int): Int {
        if (root == null) {
            return 0
        }
        return solve(root.left, root.`val`, parent) + solve(root.right, root.`val`, parent) + if (gParent % 2 == 0) root.`val` else 0
    }

    fun sumEvenGrandparent(root: TreeNode?): Int {
        return solve(root, -1, -1)
    }
}

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

Задача: 1245. Tree Diameter
Сложность: medium

Диаметр дерева - это количество ребер в самом длинном пути в этом дереве. Имеется неориентированное дерево из n узлов, помеченных от 0 до n - 1. Вам дан двумерный массив edges, где edges.length == n - 1 и edges[i] = [ai, bi] означает, что между узлами ai и bi в дереве есть неориентированное ребро. Верните диаметр дерева.

Пример:

Input: edges = [[0,1],[0,2]]
Output: 2

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

1⃣Построение графа:
Используем представление графа в виде списка смежности.

2⃣Поиск самой удаленной вершины (DFS1):
Запускаем DFS от произвольной вершины (например, 0) для нахождения самой удаленной вершины от нее.

3⃣Поиск диаметра (DFS2):
Запускаем DFS от найденной на предыдущем шаге самой удаленной вершины и находим самую удаленную вершину от нее. Это расстояние и будет диаметром дерева.reset(playerId):
Устанавливаем счет игрока в 0.

😎 Решение:

class Solution {
    fun treeDiameter(edges: Array<IntArray>): Int {
        if (edges.isEmpty()) return 0

        val graph = mutableMapOf<Int, MutableList<Int>>()
        for (edge in edges) {
            graph.computeIfAbsent(edge[0]) { mutableListOf() }.add(edge[1])
            graph.computeIfAbsent(edge[1]) { mutableListOf() }.add(edge[0])
        }

        var farthestNode = 0

        fun dfs(node: Int, parent: Int): Int {
            var maxDepth = 0
            for (neighbor in graph[node]!!) {
                if (neighbor != parent) {
                    val depth = dfs(neighbor, node)
                    if (depth + 1 > maxDepth) {
                        maxDepth = depth + 1
                        farthestNode = neighbor
                    }
                }
            }
            return maxDepth
        }

        dfs(0, -1)
        val startNode = farthestNode

        dfs(startNode, -1)
        return dfs(farthestNode, -1)
    }
}

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

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

Числа Фибоначчи, обычно обозначаемые как F(n), образуют последовательность, называемую последовательностью Фибоначчи, так что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), для n > 1.
Дано n, вычислите F(n).

Пример:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

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

1⃣Проверка начального условия
Если N <= 1, вернуть N.

2⃣Инициализация переменных
Инициализируйте current значением 0. Инициализируйте prev1 значением 1, что будет представлять fib(N-1) при вычислении текущего значения. Инициализируйте prev2 значением 0, что будет представлять fib(N-2) при вычислении текущего значения.

3⃣Итерация и вычисление
Итерация от 2 до N включительно. На каждой итерации: установите current как сумму prev1 и prev2. Обновите prev2 значением prev1. Обновите prev1 значением current. Вернуть значение current после завершения итерации.

😎 Решение:

class Solution {
    fun fib(N: Int): Int {
        if (N <= 1) return N
        var current = 0
        var prev1 = 1
        var prev2 = 0

        for (i in 2..N) {
            current = prev1 + prev2
            prev2 = prev1
            prev1 = current
        }
        return current
    }
}

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

Задача: 163. Missing Ranges
Сложность: easy

Вам дан диапазон [lower, upper] и отсортированный массив уникальных целых чисел nums, где все элементы находятся в этом диапазоне.

Число x считается пропущенным, если оно находится в диапазоне [lower, upper] и его нет в массиве nums.

Верните кратчайший отсортированный список диапазонов, который точно покрывает все пропущенные числа. То есть ни один элемент из nums не включен в какой-либо из диапазонов, и каждое пропущенное число покрыто одним из диапазонов..

Пример:

Input: nums = [-1], lower = -1, upper = -1
Output: []
Explanation: There are no missing ranges since there are no missing numbers.

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

1⃣Инициализация и проверка начальных условий:
Создайте переменную n и инициализируйте её размером массива nums.
Создайте список missingRanges, который будет содержать решение задачи.
Если массив nums пуст, верните диапазон [lower, upper].
Проверьте, совпадает ли первый элемент массива с lower. Если lower < nums[0], добавьте в missingRanges диапазон [lower, nums[0] - 1].

2⃣Итерация по элементам массива:
Проитерируйте по всем элементам в nums с помощью цикла от i = 0 до n - 2 (до предпоследнего элемента):
Если текущий элемент nums[i] и следующий элемент nums[i + 1] отличаются на 1 или меньше, между этими двумя числами нет пропущенных чисел.
В противном случае, если nums[i + 1] - nums[i] > 1, то пропущены числа от nums[i] + 1 до nums[i + 1] - 1 (включительно). В этом случае диапазон [nums[i] + 1, nums[i + 1] - 1] добавляется в missingRanges.

3⃣Проверка и добавление последнего пропущенного диапазона:
Проверьте, совпадает ли последний элемент массива с upper. Если nums[n - 1] < upper, добавьте в missingRanges диапазон [nums[n - 1] + 1, upper].

😎 Решение:

class Solution {
    fun findMissingRanges(nums: IntArray, lower: Int, upper: Int): List<List<Int>> {
        val n = nums.size
        val missingRanges = mutableListOf<List<Int>>()
        
        if (n == 0) {
            missingRanges.add(listOf(lower, upper))
            return missingRanges
        }
        if (lower < nums[0]) {
            missingRanges.add(listOf(lower, nums[0] - 1))
        }
        for (i in 0 until n - 1) {
            if (nums[i + 1] - nums[i] > 1) {
                missingRanges.add(listOf(nums[i] + 1, nums[i + 1] - 1))
            }
        }
        if (upper > nums[n - 1]) {
            missingRanges.add(listOf(nums[n - 1] + 1, upper))
        }
        
        return missingRanges
    }
}

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

Задача: 969. Pancake Sorting
Сложность: medium

Дан массив целых чисел arr, отсортируйте массив, выполняя серию переворотов блинов.

При одном перевороте блина мы выполняем следующие шаги:

Выбираем целое число k, где 1 <= k <= arr.length.
Переворачиваем подмассив arr[0...k-1] (индексация с 0).
Например, если arr = [3,2,1,4] и мы выполнили переворот блина, выбрав k = 3, мы переворачиваем подмассив [3,2,1], так что arr = [1,2,3,4] после переворота блина при k = 3.

Верните массив значений k, соответствующих последовательности переворотов блинов, которая сортирует arr. Любой допустимый ответ, который сортирует массив за количество переворотов не более чем 10 * arr.length, будет считаться правильным.

Пример:

Input: arr = [3,2,4,1]
Output: [4,2,4,3]
Explanation: 
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: arr = [3, 2, 4, 1]
After 1st flip (k = 4): arr = [1, 4, 2, 3]
After 2nd flip (k = 2): arr = [4, 1, 2, 3]
After 3rd flip (k = 4): arr = [3, 2, 1, 4]
After 4th flip (k = 3): arr = [1, 2, 3, 4], which is sorted.

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

1⃣Вдохновляясь пузырьковой сортировкой, начнем с реализации функции flip(list, k), которая выполняет переворот блина на префиксе list[0
] (в Python).

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

3⃣На каждом этапе определяем значение для сортировки (назовем его value_to_sort), которое является числом, которое мы будем ставить на место на этом этапе. Затем находим индекс value_to_sort. Если value_to_sort еще не на своем месте, выполняем максимум два переворота блинов, как объяснено в интуиции. В конце этапа value_to_sort будет на своем месте.

😎 Решение:

class Solution {
    fun pancakeSort(A: IntArray): List<Int> {
        val ans = mutableListOf<Int>()

        for (valueToSort in A.size downTo 1) {
            val index = find(A, valueToSort)
            if (index == valueToSort - 1) continue
            if (index != 0) {
                ans.add(index + 1)
                flip(A, index + 1)
            }
            ans.add(valueToSort)
            flip(A, valueToSort)
        }

        return ans
    }

    private fun flip(sublist: IntArray, k: Int) {
        var i = 0
        while (i < k / 2) {
            val temp = sublist[i]
            sublist[i] = sublist[k - i - 1]
            sublist[k - i - 1] = temp
            i++
        }
    }

    private fun find(a: IntArray, target: Int): Int {
        for (i in a.indices) {
            if (a[i] == target) {
                return i
            }
        }
        return -1
    }
}

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

Задача: 1063. Number of Valid Subarrays
Сложность: hard

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

Подмассив — это непрерывная часть массива.

Пример:

Input: nums = [1,4,2,5,3]
Output: 11
Explanation: There are 11 valid subarrays: [1],[4],[2],[5],[3],[1,4],[2,5],[1,4,2],[2,5,3],[1,4,2,5],[1,4,2,5,3].

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

1⃣нициализируйте переменную ans значением 0. Инициализируйте пустой стек st, который будет хранить индексы элементов в стеке.

2⃣Итерируйте по элементам массива nums для каждого индекса i: продолжайте извлекать элементы из стека st, пока стек не станет пустым или элемент nums[i] не станет больше элемента на вершине стека. Для каждого извлеченного элемента добавляйте количество подмассивов как i - st.top(). Поместите текущий индекс i в стек.

3⃣Извлеките все оставшиеся элементы из стека и для каждого рассмотрите размер nums как индекс следующего меньшего элемента. Соответственно, добавьте nums.size() - st.top() к переменной ans. Верните ans.

😎 Решение:

class Solution {
    fun validSubarrays(nums: IntArray): Int {
        var ans = 0
        val st = mutableListOf<Int>()
        
        for (i in nums.indices) {
            while (st.isNotEmpty() && nums[i] < nums[st.last()]) {
                ans += (i - st.removeAt(st.size - 1))
            }
            st.add(i)
        }
        
        while (st.isNotEmpty()) {
            ans += (nums.size - st.removeAt(st.size - 1))
        }
        
        return ans
    }
}

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

Задача: 670. Maximum Swap
Сложность: medium

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

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

Пример:

Input: num = 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.

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

1⃣Сохраняем кандидатов как списки длины len(num). Для каждой пары позиций (i, j) выполняем обмен цифр, записываем кандидата, если он больше текущего ответа, затем возвращаем цифры обратно.

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

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

😎 Решение:

class Solution {
    fun maximumSwap(num: Int): Int {
        val A = num.toString().toCharArray()
        var ans = A.copyOf()
        for (i in A.indices) {
            for (j in i + 1 until A.size) {
                val tmp = A[i]
                A[i] = A[j]
                A[j] = tmp
                for (k in A.indices) {
                    if (A[k] != ans[k]) {
                        if (A[k] > ans[k]) {
                            ans = A.copyOf()
                        }
                        break
                    }
                }
                A[j] = A[i]
                A[i] = tmp
            }
        }
        return String(ans).toInt()
    }
}

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

Задача: 660. Remove 9
Сложность: hard

Начните с целого числа 1, уберите любое число, которое содержит 9, такое как 9, 19, 29...

Теперь у вас будет новая последовательность целых чисел [1, 2, 3, 4, 5, 6, 7, 8, 10, 11, ...].

Дано целое число n, верните n-е (начиная с 1) целое число в новой последовательности.

Пример:

Input: n = 9
Output: 10

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

1⃣Инициализация:
Начните с числа 1 и создайте переменную для отслеживания количества найденных чисел, не содержащих цифру 9.

2⃣Итерация и проверка:
Последовательно увеличивайте число и проверяйте, содержит ли оно цифру 9.
Если не содержит, увеличьте счетчик.

3⃣Поиск n-го числа:
Продолжайте процесс до тех пор, пока не найдете n-е число, не содержащее цифру 9.

😎 Решение:

class Solution {
    fun newInteger(n: Int): Int {
        var count = 0
        var num = 0
        while (count < n) {
            num++
            if (!num.toString().contains('9')) {
                count++
            }
        }
        return num
    }
}

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

Задача: 892. Surface Area of 3D Shapes
Сложность: easy

Вам дана сетка n x n, на которой вы разместили несколько кубиков 1 x 1 x 1. Каждое значение v = grid[i][j] представляет собой башню из v кубиков, размещенных на вершине ячейки (i, j). После размещения кубиков вы решили склеить все непосредственно прилегающие кубики друг с другом, образовав несколько неправильных 3D-фигур. Верните общую площадь поверхности получившихся фигур. Примечание: нижняя грань каждой фигуры учитывается в площади ее поверхности.

Пример:

Input: grid = [[1,2],[3,4]]
Output: 34

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

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

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

3⃣Просуммировать все значения площадей для получения итоговой площади поверхности.

😎 Решение:

fun surfaceArea(grid: Array<IntArray>): Int {
    val n = grid.size
    var area = 0
    for (i in 0 until n) {
        for (j in 0 until n) {
            if (grid[i][j] > 0) {
                area += (grid[i][j] * 4) + 2
            }
            if (i > 0) {
                area -= minOf(grid[i][j], grid[i-1][j]) * 2
            }
            if (j > 0) {
                area -= minOf(grid[i][j], grid[i][j-1]) * 2
            }
        }
    }
    return area

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

Задача: 62. Unique Paths
Сложность: medium

На сетке размером m на n находится робот. Изначально робот расположен в верхнем левом углу (то есть, в клетке grid[0][0]). Робот пытается добраться до нижнего правого угла (то есть, в клетку grid[m - 1][n - 1]). Робот может двигаться только вниз или вправо в любой момент времени.

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

Тестовые случаи сгенерированы таким образом, что ответ будет меньше или равен 2 * 10^9.

Пример:

Input: m = 3, n = 7
Output: 28

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

1⃣Инициализировать двумерный массив d[m][n] = количество путей. Сначала установить количество путей равным 1 для первой строки и первого столбца. Для упрощения можно инициализировать весь двумерный массив единицами.

2⃣Проитерировать по всем "внутренним" ячейкам: d[col][row] = d[col - 1][row] + d[col][row - 1].

3⃣Вернуть d[m - 1][n - 1].

😎 Решение:

class Solution {
    fun uniquePaths(m: Int, n: Int): Int {
        if (m == 1 || n == 1) {
            return 1
        }

        return uniquePaths(m - 1, n) + uniquePaths(m, n - 1)
    }
}

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

Задача: 1190. Reverse Substrings Between Each Pair of Parentheses
Сложность: medium

Дана строка s, состоящая из строчных букв английского алфавита и скобок.

Переверните строки в каждой паре соответствующих скобок, начиная с самой внутренней.

Ваш результат не должен содержать скобок.

Пример:

Input: s = "(abcd)"
Output: "dcba"

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

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

2⃣Для каждого символа currentChar во входной строке:

Если это '(', добавьте длину строки result в openParenthesesIndices, чтобы отметить потенциальную начальную точку разворота.
Если это ')', извлеките значение из openParenthesesIndices и переверните result от извлеченного индекса для выполнения необходимого разворота.
В противном случае добавьте currentChar к result для построения строки.

3⃣Верните result как окончательную строку со всеми примененными разворотами.

😎 Решение:

class Solution {
    fun reverseParentheses(s: String): String {
        val openParenthesesIndices = mutableListOf<Int>()
        val result = StringBuilder()

        for (char in s) {
            when (char) {
                '(' -> openParenthesesIndices.add(result.length)
                ')' -> {
                    val start = openParenthesesIndices.removeAt(openParenthesesIndices.size - 1)
                    reverse(result, start, result.length - 1)
                }
                else -> result.append(char)
            }
        }

        return result.toString()
    }

    private fun reverse(sb: StringBuilder, start: Int, end: Int) {
        var start = start
        var end = end
        while (start < end) {
            val temp = sb[start]
            sb.setCharAt(start++, sb[end])
            sb.setCharAt(end--, temp)
        }
    }
}

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

Задача: 762. Prime Number of Set Bits in Binary Representation
Сложность: hard

Если даны два целых числа left и right, верните количество чисел в диапазоне [left, right], имеющих простое число битов в двоичном представлении. Напомним, что число битов в двоичном представлении - это количество единиц, присутствующих в числе 1. Например, 21 в двоичном представлении - это 10101, которое имеет 3 бита.

Пример:

Input: left = 10, right = 15
Output: 5

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

1⃣Создайте функцию для подсчета количества единиц в двоичном представлении числа.

2⃣Создайте функцию для проверки, является ли число простым.

3⃣Пройдите через все числа в диапазоне [left, right] и подсчитайте числа, у которых количество битов в двоичном представлении является простым числом.

😎 Решение:

fun countPrimeSetBits(left: Int, right: Int): Int {
    fun countBits(x: Int): Int {
        return x.toString(2).count { it == '1' }
    }
    
    fun isPrime(x: Int): Boolean {
        if (x < 2) return false
        for (i in 2..Math.sqrt(x.toDouble()).toInt()) {
            if (x % i == 0) return false
        }
        return true
    }
    
    var count = 0
    for (num in left..right) {
        if (isPrime(countBits(num))) {
            count++
        }
    }
    return count
}

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

Задача: 119. Pascal's Triangle ll
Сложность: easy

Для данного целого числа rowIndex верните rowIndex-ю строку (с индексацией с нуля) треугольника Паскаля.

Пример:

Input: rowIndex = 3
Output: [1,3,3,1]

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

1⃣Давайте представим, что у нас есть функция getNum(rowIndex, colIndex), которая дает нам число с индексом colIndex в строке с индексом rowIndex. Мы могли бы просто построить k-ю строку, повторно вызывая getNum(...) для столбцов от 0 до k.

2⃣Мы можем сформулировать нашу интуицию в следующую рекурсию: getNum(rowIndex, colIndex) = getNum(rowIndex - 1, colIndex - 1) + getNum(rowIndex - 1, colIndex)

3⃣Рекурсия заканчивается в некоторых известных базовых случаях: Первая строка - это просто одинокая 1, то есть getNum(0, ...) = 1. Первое и последнее число каждой строки равно 1, то есть getNum(k, 0) = getNum(k, k) = 1

😎 Решение:

class Solution {
    fun getNum(row: Int, col: Int): Int {
        if (row == 0 || col == 0 || row == col) {
            return 1
        }
        return getNum(row - 1, col - 1) + getNum(row - 1, col)
    }

    fun getRow(rowIndex: Int): List<Int> {
        val ans = mutableListOf<Int>()
        for (i in 0..rowIndex) {
            ans.add(getNum(rowIndex, i))
        }
        return ans
    }
}

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

Задача: 167. Two Sum II - Input Array Is Sorted
Сложность: medium

Дан массив целых чисел numbers, индексированный с 1, который уже отсортирован в неубывающем порядке. Найдите два числа так, чтобы их сумма составляла заданное целевое число. Пусть эти два числа будут numbers[index1] и numbers[index2], где 1 <= index1 < index2 <= numbers.length.

Верните индексы этих двух чисел, index1 и index2, увеличенные на один, в виде массива из двух элементов [index1, index2].

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

Ваше решение должно использовать только константное дополнительное пространство.

Пример:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

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

1⃣Инициализация указателей:
Используйте два указателя: один (left) начинается с начала массива, а другой (right) - с конца.

2⃣Поиск решения:
Сравните сумму элементов, на которые указывают left и right, с целевым значением target.
Если сумма равна target, верните индексы этих элементов как решение.
Если сумма меньше target, увеличьте left (так как массив отсортирован и увеличение left увеличивает сумму).
Если сумма больше target, уменьшите right (чтобы уменьшить сумму).

3⃣Продолжение до нахождения решения:
Перемещайте указатели left и right, повторяя сравнение, пока не будет найдено решение.
Учитывая, что задача гарантирует существование ровно одного решения, этот метод всегда найдет ответ.

😎 Решение:

class Solution {
    fun twoSum(numbers: IntArray, target: Int): IntArray {
        var low = 0
        var high = numbers.size - 1
        while (low < high) {
            val sum = numbers[low] + numbers[high]
            if (sum == target) {
                return intArrayOf(low + 1, high + 1)
            } else if (sum < target) {
                low++
            } else {
                high--
            }
        }
        return intArrayOf(-1, -1)
    }

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

Задача: 1351. Count Negative Numbers in a Sorted Matrix
Сложность: easy

Дана матрица m x n grid, которая отсортирована по убыванию как по строкам, так и по столбцам. Вернуть количество отрицательных чисел в grid.

Пример:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.

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

1⃣Инициализировать переменную count = 0 для подсчета общего числа отрицательных элементов в матрице.

2⃣Использовать два вложенных цикла для итерации по каждому элементу матрицы grid, и если элемент отрицательный, увеличить count на 1.

3⃣Вернуть count.

😎 Решение:

class Solution {
    fun countNegatives(grid: Array<IntArray>): Int {
        var count = 0
        for (row in grid) {
            for (element in row) {
                if (element < 0) {
                    count++
                }
            }
        }
        return count
    }
}

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