Kotlin | LeetCode
Открыть в Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
Больше
Сеть:1 693
Подписчики
-124 часа
-27 дней
-1030 дней
Загружаем данные
Похожие каналы
Облако тегов
Входящие и исходящие упоминания
---
---
---
---
---
---
Привлечение подписчиков
октябрь '26окт. '26
октябрь '26
+4
в 0 каналах
сентябрь '26
+6
в 0 каналах
Get PRO
август '26
+4
в 0 каналах
Get PRO
июль '26
+12
в 0 каналах
Get PRO
июнь '26
+10
в 1 каналах
Get PRO
май '26
+8
в 0 каналах
Get PRO
апрель '26
+9
в 0 каналах
Get PRO
март '26
+18
в 0 каналах
Get PRO
февраль '26
+9
в 0 каналах
Get PRO
январь '26
+14
в 0 каналах
Get PRO
декабрь '25
+11
в 0 каналах
Get PRO
ноябрь '25
+42
в 0 каналах
Get PRO
октябрь '25
+41
в 0 каналах
Get PRO
сентябрь '25
+28
в 0 каналах
Get PRO
август '25
+43
в 0 каналах
Get PRO
июль '25
+44
в 1 каналах
Get PRO
июнь '25
+52
в 0 каналах
Get PRO
май '25
+62
в 0 каналах
Get PRO
апрель '25
+57
в 0 каналах
Get PRO
март '25
+93
в 1 каналах
Get PRO
февраль '25
+100
в 0 каналах
Get PRO
январь '25
+145
в 53 каналах
Get PRO
декабрь '24
+49
в 0 каналах
Get PRO
ноябрь '24
+70
в 0 каналах
Get PRO
октябрь '24
+193
в 12 каналах
Get PRO
сентябрь '24
+640
в 333 каналах
Get PRO
август '24
+90
в 0 каналах
Get PRO
июль '24
+424
в 219 каналах
Get PRO
июнь '24
+418
в 232 каналах
| Дата | Привлечение подписчиков | Упоминания | Каналы | |
| 26 октября | 0 | |||
| 25 октября | 0 | |||
| 24 октября | 0 | |||
| 23 октября | 0 | |||
| 22 октября | 0 | |||
| 21 октября | 0 | |||
| 20 октября | 0 | |||
| 19 октября | 0 | |||
| 18 октября | 0 | |||
| 17 октября | +1 | |||
| 16 октября | 0 | |||
| 15 октября | 0 | |||
| 14 октября | +1 | |||
| 13 октября | 0 | |||
| 12 октября | 0 | |||
| 11 октября | +1 | |||
| 10 октября | 0 | |||
| 09 октября | 0 | |||
| 08 октября | +1 | |||
| 07 октября | 0 | |||
| 06 октября | 0 | |||
| 05 октября | 0 | |||
| 04 октября | 0 | |||
| 03 октября | 0 | |||
| 02 октября | 0 | |||
| 01 октября | 0 |
Посты канала
Задача: 229. Majority Element II
Сложность: medium
Дан массив целых чисел размера n, найдите все элементы, которые встречаются более ⌊ n/3 ⌋ раз.
Пример:
Input: nums = [3,2,3] Output: [3]👨💻 Алгоритм: 1⃣Поиск кандидатов: Пройдите через массив, используя алгоритм Бойера-Мура для поиска двух потенциальных кандидатов, которые могут встречаться более ⌊ n/3 ⌋ раз. Поддерживайте два счётчика и двух кандидатов. Если текущий элемент равен одному из кандидатов, увеличьте соответствующий счётчик. Если счётчик равен нулю, установите текущий элемент как кандидата и установите счётчик в 1. Если текущий элемент не совпадает ни с одним из кандидатов, уменьшите оба счётчика. 2⃣Подсчёт голосов: После определения двух кандидатов, пройдите через массив снова, чтобы посчитать фактическое количество появлений каждого кандидата. 3⃣Проверка порога: Проверьте, превышает ли количество появлений каждого кандидата порог ⌊ n/3 ⌋. Если да, добавьте кандидата в результат. 😎 Решение:
class Solution {
fun majorityElement(nums: IntArray): List<Int> {
var count1 = 0
var count2 = 0
var candidate1: Int? = null
var candidate2: Int? = null
for (n in nums) {
if (candidate1 != null && candidate1 == n) {
count1++
} else if (candidate2 != null && candidate2 == n) {
count2++
} else if (count1 == 0) {
candidate1 = n
count1 = 1
} else if (count2 == 0) {
candidate2 = n
count2 = 1
} else {
count1--
count2--
}
}
count1 = 0
count2 = 0
for (n in nums) {
if (candidate1 != null && candidate1 == n) {
count1++
}
if (candidate2 != null && candidate2 == n) {
count2++
}
}
val result = mutableListOf<Int>()
val n = nums.size
if (count1 > n / 3) {
result.add(candidate1!!)
}
if (count2 > n / 3) {
result.add(candidate2!!)
}
return result
}
}| 2 |  🔥 Скрытые вакансии с удаленной работой для Android разработчика, которые нигде больше не публикуются. Напрямую от компаний, с контактами рекрутеров.
🔹 Android Jobs | Вакансии
🔹 Flutter Dart Jobs | Вакансии
🔹 iOS Jobs | Вакансии
🔸 Все каналы с вакансиями | 106 |
| 3 | Задача: 904. Fruit Into Baskets
Сложность: medium
Вы посещаете ферму, где в один ряд слева направо расположены фруктовые деревья. Деревья представлены целочисленным массивом fruits, где fruits[i] - это тип фрукта, который производит i-е дерево. Вы хотите собрать как можно больше фруктов. Однако у владельца есть строгие правила, которым вы должны следовать: у вас есть только две корзины, и каждая корзина может содержать только один тип фруктов. Количество фруктов в каждой корзине не ограничено. Начиная с любого дерева по вашему выбору, вы должны собрать ровно один фрукт с каждого дерева (включая начальное), двигаясь при этом вправо. Собранные фрукты должны поместиться в одну из ваших корзин. Как только вы достигнете дерева с фруктами, которые не могут поместиться в ваши корзины, вы должны остановиться. Учитывая целочисленный массив fruits, верните максимальное количество фруктов, которое вы можете собрать.
Пример:
Input: fruits = [1,2,1]
Output: 3
👨💻 Алгоритм:
1⃣Использовать метод скользящего окна для поддержания текущего подмассива, содержащего не более двух типов фруктов.
2⃣Перемещать правый указатель, расширяя окно, и обновлять количество каждого типа фрукта в окне.
Если количество типов фруктов в окне превышает два, перемещать левый указатель, уменьшая окно, пока в окне снова не будет не более двух типов фруктов.
3⃣Подсчитывать максимальное количество фруктов, собранных на каждом шаге.
😎 Решение:
class Solution {
fun totalFruit(fruits: IntArray): Int {
val basket = mutableMapOf<Int, Int>()
var left = 0
var maxFruits = 0
for (right in fruits.indices) {
basket[fruits[right]] = basket.getOrDefault(fruits[right], 0) + 1
while (basket.size > 2) {
basket[fruits[left]] = basket[fruits[left]]!! - 1
if (basket[fruits[left]] == 0) {
basket.remove(fruits[left])
}
left++
}
maxFruits = maxOf(maxFruits, right - left + 1)
}
return maxFruits
}
}
Ставь 👍 и забирай 📚 Базу знаний | 161 |
| 4 |  Задача: 104. Maximum Depth of Binary Tree
Сложность: easy
Дан корень бинарного дерева, верните его максимальную глубину.
Максимальная глубина бинарного дерева — это количество узлов вдоль самого длинного пути от корневого узла до самого удалённого листового узла.
Пример:
Input: root = [3,9,20,null,null,15,7]
Output: 3
👨💻 Алгоритм:
1⃣Можно обойти дерево, используя стратегию поиска в глубину (DFS) или поиска в ширину (BFS).
2⃣Для данной задачи подойдет несколько способов.
3⃣Здесь мы демонстрируем решение, реализованное с использованием стратегии DFS и рекурсии.
😎 Решение:
class TreeNode(var `val`: Int) {
var left: TreeNode? = null
var right: TreeNode? = null
}
class Solution {
fun maxDepth(root: TreeNode?): Int {
return if (root == null) {
0
} else {
val leftHeight = maxDepth(root.left)
val rightHeight = maxDepth(root.right)
maxOf(leftHeight, rightHeight) + 1
}
}
}
Ставь 👍 и забирай 📚 Базу знаний | 138 |
| 5 | Задача: 1089. Duplicate Zeros
Сложность: easy
Дан массив целых чисел фиксированной длины arr, дублируйте каждое вхождение нуля, сдвигая оставшиеся элементы вправо.
Учтите, что элементы за пределами длины исходного массива не записываются. Внесите указанные изменения в массив на месте и ничего не возвращайте.
Пример:
Input: arr = [1,0,2,3,0,4,5,0]
Output: [1,0,0,2,3,0,0,4]
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]
👨💻 Алгоритм:
1⃣Найдите количество нулей, которые будут продублированы, назовем это possible_dups. Необходимо убедиться, что мы не считаем нули, которые будут отброшены, так как отброшенные нули не будут частью итогового массива. Количество possible_dups даст нам количество элементов, которые будут отброшены из исходного массива. В любой момент времени length_ - possible_dups — это количество элементов, которые будут включены в итоговый массив.
2⃣Обработайте крайний случай для нуля, находящегося на границе оставшихся элементов. Будьте особенно внимательны при дублировании нулей в оставшемся массиве. Следует учитывать, лежит ли ноль на границе. Этот ноль может быть учтен с возможными дубликатами или может быть просто включен в оставшиеся элементы, когда не осталось места для его дубликата. Если он является частью possible_dups, мы хотим его дублировать, в противном случае — нет.
3⃣Итерируйте массив с конца и копируйте ненулевой элемент один раз, а нулевой элемент дважды. Когда мы говорим об отбрасывании лишних элементов, это означает, что мы начинаем с левой стороны лишних элементов и начинаем перезаписывать их новыми значениями, в конечном итоге сдвигая оставшиеся элементы вправо и создавая пространство для всех дублированных элементов в массиве.
😎 Решение:
class Solution {
fun duplicateZeros(arr: IntArray) {
var possibleDups = 0
var length_ = arr.size - 1
for (left in 0..length_ - possibleDups) {
if (arr[left] == 0) {
if (left == length_ - possibleDups) {
arr[length_] = 0
length_--
break
}
possibleDups++
}
}
val last = length_ - possibleDups
for (i in last downTo 0) {
if (arr[i] == 0) {
arr[i + possibleDups] = 0
possibleDups--
arr[i + possibleDups] = 0
} else {
arr[i + possibleDups] = arr[i]
}
}
}
}
Ставь 👍 и забирай 📚 Базу знаний | 113 |
| 6 | Задача: 1015. Smallest Integer Divisible by K
Сложность: medium
Задано целое положительное число k, необходимо найти длину наименьшего целого положительного числа n, такого, что n делится на k, и n содержит только цифру 1. Верните длину n. Если такого n не существует, верните -1. Примечание: n может не поместиться в 64-битное знаковое целое число.
Пример:
Input: k = 1
Output: 1
👨💻 Алгоритм:
1⃣Использование остатка для нахождения числа с цифрами 1:
Создайте переменную num и установите ее равной 1.
Создайте переменную length и установите ее равной 1 для отслеживания длины числа.
2⃣Итеративное нахождение числа:
Используйте цикл, чтобы умножать num на 10 и добавлять 1 в каждой итерации, и каждый раз вычисляйте остаток от деления num на k.
Увеличивайте length на 1 в каждой итерации.
Если в какой-то итерации num % k == 0, верните length.
3⃣Проверка бесконечного цикла:
Если цикл длится слишком долго (например, 10^6 итераций), верните -1, чтобы предотвратить бесконечный цикл для случаев, когда решение не существует.
😎 Решение:
class Solution {
fun smallestRepunitDivByK(k: Int): Int {
var num = 1
var length = 1
val seen = mutableSetOf<Int>()
while (num % k != 0) {
if (seen.contains(num % k)) {
return -1
}
seen.add(num % k)
num = (num * 10 + 1) % k
length++
}
return length
}
}
Ставь 👍 и забирай 📚 Базу знаний | 107 |
| 7 | Задача: 1102. Path With Maximum Minimum Value
Сложность: medium
Дана целочисленная матрица grid размером m x n. Верните максимальное значение пути, начинающегося в (0, 0) и заканчивающегося в (m - 1, n - 1), двигаясь в 4 кардинальных направлениях.
Значение пути определяется минимальным числом на этом пути.
Пример:
Input: grid = [[5,4,5],[1,2,6],[7,4,6]]
Output: 4
Explanation: The path with the maximum score is highlighted in yellow.
👨💻 Алгоритм:
1⃣Начните с оценки curScore = min(grid[0][0], grid[m-1][n-1]), где m и n - общее количество строк и столбцов входной матрицы.
2⃣Выполните BFS на матрице и проверьте, существует ли путь, где все значения больше или равны curScore:
Используйте очередь (deque) для хранения всех непосещенных ячеек со значением, большим или равным curScore.
Извлекайте ячейку из начала очереди, проверяйте, есть ли у нее непосещенные соседние ячейки, и добавляйте их в конец очереди.
Если успешно достигли правой нижней ячейки, значит путь существует.
Если очередь опустела до достижения правой нижней ячейки, пути не существует.
3⃣Если пути не существует, что означает, что curScore слишком велик, уменьшите его на 1 и повторите шаг 2.
В противном случае, верните curScore как ответ.
😎 Решение:
class Solution {
private val dirs = arrayOf(
intArrayOf(1, 0), intArrayOf(0, 1), intArrayOf(-1, 0), intArrayOf(0, -1)
)
fun maximumMinimumPath(grid: Array<IntArray>): Int {
var curScore = minOf(grid[0][0], grid[grid.size - 1][grid[0].size - 1])
while (curScore >= 0) {
if (pathExists(grid, curScore)) {
return curScore
}
curScore -= 1
}
return -1
}
private fun pathExists(grid: Array<IntArray>, curScore: Int): Boolean {
val R = grid.size
val C = grid[0].size
val visited = Array(R) { BooleanArray(C) }
val dq = ArrayDeque<Pair<Int, Int>>()
dq.add(0 to 0)
visited[0][0] = true
fun push(row: Int, col: Int) {
if (row in 0 until R && col in 0 until C && !visited[row][col] && grid[row][col] >= curScore) {
dq.add(row to col)
visited[row][col] = true
}
}
while (dq.isNotEmpty()) {
val (curRow, curCol) = dq.removeFirst()
if (curRow == R - 1 && curCol == C - 1) {
return true
}
for (dir in dirs) {
push(curRow + dir[0], curCol + dir[1])
}
}
return false
}
}
Ставь 👍 и забирай 📚 Базу знаний | 119 |
| 8 | Задача: 257. Binary Tree Paths
Сложность: easy
Дано корневое дерево, верните все пути от корня до листа в любом порядке.
Лист — это узел без детей.
Пример:
Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]
👨💻 Алгоритм:
1⃣Если текущий узел не является null, добавьте его значение к текущему пути.
Если текущий узел является листом (не имеет дочерних узлов), добавьте текущий путь в список путей.
Если текущий узел не является листом, добавьте "->" к текущему пути и рекурсивно вызовите функцию для левого и правого дочерних узлов.
2⃣Начните с корневого узла, пустого пути и пустого списка путей.
3⃣Верните список всех путей от корня до листа.
😎 Решение:
class Solution {
fun construct_paths(root: TreeNode?, path: String, paths: MutableList<String>) {
if (root != null) {
var path = path + root.`val`
if (root.left == null && root.right == null) {
paths.add(path)
} else {
path += "->"
construct_paths(root.left, path, paths)
construct_paths(root.right, path, paths)
}
}
}
fun binaryTreePaths(root: TreeNode?): List<String> {
val paths = mutableListOf<String>()
construct_paths(root, "", paths)
return paths
}
}
Ставь 👍 и забирай 📚 Базу знаний | 120 |
| 9 | 🔥 Скрытые вакансии с удаленной работой для Android разработчика, которые нигде больше не публикуются. Напрямую от компаний, с контактами рекрутеров.
🔹 Android Jobs | Вакансии
🔹 Flutter Dart Jobs | Вакансии
🔹 iOS Jobs | Вакансии
🔸 Все каналы с вакансиями | 119 |
| 10 | Задача: 491. Non-decreasing Subsequences
Сложность: medium
Дан массив целых чисел nums. Верните все возможные различные неубывающие подпоследовательности данного массива, содержащие как минимум два элемента. Вы можете вернуть ответ в любом порядке.
Пример:
Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
👨💻 Алгоритм:
1⃣Инициализация и запуск функции обратного отслеживания
Создайте множество для хранения результатов. Создайте список для хранения текущей последовательности. Запустите рекурсивную функцию обратного отслеживания с начальным индексом 0.
2⃣Функция обратного отслеживания
Если текущий индекс равен длине массива, проверьте длину текущей последовательности и добавьте её в результат, если она содержит не менее двух элементов. Если текущая последовательность остаётся неубывающей после добавления текущего элемента массива, добавьте этот элемент, вызовите рекурсивную функцию для следующего индекса и удалите элемент из последовательности (обратное отслеживание). Всегда вызывайте рекурсивную функцию для следующего индекса без добавления текущего элемента.
3⃣Возврат результата
После завершения всех рекурсивных вызовов преобразуйте множество результатов в список и верните его.
😎 Решение:
class Solution {
fun findSubsequences(nums: IntArray): List<List<Int>> {
val result = mutableSetOf<List<Int>>()
val sequence = mutableListOf<Int>()
backtrack(nums, 0, sequence, result)
return result.toList()
}
private fun backtrack(nums: IntArray, index: Int, sequence: MutableList<Int>, result: MutableSet<List<Int>>) {
if (index == nums.size) {
if (sequence.size >= 2) {
result.add(sequence.toList())
}
return
}
if (sequence.isEmpty() || sequence.last() <= nums[index]) {
sequence.add(nums[index])
backtrack(nums, index + 1, sequence, result)
sequence.removeAt(sequence.size - 1)
}
backtrack(nums, index + 1, sequence, result)
}
}
Ставь 👍 и забирай 📚 Базу знаний | 107 |
| 11 | Задача: 635. Design Log Storage System
Сложность: medium
Вам дается несколько журналов, где каждый журнал содержит уникальный идентификатор и временную метку. Временная метка - это строка, имеющая следующий формат: Год:Месяц:День:Час:Минута:Секунда, например, 2017:01:01:23:59:59. Все домены - десятичные числа с нулевым добавлением. Реализация класса LogSystem: LogSystem() Инициализирует объект LogSystem. void put(int id, string timestamp) Сохраняет заданный журнал (id, timestamp) в вашей системе хранения.
int[] retrieve(string start, string end, string granularity) Возвращает идентификаторы журналов, временные метки которых находятся в диапазоне от start до end включительно. start и end имеют тот же формат, что и timestamp, а granularity означает, насколько точным должен быть диапазон (т. е. с точностью до дня, минуты и т. д.). Например, start = "2017:01:01:23:59:59", end = "2017:01:02:23:59:59", а granularity = "Day" означает, что нам нужно найти журналы в диапазоне от 1 января 2017 года до 2 января 2017 года включительно, а час, минуту и секунду для каждой записи журнала можно игнорировать.
Пример:
Input
["LogSystem", "put", "put", "put", "retrieve", "retrieve"]
[[], [1, "2017:01:01:23:59:59"], [2, "2017:01:01:22:59:59"], [3, "2016:01:01:00:00:00"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Year"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Hour"]]
Output
[null, null, null, null, [3, 2, 1], [2, 1]]
👨💻 Алгоритм:
1⃣Инициализация и хранение журналов
Реализуйте метод put, который будет сохранять журнал с заданным id и timestamp в системе хранения.
2⃣Формирование диапазона
Реализуйте метод retrieve, который будет формировать диапазон временных меток на основе заданного start, end и granularity.
3⃣Фильтрация и возврат результатов
Используйте сформированный диапазон для фильтрации журналов и возврата идентификаторов тех журналов, чьи временные метки попадают в этот диапазон.
😎 Решение:
class LogSystem {
private val logs = mutableListOf<Pair<Int, String>>()
private val granularity = mapOf(
"Year" to 4,
"Month" to 7,
"Day" to 10,
"Hour" to 13,
"Minute" to 16,
"Second" to 19
)
fun put(id: Int, timestamp: String) {
logs.add(id to timestamp)
}
fun retrieve(start: String, end: String, granularity: String): List<Int> {
val length = this.granularity[granularity]!!
val start = start.substring(0, length)
val end = end.substring(0, length)
return logs.filter { (id, timestamp) ->
val ts = timestamp.substring(0, length)
start <= ts && ts <= end
}.map { it.first }
}
}
Ставь 👍 и забирай 📚 Базу знаний | 97 |
| 12 | Задача: 1209. Remove All Adjacent Duplicates in String II
Сложность: medium
Вам дана строка s и целое число k. Удаление k дубликатов состоит в выборе k соседних и одинаковых букв из s и их удалении, что приводит к соединению левой и правой части удаленной подстроки вместе.
Мы повторяем удаление k дубликатов в s до тех пор, пока не сможем больше этого сделать.
Верните итоговую строку после всех таких удалений дубликатов. Гарантируется, что ответ уникален.
Пример:
Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation:
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"
👨💻 Алгоритм:
1⃣Инициализировать медленный указатель j значением 0 и стек counts для хранения количества одинаковых символов.
2⃣Перемещать быстрый указатель i по строке s:
Копировать s[i] в s[j].
Если s[j] совпадает с s[j - 1], увеличить значение на вершине стека.
Иначе добавить 1 в стек.
Если количество символов равно k, уменьшить j на k и извлечь из стека.
3⃣Вернуть первые j символов строки.
😎 Решение:
class Solution {
fun removeDuplicates(s: String, k: Int): String {
val counts = mutableListOf<Int>()
val sa = s.toCharArray()
var j = 0
for (i in sa.indices) {
sa[j] = sa[i]
if (j == 0 || sa[j] != sa[j - 1]) {
counts.add(1)
} else {
val incremented = counts.removeAt(counts.size - 1) + 1
if (incremented == k) {
j -= k
} else {
counts.add(incremented)
}
}
j++
}
return String(sa, 0, j)
}
}
Ставь 👍 и забирай 📚 Базу знаний | 94 |
| 13 | Задача: 535. Encode and Decode TinyURL
Сложность: medium
Спроектируйте kласс для кодирования URL и декодирования короткого URL.
Нет ограничений на то, как ваш алгоритм кодирования/декодирования должен работать. Вам просто нужно убедиться, что URL может быть закодирован в короткий URL, а короткий URL может быть декодирован в исходный URL.
Реализуйте класс Solution:
Solution() Инициализирует объект системы.
String encode(String longUrl) Возвращает короткий URL для данного longUrl.
String decode(String shortUrl) Возвращает исходный длинный URL для данного shortUrl. Гарантируется, что данный shortUrl был закодирован тем же объектом.
Пример:
Input: url = "https://leetcode.com/problems/design-tinyurl"
Output: "https://leetcode.com/problems/design-tinyurl"
Explanation:
Solution obj = new Solution();
string tiny = obj.encode(url); // returns the encoded tiny url.
string ans = obj.decode(tiny); // returns the original url after decoding it.
👨💻 Алгоритм:
1⃣ Инициализация:
Создайте строку, содержащую все возможные символы (цифры и буквы), которые могут быть использованы для генерации кода.
Создайте хэш-таблицу для хранения соответствий коротких и длинных URL-адресов.
Создайте объект для генерации случайных чисел.
2⃣ Кодирование:
Сгенерируйте случайный 6-символьный код.
Если такой код уже существует в хэш-таблице, повторите генерацию.
Сохраните соответствие длинного URL и сгенерированного кода в хэш-таблице.
Верните полный короткий URL.
3⃣ Декодирование:
Удалите префикс короткого URL, чтобы получить код.
Используйте код для поиска длинного URL в хэш-таблице.
Верните длинный URL.
😎 Решение:
class Codec {
private val alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
private val map = mutableMapOf<String, String>()
private val rand = java.util.Random()
private fun getRand(): String {
val sb = StringBuilder()
repeat(6) {
sb.append(alphabet[rand.nextInt(62)])
}
return sb.toString()
}
fun encode(longUrl: String): String {
var key = getRand()
while (map.containsKey(key)) {
key = getRand()
}
map[key] = longUrl
return "http://tinyurl.com/$key"
}
fun decode(shortUrl: String): String? {
val key = shortUrl.replace("http://tinyurl.com/", "")
return map[key]
}
}
Ставь 👍 и забирай 📚 Базу знаний | 87 |
| 14 | Задача: 981. Time Based Key-Value Store
Сложность: medium
Спроектируйте структуру данных на основе времени для ключей и значений, которая может хранить несколько значений для одного и того же ключа в разные временные метки и извлекать значение ключа в определённый момент времени.
Реализуйте класс TimeMap:
TimeMap() Инициализирует объект структуры данных.
void set(String key, String value, int timestamp) Сохраняет ключ key с значением value в заданное время timestamp.
String get(String key, int timestamp) Возвращает значение, такое что set был вызван ранее с timestamp_prev <= timestamp. Если таких значений несколько, возвращается значение, связанное с наибольшим timestamp_prev. Если значений нет, возвращается "".
Пример:
Input
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
Output
[null, null, "bar", "bar", null, "bar2", "bar2"]
👨💻 Алгоритм:
1⃣Создайте hashmap keyTimeMap, который хранит строку в качестве ключа и другой hashmap в качестве значения, как обсуждалось выше.
2⃣В функции set() сохраните значение в позиции timestamp в корзине ключа keyTimeMap, т.е. keyTimeMap[key][timestamp] = value.
3⃣В функции get() итерируйтесь по всем временам в порядке убывания от timestamp до 1. Для любого времени во время итерации, если существует значение в корзине ключа, верните это значение. В противном случае, в конце верните пустую строку.
😎 Решение:
class TimeMap {
private val keyTimeMap = mutableMapOf<String, MutableMap<Int, String>>()
fun set(key: String, value: String, timestamp: Int) {
if (!keyTimeMap.containsKey(key)) {
keyTimeMap[key] = mutableMapOf()
}
keyTimeMap[key]?.put(timestamp, value)
}
fun get(key: String, timestamp: Int): String {
val times = keyTimeMap[key] ?: return ""
for (currTime in timestamp downTo 1) {
if (times.containsKey(currTime)) {
return times[currTime]!!
}
}
return ""
}
}
Ставь 👍 и забирай 📚 Базу знаний | 103 |
| 15 | Задача: 970. Powerful Integers
Сложность: medium
Даны три целых числа x, y и bound. Верните список всех мощных чисел, которые имеют значение меньше или равное bound.
Целое число является мощным, если оно может быть представлено как x^i + y^j для некоторых целых чисел i >= 0 и j >= 0.
Вы можете вернуть ответ в любом порядке. В вашем ответе каждое значение должно встречаться не более одного раза.
Пример:
Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]
Explanation:
2 = 20 + 30
3 = 21 + 30
4 = 20 + 31
5 = 21 + 31
7 = 22 + 31
9 = 23 + 30
10 = 20 + 32
👨💻 Алгоритм:
1⃣Вычислите степени a и b как логарифмы bound по основаниям x и y соответственно. Создайте множество powerfulIntegers для хранения результатов.
2⃣Используйте вложенные циклы, где внешний цикл проходит от 0 до a, а внутренний цикл от 0 до b. На каждом шаге вычисляйте x^i + y^j и, если значение меньше или равно bound, добавляйте его в множество powerfulIntegers.
3⃣Используйте вложенные циклы, где внешний цикл проходит от 0 до a, а внутренний цикл от 0 до b. На каждом шаге вычисляйте x^i + y^j и, если значение меньше или равно bound, добавляйте его в множество powerfulIntegers.
😎 Решение:
class Solution {
fun powerfulIntegers(x: Int, y: Int, bound: Int): List<Int> {
val a = if (x == 1) bound else (Math.log(bound.toDouble()) / Math.log(x.toDouble())).toInt()
val b = if (y == 1) bound else (Math.log(bound.toDouble()) / Math.log(y.toDouble())).toInt()
val powerfulIntegers = mutableSetOf<Int>()
for (i in 0..a) {
for (j in 0..b) {
val value = Math.pow(x.toDouble(), i.toDouble()).toInt() + Math.pow(y.toDouble(), j.toDouble()).toInt()
if (value <= bound) {
powerfulIntegers.add(value)
}
if (y == 1) break
}
if (x == 1) break
}
return powerfulIntegers.toList()
}
}
Ставь 👍 и забирай 📚 Базу знаний | 89 |
| 16 | Задача: 338. Counting Bits
Сложность: easy
Дано целое число n, верните массив ans длиной n + 1, такой что для каждого i (0 <= i <= n), ans[i] будет равняться количеству единиц в двоичном представлении числа i.
Пример:
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
👨💻 Алгоритм:
1⃣Инициализация массива:
Создайте массив ans длиной n + 1, заполненный нулями. Этот массив будет содержать количество единиц в двоичном представлении каждого числа от 0 до n.
2⃣Итерация и вычисление:
Пройдите в цикле по всем числам от 1 до n. Для каждого числа x используйте битовую операцию x & (x - 1), чтобы убрать последнюю установленную биту, и добавьте 1 к значению ans для этого результата. Это количество единиц в двоичном представлении числа x.
3⃣Возврат результата:
Верните заполненный массив ans, который содержит количество единиц для каждого числа от 0 до n.
😎 Решение:
class Solution {
fun countBits(num: Int): IntArray {
val ans = IntArray(num + 1)
for (x in 1..num) {
ans[x] = ans[x and (x - 1)] + 1
}
return ans
}
}
Ставь 👍 и забирай 📚 Базу знаний | 105 |
| 17 | Задача: 790. Domino and Tromino Tiling
Сложность: medium
У вас есть два типа плиток: домино размером 2 x 1 и тромино. Вы можете вращать эти фигуры.
Дано целое число n. Верните количество способов выложить плитками доску размером 2 x n. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.
При укладке каждая клетка должна быть покрыта плиткой. Две укладки считаются разными, если и только если есть две 4-направленно смежные клетки на доске, такие, что в одной укладке обе клетки заняты плиткой, а в другой - нет.
Пример:
Input: n = 3
Output: 5
Explanation: The five different ways are show above.
👨💻 Алгоритм:
1⃣Начнем с f(n) и далее спустимся до базовых случаев, f(1), f(2) и p(2). Используйте те же определения для f и p из раздела Обзор. f(k): количество способов полностью покрыть доску шириной k. p(k): количество способов частично покрыть доску шириной k. Рекурсивные вызовы будут использовать результаты подзадач и базовых случаев, чтобы помочь нам получить окончательный результат, f(n).
2⃣Условие остановки для рекурсивных вызовов - когда k достигает базового случая (т.е. k <= 2). Значения для базовых случаев будут возвращены напрямую, вместо того чтобы делать дополнительные рекурсивные вызовы. f(1)=1, f(2)=2, p(2)=1. Чтобы избежать повторных вычислений, мы будем использовать 2 хэшмапы (f_cache и p_cache) для хранения рассчитанных значений для f и p. В Python встроенный декоратор @cache автоматически поддерживает эти хэшмапы для нас.
3⃣Если k больше 2, мы будем делать рекурсивные вызовы к f и p в соответствии с переходной функцией: f(k) = f(k−1) + f(k−2) + 2 * p(k−1), p(k) = p(k−1) + f(k−2). f(n) будет возвращено, как только все рекурсивные вызовы завершатся.
😎 Решение:
class Solution {
private val MOD = 1_000_000_007
private val fCache = mutableMapOf<Int, Int>()
private val pCache = mutableMapOf<Int, Int>()
private fun p(n: Int): Int {
if (pCache.containsKey(n)) {
return pCache[n]!!
}
if (n == 2) {
return 1
}
val result = (p(n - 1) + f(n - 2)) % MOD
pCache[n] = result
return result
}
private fun f(n: Int): Int {
if (fCache.containsKey(n)) {
return fCache[n]!!
}
if (n <= 2) {
return n
}
val result = (f(n - 1) + f(n - 2) + 2 * p(n - 1)) % MOD
fCache[n] = result
return result
}
fun numTilings(n: Int): Int {
return f(n)
}
}
Ставь 👍 и забирай 📚 Базу знаний | 112 |
| 18 | Задача: 169. Majority Element
Сложность: easy
Дан массив nums размера n, верните элемент большинства.
Элемент большинства — это элемент, который встречается более чем ⌊n / 2⌋ раз. Можно предположить, что элемент большинства всегда существует в массиве.
Пример:
Input: nums = [3,2,3]
Output: 3
👨💻 Алгоритм:
1⃣Использование HashMap для подсчета:
Создайте HashMap для отслеживания количества каждого элемента в массиве.
2⃣Подсчет вхождений элементов:
Пройдите по массиву nums, увеличивая счетчик в HashMap для каждого элемента.
3⃣Поиск элемента большинства:
Определите элемент большинства, просмотрев HashMap и найдя ключ с максимальным значением, которое должно быть больше ⌊n / 2⌋
😎 Решение:
fun majorityElement(nums: IntArray): Int {
val counts = mutableMapOf<Int, Int>()
nums.forEach { num ->
counts[num] = counts.getOrDefault(num, 0) + 1
}
counts.forEach { (num, count) ->
if (count > nums.size / 2) return num
}
return 0
}
Ставь 👍 и забирай 📚 Базу знаний | 127 |
| 19 | Задача: 334. Increasing Triplet Subsequence
Сложность: Medium
Дан массив целых чисел nums. Верните true, если существуют такие три индекса (i, j, k), что i < j < k и nums[i] < nums[j] < nums[k]. Если таких индексов не существует, верните false.
Пример:
Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.
👨💻 Алгоритм:
1⃣Инициализация переменных:
Создайте две переменные first_num и second_num и установите их значение на максимальное целое значение (Integer.MAX_VALUE или аналогичный максимум для выбранного языка программирования). Эти переменные будут хранить минимальные значения, необходимые для проверки существования возрастающей тройки.
2⃣Итерация по массиву:
Пройдите по каждому элементу массива nums. Для каждого элемента выполните следующие проверки:
- если текущий элемент меньше или равен first_num, обновите first_num текущим элементом.
- иначе, если текущий элемент меньше или равен second_num, обновите second_num текущим элементом.
- иначе, если текущий элемент больше second_num, это означает, что найдена возрастающая тройка, поэтому верните true.
3⃣Возврат результата:
Если после завершения итерации по массиву не была найдена возрастающая тройка, верните false.
😎 Решение:
class Solution {
fun increasingTriplet(nums: IntArray): Boolean {
var firstNum = Int.MAX_VALUE
var secondNum = Int.MAX_VALUE
for (n in nums) {
if (n <= firstNum) {
firstNum = n
} else if (n <= secondNum) {
secondNum = n
} else {
return true
}
}
return false
}
}
Ставь 👍 и забирай 📚 Базу знаний | 156 |
| 20 | Задача: 1074. Number of Submatrices That Sum to Target
Сложность: hard
Дана матрица и целевое значение. Верните количество непустых подматриц, сумма элементов которых равна целевому значению.
Подматрица x1, y1, x2, y2 — это набор всех ячеек matrix[x][y] с x1 <= x <= x2 и y1 <= y <= y2.
Две подматрицы (x1, y1, x2, y2) и (x1', y1', x2', y2') различны, если у них есть какая-то различающаяся координата: например, если x1 != x1'.
Пример:
Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
Explanation: The four 1x1 submatrices that only contain 0.
👨💻 Алгоритм:
1⃣Инициализируйте результат: count = 0. Вычислите количество строк: r = len(matrix) и количество столбцов: c = len(matrix[0]). Вычислите двумерную префиксную сумму ps, выделив еще одну строку и еще один столбец для нулевых значений.
2⃣Итерируйте по строкам: r1 от 1 до r и r2 от r1 до r. Внутри этого двойного цикла фиксируйте левые и правые границы строк и инициализируйте хэш-таблицу для хранения префиксных сумм. Итерируйте по столбцам от 1 до c + 1, вычислите текущую префиксную сумму 1D curr_sum и увеличьте count на количество матриц, сумма которых равна target.
3⃣Добавьте текущую префиксную сумму 1D в хэш-таблицу. Когда все итерации завершены, верните count.
😎 Решение:
class Solution {
fun numSubmatrixSumTarget(matrix: Array<IntArray>, target: Int): Int {
val r = matrix.size
val c = matrix[0].size
val ps = Array(r + 1) { IntArray(c + 1) }
for (i in 1..r) {
for (j in 1..c) {
ps[i][j] = ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1] + matrix[i - 1][j - 1]
}
}
var count = 0
for (r1 in 1..r) {
for (r2 in r1..r) {
val h = mutableMapOf<Int, Int>()
h[0] = 1
for (col in 1..c) {
val currSum = ps[r2][col] - ps[r1 - 1][col]
count += h.getOrDefault(currSum - target, 0)
h[currSum] = h.getOrDefault(currSum, 0) + 1
}
}
}
return count
}
}
Ставь 👍 и забирай 📚 Базу знаний | 147 |
