Уже доступно! Исследование Telegram 2025 — ключевые инсайты года 
Swift | LeetCode
Открыть в Telegram
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+bn3i_aLL0-A2ZGMy Вопросы собесов t.me/+wtkjBoN6OI5hNGEy Вакансии t.me/+3o9-Ytdiv_E5OGIy
Больше1 353
Подписчики
Нет данных24 часа
-117 дней
-1530 день
Архив постов
1 353
Задача: 604. Design Compressed String Iterator
Сложность: easy
Разработайте и реализуйте структуру данных для итератора сжатой строки. Данная сжатая строка будет в виде каждой буквы, за которой следует положительное целое число, представляющее количество этой буквы в оригинальной несжатой строке.
Реализуйте класс
StringIterator:
- next(): Возвращает следующий символ, если в оригинальной строке еще остались несжатые символы, в противном случае возвращает пробел.
- hasNext(): Возвращает true, если в оригинальной строке остались символы, которые нужно распаковать, в противном случае возвращает false.
Пример:
Input
["StringIterator", "next", "next", "next", "next", "next", "next", "hasNext", "next", "hasNext"]
[["L1e2t1C1o1d1e1"], [], [], [], [], [], [], [], [], []]
Output
[null, "L", "e", "e", "t", "C", "o", true, "d", true]
Explanation
StringIterator stringIterator = new StringIterator("L1e2t1C1o1d1e1");
stringIterator.next(); // return "L"
stringIterator.next(); // return "e"
stringIterator.next(); // return "e"
stringIterator.next(); // return "t"
stringIterator.next(); // return "C"
stringIterator.next(); // return "o"
stringIterator.hasNext(); // return True
stringIterator.next(); // return "d"
stringIterator.hasNext(); // return Trueclass StringIterator {
var res = [Character]()
var ptr = 0
init(_ s: String) {
var i = s.startIndex
while i < s.endIndex {
let ch = s[i]
i = s.index(after: i)
var num = 0
while i < s.endIndex, let digit = s[i].wholeNumberValue {
num = num * 10 + digit
i = s.index(after: i)
}
res.append(contentsOf: repeatElement(ch, count: num))
}
}
func next() -> Character {
guard hasNext() else { return " " }
let char = res[ptr]
ptr += 1
return char
}
func hasNext() -> Bool {
return ptr < res.count
}
}1 353
Задача: 763. Partition Labels
Сложность: medium
Вам дана строка s. Мы хотим разбить строку на как можно больше частей так, чтобы каждая буква встречалась не более чем в одной части. Обратите внимание, что разбиение выполняется так, чтобы после конкатенации всех частей по порядку получилась строка s. Верните список целых чисел, представляющих размер этих частей.
Пример:
Input: s = "ababcbacadefegdehijhklij" Output: [9,7,8]👨💻 Алгоритм: 1⃣Создайте словарь для хранения последней позиции каждой буквы в строке. 2⃣Пройдите по строке, отслеживая максимальную позицию текущей части. 3⃣Когда текущая позиция совпадает с максимальной позицией, завершите часть и начните новую. 😎 Решение:
func partitionLabels(_ s: String) -> [Int] {
var lastPos = [Character: Int]()
for (idx, char) in s.enumerated() {
lastPos[char] = idx
}
var partitions = [Int]()
var j = 0, anchor = 0
for (i, char) in s.enumerated() {
j = max(j, lastPos[char]!)
if i == j {
partitions.append(i - anchor + 1)
anchor = i + 1
}
}
return partitions
}1 353
Задача: 1539. Kth Missing Positive Number
Сложность: easy
Дан массив
arr из положительных целых чисел, отсортированных в строго возрастающем порядке, и целое число k.
Верните k-й положительный целочисленный элемент, который отсутствует в этом массиве.
Пример:
Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.class Solution {
func findKthPositive(_ arr: [Int], _ k: Int) -> Int {
var k = k
if k <= arr[0] - 1 {
return k
}
k -= arr[0] - 1
let n = arr.count
for i in 0..<n - 1 {
let currMissing = arr[i + 1] - arr[i] - 1
if k <= currMissing {
return arr[i] + k
}
k -= currMissing
}
return arr[n - 1] + k
}
}1 353
Осталось 3 часа до конца акции:
«Пожизненный PRO тариф — по цене 1 года»
Поиск работы отнимает силы, время и веру в себя, но не у тех кто использует easyoffer PRO. Успей сделать самую выгодную инвестицию в развитие своей карьеры.
Акция закончится уже сегодня 23 июня 23:59 по мск:
👉 https://easyoffer.ru/pro
1 353
Задача: 1356. Sort Integers by The Number of 1 Bits
Сложность: easy
Дан целочисленный массив arr. Отсортируйте целые числа в массиве по возрастанию числа единиц в их двоичном представлении, а в случае, если у двух или более чисел одинаковое количество единиц, отсортируйте их по возрастанию.
Верните массив после сортировки.
Пример:
Input: arr = [1024,512,256,128,64,32,16,8,4,2,1] Output: [1,2,4,8,16,32,64,128,256,512,1024] Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.👨💻 Алгоритм: 1⃣Создание функции для подсчета единиц: Создайте функцию, которая принимает целое число и возвращает количество единиц в его двоичном представлении. 2⃣Сортировка массива: Используйте встроенную функцию сортировки, передавая ей пользовательскую функцию сравнения, которая использует количество единиц в двоичном представлении чисел для сортировки. Если количество единиц одинаковое, используйте само число для сортировки. 3⃣Возврат отсортированного массива: Верните отсортированный массив. 😎 Решение:
class Solution {
func sortByBits(_ arr: [Int]) -> [Int] {
return arr.sorted { (a, b) -> Bool in
let countA = a.nonzeroBitCount
let countB = b.nonzeroBitCount
return countA == countB ? a < b : countA < countB
}
}
}1 353
Задача: 128. Longest Consecutive Sequence
Сложность: Medium
Дан несортированный массив целых чисел nums. Верните длину самой длинной последовательности последовательных элементов.
Необходимо написать алгоритм, который работает за время O(n).
Пример:
Input: nums = [100,4,200,1,3,2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.👨💻 Алгоритм: 1⃣Проверка базового случая: Перед началом работы проверяем базовый случай с пустым массивом. Самая длинная последовательность в пустом массиве, очевидно, равна 0, поэтому мы можем просто вернуть это значение. 2⃣Обработка чисел в массиве: Для всех других случаев мы сортируем массив nums и рассматриваем каждое число, начиная со второго (поскольку нам нужно сравнивать каждое число с предыдущим). Если текущее число и предыдущее равны, то текущая последовательность не удлиняется и не прерывается, поэтому мы просто переходим к следующему числу. Если числа не равны, то нужно проверить, удлиняет ли текущее число последовательность (т.е. nums[i] == nums[i-1] + 1). Если удлиняет, то мы увеличиваем наш текущий счёт и продолжаем. 3⃣Завершение обработки и возврат результата: В противном случае последовательность прерывается, и мы записываем нашу текущую последовательность и сбрасываем её до 1 (чтобы включить число, которое прервало последовательность). Возможно, что последний элемент массива nums является частью самой длинной последовательности, поэтому мы возвращаем максимум из текущей последовательности и самой длинной. 😎 Решение:
func longestConsecutive(_ nums: [Int]) -> Int {
var longestStreak = 0
let numSet = Set(nums)
for num in numSet {
if !numSet.contains(num - 1) {
var currentNum = num
var currentStreak = 1
while numSet.contains(currentNum + 1) {
currentNum += 1
currentStreak += 1
}
longestStreak = max(longestStreak, currentStreak)
}
}
return longestStreak
}1 353
Последний день акции:
«Пожизненный PRO тариф — по цене 1 года»
🚀 PRO включает:
– Полный доступ ко всем грейдам и профессиям
– База live-coding задач и вопросов из технических собеседований с вероятностью их встречи
– Примеры лучших ответов от Senior разработчиков
– 1100+ записи реальных собеседований, в том числе в топовые компании (Сбер, Авито, Яндекс, WB, OZON, МТС и др.)
– База 400+ тестовых заданий от компаний.
– Автоотклики на вакансии в хедхантер
– Аналитика ТОП-требований из вакансий для лучшего написания резюме и прохождения ATS систем рекрутеров
– Генератор уникального резюме и CV под каждую вакансию
– Тренажеры подготовки к собеседованию: «Реальное собеседование» и «Проработка вопросов» по методике интервальных повторений (как Anki)
– (скоро) Агрегатор вакансий
– (скоро) Сообщество
Акция закончится уже сегодня 23 июня 23:59 по мск:
👉 https://easyoffer.ru/pro
1 353
Задача: 1295. Find Numbers with Even Number of Digits
Сложность: easy
Дан массив чисел nums. Верните количество чисел в массиве, которые содержат четное количество цифр.
Пример:
Input: nums = [12,345,2,6,7896] Output: 2 Explanation: 12 contains 2 digits (even number of digits). 345 contains 3 digits (odd number of digits). 2 contains 1 digit (odd number of digits). 6 contains 1 digit (odd number of digits). 7896 contains 4 digits (even number of digits). Therefore only 12 and 7896 contain an even number of digits.👨💻 Алгоритм: 1⃣Определите вспомогательную функцию hasEvenDigits, которая принимает num в качестве входных данных и возвращает true, если количество цифр четное, иначе возвращает false. 2⃣Внутри функции hasEvenDigits. Инициализируйте переменную digitCount значением 0. Пока num не равно нулю: Увеличивайте digitCount на 1. Делите num на 10. Возвращайте digitCount & 1 == 0. 3⃣В функции findNumbers. Инициализируйте переменную evenDigitCount значением 0. Для каждого числа num в массиве nums, проверяйте, возвращает ли hasEvenDigits(num) значение true. Если да, увеличивайте evenDigitCount на 1. Возвращайте evenDigitCount. 😎 Решение:
class Solution {
func hasEvenDigits(_ num: Int) -> Bool {
var digitCount = 0
var num = num
while num > 0 {
digitCount += 1
num /= 10
}
return (digitCount & 1) == 0
}
func findNumbers(_ nums: [Int]) -> Int {
var evenDigitCount = 0
for num in nums {
if hasEvenDigits(num) {
evenDigitCount += 1
}
}
return evenDigitCount
}
}1 353
Пожизненный PRO тариф — по цене 1 года.
Покупаешь один раз — пользуешься всю жизнь:
👉 https://easyoffer.ru/pro
🚀 PRO-доступ закроет 99% проблем на пути к офферу:
1. Полный доступ ко всем грейдам и профессиям. Не важно, Junior вы или Senior, Тестировщик, Разработчик, Проджект — вы получите материалы под ваш текущий уровень и цели, без ограничений.
2. База live-coding задач и вопросов с реальных собесов с уникальной системой вероятности их встречи. Вы будете готовиться не вслепую, а точечно по тем темам, которые спрашивают чаще всего.
3. Эталонные ответы от Senior-разработчиков. Никакой воды и догадок — только четкие, структурированные решения, за которые дают «зеленый свет» к офферу
4. 1100+ записей реальных собеседований (включая топы: Сбер, Авито, Яндекс, WB, OZON, МТС). Вы увидите всё изнутри: как спрашивают, как отвечают сильные кандидаты и на каких ошибках проваливаются 80% проходящих.
5. База 400+ тестовых заданий. Если вы еще студент, то практикуйтесь на решении задач, которые помогут попасть на собес
6. Автоотклики на Хедхантере — пока вы спите, ваше резюме летит к рекрутерам автоматически. Это экономия сотен часов ручного кликанья.
7. Аналитика ТОП-требований из вакансий. Мы парсим рынок и показываем, какие скиллы сейчас в цене. Это позволит вам точечно апгрейдить резюме и проходить суровые ATS-фильтры (которые отсеивают до 75% резюме еще до просмотра рекрутером).
8. Генератор уникального резюме и CV под каждую вакансию. Забудьте про «универсальное» резюме — нейросеть адаптирует ваш опыт под конкретную позицию за минуту, повышая шансы на приглашение в разы.
9. Тренажеры подготовки к собеседованию:
«Реальное собеседование» — сценарий вопросов из реальных интервью
«Проработка вопросов» — флеш карточки с вопросами/ответами по методике интервальных повторений (как Anki)
10. (Скоро) Агрегатор вакансий — все вакансии из HH, Telegram, LinkedIn и других площадок в одной ленте.
11. (Скоро) Закрытое комьюнити — нетворкинг и помощь в сложных вопросах от таких же целеустремленных айтишников.
Завтра последний день акции:
👉 https://easyoffer.ru/pro
1 353
Задача: 1359. Count All Valid Pickup and Delivery Options
Сложность: hard
Дано n заказов, каждый из которых состоит из услуги забора и доставки.
Посчитайте все возможные допустимые последовательности забора/доставки, такие что доставка(i) всегда идет после забора(i).
Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Пример:
Input: n = 1 Output: 1 Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.👨💻 Алгоритм: 1⃣Инициализация: Используйте динамическое программирование для хранения количества допустимых последовательностей для каждого количества заказов от 1 до n. 2⃣Рекурсивное вычисление: Для каждого количества заказов k используйте рекурсивную формулу для вычисления количества допустимых последовательностей, учитывая, что каждая новая пара (забор и доставка) может быть вставлена в любую из существующих позиций. 3⃣Возвращение результата: Верните результат для n заказов, применяя модуль 10^9 + 7 для предотвращения переполнения. 😎 Решение:
class Solution {
func countOrders(_ n: Int) -> Int {
let MOD = 1_000_000_007
var dp = [Int](repeating: 0, count: n + 1)
dp[0] = 1
for i in 1...n {
dp[i] = dp[i - 1] * (2 * i - 1) * i % MOD
}
return dp[n]
}
}1 353
Задача: 96. Unique Binary Search Trees
Сложность: medium
Дано целое число n. Верните количество структурно уникальных деревьев бинарного поиска (BST), которые содержат ровно n узлов с уникальными значениями от 1 до n.
Пример:
Input: n = 3 Output: 5👨💻 Алгоритм: 1⃣Задача состоит в том, чтобы рассчитать количество уникальных BST (бинарных деревьев поиска). Для этого мы можем определить две функции: G(n): количество уникальных BST для последовательности длины n. F(i, n): количество уникальных BST, где число i является корнем BST (1 ≤ i ≤ n). Как видно, G(n) - это именно та функция, которая нам нужна для решения задачи. 2⃣Позднее мы увидим, что G(n) можно вывести из F(i, n), которая, в свою очередь, рекурсивно относится к G(n). Следуя идее из раздела "Интуиция", мы видим, что общее количество уникальных BST G(n) равно сумме BST F(i, n) с перечислением каждого числа i (1 ≤ i ≤ n) в качестве корня. Таким образом, G(n) = ∑ F(i, n) для i от 1 до n. В частности, для базовых случаев есть только одна комбинация для построения BST из последовательности длиной 1 (только корень) или ничего (пустое дерево). То есть G(0) = 1, G(1) = 1. 3⃣Дана последовательность от 1 до n, мы выбираем число i из последовательности в качестве корня, тогда количество уникальных BST с указанным корнем, определенным как F(i, n), является декартовым произведением количества BST для его левого и правого поддеревьев, как показано ниже: Например, F(3,7) - количество уникальных деревьев BST с числом 3 в качестве корня. Для построения уникального BST из всей последовательности [1, 2, 3, 4, 5, 6, 7] с 3 в качестве корня, мы должны построить поддерево из его левой подпоследовательности [1, 2] и другое поддерево из правой подпоследовательности [4, 5, 6, 7], а затем соединить их вместе (то есть декартово произведение). Теперь хитрость заключается в том, что мы можем рассматривать количество уникальных BST из последовательности [1,2] как G(2), и количество уникальных BST из последовательности [4, 5, 6, 7] как G(4). Для G(n) не имеет значения содержание последовательности, а только длина последовательности. Следовательно, F(3,7) = G(2)⋅G(4). Обобщая пример, мы можем вывести следующую формулу: F(i, n) = G(i−1)⋅G(n−i) Объединяя формулы (1), (2), мы получаем рекурсивную формулу для G(n), то есть G(n) = ∑ G(i−1)⋅G(n−i) для i от 1 до n. Чтобы вычислить результат функции, мы начинаем с меньшего числа, так как значение G(n) зависит от значений G(0)...G(n−1). 😎 Решение:
class Solution {
func numTrees(_ n: Int) -> Int {
var G = Array(repeating: 0, count: n + 1)
G[0] = 1
G[1] = 1
for i in 2...n {
for j in 1...i {
G[i] += G[j - 1] * G[i - j]
}
}
return G[n]
}
}1 353
Задача: 1038. Binary Search Tree to Greater Sum Tree
Сложность: medium
Получив корень двоичного дерева поиска (BST), преобразуйте его в большее дерево таким образом, чтобы каждый ключ исходного BST был заменен на исходный ключ плюс сумма всех ключей, превышающих исходный ключ в BST. Напомним, что двоичное дерево поиска - это дерево, удовлетворяющее следующим ограничениям: левое поддерево узла содержит только узлы с ключами меньше, чем ключ узла. Правое поддерево узла содержит только узлы с ключами больше, чем ключ узла. И левое, и правое поддеревья должны быть двоичными деревьями поиска.
Пример:
Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]👨💻 Алгоритм: 1⃣Обратный обход in-order: Пройдите по дереву в порядке "правый, корень, левый" (обратный in-order обход). Это обеспечит посещение узлов в порядке убывания их значений. 2⃣Накопление суммы: Во время обхода поддерживайте переменную для хранения накопленной суммы. На каждом узле добавляйте значение узла к накопленной сумме и обновляйте значение узла этой накопленной суммой. 3⃣Преобразование узлов: Преобразуйте значение каждого узла в накопленную сумму. 😎 Решение:
public class TreeNode {
public var val: Int
public var left: TreeNode?
public var right: TreeNode?
public init() { self.val = 0; self.left = nil; self.right = nil; }
public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
self.val = val
self.left = left
self.right = right
}
}
class Solution {
var sum = 0
func bstToGst(_ root: TreeNode?) -> TreeNode? {
reverseInorder(root)
return root
}
func reverseInorder(_ node: TreeNode?) {
guard let node = node else { return }
reverseInorder(node.right)
sum += node.val
node.val = sum
reverseInorder(node.left)
}
}1 353
Привет, ребята!
У нас для вас отличные новости — на easyoffer вышло сразу несколько крупных обновлений:
1. Автоотклики на HeadHunter
Снова работают в полную силу — можно смело возвращаться к активному поиску.
2. Новый раздел «Резюмейкер»
Теперь вы можете быстро создавать уникальные резюме, адаптированные под каждую вакансию, и сразу добавлять сопроводительное письмо. Это заметно повышает шансы получить приглашение на собеседование.
3. База вопросов стала чище
Мы навели порядок и удалили около 30% дубликатов.
Ориентироваться стало проще.
––––––––––––––––––
🔥 Акция в честь обновления
Пожизненный тариф easyoffer PRO — по цене одного года.
Успейте до 23 июня:
👉 https://easyoffer.ru/pro
––––––––––––––––––
Что дальше?
В ближайшие пару недель добавим ещё два раздела:
1. Сообщество с чатами по всем профессиональным направлениям.
2. Агрегатор вакансий, чтобы поиск работы стал ещё удобнее.
1 353
Задача: 1365. How Many Numbers Are Smaller Than the Current Number
Сложность: easy
Дан массив nums. Для каждого элемента nums[i] определите, сколько чисел в массиве меньше его. То есть, для каждого nums[i] вам нужно посчитать количество допустимых j, таких что j != i и nums[j] < nums[i].
Верните ответ в виде массива.
Пример:
Input: nums = [6,5,4,8] Output: [2,1,0,3]👨💻 Алгоритм: 1⃣Создание копии и сортировка массива: Создайте отсортированную копию массива nums, чтобы легко находить количество элементов, меньших текущего. 2⃣Поиск индекса каждого элемента: Для каждого элемента nums[i] найдите его индекс в отсортированной копии массива. Этот индекс указывает количество элементов, меньших nums[i]. 3⃣Формирование ответа: Сформируйте массив ответов, где каждый элемент будет соответствовать количеству чисел, меньших текущего. 😎 Решение:
class Solution {
func smallerNumbersThanCurrent(_ nums: [Int]) -> [Int] {
let sortedNums = nums.sorted()
var result = [Int]()
for num in nums {
result.append(sortedNums.firstIndex(of: num)!)
}
return result
}
}1 353
Задача: 190. Reverse Bits
Сложность: easy
Переверните биты заданного 32-битного беззнакового целого числа.
Пример:
Input: n = 00000010100101000001111010011100 Output: 964176192 (00111001011110000010100101000000) Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000. Example 2:👨💻 Алгоритм: 1⃣Итерируем по байтам целого числа, используя побитовую операцию И (n & 0xff) с маской 11111111, чтобы извлечь крайний правый байт числа. 2⃣Для каждого байта сначала переворачиваем биты внутри байта с помощью функции reverseByte(byte). Затем сдвигаем перевернутые биты на их окончательные позиции. 3⃣В функции reverseByte(byte) используем технику мемоизации, которая сохраняет результат функции и возвращает его непосредственно при последующих вызовах с тем же входным значением. Мемоизация — это компромисс между использованием памяти и объемом вычислений. 😎 Решение:
class Solution {
var cache = [UInt32: UInt32]()
func reverseByte(_ byte: UInt32) -> UInt32 {
if let cachedValue = cache[byte] {
return cachedValue
}
let value = ((byte * 0x0202020202) & 0x010884422010) % 1023
cache[byte] = value
return value
}
func reverseBits(_ n: UInt32) -> UInt32 {
var ret: UInt32 = 0
var power: UInt32 = 24
var n = n
while n != 0 {
ret += reverseByte(n & 0xff) << power
n = n >> 8
power -= 8
}
return ret
}
}1 353
Задача: 141. Linked List Cycle
Сложность: easy
Дана переменная head, которая является началом связного списка. Определите, содержит ли связный список цикл.
Цикл в связном списке существует, если существует узел в списке, до которого можно добраться снова, последовательно следуя по указателю next. Внутренне переменная pos используется для обозначения индекса узла, к которому подключен указатель next последнего узла. Обратите внимание, что pos не передается в качестве параметра.
Верните true, если в связном списке есть цикл. В противном случае верните false.
Пример:
Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).👨💻 Алгоритм: 1⃣Инициализация структуры данных: Создайте хеш-таблицу (или множество) для хранения ссылок на узлы, чтобы отслеживать уже посещённые узлы. 2⃣Обход списка: Перемещайтесь по связному списку, начиная с головы (head), и проверяйте каждый узел по очереди. 3⃣Проверка на цикл: Если текущий узел равен null, это означает, что вы достигли конца списка, и список не имеет циклов. В этом случае верните false. Если текущий узел уже содержится в хеш-таблице, это означает, что вы вернулись к ранее посещённому узлу, и, следовательно, в списке присутствует цикл. Верните true. Если ни одно из этих условий не выполнено, добавьте текущий узел в хеш-таблицу и продолжите обход списка. 😎 Решение:
class ListNode {
var val: Int
var next: ListNode?
init(_ val: Int, _ next: ListNode? = nil) {
self.val = val
self.next = next
}
}
class Solution {
func hasCycle(_ head: ListNode?) -> Bool {
var nodesSeen = Set<ListNode>()
var current = head
while current != nil {
if nodesSeen.contains(current!) {
return true
}
nodesSeen.insert(current!)
current = current?.next
}
return false
}
}1 353
Задача: 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 {
func hIndex(_ citations: [Int]) -> Int {
let n = citations.count
var left = 0
var right = n - 1
while left <= right {
let 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 353
Задача: 91. Decode Ways
Сложность: medium
Сообщение, содержащее буквы от A до Z, можно закодировать в числа с использованием следующего соответствия:
- 'A' -> "1"
- 'B' -> "2"
- ...
- 'Z' -> "26"
Для декодирования закодированного сообщения все цифры должны быть сгруппированы и затем отображены обратно в буквы с использованием обратного соответствия (существует несколько способов). Например, "11106" можно представить как:
- "AAJF" с группировкой (1 1 10 6)
- "KJF" с группировкой (11 10 6)
Обратите внимание, что группировка (1 11 06) недопустима, потому что "06" не может быть преобразовано в 'F', так как "6" отличается от "06".
Для данной строки s, содержащей только цифры, верните количество способов декодирования.
Тестовые случаи сформированы таким образом, что ответ укладывается в 32-битное целое число.
Пример:
Input: s = "12" Output: 2 Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).👨💻 Алгоритм: 1⃣Входим в рекурсию с данной строкой, начиная с индекса 0. 2⃣Для окончательного случая рекурсии мы проверяем конец строки. Если мы достигли конца строки, возвращаем 1. Каждый раз, когда мы входим в рекурсию, это для подстроки исходной строки. Если первый символ в подстроке равен 0, то прекращаем этот путь, возвращая 0. Таким образом, этот путь не будет влиять на количество способов. 3⃣Мемоизация помогает снизить сложность, которая иначе была бы экспоненциальной. Мы проверяем словарь memo, чтобы увидеть, существует ли уже результат для данной подстроки. Если результат уже находится в memo, мы возвращаем этот результат. В противном случае количество способов для данной строки определяется путем рекурсивного вызова функции с индексом +1 для следующей подстроки и индексом +2 после проверки на валидность двузначного декодирования. Результат также сохраняется в memo с ключом как текущий индекс, чтобы сохранить его для будущих пересекающихся подзадач. 😎 Решение:
import Foundation
class Solution {
private var memo: [Int: Int] = [:]
private func recursiveWithMemo(_ index: Int, _ s: String) -> Int {
if index == s.count {
return 1
}
let startIndex = s.index(s.startIndex, offsetBy: index)
let firstChar = s[startIndex]
if firstChar == "0" {
return 0
}
if index == s.count - 1 {
return 1
}
if let cachedResult = memo[index] {
return cachedResult
}
let nextIndex = s.index(after: startIndex)
var answer = recursiveWithMemo(index + 1, s)
if index < s.count - 1 {
let secondIndex = s.index(after: nextIndex)
let range = startIndex..<secondIndex
let number = Int(s[range])!
if number <= 26 {
answer += recursiveWithMemo(index + 2, s)
}
}
memo[index] = answer
return answer
}
func numDecodings(_ s: String) -> Int {
return recursiveWithMemo(0, s)
}
}1 353
Задача: 1129. Shortest Path with Alternating Colors
Сложность: medium
Вам дано целое число n, количество узлов в ориентированном графе, где узлы помечены от 0 до n - 1. Каждое ребро в этом графе может быть красным или синим, и могут быть самопетли и параллельные ребра.
Вам даны два массива redEdges и blueEdges, где:
redEdges[i] = [ai, bi] указывает, что в графе существует направленное красное ребро от узла ai к узлу bi, и
blueEdges[j] = [uj, vj] указывает, что в графе существует направленное синее ребро от узла uj к узлу vj.
Верните массив answer длины n, где каждый answer[x] — это длина кратчайшего пути от узла 0 до узла x, такого что цвета ребер чередуются вдоль пути, или -1, если такого пути не существует.
Пример:
Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = [] Output: [0,1,-1]👨💻 Алгоритм: 1⃣Создание структуры данных и инициализация: Создайте список смежности adj, который будет содержать пары (сосед, цвет) для каждого узла. Создайте массив answer длиной n, инициализированный значением -1, чтобы хранить длину кратчайшего пути для каждого узла. Создайте 2D массив visit для отслеживания, были ли узлы посещены с использованием ребра определённого цвета. 2⃣Инициализация очереди и начальных условий: Создайте очередь для хранения трёх значений (узел, количество шагов, цвет предыдущего ребра). Добавьте в очередь начальный узел (0, 0, -1) и установите visit[0][0] и visit[0][1] в true, так как повторное посещение узла 0 бессмысленно. 3⃣Обработка очереди и обновление результата: Пока очередь не пуста, извлекайте элемент из очереди и получайте (узел, количество шагов, цвет предыдущего ребра). Для каждого соседа, если сосед не был посещён с использованием ребра текущего цвета и текущий цвет не равен предыдущему, обновите массив answer и добавьте соседа в очередь. 😎 Решение:
class Solution {
func shortestAlternatingPaths(_ n: Int, _ redEdges: [[Int]], _ blueEdges: [[Int]]) -> [Int] {
var adj = [Int: [[Int]]]()
for redEdge in redEdges {
adj[redEdge[0], default: []].append([redEdge[1], 0])
}
for blueEdge in blueEdges {
adj[blueEdge[0], default: []].append([blueEdge[1], 1])
}
var answer = [Int](repeating: -1, count: n)
var visit = Array(repeating: [false, false], count: n)
var queue = [(0, 0, -1)]
answer[0] = 0
visit[0][0] = true
visit[0][1] = true
while !queue.isEmpty {
let (node, steps, prevColor) = queue.removeFirst()
if let neighbors = adj[node] {
for neighbor in neighbors {
let nextNode = neighbor[0]
let color = neighbor[1]
if !visit[nextNode][color] && color != prevColor {
if answer[nextNode] == -1 {
answer[nextNode] = steps + 1
}
visit[nextNode][color] = true
queue.append((nextNode, steps + 1, color))
}
}
}
}
return answer
}
}1 353
Задача: 1200. Minimum Absolute Difference
Сложность: easy
Дан массив различных целых чисел arr, найдите все пары элементов с минимальной абсолютной разницей между любыми двумя элементами.
Верните список пар в порядке возрастания (по отношению к парам), каждая пара [a, b] следует условиям:
a, b из arr
a < b
b - a равна минимальной абсолютной разнице между любыми двумя элементами в arr
Пример:
Input: arr = [4,2,1,3] Output: [[1,2],[2,3],[3,4]] Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.👨💻 Алгоритм: 1⃣Инициализация вспомогательного массива: Найдите минимальный элемент minElement и максимальный элемент maxElement в массиве arr. Инициализируйте вспомогательный массив line размером maxElement - minElement + 1 и установите смещение shift равным -minElement. Пройдите по массиву arr и для каждого элемента value увеличьте значение в индексе value + shift на 1. 2⃣Поиск минимальной абсолютной разницы: Пройдите по вспомогательному массиву line, начиная с индекса, соответствующего минимальному элементу. Проверьте значения на каждом индексе curr: - если line[curr] равно 0, пропустите этот индекс. - если line[curr] равно 1, сравните абсолютную разницу текущей пары currPairDiff с минимальной найденной разницей minPairDiff. - если currPairDiff больше minPairDiff, продолжайте. - если currPairDiff равно minPairDiff, добавьте эту пару в список ответов. - если currPairDiff меньше minPairDiff, очистите список ответов, добавьте эту пару и обновите minPairDiff. 3⃣Возврат результата: После прохождения всех элементов массива line, список ответов будет содержать все пары с минимальной абсолютной разницей. Верните список ответов. 😎 Решение:
class Solution {
func minimumAbsDifference(_ arr: [Int]) -> [[Int]] {
let sortedArr = arr.sorted()
var minDiff = Int.max
var result = [[Int]]()
for i in 1..<sortedArr.count {
let diff = sortedArr[i] - sortedArr[i - 1]
if diff < minDiff {
minDiff = diff
result = [[sortedArr[i - 1], sortedArr[i]]]
} else if diff == minDiff {
result.append([sortedArr[i - 1], sortedArr[i]])
}
}
return result
}
}