Kotlin | LeetCode
الذهاب إلى القناة على Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
إظهار المزيد
الشبكة:1 706
المشتركون
لا توجد بيانات24 ساعات
لا توجد بيانات7 أيام
-1130 أيام
أرشيف المشاركات
1 705
Задача: 189. Rotate Array
Сложность: medium
Для целочисленного массива nums, поверните массив вправо на k шагов, где k — неотрицательное число.
Пример:
Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4]👨💻 Алгоритм: 1⃣Создаем дополнительный массив, в который будем помещать каждый элемент исходного массива на его новую позицию. Элемент на позиции i в исходном массиве будет размещен на индексе (i+k) % длина массива. 2⃣Копируем элементы из нового массива в исходный массив, сохраняя новый порядок элементов. 3⃣Заменяем исходный массив полученным результатом, завершая процесс поворота массива. 😎 Решение:
class Solution {
fun rotate(nums: IntArray, k: Int) {
val n = nums.size
val a = IntArray(n)
for (i in nums.indices) {
a[(i + k) % n] = nums[i]
}
for (i in nums.indices) {
nums[i] = a[i]
}
}
}1 705
Задача: 210. Course Schedule II
Сложность: medium
Всего есть numCourses курсов, которые вы должны пройти, пронумерованных от 0 до numCourses - 1. Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] указывает на то, что вы должны сначала пройти курс bi, если хотите взять курс ai.
Например, пара [0, 1] указывает на то, что для прохождения курса 0 сначала нужно пройти курс 1.
Верните порядок курсов, которые вы должны пройти, чтобы завершить все курсы. Если существует несколько правильных ответов, верните любой из них. Если невозможно завершить все курсы, верните пустой массив.
Пример:
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] Output: [0,2,1,3] Объяснение: Всего есть 4 курса, которые нужно пройти. Чтобы взять курс 3, вы должны завершить оба курса 1 и 2. Оба курса 1 и 2 должны быть взяты после того, как вы завершите курс 0. Таким образом, один из правильных порядков курсов — [0,1,2,3]. Другой правильный порядок — [0,2,1,3].👨💻 Алгоритм: 1⃣Инициализация и построение графа: Инициализируйте стек S, который будет содержать топологически отсортированный порядок курсов в нашем графе. Постройте список смежности, используя пары ребер, указанные на входе. Важно отметить, что пара вида [a, b] указывает на то, что курс b должен быть пройден, чтобы взять курс a. Это подразумевает ребро вида b ➔ a. Учтите это при реализации алгоритма. 2⃣Запуск поиска в глубину (DFS): Для каждого узла в нашем графе выполните поиск в глубину (DFS), если этот узел еще не был посещен во время DFS другого узла. Предположим, что мы выполняем поиск в глубину для узла N. Рекурсивно обойдите всех соседей узла N, которые еще не были обработаны. 3⃣Обработка узлов и возвращение результата: После обработки всех соседей добавьте узел N в стек. Мы используем стек для моделирования необходимого порядка. Когда мы добавляем узел N в стек, все узлы, которые требуют узел N в качестве предшественника (среди других), уже будут в стеке. После обработки всех узлов просто верните узлы в порядке их присутствия в стеке от вершины до основания. 😎 Решение:
class Solution {
companion object {
const val WHITE = 1
const val GRAY = 2
const val BLACK = 3
}
private var isPossible: Boolean = true
private lateinit var color: MutableMap<Int, Int>
private val adjList: MutableMap<Int, MutableList<Int>> = HashMap()
private val topologicalOrder: MutableList<Int> = ArrayList()
private fun init(numCourses: Int) {
isPossible = true
color = HashMap()
adjList.clear()
topologicalOrder.clear()
for (i in 0 until numCourses) {
color[i] = WHITE
}
}
private fun dfs(node: Int) {
if (!isPossible) return
color[node] = GRAY
for (neighbor in adjList.getOrDefault(node, mutableListOf())) {
when (color[neighbor]) {
WHITE -> dfs(neighbor)
GRAY -> isPossible = false
}
}
color[node] = BLACK
topologicalOrder.add(node)
}
fun findOrder(numCourses: Int, prerequisites: Array<IntArray>): IntArray {
init(numCourses)
for (prerequisite in prerequisites) {
val (dest, src) = prerequisite
adjList.computeIfAbsent(src) { mutableListOf() }.add(dest)
}
for (i in 0 until numCourses) {
if (color[i] == WHITE) {
dfs(i)
}
}
return if (isPossible) {
val order = IntArray(numCourses)
for (i in 0 until numCourses) {
order[i] = topologicalOrder[numCourses - i - 1]
}
order
} else {
intArrayOf()
}
}
}1 705
Задача: 1031. Maximum Sum of Two Non-Overlapping Subarrays
Сложность: medium
Если задан целочисленный массив nums и два целых числа firstLen и secondLen, верните максимальную сумму элементов в двух непересекающихся подмассивах с длинами firstLen и secondLen. Массив с длиной firstLen может находиться до или после массива с длиной secondLen, но они должны быть непересекающимися. Подмассив - это смежная часть массива.
Пример:
Input: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2 Output: 20👨💻 Алгоритм: 1⃣Предварительные вычисления: Вычислите сумму всех подмассивов длины firstLen и secondLen и сохраните их в списках. 2⃣Поиск максимальной суммы: Переберите все возможные позиции для подмассива длины firstLen и для каждого такого подмассива найдите максимальную сумму для подмассива длины secondLen, который не пересекается с текущим подмассивом длины firstLen. 3⃣Сравнение двух случаев: Рассмотрите оба случая: подмассив длины firstLen до подмассива длины secondLen и подмассив длины secondLen до подмассива длины firstLen. Найдите максимальную сумму для каждого случая. 😎 Решение:
class Solution {
fun maxSumTwoNoOverlap(nums: IntArray, firstLen: Int, secondLen: Int): Int {
fun maxSumNonOverlap(nums: IntArray, firstLen: Int, secondLen: Int): Int {
val n = nums.size
val prefix = IntArray(n + 1)
for (i in 0 until n) {
prefix[i + 1] = prefix[i] + nums[i]
}
val maxFirst = IntArray(n)
for (i in firstLen - 1 until n) {
maxFirst[i] = maxOf(if (i > 0) maxFirst[i - 1] else 0, prefix[i + 1] - prefix[i + 1 - firstLen])
}
val maxSecond = IntArray(n)
for (i in secondLen - 1 until n) {
maxSecond[i] = maxOf(if (i > 0) maxSecond[i - 1] else 0, prefix[i + 1] - prefix[i + 1 - secondLen])
}
var maxSum = 0
for (i in firstLen + secondLen - 1 until n) {
maxSum = maxOf(maxSum, maxFirst[i - secondLen] + (prefix[i + 1] - prefix[i + 1 - secondLen]))
}
return maxSum
}
return maxOf(maxSumNonOverlap(nums, firstLen, secondLen), maxSumNonOverlap(nums.reversedArray(), secondLen, firstLen))
}
}1 705
Задача: 1361. Validate Binary Tree Nodes
Сложность: easy
У вас есть n узлов бинарного дерева, пронумерованных от 0 до n-1, где узел i имеет двух детей: leftChild[i] и rightChild[i]. Верните true, если и только если все заданные узлы образуют ровно одно допустимое бинарное дерево.
Если у узла i нет левого ребенка, то leftChild[i] будет равен -1, аналогично для правого ребенка.
Обратите внимание, что узлы не имеют значений и мы используем только номера узлов в этой задаче.
Пример:
Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1] Output: true👨💻 Алгоритм: 1⃣Проверка количества родителей для каждого узла: Создайте массив для отслеживания количества родителей для каждого узла. Проходите через leftChild и rightChild, увеличивая счетчик для каждого ребенка. Если какой-либо узел имеет более одного родителя, возвращайте false. 2⃣Поиск корневого узла и проверка на единственное дерево: Найдите корневой узел (узел с нулевым количеством родителей). Если корневых узлов нет или больше одного, верните false. Используйте BFS или DFS, чтобы проверить, что все узлы достижимы от корня и что нет циклов. 3⃣Проверка на достижение всех узлов: Проверьте, что количество посещенных узлов равно n. Если нет, верните false. В противном случае, верните true. 😎 Решение:
class Solution {
fun validateBinaryTreeNodes(n: Int, leftChild: IntArray, rightChild: IntArray): Boolean {
val parents = IntArray(n)
for (i in 0 until n) {
if (leftChild[i] != -1) {
parents[leftChild[i]]++
if (parents[leftChild[i]] > 1) {
return false
}
}
if (rightChild[i] != -1) {
parents[rightChild[i]]++
if (parents[rightChild[i]] > 1) {
return false
}
}
}
var root = -1
for (i in 0 until n) {
if (parents[i] == 0) {
if (root == -1) {
root = i
} else {
return false
}
}
}
if (root == -1) {
return false
}
val visited = mutableSetOf<Int>()
val queue = ArrayDeque<Int>()
queue.add(root)
while (queue.isNotEmpty()) {
val node = queue.removeFirst()
if (visited.contains(node)) {
return false
}
visited.add(node)
if (leftChild[node] != -1) {
queue.add(leftChild[node])
}
if (rightChild[node] != -1) {
queue.add(rightChild[node])
}
}
return visited.size == n
}
}1 705
Задача: 710. Random Pick with Blacklist
Сложность: hard
Вам дано целое число n и массив уникальных целых чисел blacklist. Разработайте алгоритм выбора случайного целого числа из диапазона [0, n - 1], не входящего в черный список. Любое целое число, находящееся в указанном диапазоне и не входящее в черный список, должно с равной вероятностью быть возвращено. Оптимизируйте алгоритм так, чтобы он минимизировал количество обращений к встроенной функции random вашего языка. Реализуйте класс Solution: Solution(int n, int[] blacklist) Инициализирует объект целым числом n и целым числом из черного списка blacklist. int pick() Возвращает случайное целое число в диапазоне [0, n - 1] и не входящее в черный список.
Пример:
Input ["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"] [[7, [2, 3, 5]], [], [], [], [], [], [], []] Output [null, 0, 4, 1, 6, 1, 0, 4]👨💻 Алгоритм: 1⃣Создайте маппинг для чисел, входящих в черный список, чтобы сопоставить их с числами из диапазона [n - len(blacklist), n - 1], которые не входят в черный список. 2⃣Создайте массив для хранения возможных чисел для выбора, исключая числа из черного списка. 3⃣При каждом вызове функции pick() используйте встроенную функцию random для выбора случайного индекса из массива возможных чисел и возвращайте соответствующее значение. 😎 Решение:
import kotlin.random.Random
class Solution(n: Int, blacklist: IntArray) {
private val map = mutableMapOf<Int, Int>()
private val bound = n - blacklist.size
init {
val blackset = blacklist.toSet()
var whitelist = bound
for (b in blacklist) {
if (b < bound) {
while (blackset.contains(whitelist)) {
whitelist++
}
map[b] = whitelist
whitelist++
}
}
}
fun pick(): Int {
val r = Random.nextInt(bound)
return map.getOrDefault(r, r)
}
}1 705
Задача: 634. Find the Derangement of An Array
Сложность: hard
В комбинаторной математике отклонение - это перестановка элементов множества таким образом, что ни один элемент не оказывается на прежнем месте. Вам дано целое число n. Изначально имеется массив, состоящий из n целых чисел от 1 до n в порядке возрастания, верните количество отклонений, которые он может породить. Поскольку ответ может быть огромным, верните его по модулю 109 + 7.
Пример:
Input: n = 3 Output: 2👨💻 Алгоритм: 1⃣Инициализация массива для хранения результатов Создайте массив dp для хранения количества отклонений для каждого значения от 0 до n. Установите начальные значения: dp[0] = 1 и dp[1] = 0. 2⃣Вычисление количества отклонений Используйте динамическое программирование для вычисления количества отклонений для каждого значения от 2 до n. Формула для вычисления: dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % MOD. 3⃣Возвращение результата Верните значение dp[n], которое будет количеством отклонений для n элементов, по модулю 10^9 + 7. 😎 Решение:
class Solution {
fun countDerangements(n: Int): Int {
val MOD = 1_000_000_007
if (n == 0) return 1
if (n == 1) return 0
val dp = IntArray(n + 1)
dp[0] = 1
dp[1] = 0
for (i in 2..n) {
dp[i] = ((i - 1) * (dp[i - 1] + dp[i - 2].toLong()) % MOD).toInt()
}
return dp[n]
}
}1 705
Задача: 340. Longest Substring with At Most K Distinct Characters
Сложность: medium
Дана строка s и целое число k. Верните длину самой длинной подстроки s, которая содержит не более k различных символов.
Пример:
Input: n = 27 Output: true Explanation: 27 = 3^3👨💻 Алгоритм: 1⃣Инициализация Используйте два указателя (left и right) для отслеживания текущего окна в строке. Создайте словарь для отслеживания количества каждого символа в текущем окне. Инициализируйте переменные для хранения максимальной длины подстроки (max_length). 2⃣Раздвижение окна Перемещайте правый указатель (right) по строке и обновляйте словарь. Если количество различных символов в словаре превышает k, перемещайте левый указатель (left) вправо, уменьшая счетчик символов, пока количество различных символов снова не станет меньше или равно k. 3⃣Обновление максимальной длины На каждом шаге проверяйте и обновляйте максимальную длину подстроки, если текущее окно содержит не более k различных символов. В конце верните максимальную длину подстроки. 😎 Решение:
class Solution {
fun lengthOfLongestSubstringKDistinct(s: String, k: Int): Int {
var left = 0
var right = 0
val charCount = mutableMapOf<Char, Int>()
var maxLength = 0
while (right < s.length) {
charCount[s[right]] = charCount.getOrDefault(s[right], 0) + 1
while (charCount.size > k) {
charCount[s[left]] = charCount[s[left]]!! - 1
if (charCount[s[left]] == 0) {
charCount.remove(s[left])
}
left++
}
maxLength = maxOf(maxLength, right - left + 1)
right++
}
return maxLength
}
}1 705
Задача: 1512. Number of Good Pairs
Сложность: easy
Дан массив целых чисел nums, верните количество хороших пар.
Пара (i, j) называется хорошей, если nums[i] == nums[j] и i < j.
Пример:
Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.class Solution {
fun numIdenticalPairs(nums: IntArray): Int {
var ans = 0
for (i in nums.indices) {
for (j in i + 1 until nums.size) {
if (nums[i] == nums[j]) {
ans++
}
}
}
return ans
}
}1 705
Задача: 661. Image Smoother
Сложность: easy
Дан целочисленный матрица img размером m x n, представляющая градации серого изображения. Верните изображение после применения сглаживания к каждой его ячейке.
Пример:
Input: img = [[1,1,1],[1,0,1],[1,1,1]] Output: [[0,0,0],[0,0,0],[0,0,0]] Explanation: For the points (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0 For the points (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0 For the point (1,1): floor(8/9) = floor(0.88888889) = 0👨💻 Алгоритм: 1⃣Инициализация: Создайте новую матрицу такого же размера, чтобы сохранить результат сглаживания. 2⃣Обработка каждой ячейки: Для каждой ячейки исходной матрицы найдите всех её соседей (включая саму ячейку). Вычислите среднее значение этих ячеек и сохраните его в соответствующей ячейке результирующей матрицы. 3⃣Возврат результата: Верните результирующую матрицу после применения сглаживания ко всем ячейкам. 😎 Решение:
class Solution {
fun imageSmoother(img: Array<IntArray>): Array<IntArray> {
val m = img.size
val n = img[0].size
val result = Array(m) { IntArray(n) }
for (i in 0 until m) {
for (j in 0 until n) {
var count = 0
var total = 0
for (ni in maxOf(0, i - 1)..minOf(m - 1, i + 1)) {
for (nj in maxOf(0, j - 1)..minOf(n - 1, j + 1)) {
total += img[ni][nj]
count += 1
}
}
result[i][j] = total / count
}
}
return result
}
}1 705
Задача: 347. Top K Frequent Elements
Сложность: medium
Дан массив целых чисел nums и целое число k. Верните k самых частых элементов. Вы можете вернуть ответ в любом порядке.
Пример:
Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]👨💻 Алгоритм: 1⃣Подсчет частоты: Используйте хеш-таблицу или словарь для подсчета количества вхождений каждого элемента в массиве nums. 2⃣Создание кучи: Создайте кучу, чтобы отсортировать элементы по их частоте и выбрать k самых частых элементов. 3⃣Возврат результата: Верните k самых частых элементов. 😎 Решение:
class Solution {
fun topKFrequent(nums: IntArray, k: Int): List<Int> {
val count = nums.groupingBy { it }.eachCount()
return count.entries.sortedByDescending { it.value }.take(k).map { it.key }
}
}1 705
🚨60 минут
Пожизненный PRO-доступ на easyoffer (подготовка к IT-собесам + поиск оффера) по цене одного года закрывается прямо сейчас. Один платёж — доступ навсегда.
Последнее напоминание 👇
👉 https://easyoffer.ru/pro
1 705
⚠️ 3 часа до конца акции.
Последний шанс забрать пожизненный PRO на easyoffer по цене одного года. Это полный доступ к подготовке к собесам и инструментам поиска работы (вопросы с реальных интервью, ответы сеньоров, автоотклики, тренажёры) — один раз и навсегда, вместо ежегодной оплаты.
В полночь цена возвращается к обычной.
👉 https://easyoffer.ru/pro
1 705
⏳ Ребята, сегодня заканчивается акция, о которой стоит знать, если вы в поиске работы или планируете сменить её в ближайший год.
easyoffer — это платформа для подготовки к IT-собесам и поиска оффера. Внутри:
– база реальных вопросов и live-coding задач с собесов (с частотой их встречаемости)
– эталонные ответы от Senior-разработчиков
– 1100+ записей настоящих интервью (Сбер, Яндекс, Авито, WB, OZON, МТС)
– автоотклики на hh, генератор резюме под вакансию, тренажёры собеседований
Сегодня пожизненный PRO-доступ продаётся по цене одного года — платишь один раз и пользуешься всем этим всю жизнь, включая будущие фичи. С завтрашнего дня — только обычная годовая подписка.
👉 https://easyoffer.ru/pro
1 705
Пожизненный PRO — по цене одного года.
Покупаешь один раз — пользуешься всю жизнь:
👉 https://easyoffer.ru/pro
🚀 PRO-доступ закроет 99% проблем на пути к офферу:
1. 1100+ записей реальных собеседований (включая топы: Сбер, Авито, Яндекс, WB, OZON, МТС). Видите всё изнутри: как спрашивают, как отвечают сильные кандидаты и на каких ошибках проваливаются 80%.
2. База live-coding задач и вопросов с реальных собесов — с уникальной системой вероятности их встречи. Готовитесь не вслепую, а точечно по темам, которые спрашивают чаще всего.
3. Эталонные ответы от Senior-разработчиков. Никакой воды и догадок — только чёткие структурированные решения, за которые дают «зелёный свет» к офферу.
4. Полный доступ ко всем грейдам и профессиям. Junior вы или Senior, тестировщик, разработчик или проджект — вы получаете ВСЕ материалы easyoffer без ограничений. Безлимитно, Все, Навсегда.
5. База 400+ тестовых заданий. Прокачивайте навыки на реальных задачах — тех самых, что дают перед собесом.
6. Автоотклики на hh.ru — пока вы спите, резюме уходит рекрутерам автоматически. Экономия сотен часов ручного кликанья.
7. Аналитика ТОП-требований из вакансий. Парсим рынок и показываем, какие скиллы сейчас в цене. Апгрейдите резюме точечно и проходите ATS-фильтры (они отсеивают до 75% резюме ещё до рекрутера).
8. Генератор резюме и CV под каждую вакансию. Забудьте про «универсальное» резюме — нейросеть адаптирует ваш опыт под конкретную позицию за минуту и повышает шансы на приглашение в разы.
9. Тренажёры подготовки к собеседованию:
«Реальное собеседование» — сценарий вопросов из настоящих интервью. «Проработка вопросов» — флеш-карточки по методике интервальных повторений (как Anki)
10. 🔥 Самое важное: все будущие фичи
Вы платите один раз, а продукт растёт всю жизнь. Каждое обновление, каждый новый инструмент, каждая фича, которая появится за все годы проекта, автоматически падает вам в подписку без доплат. Вы фиксируете цену года, а получаете продукт, который через пару лет будет стоить в разы дороже
⭐️ Это уникальная акция пока сайт в режиме Beta.
Успей ей воспользоваться⏳ Завтра последний день.
👉 https://easyoffer.ru/pro
1 705
🔥 Осталось 3 дня!
Пожизненный easyoffer PRO по цене одного года. Покупаешь один раз – пользуешься всю жизнь.
Что входит в PRO:
– Вопросы и задачи с реальных собеседований в конкретных компаниях
– Лучшие ответы и видео-примеры от middle/senior специалистов
– Записи реальных собеседований
– Обход фильтров ATS с топ-30 ключевых слов в резюме
– Автоотклики на hh
– Тренажёры и симуляторы для идеальной подготовки к интервью
⏳ Акция действует только до 2 сентября 23:59 по МСК
👉 Забрать PRO со скидкой 70%: https://easyoffer.ru/pro
1 705
Задача: 1005. Maximize Sum Of Array After K Negations
Сложность: easy
Учитывая целочисленный массив nums и целое число k, измените массив следующим образом: выберите индекс i и замените nums[i] на -nums[i]. Вы должны применить этот процесс ровно k раз. Вы можете выбрать один и тот же индекс i несколько раз. Верните наибольшую возможную сумму массива после его модификации таким образом.
Пример:
Input: nums = [4,2,3], k = 1 Output: 5👨💻 Алгоритм: 1⃣Сортировка массива: Отсортируйте массив nums по возрастанию, чтобы наибольшее количество раз менять самые маленькие (отрицательные) значения на их противоположные. 2⃣Модификация массива: Пройдитесь по отсортированному массиву и замените k наименьших значений на их противоположные (умножьте на -1). Если встретите 0, прекратите дальнейшие изменения, так как изменение 0 на -0 не имеет смысла. 3⃣Проверка остатка изменений: Если после первого прохода остались изменения (k нечетное), то найдите минимальное значение в измененном массиве и еще раз поменяйте его знак. Это обеспечит максимальную сумму. 😎 Решение:
class Solution {
fun largestSumAfterKNegations(nums: IntArray, k: Int): Int {
nums.sort()
var k = k
for (i in nums.indices) {
if (k > 0 && nums[i] < 0) {
nums[i] = -nums[i]
k--
}
}
if (k % 2 == 1) {
nums.sort()
nums[0] = -nums[0]
}
return nums.sum()
}
}1 705
Задача: 893. Groups of Special-Equivalent Strings
Сложность: medium
Вам дан массив строк одинаковой длины words. За один ход вы можете поменять местами любые два четных или любые два нечетных символа строки words[i]. Две строки words[i] и words[j] являются специально-эквивалентными, если после любого количества ходов words[i] == words[j].
Например, words[i] = "zzxy" и words[j] = "xyzz" являются специально-эквивалентными, потому что мы можем делать ходы "zzxy" -> "xzzy" -> "xyzz". Группа специально-эквивалентных строк из слов - это непустое подмножество слов, такое, что: каждая пара строк в группе специально-эквивалентна, и группа имеет максимально возможный размер (т.е, не существует строки words[i], не входящей в группу, такой, что words[i] является специально-эквивалентной каждой строке в группе). Верните количество групп специально-эквивалентных строк из слов.
Пример:
Input: words = ["abcd","cdab","cbad","xyzz","zzxy","zzyx"] Output: 3👨💻 Алгоритм: 1⃣Для каждой строки в массиве words создать два новых списка: один из символов на четных позициях, другой из символов на нечетных позициях. Отсортировать оба списка и объединить их в одну строку, которая будет представлять каноническую форму строки. 2⃣Использовать множество, чтобы хранить все уникальные канонические формы строк. 3⃣Размер множества будет равен количеству групп специально-эквивалентных строк. 😎 Решение:
fun numSpecialEquivGroups(words: Array<String>): Int {
val uniqueForms = mutableSetOf<String>()
for (word in words) {
val evenChars = word.filterIndexed { index, _ -> index % 2 == 0 }.toCharArray().sorted()
val oddChars = word.filterIndexed { index, _ -> index % 2 != 0 }.toCharArray().sorted()
val canonicalForm = evenChars.joinToString("") + oddChars.joinToString("")
uniqueForms.add(canonicalForm)
}
return uniqueForms.size1 705
Задача: 1019. Next Greater Node In Linked List
Сложность: medium
Вам дана голова связного списка с n узлами. Для каждого узла в списке найдите значение следующего большего узла. То есть для каждого узла найдите значение первого узла, который находится рядом с ним и имеет строго большее значение, чем он. Верните целочисленный массив answer, где answer[i] - это значение следующего большего узла ith-узла (с индексацией по 1). Если у узла ith нет следующего большего узла, установите answer[i] = 0.
Пример:
Input: head = [2,1,5] Output: [5,5,0]👨💻 Алгоритм: 1⃣Инициализация переменных: Пройдитесь по всему списку и сохраните значения узлов в массив. Инициализируйте стек для хранения индексов узлов, которые нужно обработать. 2⃣Поиск следующего большего элемента: Итерируйте по массиву значений узлов. Для каждого элемента, пока стек не пуст и текущий элемент больше, чем элемент на вершине стека, обновите массив ответов значением текущего элемента и удалите элемент из стека. Добавьте текущий индекс в стек. 3⃣Заполнение оставшихся значений: Для всех индексов, оставшихся в стеке, установите значение ответа равным 0, так как для них не найдено большего элемента. 😎 Решение:
class ListNode(var `val`: Int) {
var next: ListNode? = null
}
class Solution {
fun nextLargerNodes(head: ListNode?): IntArray {
val values = mutableListOf<Int>()
var current = head
while (current != null) {
values.add(current.`val`)
current = current.next
}
val answer = IntArray(values.size)
val stack = mutableListOf<Int>()
for (i in values.indices) {
while (stack.isNotEmpty() && values[stack.last()] < values[i]) {
answer[stack.removeAt(stack.size - 1)] = values[i]
}
stack.add(i)
}
return answer
}
}1 705
Пожизненный PRO доступ на easyoffer — по цене одного года!
До 2 сентября вы можете купить PRO навсегда.
Покупаешь один раз — пользуешься всю жизнь.
– База вопросов и задач из собеседований
– Примеры видео-ответов на вопросы
– Записи реальных собеседований
– Тренажеры "Проработка вопросов" и "Реальное собеседование"
– Аналитика требований из вакансий
– Автоотклики на вакансии
– Агрегатор вакансий (скоро)
👉 Купить PRO со скидкой 70%: https://easyoffer.ru/pro
1 705
Задача: 1053. Previous Permutation With One Swap
Сложность: medium
Учитывая массив целых положительных чисел arr (не обязательно различных), верните лексикографически наибольшую перестановку, которая меньше arr и может быть сделана ровно с одной подстановкой. Если это невозможно, то верните тот же массив. Обратите внимание, что перестановка меняет местами два числа arr[i] и arr[j].
Пример:
Input: arr = [3,2,1] Output: [3,1,2]👨💻 Алгоритм: 1⃣Определи общее количество покупателей, которые удовлетворены в минуты, когда владелец магазина не ворчлив. 2⃣Пройди по массиву, используя скользящее окно для учета эффекта от техники. 3⃣Найди максимальное количество дополнительных удовлетворенных покупателей, которые можно получить, используя технику на k минут подряд. 😎 Решение:
fun prevPermOpt1(arr: IntArray): IntArray {
val n = arr.size
var i = n - 2
while (i >= 0 && arr[i] <= arr[i + 1]) {
i--
}
if (i == -1) return arr
var j = n - 1
while (arr[j] >= arr[i] || (j < n - 1 && arr[j] == arr[j + 1])) {
j--
}
val temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
return arr
}