Уже доступно! Исследование Telegram 2025 — ключевые инсайты года 
Swift | LeetCode
Открыть в Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Больше1 343
Подписчики
-424 часа
-97 дней
-2230 день
Архив постов
1 343
Задача: 988. Smallest String Starting From Leaf
Сложность: medium
Дан корень бинарного дерева, где каждый узел имеет значение в диапазоне [0, 25], представляющее буквы от 'a' до 'z'.
Верните лексикографически наименьшую строку, которая начинается с листа этого дерева и заканчивается у корня.
Напоминаем, что любая более короткая префиксная строка является лексикографически меньшей.
Например, "ab" лексикографически меньше, чем "aba".
Лист узла - это узел, у которого нет потомков.
Пример:
Input: root = [0,1,2,3,4,3,4] Output: "dba"👨💻 Алгоритм: 1⃣Инициализация и подготовка: Создайте переменную ans и установите ее значение как максимальное возможное (например, "~" для строк). Определите вспомогательную функцию dfs, которая будет выполнять обход дерева в глубину (DFS), принимая текущий узел и путь как аргументы. 2⃣Обход дерева: Если текущий узел пуст (null), просто вернитесь из функции. Добавьте текущий символ (соответствующий значению узла) в начало строки пути. Если текущий узел является листом (не имеет потомков), сравните текущий путь с ans и обновите ans, если текущий путь лексикографически меньше. Рекурсивно вызовите dfs для левого и правого потомков текущего узла. 3⃣Возврат результата: Вызовите функцию dfs с корневым узлом и пустым путем. Верните значение переменной ans, содержащее лексикографически наименьший путь от листа до корня. 😎 Решение:
class Solution {
var ans = "~"
func smallestFromLeaf(_ root: TreeNode?) -> String {
dfs(root, "")
return ans
}
func dfs(_ node: TreeNode?, _ path: String) {
guard let node = node else { return }
let currentPath = String(UnicodeScalar(node.val + 97)!) + path
if node.left == nil && node.right == nil {
ans = min(ans, currentPath)
}
dfs(node.left, currentPath)
dfs(node.right, currentPath)
}
}1 343
Задача: 217. Contains Duplicate
Сложность: easy
Дан массив целых чисел nums. Верните true, если любое значение появляется в массиве хотя бы дважды, и верните false, если каждый элемент уникален.
Пример:
Input: nums = [1,2,3,4] Output: false👨💻 Алгоритм: 1⃣Отсортируйте массив nums по возрастанию. 2⃣Итерируйте по отсортированному массиву и сравнивайте каждое число с следующим. 3⃣Если любое число совпадает с следующим, верните true. Если цикл завершится без совпадений, верните false. 😎 Решение:
func containsDuplicate(_ nums: [Int]) -> Bool {
let sortedNums = nums.sorted()
for i in 0..<sortedNums.count - 1 {
if sortedNums[i] == sortedNums[i + 1] {
return true
}
}
return false
}1 343
Задача: 1026. Maximum Difference Between Node and Ancestor
Сложность: medium
Учитывая корень бинарного дерева, найдите максимальное значение v, для которого существуют различные вершины a и b, где v = |a.val - b.val| и a является предком b. Вершина a является предком b, если: любой ребенок a равен b или любой ребенок a является предком b.
Пример:
Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7public 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 {
func maxAncestorDiff(_ root: TreeNode?) -> Int {
func dfs(_ node: TreeNode?, _ min_val: Int, _ max_val: Int) -> Int {
guard let node = node else { return max_val - min_val }
let min_val = min(min_val, node.val)
let max_val = max(max_val, node.val)
let left = dfs(node.left, min_val, max_val)
let right = dfs(node.right, min_val, max_val)
return max(left, right)
}
return dfs(root, root!.val, root!.val)
}
}1 343
Задача: 731. My Calendar II
Сложность: medium
Вы создаете программу для использования в качестве календаря. Мы можем добавить новое событие, если его добавление не приведет к тройному бронированию. Тройное бронирование происходит, когда три события имеют некоторое непустое пересечение (т.е, Событие можно представить в виде пары целых чисел start и end, которая представляет собой бронирование на полуоткрытом интервале [start, end), диапазоне вещественных чисел x таких, что start <= x < end. Реализация класса MyCalendarTwo: MyCalendarTwo() Инициализирует объект календаря. boolean book(int start, int end) Возвращает true, если событие может быть успешно добавлено в календарь, не вызывая тройного бронирования. В противном случае возвращается false и событие не добавляется в календарь.
Пример:
Input ["MyCalendarTwo", "book", "book", "book", "book", "book", "book"] [[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]] Output [null, true, true, true, false, true, true]👨💻 Алгоритм: 1⃣Создайте два списка: один для отслеживания всех событий, второй для отслеживания пересечений. подпоследовательностей. 2⃣При добавлении нового события сначала проверьте, не пересекается ли оно с любыми существующими пересечениями. 3⃣Если пересечение не обнаружено, добавьте новое событие и обновите список пересечений при необходимости. 😎 Решение:
class MyCalendarTwo {
var events: [(Int, Int)]
var overlaps: [(Int, Int)]
init() {
events = []
overlaps = []
}
func book(_ start: Int, _ end: Int) -> Bool {
for (os, oe) in overlaps {
if start < oe && end > os {
return false
}
}
for (es, ee) in events {
if start < ee && end > es {
overlaps.append((max(start, es), min(end, ee)))
}
}
events.append((start, end))
return true
}
}1 343
Задача: 896. Monotonic Array
Сложность: easy
Массив является монотонным, если он либо монотонно возрастает, либо монотонно убывает. Массив nums является монотонно возрастающим, если для всех i <= j, nums[i] <= nums[j]. Массив nums является монотонно убывающим, если для всех i <= j, nums[i] >= nums[j]. Если задан целочисленный массив nums, верните true, если данный массив монотонный, или false в противном случае.
Пример:
Input: nums = [1,2,2,3] Output: true👨💻 Алгоритм: 1⃣Определить два флага: increasing и decreasing. 2⃣Пройтись по массиву: Если текущий элемент больше следующего, установить increasing в false. Если текущий элемент меньше следующего, установить decreasing в false. 3⃣Вернуть true, если хотя бы один из флагов true, иначе вернуть false. 😎 Решение:
func isMonotonic(_ nums: [Int]) -> Bool {
var increasing = true
var decreasing = true
for i in 1..<nums.count {
if nums[i] > nums[i - 1] {
decreasing = false
}
if nums[i] < nums[i - 1] {
increasing = false
}
}
return increasing || decreasing
}1 343
Задача: 654. Maximum Binary Tree
Сложность: medium
Вам дан целочисленный массив nums без дубликатов. Из nums можно рекурсивно построить максимальное двоичное дерево, используя следующий алгоритм: создайте корневой узел, значение которого равно максимальному значению в nums. Рекурсивно постройте левое поддерево по префиксу подмассива слева от максимального значения. Рекурсивно постройте правое поддерево по суффиксу подмассива справа от максимального значения. Верните максимальное двоичное дерево, построенное из nums.
Пример:
Input: nums = [3,2,1,6,0,5] Output: [6,3,5,null,2,0,null,null,1]👨💻 Алгоритм: 1⃣Найдите максимальное значение в текущем подмассиве и создайте узел с этим значением. 2⃣Рекурсивно постройте левое поддерево для подмассива слева от максимального значения. 3⃣Рекурсивно постройте правое поддерево для подмассива справа от максимального значения. 😎 Решение:
public class TreeNode {
public var val: Int
public var left: TreeNode?
public var right: TreeNode?
public init(_ val: Int) {
self.val = val
self.left = nil
self.right = nil
}
}
func constructMaximumBinaryTree(_ nums: [Int]) -> TreeNode? {
guard !nums.isEmpty else { return nil }
let maxIndex = nums.firstIndex(of: nums.max()!)!
let root = TreeNode(nums[maxIndex])
root.left = constructMaximumBinaryTree(Array(nums[..<maxIndex]))
root.right = constructMaximumBinaryTree(Array(nums[(maxIndex + 1)...]))
return root
}1 343
Задача: 360. Sort Transformed Array
Сложность: medium
Дан отсортированный массив целых чисел nums и три целых числа a, b и c. Примените квадратичную функцию вида f(x) = ax^2 + bx + c к каждому элементу nums[i] в массиве и верните массив в отсортированном порядке.
Пример:
Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]class Solution {
func sortTransformedArray(_ nums: [Int], _ a: Int, _ b: Int, _ c: Int) -> [Int] {
var transformed = nums.map { a * $0 * $0 + b * $0 + c }
radixSort(&transformed)
return transformed
}
private func radixSort(_ array: inout [Int]) {
let maxElement = array.map { abs($0) }.max() ?? 0
var placeValue = 1
while maxElement / placeValue > 0 {
countingSortByDigit(&array, placeValue)
placeValue *= 10
}
let negatives = array.filter { $0 < 0 }.sorted()
let positives = array.filter { $0 >= 0 }.sorted()
array = negatives + positives
}
private func countingSortByDigit(_ array: inout [Int], _ placeValue: Int) {
var output = Array(repeating: 0, count: array.count)
var count = Array(repeating: 0, count: 10)
for num in array {
let digit = (abs(num) / placeValue) % 10
count[digit] += 1
}
for i in 1..<10 {
count[i] += count[i - 1]
}
for num in array.reversed() {
let digit = (abs(num) / placeValue) % 10
output[count[digit] - 1] = num
count[digit] -= 1
}
array = output
}
}1 343
Задача: 925. Long Pressed Name
Сложность: easy
Ваш друг набирает на клавиатуре свое имя. Иногда, при наборе символа c, клавиша может быть долго нажата, и символ будет набран 1 или более раз. Вы исследуете набранные символы клавиатуры. Верните True, если возможно, что это было имя вашего друга, при этом некоторые символы (возможно, ни один) не были долго нажаты.
Пример:
Input: name = "alex", typed = "aaleex" Output: true👨💻 Алгоритм: 1⃣Инициализировать два указателя i и j для строки имени и набранной строки соответственно. 2⃣Пройти по набранной строке: Если символы имени и набранной строки совпадают, сдвинуть оба указателя. Если символы не совпадают, проверить, является ли текущий символ набранной строки повторением предыдущего символа. Если да, сдвинуть указатель набранной строки. Если символ не совпадает и не является повторением предыдущего символа, вернуть False. После завершения цикла проверить, что все символы имени были обработаны. 3⃣Вернуть True, если все символы имени были обработаны, иначе False. 😎 Решение:
class Solution {
func isLongPressedName(_ name: String, _ typed: String) -> Bool {
let nameArray = Array(name)
let typedArray = Array(typed)
var i = 0
var j = 0
while j < typedArray.count {
if i < nameArray.count && nameArray[i] == typedArray[j] {
i += 1
} else if j == 0 || typedArray[j] != typedArray[j - 1] {
return false
}
j += 1
}
return i == nameArray.count
}
}1 343
Задача: 767. Reorganize String
Сложность: medium
Дана строка s, переставьте символы строки s так, чтобы любые два соседних символа не были одинаковыми.
Верните любую возможную перестановку строки s или верните "", если это невозможно.
Пример:
Input: s = "aab"
Output: "aba"class Solution {
func reorganizeString(_ s: String) -> String {
var charCounts = [Int](repeating: 0, count: 26)
for c in s {
charCounts[Int(c.asciiValue! - Character("a").asciiValue!)] += 1
}
var pq = PriorityQueue<(Int, Character)>(by: { $0.0 > $1.0 })
for i in 0..<26 {
if charCounts[i] > 0 {
pq.push((charCounts[i], Character(UnicodeScalar(i + Int(Character("a").asciiValue!))!)))
}
}
var result = ""
while !pq.isEmpty {
let first = pq.pop()!
if result.isEmpty || first.1 != result.last {
result.append(first.1)
if first.0 > 1 {
pq.push((first.0 - 1, first.1))
}
} else {
if pq.isEmpty {
return ""
}
let second = pq.pop()!
result.append(second.1)
if second.0 > 1 {
pq.push((second.0 - 1, second.1))
}
pq.push(first)
}
}
return result
}
}
struct PriorityQueue<T> {
private var elements: [T]
private let priorityFunction: (T, T) -> Bool
init(by priorityFunction: @escaping (T, T) -> Bool) {
self.elements = []
self.priorityFunction = priorityFunction
}
var isEmpty: Bool {
return elements.isEmpty
}
func peek() -> T? {
return elements.first
}
mutating func push(_ element: T) {
elements.append(element)
elements.sort(by: priorityFunction)
}
mutating func pop() -> T? {
return isEmpty ? nil : elements.removeFirst()
}
}1 343
📺 Уникальная база IT собеседований
456+ реальных собеседований на программиста, тестировщика, аналитика и прочие IT профы.
Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д.
🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!
1 343
Задача: 374. Guess Number Higher or Lower
Сложность: easy
Мы играем в игру "Угадай число". Правила игры следующие:
Я загадываю число от 1 до n. Вам нужно угадать, какое число я загадал.
Каждый раз, когда вы угадываете неправильно, я говорю вам, загаданное число больше или меньше вашего предположения.
Вы вызываете предопределенный API int guess(int num), который возвращает один из трех возможных результатов:
-1: Ваше предположение больше загаданного числа (т.е. num > pick).
1: Ваше предположение меньше загаданного числа (т.е. num < pick).
0: Ваше предположение равно загаданному числу (т.е. num == pick).
Верните загаданное число.
Пример:
Input: n = 10, pick = 6 Output: 6👨💻 Алгоритм: 1⃣Применяем бинарный поиск для нахождения загаданного числа. Начинаем с числа, расположенного в середине диапазона. Передаем это число функции guess. 2⃣Если функция guess возвращает -1, это означает, что загаданное число меньше предположенного. Продолжаем бинарный поиск в диапазоне чисел, меньших данного. 3⃣Если функция guess возвращает 1, это означает, что загаданное число больше предположенного. Продолжаем бинарный поиск в диапазоне чисел, больших данного. 😎 Решение:
class Solution: GuessGame {
func guessNumber(_ n: Int) -> Int {
var low = 1
var high = n
while low <= high {
let mid = low + (high - low) / 2
let res = guess(mid)
if res == 0 {
return mid
} else if res < 0 {
high = mid - 1
} else {
low = mid + 1
}
}
return -1
}
}1 343
Задача: 730. Count Different Palindromic Subsequences
Сложность: hard
Поскольку ответ может быть очень большим, верните его по модулю 109 + 7. Подпоследовательность строки получается путем удаления из нее нуля или более символов. Последовательность является палиндромной, если она равна последовательности, обращенной назад. Две последовательности a1, a2, ... и b1, b2, ... различны, если существует некоторое i, для которого ai != bi.
Пример:
Input: s = "bccb" Output: 6👨💻 Алгоритм: 1⃣Используйте динамическое программирование для подсчета количества палиндромных подпоследовательностей. 2⃣Введите двумерный массив dp, где dp[i][j] представляет количество палиндромных подпоследовательностей в подстроке от i до j. 3⃣Итерируйте по длине подстрок от 1 до длины строки и обновляйте значения в dp на основе состояния предыдущих подстрок. 😎 Решение:
func countPalindromicSubsequences(_ s: String) -> Int {
let MOD = 1_000_000_007
let n = s.count
var dp = Array(repeating: Array(repeating: 0, count: n), count: n)
let sArray = Array(s)
for i in 0..<n {
dp[i][i] = 1
}
for length in 2...n {
for i in 0...(n - length) {
let j = i + length - 1
if sArray[i] == sArray[j] {
var l = i + 1
var r = j - 1
while l <= r && sArray[l] != sArray[i] {
l += 1
}
while l <= r && sArray[r] != sArray[j] {
r -= 1
}
if l > r {
dp[i][j] = dp[i + 1][j - 1] * 2 + 2
} else if l == r {
dp[i][j] = dp[i + 1][j - 1] * 2 + 1
} else {
dp[i][j] = dp[i + 1][j - 1] * 2 - dp[l + 1][r - 1]
}
} else {
dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
}
dp[i][j] = (dp[i][j] + MOD) % MOD
}
}
return dp[0][n - 1]
}1 343
Задача: 718. Maximum Length of Repeated Subarray
Сложность: medium
Если даны два целочисленных массива nums1 и nums2, верните максимальную длину подмассива, который встречается в обоих массивах.
Пример:
Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] Output: 3👨💻 Алгоритм: 1⃣Создайте двумерный массив для хранения длин общих подмассивов. 2⃣Используйте динамическое программирование для нахождения максимальной длины общего подмассива. 3⃣Итеративно обновляйте массив, сравнивая элементы обоих массивов и обновляя максимальную длину подмассива. 😎 Решение:
func findLength(_ nums1: [Int], _ nums2: [Int]) -> Int {
var dp = Array(repeating: Array(repeating: 0, count: nums2.count + 1), count: nums1.count + 1)
var maxLength = 0
for i in (0..<nums1.count).reversed() {
for j in (0..<nums2.count).reversed() {
if nums1[i] == nums2[j] {
dp[i][j] = dp[i + 1][j + 1] + 1
maxLength = max(maxLength, dp[i][j])
}
}
}
return maxLength
}1 343
Задача: 369. Plus One Linked List
Сложность: medium
Дано неотрицательное целое число, представленное в виде связного списка цифр. Добавьте к этому числу единицу.
Цифры хранятся таким образом, что самая значимая цифра находится в начале списка.
Пример:
Input: head = [1,2,3] Output: [1,2,4]👨💻 Алгоритм: 1⃣Инициализируйте стражевой узел как ListNode(0) и установите его как новую голову: sentinel.next = head. Найдите крайний правый элемент, не равный девяти. 2⃣Увеличьте найденную цифру на единицу и установите все следующие девятки в ноль. 3⃣Верните sentinel, если его значение было установлено на 1, иначе верните head (sentinel.next). 😎 Решение:
class ListNode {
var val: Int
var next: ListNode?
init(_ val: Int) { self.val = val; self.next = nil }
}
class Solution {
func plusOne(_ head: ListNode?) -> ListNode? {
let sentinel = ListNode(0)
sentinel.next = head
var notNine = sentinel
var current = head
while current != nil {
if current!.val != 9 {
notNine = current!
}
current = current!.next
}
notNine.val += 1
notNine = notNine.next
while notNine != nil {
notNine!.val = 0
notNine = notNine!.next
}
return sentinel.val == 0 ? sentinel.next : sentinel
}
}1 343
Задача: 682. Baseball Game
Сложность: medium
Вы ведете учет очков в бейсбольной игре с необычными правилами. В начале игры у вас пустая запись.
Вам дается список строк operations, где operations[i] — это i-я операция, которую вы должны применить к записи, и она может быть одной из следующих:
Целое число x.
Записать новый счет, равный x.
'+'.
Записать новый счет, который является суммой двух предыдущих очков.
'D'.
Записать новый счет, который в два раза больше предыдущего очка.
'C'.
Аннулировать предыдущее очко, удалив его из записи.
Верните сумму всех очков в записи после применения всех операций.
Тестовые случаи сформированы таким образом, что ответ и все промежуточные вычисления умещаются в 32-битное целое число, и что все операции корректны.
Пример:
Input: ops = ["5","2","C","D","+"]
Output: 30
Explanation:
"5" - Add 5 to the record, record is now [5].
"2" - Add 2 to the record, record is now [5, 2].
"C" - Invalidate and remove the previous score, record is now [5].
"D" - Add 2 * 5 = 10 to the record, record is now [5, 10].
"+" - Add 5 + 10 = 15 to the record, record is now [5, 10, 15].
The total sum is 5 + 10 + 15 = 30.class Solution {
func calPoints(_ ops: [String]) -> Int {
var stack = [Int]()
for op in ops {
if op == "+" {
let top = stack.removeLast()
let newTop = top + stack.last!
stack.append(top)
stack.append(newTop)
} else if op == "C" {
stack.removeLast()
} else if op == "D" {
stack.append(2 * stack.last!)
} else {
stack.append(Int(op)!)
}
}
return stack.reduce(0, +)
}
}1 343
Задача: 1020. Number of Enclaves
Сложности: medium
Вам дана двоичная матричная сетка m x n, где 0 обозначает морскую ячейку, а 1 - сухопутную. Ход состоит из перехода от одной сухопутной ячейки к другой соседней (в 4-х направлениях) или выхода за границу сетки. Верните количество сухопутных ячеек в сетке, для которых мы не можем выйти за границу сетки за любое количество ходов.
Пример:
Input: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]] Output: 3👨💻 Алгоритм: 1⃣Обработка граничных сухопутных ячеек: Пройдитесь по всем ячейкам, которые находятся на границе сетки (первый и последний ряды, первый и последний столбцы). Если ячейка содержит 1, начните поиск в глубину (DFS) или поиск в ширину (BFS), чтобы пометить все достижимые из нее сухопутные ячейки как посещенные. 2⃣Проверка всех ячеек: Пройдите по всем ячейкам матрицы, считая количество сухопутных ячеек, которые не были посещены в предыдущем шаге. 3⃣Возврат результата: Верните количество не посещенных сухопутных ячеек. 😎 Решение:
class Solution {
func numEnclaves(_ grid: [[Int]]) -> Int {
var grid = grid
let m = grid.count
let n = grid[0].count
func dfs(_ x: Int, _ y: Int) {
if x < 0 || y < 0 || x >= m || y >= n || grid[x][y] != 1 {
return
}
grid[x][y] = 0
dfs(x + 1, y)
dfs(x - 1, y)
dfs(x, y + 1)
dfs(x, y - 1)
}
for i in 0..<m {
if grid[i][0] == 1 {
dfs(i, 0)
}
if grid[i][n - 1] == 1 {
dfs(i, n - 1)
}
}
for j in 0..<n {
if grid[0][j] == 1 {
dfs(0, j)
}
if grid[m - 1][j] == 1 {
dfs(m - 1, j)
}
}
var count = 0
for i in 0..<m {
for j in 0..<n {
if grid[i][j] == 1 {
count += 1
}
}
}
return count
}
}1 343
Задача: 1509. Minimum Difference Between Largest and Smallest Value in Three Moves
Сложность: medium
Вам дан массив целых чисел nums.
За один ход вы можете выбрать один элемент массива nums и изменить его на любое значение.
Верните минимальную разницу между наибольшим и наименьшим значением в массиве nums после выполнения не более трех ходов.
Пример:
Input: nums = [5,3,2,4]
Output: 0
Explanation: We can make at most 3 moves.
In the first move, change 2 to 3. nums becomes [5,3,3,4].
In the second move, change 4 to 3. nums becomes [5,3,3,3].
In the third move, change 5 to 3. nums becomes [3,3,3,3].
After performing 3 moves, the difference between the minimum and maximum is 3 - 3 = 0.class Solution {
func minDifference(_ nums: [Int]) -> Int {
let numsSize = nums.count
if numsSize <= 4 { return 0 }
let sortedNums = nums.sorted()
var minDiff = Int.max
for left in 0..<4 {
let right = numsSize - 4 + left
minDiff = min(minDiff, sortedNums[right] - sortedNums[left])
}
return minDiff
}
}1 343
Задача: 986. Interval List Intersections
Сложность: medium
Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным.
Верните пересечение этих двух списков интервалов.
Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b.
Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3].
Пример:
Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]] Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]👨💻 Алгоритм: 1⃣Инициализация указателей: Завести два указателя i и j, указывающие на начало firstList и secondList соответственно. 2⃣Поиск пересечений: Пока оба указателя находятся в пределах своих списков, выполнить следующие действия: Найти максимальное начало и минимальный конец текущих интервалов. Если начало меньше или равно концу, добавить пересечение в результат. Сдвинуть указатель списка, у которого текущий интервал заканчивается раньше. 3⃣Возврат результата: Вернуть список пересечений. 😎 Решение:
func intervalIntersection(_ firstList: [[Int]], _ secondList: [[Int]]) -> [[Int]] {
var i = 0, j = 0
var result = [[Int]]()
while i < firstList.count && j < secondList.count {
let start = max(firstList[i][0], secondList[j][0])
let end = min(firstList[i][1], secondList[j][1])
if start <= end {
result.append([start, end])
}
if firstList[i][1] < secondList[j][1] {
i += 1
} else {
j += 1
}
}
return result
}1 343
Задача: 1216. Valid Palindrome III
Сложность: hard
Дана строка s и целое число k. Верните true, если s является k-палиндромом.
Строка является k-палиндромом, если её можно преобразовать в палиндром, удалив из неё не более k символов.
Пример:
Input: s = "abcdeca", k = 2 Output: true Explanation: Remove 'b' and 'e' characters.👨💻 Алгоритм: 1⃣Инициализируйте двухмерный массив memo для хранения промежуточных результатов, чтобы избежать повторных вычислений. Определите функцию isValidPalindrome, которая будет возвращать минимальное количество удалений для создания палиндрома в подстроке от индекса i до j. 2⃣Реализуйте базовые случаи для функции isValidPalindrome: если i равно j, то это уже палиндром, если i и j - соседние индексы, то возвращается 1, если символы не совпадают. Если значение для пары индексов уже рассчитано, то возвращается сохраненное значение из memo. 3⃣Реализуйте основные случаи рекурсивного вычисления: если символы на позициях i и j совпадают, продолжайте проверку для подстроки без этих символов. В противном случае, рассмотрите два варианта удаления символов и выберите минимальное количество удалений, добавив 1 за текущее удаление. 😎 Решение:
class Solution {
var memo: [[Int?]] = []
func isValidPalindrome(_ s: String, _ k: Int) -> Bool {
let n = s.count
memo = Array(repeating: Array(repeating: nil, count: n), count: n)
let sArray = Array(s)
return isValidPalindromeHelper(sArray, 0, n - 1) <= k
}
private func isValidPalindromeHelper(_ s: [Character], _ i: Int, _ j: Int) -> Int {
if i == j {
return 0
}
if i == j - 1 {
return s[i] != s[j] ? 1 : 0
}
if let res = memo[i][j] {
return res
}
if s[i] == s[j] {
memo[i][j] = isValidPalindromeHelper(s, i + 1, j - 1)
} else {
memo[i][j] = 1 + min(isValidPalindromeHelper(s, i + 1, j), isValidPalindromeHelper(s, i, j - 1))
}
return memo[i][j]!
}
}1 343
Задача: 998. Maximum Binary Tree II
Сложность: medium
Максимальное дерево - это дерево, в котором каждый узел имеет значение большее, чем любое другое значение в его поддереве. Вам дан корень максимального двоичного дерева и целое число val. Как и в предыдущей задаче, данное дерево было построено из списка a (root = Construct(a)) рекурсивно с помощью следующей процедуры Construct(a): Если a пусто, верните null.
В противном случае пусть a[i] - наибольший элемент a. Создайте корневой узел со значением a[i]. Левым ребенком root будет Construct([a[0], a[1], ..., a[i - 1]]). Правым ребенком root будет Construct([a[i + 1], a[i + 2], ..., a[a.length])...., a[a.length - 1]]). Возвращаем root. Обратите внимание, что нам не было дано непосредственно a, а только корневой узел root = Construct(a). Предположим, что b - это копия a с добавленным к ней значением val. Гарантируется, что b имеет уникальные значения. Возвращаем Construct(b).
Пример:
Input: n = 2, trust = [[1,2]] Output: 2👨💻 Алгоритм: 1⃣Поиск места вставки: Итерируйте через дерево, начиная с корня. Найдите место для вставки нового значения val так, чтобы дерево оставалось максимальным деревом. Если значение val больше, чем значение текущего узла, создайте новый узел с val и сделайте текущий узел его левым ребенком. 2⃣Вставка нового узла: Если значение val меньше, чем значение текущего узла, продолжайте спускаться по правому поддереву, пока не найдете место для вставки. 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 {
func insertIntoMaxTree(_ root: TreeNode?, _ val: Int) -> TreeNode? {
guard let root = root else { return TreeNode(val) }
if val > root.val {
return TreeNode(val, root, nil)
}
root.right = insertIntoMaxTree(root.right, val)
return root
}
}