Kotlin | LeetCode
Ir al canal en Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
Mostrar más
Red:1 700
Suscriptores
Sin datos24 horas
-17 días
-830 días
Archivo de publicaciones
1 700
Задача: 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)
}
}1 700
Задача: 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 }
}
}1 700
Задача: 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)
}
}1 700
Задача: 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.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]
}
}1 700
Задача: 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 ""
}
}1 700
Задача: 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()
}
}1 700
Задача: 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
}
}1 700
Задача: 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)
}
}1 700
Задача: 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
}1 700
Задача: 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
}
}1 700
Задача: 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.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
}
}1 700
Задача: 606. Construct String from Binary Tree
Сложность: Medium
Дано корневой узел бинарного дерева, ваша задача — создать строковое представление дерева, следуя определенным правилам форматирования. Представление должно быть основано на прямом обходе бинарного дерева и должно соответствовать следующим требованиям:
Представление узлов: Каждый узел в дереве должен быть представлен его целочисленным значением.
Скобки для дочерних узлов: Если у узла есть хотя бы один дочерний узел (левый или правый), его дочерние узлы должны быть представлены в скобках. Конкретно:
- Если у узла есть левый дочерний узел, значение левого дочернего узла должно быть заключено в скобки сразу после значения узла.
- Если у узла есть правый дочерний узел, значение правого дочернего узла также должно быть заключено в скобки. Скобки для правого дочернего узла должны следовать за скобками для левого дочернего узла.
Пропуск пустых скобок: Любые пустые пары скобок (т.е. ()) должны быть опущены в окончательном строковом представлении дерева, за одним исключением: когда у узла есть правый дочерний узел, но нет левого дочернего узла. В таких случаях вы должны включить пустую пару скобок, чтобы указать на отсутствие левого дочернего узла. Это гарантирует, что однозначное соответствие между строковым представлением и исходной структурой бинарного дерева сохраняется.
В итоге, пустые пары скобок должны быть опущены, когда у узла есть только левый дочерний узел или нет дочерних узлов. Однако, когда у узла есть правый дочерний узел, но нет левого дочернего узла, пустая пара скобок должна предшествовать представлению правого дочернего узла, чтобы точно отразить структуру дерева.
Пример:
Input: root = [1,2,3,4]
Output: "1(2(4))(3)"
Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the empty parenthesis pairs. And it will be "1(2(4))(3)".class Solution {
fun tree2str(t: TreeNode?): String {
val res = StringBuilder()
dfs(t, res)
return res.toString()
}
private fun dfs(t: TreeNode?, res: StringBuilder) {
if (t == null) return
res.append(t.`val`)
if (t.left == null && t.right == null) return
res.append('(')
dfs(t.left, res)
res.append(')')
if (t.right != null) {
res.append('(')
dfs(t.right, res)
res.append(')')
}
}
}1 700
Задача: 275. H-Index II
Сложность: medium
Дан массив целых чисел citations, где citations[i] — количество цитирований, которое исследователь получил за свою i-ю статью, и массив отсортирован в порядке возрастания. Верните h-индекс исследователя.
Согласно определению h-индекса на Википедии: h-индекс определяется как максимальное значение h, такое что данный исследователь опубликовал по крайней мере h статей, каждая из которых была процитирована как минимум h раз.
Вы должны написать алгоритм, который работает за логарифмическое время.
Пример:
Input: citations = [0,1,3,5,6] Output: 3 Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.👨💻 Алгоритм: 1⃣Найти середину массива: Определить средний элемент массива, чтобы разделить его на две подмножества: citations[0: mid - 1] и citations[mid + 1: n]. 2⃣Сравнить количество статей с цитированиями больше или равными citations[mid]: Если citations[mid] == n - mid, то найден h-индекс и его можно вернуть. Если citations[mid] < n - mid, то необходимо искать в правой подмножности citations[mid + 1: n]. Если citations[mid] > n - mid, то необходимо искать в левой подмножности citations[0: mid - 1]. 3⃣Возвращение результата: Продолжать процесс, пока не будет найден h-индекс. Возвратить n - mid, что является количеством статей с цитированиями больше или равными citations[mid]. 😎 Решение:
class Solution {
fun hIndex(citations: IntArray): Int {
val n = citations.size
var left = 0
var right = n - 1
while (left <= right) {
val mid = left + (right - left) / 2
if (citations[mid] == n - mid) {
return n - mid
} else if (citations[mid] < n - mid) {
left = mid + 1
} else {
right = mid - 1
}
}
return n - left
}
}1 700
Задача: 1275. Find Winner on a Tic Tac Toe Game
Сложность: easy
В игру "Крестики-нолики" играют два игрока A и B на сетке 3 x 3. Правила игры "Крестики-нолики" таковы: игроки по очереди помещают символы в пустые квадраты ' '. Первый игрок A всегда помещает символы "X", а второй игрок B - "O". Символы "X" и "O" всегда помещаются в пустые квадраты, а не в заполненные.
Игра заканчивается, когда три одинаковых (непустых) символа заполняют любую строку, столбец или диагональ. Игра также заканчивается, если все клетки непустые. Больше ходов не может быть сыграно, если игра закончена. Учитывая двумерный целочисленный массив moves, где moves[i] = [rowi, coli] указывает, что i-й ход будет сыгран на сетке[rowi][coli]. верните победителя игры, если он существует (A или B). Если игра закончилась вничью, верните "Ничья". Если еще есть ходы для игры, верните "Pending". Можно предположить, что ходы действительны (т.е. соответствуют правилам игры в Крестики-нолики), сетка изначально пуста, и A будет играть первым.
Пример:
Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]] Output: "A"👨💻 Алгоритм: 1⃣Инициализируйте пустую 3x3 сетку. 2⃣Пройдите по списку ходов и обновите сетку в соответствии с ходами игроков A и B. 3⃣После каждого хода проверяйте, есть ли победитель. Если все ходы сделаны и нет победителя, проверьте, завершена ли игра вничью или еще есть ходы. 😎 Решение:
class Solution {
fun tictactoe(moves: Array<IntArray>): String {
val grid = Array(3) { CharArray(3) }
for (i in moves.indices) {
val (r, c) = moves[i]
grid[r][c] = if (i % 2 == 0) 'X' else 'O'
}
for (i in 0..2) {
if (grid[i][0] == grid[i][1] && grid[i][1] == grid[i][2] && grid[i][0] != '\u0000')
return if (grid[i][0] == 'X') "A" else "B"
if (grid[0][i] == grid[1][i] && grid[1][i] == grid[2][i] && grid[0][i] != '\u0000')
return if (grid[0][i] == 'X') "A" else "B"
}
if (grid[0][0] == grid[1][1] && grid[1][1] == grid[2][2] && grid[0][0] != '\u0000')
return if (grid[0][0] == 'X') "A" else "B"
if (grid[0][2] == grid[1][1] && grid[1][1] == grid[2][0] && grid[0][2] != '\u0000')
return if (grid[0][2] == 'X') "A" else "B"
return if (moves.size == 9) "Draw" else "Pending"
}
}1 700
Задача: 723. Candy Crush
Сложность: medium
Этот вопрос касается реализации базового алгоритма исключения для Candy Crush. Дан целочисленный массив board размером m x n, представляющий сетку конфет, где board[i][j] представляет тип конфеты. Значение board[i][j] == 0 означает, что ячейка пуста. Данная доска представляет собой состояние игры после хода игрока. Теперь необходимо вернуть доску в стабильное состояние, раздавив конфеты по следующим правилам: если три или более конфет одного типа находятся рядом по вертикали или горизонтали, раздавите их все одновременно - эти позиции станут пустыми. После одновременного раздавливания всех конфет, если на пустом месте доски есть конфеты, расположенные сверху, то эти конфеты будут падать, пока не ударятся о конфету или дно одновременно. Новые конфеты не будут падать за верхнюю границу. После выполнения описанных выше действий может остаться больше конфет, которые можно раздавить. Если конфет, которые можно раздавить, больше не существует (т. е. доска стабильна), верните текущую доску. Выполняйте описанные выше правила, пока доска не станет стабильной, затем верните стабильную доску.
Пример:
Input: board = [[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]] Output: [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[110,0,0,0,114],[210,0,0,0,214],[310,0,0,113,314],[410,0,0,213,414],[610,211,112,313,614],[710,311,412,613,714],[810,411,512,713,1014]]👨💻 Алгоритм: 1⃣Найдите все группы из трех или более одинаковых конфет, как в горизонтальном, так и в вертикальном направлениях, и отметьте их для удаления. 2⃣Удалите отмеченные конфеты, установив их значение в 0. 3⃣Переместите конфеты вниз, чтобы заполнить пустые ячейки, и повторите процесс, пока не останется групп конфет для удаления. 😎 Решение:
class Solution {
fun candyCrush(board: Array<IntArray>): Array<IntArray> {
val m = board.size
val n = board[0].size
var stable = false
while (!stable) {
stable = true
val crush = Array(m) { BooleanArray(n) }
for (i in 0 until m) {
for (j in 0 until n - 2) {
val v = Math.abs(board[i][j])
if (v != 0 && v == Math.abs(board[i][j + 1]) && v == Math.abs(board[i][j + 2])) {
stable = false
crush[i][j] = true
crush[i][j + 1] = true
crush[i][j + 2] = true
}
}
}
for (i in 0 until m - 2) {
for (j in 0 until n) {
val v = Math.abs(board[i][j])
if (v != 0 && v == Math.abs(board[i + 1][j]) && v == Math.abs(board[i + 2][j])) {
stable = false
crush[i][j] = true
crush[i + 1][j] = true
crush[i + 2][j] = true
}
}
}
for (i in 0 until m) {
for (j in 0 until n) {
if (crush[i][j]) {
board[i][j] = 0
}
}
}
for (j in 0 until n) {
var idx = m - 1
for (i in m - 1 downTo 0) {
if (board[i][j] != 0) {
board[idx][j] = board[i][j]
idx--
}
}
for (i in idx downTo 0) {
board[i][j] = 0
}
}
}
return board
}
}1 700
Задача: 745. Prefix and Suffix Search
Сложность: hard
Создайте специальный словарь, в котором поиск слов осуществляется по префиксу и суффиксу. Реализуйте класс WordFilter: WordFilter(string[] words) Инициализирует объект со словами в словаре. f(string pref, string suff) Возвращает индекс слова в словаре, которое имеет префикс pref и суффикс suff. Если существует более одного допустимого индекса, возвращается наибольший из них. Если в словаре нет такого слова, возвращается -1.
Пример:
Input: letters = ["c","f","j"], target = "a" Output: "c"👨💻 Алгоритм: 1⃣Сохраните слова и их индексы в словаре. 2⃣Создайте объединенные ключи, состоящие из префиксов и суффиксов для всех возможных комбинаций. 3⃣Реализуйте функцию поиска, которая ищет наибольший индекс слова по префиксу и суффиксу. 😎 Решение:
class WordFilter(words: Array<String>) {
private val prefixSuffixMap = mutableMapOf<String, Int>()
init {
for ((index, word) in words.withIndex()) {
val length = word.length
for (prefixLength in 1..length) {
for (suffixLength in 1..length) {
val prefix = word.substring(0, prefixLength)
val suffix = word.substring(length - suffixLength)
val key = "$prefix#$suffix"
prefixSuffixMap[key] = index
}
}
}
}
fun f(pref: String, suff: String): Int {
val key = "$pref#$suff"
return prefixSuffixMap[key] ?: -1
}
}1 700
Задача: 25. Reverse Nodes in k-Group
Сложность: hard
Учитывая заголовок связанного списка, поменяйте местами узлы списка k за раз и верните измененный список.
k — целое положительное число, меньшее или равное длине связанного списка. Если количество узлов не кратно k, то пропущенные узлы в конечном итоге должны остаться такими, какие они есть.
Вы не можете изменять значения в узлах списка, можно изменять только сами узлы.
Пример:
Input: head = [1,2,3,4,5], k = 3 Output: [3,2,1,4,5]👨💻 Алгоритм: 1⃣ Проверяем, хватает ли элементов в текущей группе (не менее k узлов). 2⃣ Если хватает, переворачиваем узлы в группе, используя указатели. 3⃣ Рекурсивно вызываем
reverseKGroup для следующей группы и соединяем с уже перевернутыми узлами.
😎 Решение:
class Solution {
fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
var count = 0
var cur = head
while (count < k && cur != null) {
cur = cur.next
count++
}
if (count < k) return head
var prev: ListNode? = null
cur = head
repeat(k) {
val next = cur?.next
cur?.next = prev
prev = cur
cur = next
}
head?.next = reverseKGroup(cur, k)
return prev
}
}1 700
Задача: 859. Buddy Strings
Сложность: easy
Даны две строки s и goal. Верните true, если вы можете поменять местами две буквы в s так, чтобы результат был равен goal, в противном случае верните false.
Обмен буквами определяется как взятие двух индексов i и j (нумерация с 0), таких что i != j, и обмен символов в s[i] и s[j].
Например, обмен символов на индексах 0 и 2 в строке "abcd" приводит к "cbad".
Пример:
Input: s = "ab", goal = "ba"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.class Solution {
fun buddyStrings(s: String, goal: String): Boolean {
if (s.length != goal.length) return false
if (s == goal) {
val freq = IntArray(26)
for (ch in s) {
if (++freq[ch - 'a'] > 1) return true
}
return false
}
var firstIndex = -1
var secondIndex = -1
for (i in s.indices) {
if (s[i] != goal[i]) {
if (firstIndex == -1) firstIndex = i
else if (secondIndex == -1) secondIndex = i
else return false
}
}
return secondIndex != -1 &&
s[firstIndex] == goal[secondIndex] &&
s[secondIndex] == goal[firstIndex]
}
}1 700
Задача: 1214. Two Sum BSTs
Сложность: medium
Даны корни двух бинарных деревьев поиска, root1 и root2, верните true, если и только если существует узел в первом дереве и узел во втором дереве, значения которых в сумме равны заданному целому числу target.
Пример:
Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18 Output: false👨💻 Алгоритм: 1⃣Создайте два пустых множества node_set1 и node_set2. Выполните обход дерева root1, добавляя значения каждого узла в node_set1, и выполните обход дерева root2, добавляя значения каждого узла в node_set2. 2⃣Итерация по элементам в node_set1: для каждого элемента value1 проверяйте, находится ли target - value1 в node_set2. 3⃣Если target - value1 находится в node_set2, верните true. Если после завершения итерации не найдено ни одной подходящей пары, верните false. 😎 Решение:
class TreeNode(var `val`: Int) {
var left: TreeNode? = null
var right: TreeNode? = null
}
class Solution {
private fun dfs(node: TreeNode?, nodeSet: MutableSet<Int>) {
if (node == null) return
dfs(node.left, nodeSet)
nodeSet.add(node.`val`)
dfs(node.right, nodeSet)
}
fun twoSumBSTs(root1: TreeNode?, root2: TreeNode?, target: Int): Boolean {
val nodeSet1 = mutableSetOf<Int>()
val nodeSet2 = mutableSetOf<Int>()
dfs(root1, nodeSet1)
dfs(root2, nodeSet2)
for (value1 in nodeSet1) {
if (nodeSet2.contains(target - value1)) {
return true
}
}
return false
}
}1 700
Задача: 1155. Number of Dice Rolls With Target Sum
Сложность: medium
У вас есть n кубиков, и на каждом кубике k граней, пронумерованных от 1 до k.
Даны три целых числа n, k и target. Необходимо вернуть количество возможных способов (из общего количества kn способов) выбросить кубики так, чтобы сумма выпавших чисел равнялась target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Пример:
Input: n = 1, k = 6, target = 3
Output: 1
Explanation: You throw one die with 6 faces.
There is only one way to get a sum of 3.class Solution {
val MOD = 1_000_000_007
fun waysToTarget(memo: Array<IntArray>, diceIndex: Int, n: Int, currSum: Int, target: Int, k: Int): Int {
if (diceIndex == n) {
return if (currSum == target) 1 else 0
}
if (memo[diceIndex][currSum] != -1) {
return memo[diceIndex][currSum]
}
var ways = 0
for (i in 1..minOf(k, target - currSum)) {
ways = (ways + waysToTarget(memo, diceIndex + 1, n, currSum + i, target, k)) % MOD
}
memo[diceIndex][currSum] = ways
return ways
}
fun numRollsToTarget(n: Int, k: Int, target: Int): Int {
val memo = Array(n + 1) { IntArray(target + 1) { -1 } }
return waysToTarget(memo, 0, n, 0, target, k)
}
}