Задача: 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
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 767. Reorganize String
Сложность: medium

Дана строка s, переставьте символы строки s так, чтобы любые два соседних символа не были одинаковыми.

Верните любую возможную перестановку строки s или верните "", если это невозможно.

Пример:

Input: s = "aab"
Output: "aba"

👨‍💻 Алгоритм:

1⃣Инициализируйте пустой список ans для хранения переставленных символов. Создайте приоритетную очередь pq, используя структуру данных кучи. Каждый элемент в pq — это кортеж, содержащий количество символов и сам символ. Приоритетная очередь упорядочена так, что элементы с большим количеством имеют более высокий приоритет.

2⃣Извлеките элемент с наивысшим приоритетом из pq. Присвойте его количество и символ переменным count_first и char_first соответственно. Если ans пуст или текущий символ char_first отличается от последнего символа в ans, добавьте char_first в ans. Если количество char_first не равно нулю, уменьшите его на один. Если обновленное количество больше нуля, поместите его обратно в pq. Перейдите к следующей итерации.

3⃣В противном случае, если char_first совпадает с последним символом в ans, нужно выбрать другой символ. Если pq пуста, верните пустую строку, так как переставить символы невозможно. Извлеките следующий элемент из pq, присвоив его количество и символ переменным count_second и char_second соответственно. Добавьте char_second в ans. Если количество char_second не равно нулю, уменьшите его на один. Если обновленное количество больше нуля, поместите его обратно в pq. Наконец, поместите оригинальный char_first обратно в pq. Верните переставленные символы как строку, объединив элементы в ans.

😎 Решение:

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()
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 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
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 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]

👨‍💻 Алгоритм:

1⃣Преобразование и сортировка
Преобразуем каждый элемент массива nums по квадратичной функции f(x) = ax^2 + bx + c и сохраняем результаты в массив transformed. Используем алгоритм поразрядной сортировки для сортировки массива transformed.

2⃣Поразрядная сортировка
Находим максимальное значение по модулю в массиве для определения количества цифр. Применяем поразрядную сортировку к массиву transformed.

3⃣Сортировка по цифре
Для каждой цифры (разряда) используем подсчет для сортировки массива.

😎 Решение:

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
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 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
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 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
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 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
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 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: 7

👨‍💻 Алгоритм:

1⃣Рекурсивный обход дерева:
Используйте рекурсивную функцию для обхода дерева. Передавайте минимальное и максимальное значения, встреченные на пути от корня к текущему узлу.

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 {
    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)
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 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
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 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)
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1011. Capacity To Ship Packages Within D Days
Сложность: medium

На конвейерной ленте находятся пакеты, которые должны быть отправлены из одного порта в другой в течение нескольких дней. i-й пакет на конвейерной ленте имеет массу weights[i]. Каждый день мы загружаем корабль пакетами на конвейерной ленте (в порядке, заданном весами). Мы не можем загрузить больше груза, чем максимальная грузоподъемность корабля. Верните наименьшую грузоподъемность корабля, при которой все посылки на конвейере будут отправлены в течение нескольких дней.

Пример:

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15

👨‍💻 Алгоритм:

1⃣Определение диапазона возможных ответов:
Минимальная грузоподъемность должна быть не меньше максимального веса одного пакета (чтобы хотя бы один пакет можно было загрузить).
Максимальная грузоподъемность - это сумма всех весов (если все пакеты будут отправлены за один день).

2⃣Использование бинарного поиска:
Примените бинарный поиск в диапазоне от минимальной до максимальной грузоподъемности, чтобы найти наименьшую грузоподъемность, при которой все пакеты можно отправить за заданное количество дней.

3⃣Проверка возможности отправки всех пакетов за заданное количество дней:
Напишите вспомогательную функцию, которая проверяет, можно ли отправить все пакеты при заданной грузоподъемности за определенное количество дней. Эта функция проходит по списку весов и считает количество необходимых дней для отправки всех пакетов при текущей грузоподъемности.

😎 Решение:

class Solution {
    func shipWithinDays(_ weights: [Int], _ D: Int) -> Int {
        func canShipInDays(_ capacity: Int) -> Bool {
            var days = 1
            var total = 0
            for weight in weights {
                if total + weight > capacity {
                    days += 1
                    total = 0
                }
                total += weight
            }
            return days <= D
        }
        
        var left = weights.max()!
        var right = weights.reduce(0, +)
        
        while left < right {
            let mid = (left + right) / 2
            if canShipInDays(mid) {
                right = mid
            } else {
                left = mid + 1
            }
        }
        
        return left
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 936. Stamping The Sequence
Сложность: hard

Вам даны две строки stamp и target. Изначально имеется строка s длины target.length со всеми s[i] == '?'. За один ход вы можете поместить штамп над s и заменить каждую букву в s на соответствующую букву из штампа. Например, если штамп = "abc" и target = "abcba", то s изначально будет "?????". За один ход вы можете: поместить штамп в индекс 0 s, чтобы получить "abc??", поместить штамп в индекс 1 s, чтобы получить "?abc?", или поместить штамп в индекс 2 s, чтобы получить "??abc". Обратите внимание, что штамп должен полностью находиться в границах s, чтобы штамповать (то есть вы не можете поместить штамп в индекс 3 s). Мы хотим преобразовать s в цель, используя не более 10 * target.length ходов. Верните массив индекса самой левой буквы, которая штампуется на каждом ходу. Если мы не можем получить цель из s за 10 * target.length оборотов, верните пустой массив

Пример:

Input: stamp = "abc", target = "ababc"
Output: [0,2]

👨‍💻 Алгоритм:

1⃣Инициализировать переменные:
s как массив символов '?', длиной target.length.
res как список для хранения результатов.
done как массив булевых значений для отслеживания того, какие позиции уже штампованы.
target как массив символов для удобства.

2⃣Использовать функцию canStamp для проверки, можно ли штамповать stamp в target начиная с индекса i.
Использовать функцию doStamp для штампования stamp в target начиная с индекса i.
Повторять шаги, пока штампы возможны или достигнут максимум ходов (10 * target.length):
Перебрать все возможные начальные позиции для штампа.
Проверить, можно ли штамповать в текущей позиции.
Если можно, штамповать и добавить индекс в res.

3⃣Если все символы в s соответствуют символам в target, вернуть массив res в обратном порядке. Иначе, вернуть пустой массив.

😎 Решение:

class Solution {
    func movesToStamp(_ stamp: String, _ target: String) -> [Int] {
        var s = Array(stamp), t = Array(target)
        let m = s.count, n = t.count
        var res = [Int]()
        var done = [Bool](repeating: false, count: n)
        
        func canStamp(_ i: Int) -> Bool {
            for j in 0..<m {
                if t[i + j] != "?" && t[i + j] != s[j] {
                    return false
                }
            }
            return true
        }
        
        func doStamp(_ i: Int) {
            for j in 0..<m {
                t[i + j] = "?"
            }
            res.append(i)
            done[i] = true
        }
        
        var changed = true
        while changed {
            changed = false
            for i in 0...(n - m) {
                if !done[i] && canStamp(i) {
                    doStamp(i)
                    changed = true
                }
            }
        }
        
        return t.allSatisfy { $0 == "?" } ? res.reversed() : []
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1217. Minimum Cost to Move Chips to The Same Position
Сложность: easy

У нас есть n фишек, где позиция i-й фишки равна position[i].

Нам нужно переместить все фишки в одну и ту же позицию. За один шаг мы можем изменить позицию i-й фишки с position[i] на:
position[i] + 2 или position[i] - 2 с затратами = 0.
position[i] + 1 или position[i] - 1 с затратами = 1.
Верните минимальные затраты, необходимые для перемещения всех фишек в одну и ту же позицию.

Пример:

Input: position = [2,2,2,3,3]
Output: 2
Explanation: We can move the two chips at position  3 to position 2. Each move has cost = 1. The total cost = 2.

👨‍💻 Алгоритм:

1⃣Посчитать количество фишек на четных и нечетных позициях.

2⃣Сравнить количество фишек на четных и нечетных позициях.

3⃣Вернуть минимальное количество фишек как минимальную стоимость для перемещения всех фишек в одну позицию.

😎 Решение:

class Solution {
    func minCostToMoveChips(_ position: [Int]) -> Int {
        var evenCount = 0
        var oddCount = 0
        
        for pos in position {
            if pos % 2 == 0 {
                evenCount += 1
            } else {
                oddCount += 1
            }
        }
        
        return min(evenCount, oddCount)
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1007. Minimum Domino Rotations For Equal Row
Сложность: medium

В ряду домино, tops[i] и bottoms[i] представляют собой верхнюю и нижнюю половинки i-го домино. (Домино - это плитка с двумя числами от 1 до 6 - по одному на каждой половине плитки.) Мы можем повернуть i-е домино так, чтобы tops[i] и bottoms[i] поменялись значениями. Верните минимальное количество поворотов, чтобы все значения tops были одинаковыми или все значения bottoms были одинаковыми. Если это невозможно сделать, верните -1.

Пример:

Input: tops = [2,1,2,4,2,2], bottoms = [5,2,6,2,3,2]
Output: 2

👨‍💻 Алгоритм:

1⃣Проверка кандидатов:
Для начала рассмотрим два кандидата для достижения цели: tops[0] и bottoms[0]. Это кандидаты для унификации значений в ряду домино, поскольку если есть решение, один из этих двух кандидатов должен быть в верхней или нижней строке всех домино.

2⃣Подсчет поворотов для каждого кандидата:
Для каждого из кандидатов (tops[0] и bottoms[0]) подсчитайте количество поворотов, необходимых для унификации значений во всех tops или во всех bottoms.
Если какой-либо домино не может быть повернут для достижения требуемого кандидата, этот кандидат исключается из рассмотрения.

3⃣Возврат минимального количества поворотов:
Верните минимальное количество поворотов из всех возможных кандидатов. Если ни один кандидат не подходит, верните -1.

😎 Решение:

class Solution {
    func minDominoRotations(_ tops: [Int], _ bottoms: [Int]) -> Int {
        func check(_ x: Int) -> Int {
            var rotations_a = 0
            var rotations_b = 0
            for i in 0..<tops.count {
                if tops[i] != x && bottoms[i] != x {
                    return -1
                } else if tops[i] != x {
                    rotations_a += 1
                } else if bottoms[i] != x {
                    rotations_b += 1
                }
            }
            return min(rotations_a, rotations_b)
        }
        
        let rotations = check(tops[0])
        if rotations != -1 || tops[0] == bottoms[0] {
            return rotations
        } else {
            return check(bottoms[0])
        }
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 905. Sort Array By Parity
Сложность: easy

Если задан целочисленный массив nums, переместите все четные числа в начало массива, а затем все нечетные. Верните любой массив, удовлетворяющий этому условию.

Пример:

Input: nums = [3,1,2,4]
Output: [2,4,3,1]

👨‍💻 Алгоритм:

1⃣Создать два списка: один для четных чисел, другой для нечетных.

2⃣Пройтись по массиву и добавить четные числа в один список, а нечетные в другой.

3⃣Объединить два списка и вернуть результат.

😎 Решение:

class Solution {
    func sortArrayByParity(_ nums: [Int]) -> [Int] {
        var evens = [Int]()
        var odds = [Int]()
        for num in nums {
            if num % 2 == 0 {
                evens.append(num)
            } else {
                odds.append(num)
            }
        }
        return evens + odds
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 419. Battleships in a Board
Сложность: medium

Если задана матричная доска размером m x n, где каждая клетка - линкор 'X' или пустая '.', верните количество линкоров на доске. Линкоры могут располагаться на доске только горизонтально или вертикально. Другими словами, они могут быть выполнены только в форме 1 x k (1 строка, k столбцов) или k x 1 (k строк, 1 столбец), где k может быть любого размера. Между двумя линкорами есть хотя бы одна горизонтальная или вертикальная клетка (т. е. нет соседних линкоров).

Пример:

Input: board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
Output: 2

👨‍💻 Алгоритм:

1⃣Пройдите по каждой клетке матрицы.

2⃣Если текущая клетка содержит 'X' и она не является продолжением линкора (т.е. не имеет 'X' сверху или слева), увеличьте счетчик линкоров.

3⃣Верните итоговый счетчик.

😎 Решение:

func countBattleships(_ board: [[Character]]) -> Int {
    let m = board.count
    let n = board[0].count
    var count = 0
    
    for i in 0..<m {
        for j in 0..<n {
            if board[i][j] == "X" {
                if (i == 0 || board[i-1][j] != "X") && (j == 0 || board[i][j-1] != "X") {
                    count += 1
                }
            }
        }
    }
    
    return count
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 28. Find the Index of the First Occurrence in a String
Сложность: easy

Учитывая две строки needle (игла) и haystack (стог сена), верните индекс первого вхождения needle в haystack или -1, если needle не является частью haystack.

Пример:

Input: haystack = "hello", needle = "ll"  
Output: 2  

👨‍💻Алгоритм:

1⃣Используем метод range(of:) для поиска первого вхождения needle в haystack.

2⃣Если подстрока найдена, вычисляем индекс начала с помощью distance(from:to:).

3⃣Если подстрока не найдена, возвращаем -1.

😎Решение:

func findNeedleInHaystack(_ haystack: String, _ needle: String) -> Int {
    if let range = haystack.range(of: needle) {
        return haystack.distance(from: haystack.startIndex, to: range.lowerBound)
    } else {
        return -1
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 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 {
    var keyTimeMap = [String: [Int: String]]()

    func set(_ key: String, _ value: String, _ timestamp: Int) {
        if keyTimeMap[key] == nil {
            keyTimeMap[key] = [:]
        }
        keyTimeMap[key]?[timestamp] = value
    }

    func get(_ key: String, _ timestamp: Int) -> String {
        if let times = keyTimeMap[key] {
            for currTime in stride(from: timestamp, through: 1, by: -1) {
                if let value = times[currTime] {
                    return value
                }
            }
        }
        return ""
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1353. Maximum Number of Events That Can Be Attended
Сложность: medium

Дан массив событий, где events[i] = [startDayi, endDayi]. Каждое событие i начинается в startDayi и заканчивается в endDayi.

Вы можете посетить событие i в любой день d, где startDayi <= d <= endDayi. Вы можете посещать только одно событие в любой момент времени d.

Верните максимальное количество событий, которые вы можете посетить.

Пример:

Input: events= [[1,2],[2,3],[3,4],[1,2]]
Output: 4

👨‍💻 Алгоритм:

1⃣Сортировка событий по времени завершения:
Сначала отсортируйте массив событий по времени окончания каждого события в порядке возрастания. Это позволит сначала рассматривать события, которые заканчиваются раньше.

2⃣Использование множества для отслеживания посещенных дней:
Создайте множество для хранения дней, в которые уже были посещены события. Это позволит легко проверять, был ли день уже использован для посещения другого события.

3⃣Посещение событий в доступные дни:
Пройдитесь по отсортированному массиву событий. Для каждого события проверьте каждый день от начала события до его окончания и найдите первый доступный день, который еще не был использован. Если такой день найден, добавьте его в множество и увеличьте счетчик посещенных событий.

😎 Решение:

class Solution {
    func maxEvents(_ events: [[Int]]) -> Int {
        var events = events.sorted { $0[1] < $1[1] }
        var visitedDays = Set<Int>()
        var count = 0
        
        for event in events {
            for day in event[0]...event[1] {
                if !visitedDays.contains(day) {
                    visitedDays.insert(day)
                    count += 1
                    break
                }
            }
        }
        return count
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 223. Rectangle Area
Сложность: medium

Даны координаты двух прямоугольных прямоугольников на двумерной плоскости, верните общую площадь, покрытую этими двумя прямоугольниками.

Первый прямоугольник определяется его нижним левым углом (ax1, ay1) и верхним правым углом (ax2, ay2).

Второй прямоугольник определяется его нижним левым углом (bx1, by1) и верхним правым углом (bx2, by2).

Пример:

Input: ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2
Output: 45

👨‍💻 Алгоритм:

1⃣Вычислить площади двух прямоугольников:
Рассчитайте площади прямоугольников A и B, умножив их ширину на высоту.

2⃣Вычислить перекрытие:
Найдите перекрытие по оси X и оси Y. Если перекрытие существует, вычислите площадь перекрытия.

3⃣Вычислить и вернуть общую площадь:
Вычтите площадь перекрытия из суммы площадей двух прямоугольников и верните результат.

😎 Решение:

class Solution {
    func computeArea(_ ax1: Int, _ ay1: Int, _ ax2: Int, _ ay2: Int, _ bx1: Int, _ by1: Int, _ bx2: Int, _ by2: Int) -> Int {
        let areaOfA = (ay2 - ay1) * (ax2 - ax1)
        let areaOfB = (by2 - by1) * (bx2 - bx1)

        let left = max(ax1, bx1)
        let right = min(ax2, bx2)
        let xOverlap = right - left

        let top = min(ay2, by2)
        let bottom = max(ay1, by1)
        let yOverlap = top - bottom

        var areaOfOverlap = 0
        if xOverlap > 0 && yOverlap > 0 {
            areaOfOverlap = xOverlap * yOverlap
        }

        return areaOfA + areaOfB - areaOfOverlap
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 122. Best Time to Buy and Sell Stock II
Сложность: medium

Вам дан массив целых чисел prices, где prices[i] — это цена данной акции в i-й день.

Каждый день вы можете решить купить и/или продать акцию. Вы можете держать в руках только одну акцию за раз. Однако вы можете купить её и сразу же продать в тот же день.

Найдите и верните максимальную прибыль, которую вы можете получить.

Пример:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

👨‍💻 Алгоритм:

1⃣Предположим, что дан массив:
\[ 7, 1, 5, 3, 6, 4 \]
Если мы изобразим числа данного массива на графике, мы получим: *приложенное изображение*

2⃣Анализируя график, мы замечаем, что точки интереса — это последовательные впадины и пики.
Математически говоря:
Общая прибыль = ∑ (высота(пик i) - высота(впадина i))

3⃣Ключевой момент заключается в том, что мы должны учитывать каждый пик, следующий сразу за впадиной, чтобы максимизировать прибыль. Если мы пропустим один из пиков (пытаясь получить больше прибыли), мы потеряем прибыль по одной из сделок, что приведет к общей меньшей прибыли.

😎 Решение:

class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        var i = 0
        var valley = prices[0]
        var peak = prices[0]
        var maxProfit = 0
        while i < prices.count - 1 {
            while i < prices.count - 1 && prices[i] >= prices[i + 1] {
                i += 1
            }
            valley = prices[i]
            while i < prices.count - 1 && prices[i] <= prices[i + 1] {
                i += 1
            }
            peak = prices[i]
            maxProfit += peak - valley
        }
        return maxProfit
    }
}

Ставь 👍 и забирай 📚 Базу знаний