Задача: 154. Find Minimum in Rotated Sorted Array II
Сложность: Hard

Предположим, что массив длиной n, отсортированный в порядке возрастания, повернут от 1 до n раз. Например, массив nums = [0,1,4,4,5,6,7] может стать:

[4,5,6,7,0,1,4], если он был повернут 4 раза.
[0,1,4,4,5,6,7], если он был повернут 7 раз.
Обратите внимание, что поворот массива [a[0], a[1], a[2], ..., a[n-1]] 1 раз приводит к массиву [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

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

Необходимо максимально уменьшить количество операций.

Пример:

Input: nums = [1,3,5]
Output: 1

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

1⃣Сравнение с правой границей:
В классическом бинарном поиске мы бы сравнивали элемент в середине (nums[mid]) с искомым значением. В нашем случае мы сравниваем его с элементом, на который указывает правый указатель (nums[high]).

2⃣Обновление указателей:
Если элемент в середине находится в той же половине массива, что и элемент на правой границе (nums[mid] > nums[high]), минимальный элемент должен находиться в левой половине от mid. Следовательно, сдвигаем правый указатель на позицию mid.
Если nums[mid] < nums[high], это указывает, что минимальный элемент находится в правой половине или равен mid. Сдвигаем правый указатель на mid.
Если nums[mid] == nums[high], мы не можем быть уверены, в какой половине находится минимальный элемент из-за наличия дубликатов. В этом случае безопасно сдвинуть правый указатель на один шаг влево (high = high - 1), чтобы сузить область поиска без пропуска возможного минимального элемента.

3⃣Итерация до сужения диапазона поиска:
Продолжаем процесс, пока левый указатель не встретится с правым. В конечном итоге правый указатель укажет на минимальный элемент массива после всех поворотов.

😎 Решение:

class Solution {
    func findMin(_ nums: [Int]) -> Int {
        var low = 0
        var high = nums.count - 1
        
        while low < high {
            let pivot = low + (high - low) / 2
            if nums[pivot] < nums[high] {
                high = pivot
            } else if nums[pivot] > nums[high] {
                low = pivot + 1
            } else {
                high -= 1
            }
        }
        return nums[low]
    }
}

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

Задача: 171. Excel Sheet Column Number
Сложность: easy

Дана строка columnTitle, представляющая название столбца, как это отображается в Excel. Вернуть соответствующий номер столбца.

Пример:

Input: columnTitle = "A"
Output: 1

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

1⃣Создайте отображение букв алфавита и их соответствующих значений (начиная с 1).

2⃣Инициализируйте переменную-аккумулятор result.

3⃣Начиная справа налево, вычислите значение символа в
зависимости от его позиции и добавьте его к result.

😎 Решение:

func titleToNumber(_ s: String) -> Int {
    var result = 0

    let alpha_map: [Character: Int] = {
        var map = [Character: Int]()
        for i in 0..<26 {
            map[Character(UnicodeScalar(i + 65)!)] = i + 1
        }
        return map
    }()

    let n = s.count
    for (i, char) in s.reversed().enumerated() {
        result += alpha_map[char]! * Int(pow(26.0, Double(i)))
    }
    return result
}

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

Задача: 629. K Inverse Pairs Array
Сложность: hard

Для целочисленного массива nums инверсная пара - это пара целых чисел [i, j], где 0 <= i < j < nums.length и nums[i] > nums[j]. Учитывая два целых числа n и k, верните количество различных массивов, состоящих из чисел от 1 до n, в которых существует ровно k инверсных пар. Поскольку ответ может быть огромным, верните его по модулю 109 + 7.

Пример:

Input: n = 3, k = 0
Output: 1

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

1⃣Инициализация
Создайте двумерный массив dp размером [n+1][k+1] и установите начальное значение dp[0][0] = 1. Остальные значения установите в 0.

2⃣Заполнение DP-таблицы
Используйте два вложенных цикла для заполнения таблицы DP. Внешний цикл перебирает длину массива i от 1 до n, а внутренний цикл перебирает количество инверсий j от 0 до k. Если j == 0, то dp[i][j] = 1. В противном случае обновляйте dp[i][j] с учетом всех возможных позиций вставки нового элемента в массив длины i-1.

3⃣Возвращение результата
Результатом будет значение dp[n][k].

😎 Решение:

func kInversePairs(_ n: Int, _ k: Int) -> Int {
    let MOD = 1_000_000_007
    var dp = Array(repeating: Array(repeating: 0, count: k + 1), count: n + 1)
    dp[0][0] = 1

    for i in 1...n {
        dp[i][0] = 1
        for j in 1...k {
            dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % MOD
            if j >= i {
                dp[i][j] = (dp[i][j] - dp[i - 1][j - i] + MOD) % MOD
            }
        }
    }

    return dp[n][k]
}

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

Задача: 439. Ternary Expression Parser
Сложность: medium

Дана строка expression, представляющая произвольно вложенные тернарные выражения, вычислите это выражение и верните его результат.

Можно всегда считать, что данное выражение является корректным и содержит только цифры, '?', ':', 'T' и 'F', где 'T' означает истину, а 'F' - ложь. Все числа в выражении являются однозначными числами (т.е. в диапазоне от 0 до 9).

Условные выражения группируются справа налево (как обычно в большинстве языков), и результат выражения всегда будет либо цифрой, либо 'T', либо 'F'.

Пример:

Input: expression = "T?2:3"
Output: "2"
Explanation: If true, then result is 2; otherwise result is 3.

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

1⃣Определите вспомогательную функцию isValidAtomic(s), которая принимает строку s и возвращает True, если s является допустимым атомарным выражением. В противном случае функция возвращает False. Функция будет вызываться только с пятисимвольными строками. Если все следующие условия выполнены, функция возвращает True, иначе - False: s[0] является T или F. s[1] является ?. s[2] является T, F или цифрой от 0 до 9. s[3] является :. s[4] является T, F или цифрой от 0 до 9.

2⃣Определите вспомогательную функцию solveAtomic(s), которая принимает строку s и возвращает значение атомарного выражения. Значение атомарного выражения равно E1, если B - это T, иначе значение равно E2. Функция будет вызываться только с пятисимвольными строками и возвращать один символ:.

3⃣Если s[0] является T, функция возвращает s[2], иначе возвращает s[4]. В функции parseTernary(expression) уменьшайте выражение до тех пор, пока не останется односимвольная строка. Инициализируйте j как expression.size() - 1 (это будет самый правый индекс окна). Пока самое правое окно длиной 5 не является допустимым атомарным выражением, уменьшайте j на 1. Когда будет найдено самое правое допустимое атомарное выражение, решите его и уменьшите до одного символа. Замените самое правое допустимое атомарное выражение одним символом, после чего длина выражения уменьшится на 4. В итоге останется односимвольная строка, которую и верните.

😎 Решение:

class Solution {
    func parseTernary(_ expression: String) -> String {
        func isValidAtomic(_ s: String) -> Bool {
            let chars = Array(s)
            return chars[0] == "T" || chars[0] == "F" &&
                   chars[1] == "?" &&
                   ("TF0123456789".contains(chars[2])) &&
                   chars[3] == ":" &&
                   ("TF0123456789".contains(chars[4]))
        }
        
        func solveAtomic(_ s: String) -> Character {
            let chars = Array(s)
            return chars[0] == "T" ? chars[2] : chars[4]
        }
        
        var expression = Array(expression)
        while expression.count != 1 {
            var j = expression.count - 1
            while !isValidAtomic(String(expression[(j-4)...j])) {
                j -= 1
            }
            let result = solveAtomic(String(expression[(j-4)...j]))
            expression = Array(expression[0..<(j-4)]) + [result] + Array(expression[(j+1)...])
        }
        return String(expression)
    }
}

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

Задача: 1339. Maximum Product of Splitted Binary Tree
Сложность: medium

Дано корневое дерево. Разделите бинарное дерево на два поддерева, удалив одно ребро так, чтобы произведение сумм поддеревьев было максимальным.

Верните максимальное произведение сумм двух поддеревьев. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Обратите внимание, что вам нужно максимально увеличить ответ до взятия модуля, а не после.

Пример:

Input: root = [1,2,3,4,5,6]
Output: 110
Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10)

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

1⃣Рассчитать сумму значений всех узлов дерева и сохранить суммы всех поддеревьев в списке.

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

3⃣Найти максимальное произведение среди всех вычисленных и вернуть его значение по модулю 10^9 + 7.

😎 Решение:

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
}

class Solution {
    private var allSums: [Int] = []

    func maxProduct(_ root: TreeNode?) -> Int {
        let totalSum = treeSum(root)
        var best: Int64 = 0
        for sum in allSums {
            best = max(best, Int64(sum) * (totalSum - Int64(sum)))
        }
        return Int(best % 1000000007)
    }

    private func treeSum(_ subroot: TreeNode?) -> Int64 {
        guard let subroot = subroot else { return 0 }
        let leftSum = treeSum(subroot.left)
        let rightSum = treeSum(subroot.right)
        let totalSum = leftSum + rightSum + Int64(subroot.val)
        allSums.append(Int(totalSum))
        return totalSum
    }
}

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

Задача: 165. Compare Version Numbers
Сложность: medium

Даны две строки версий, version1 и version2. Сравните их. Строка версии состоит из ревизий, разделенных точками '.'. Значение ревизии — это её целочисленное преобразование с игнорированием ведущих нулей.

Для сравнения строк версий сравнивайте их значения ревизий в порядке слева направо. Если одна из строк версий имеет меньше ревизий, то отсутствующие значения ревизий следует считать равными 0.

Верните следующее:

- Если version1 < version2, верните -1.
- Если version1 > version2, верните 1.
- В противном случае верните 0.

Пример:

Input: version1 = "1.2", version2 = "1.10"
Output: -1
Explanation:
version1's second revision is "2" and version2's second revision is "10": 2 < 10, so version1 < version2.

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

1⃣Разделение строк: Разделите обе строки по символу точки на два массива.

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

3⃣Определение результатов сравнения:
Если два сегмента не равны, верните 1 или -1 в зависимости от того, какой сегмент больше.
Если все сегменты равны после завершения цикла, версии считаются равными. Верните 0

😎 Решение:

class Solution {
    func compareVersion(_ version1: String, _ version2: String) -> Int {
        let tokens1 = version1.split(separator: ".").map { Int($0)! }
        let tokens2 = version2.split(separator: ".").map { Int($0)! }

        for i in 0..<max(tokens1.count, tokens2.count) {
            let i1 = i < tokens1.count ? tokens1[i] : 0
            let i2 = i < tokens2.count ? tokens2[i] : 0

            if i1 != i2 {
                return i1 > i2 ? 1 : -1
            }
        }
        return 0
    }
}

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

Задача: 80. Remove Duplicates from Sorted Array II
Сложность: medium

Дан массив целых чисел nums, отсортированный в неубывающем порядке. Удалите из него некоторые дубликаты на месте так, чтобы каждый уникальный элемент встречался не более двух раз. Относительный порядок элементов должен быть сохранён.

Поскольку в некоторых языках программирования невозможно изменить длину массива, результат следует разместить в первой части массива nums. Более формально, если после удаления дубликатов остаётся k элементов, то первые k элементов массива nums должны содержать итоговый результат. Не важно, что остаётся за пределами первых k элементов.

Верните k после размещения итогового результата в первые k слотов массива nums.

Не выделяйте дополнительное пространство для другого массива. Вы должны сделать это, изменяя исходный массив на месте с использованием дополнительной памяти O(1).

Пример:

Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

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

1⃣Инициализация переменных: Используйте две переменные: i, которая указывает на текущий индекс в массиве, и count, которая отслеживает количество каждого элемента. Начните обработку массива с первого элемента (индекс 1), предполагая, что первый элемент всегда имеет count равный 1.

2⃣Обработка элементов массива: Для каждого элемента в массиве:

3⃣Если текущий элемент такой же, как предыдущий (nums[i] == nums[i - 1]), увеличьте count.
Если count больше 2, это означает, что текущий элемент встречается более двух раз. В этом случае удалите этот элемент из массива с помощью операции удаления, поддерживаемой вашим языком программирования (например, del, pop, remove), и уменьшите индекс i на 1, чтобы корректно обработать следующий элемент.
Если текущий элемент отличается от предыдущего (nums[i] != nums[i - 1]), это означает начало новой последовательности, поэтому сбросьте count к 1.
Возвращение результата: После обработки всех элементов в массиве, все ненужные дубликаты удалены, и в массиве остаются только допустимые элементы. Верните длину обработанного массива, так как это количество элементов, которые теперь соответствуют условиям задачи.

😎 Решение:

func removeDuplicates(_ nums: inout [Int]) -> Int {
    var j = 0
    for i in 0..<nums.count {
        if j < 2 || nums[i] > nums[j - 2] {
            nums[j] = nums[i]
            j += 1
        }
    }
    return j
}

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

Задача: 1277. Count Square Submatrices with All Ones
Сложность: medium

Если задана матрица m * n из единиц и нулей, верните, сколько квадратных подматриц имеют все единицы.

Пример:

Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15

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

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

2⃣Пройдите по каждому элементу матрицы и обновите dp следующим образом: если элемент равен 1, то dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1.

3⃣Суммируйте все значения в dp, чтобы получить количество квадратных подматриц, состоящих из всех единиц.

😎 Решение:

class Solution {
    func countSquares(_ matrix: [[Int]]) -> Int {
        let m = matrix.count, n = matrix[0].count
        var dp = Array(repeating: Array(repeating: 0, count: n), count: m)
        var count = 0

        for i in 0..<m {
            for j in 0..<n {
                if matrix[i][j] == 1 {
                    if i == 0 || j == 0 {
                        dp[i][j] = 1
                    } else {
                        dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1
                    }
                    count += dp[i][j]
                }
            }
        }

        return count
    }
}

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

Задача: 1425. Constrained Subsequence Sum
Сложность: hard

Дан целочисленный массив nums и целое число k, верните максимальную сумму непустой подпоследовательности этого массива, такую, что для любых двух последовательных целых чисел в подпоследовательности nums[i] и nums[j], где i < j, выполняется условие j - i <= k.

Подпоследовательность массива получается путем удаления некоторого количества элементов (может быть ноль) из массива, оставляя оставшиеся элементы в их исходном порядке.

Пример:

Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subsequence is [10, 2, 5, 20].

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

1⃣Инициализируйте очередь queue и массив dp той же длины, что и nums.

2⃣Итерируйте i по индексам nums:
Если i минус первый элемент queue больше k, удалите элемент из начала queue.
Установите dp[i] как dp[queue.front()] + nums[i]. Если queue пуст, используйте 0 вместо dp[queue.front()].
Пока dp[queue.back()] меньше dp[i], удаляйте элементы с конца queue.
Если dp[i] > 0, добавьте i в конец queue.

3⃣Верните максимальное значение в массиве dp.

😎 Решение:

class Solution {
    func constrainedSubsetSum(_ nums: [Int], _ k: Int) -> Int {
        var queue = [Int]()
        var dp = [Int](repeating: 0, count: nums.count)
        var maxSum = Int.min
        
        for i in 0..<nums.count {
            if !queue.isEmpty && i - queue.first! > k {
                queue.removeFirst()
            }
            
            dp[i] = (!queue.isEmpty ? dp[queue.first!] : 0) + nums[i]
            
            while !queue.isEmpty && dp[queue.last!] < dp[i] {
                queue.removeLast()
            }
            
            if dp[i] > 0 {
                queue.append(i)
            }
            
            maxSum = max(maxSum, dp[i])
        }
        
        return maxSum
    }
}

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

Задача: 344. Reverse String
Сложность: easy

Напишите функцию, которая переворачивает строку. Входная строка представлена в виде массива символов s.

Вы должны сделать это, изменяя входной массив на месте с использованием O(1) дополнительной памяти.

Пример:

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

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

1⃣Инициализация указателей:
Установите два указателя: один на начало массива (left), другой на конец массива (right).

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

3⃣Завершение работы:
Повторяйте шаг 2 до тех пор, пока левый указатель не станет больше или равен правому.

😎 Решение:

class Solution {
    func reverseString(_ s: inout [Character]) {
        var left = 0
        var right = s.count - 1
        while left < right {
            s.swapAt(left, right)
            left += 1
            right -= 1
        }
    }
}

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

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

Вам дан массив цен, где prices[i] является ценой данной акции в i-й день.
Нужно выбрать день для покупки и день в будущем для продажи, чтобы получить максимальную прибыль. Если прибыли нет — вернуть 0.
Пример:
Input: prices = [7,1,5,3,6,4] Output: 5

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

1⃣Поддерживаем переменную minPrice, обновляем её при каждом снижении цены

2⃣Вычисляем потенциальную прибыль на каждом шаге и обновляем maxProfit

3⃣Возвращаем максимальную прибыль после прохода по массиву

😎 Решение:

class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        var minPrice = Int.max
        var maxProfit = 0
        
        for price in prices {
            if price < minPrice {
                minPrice = price
            } else if price - minPrice > maxProfit {
                maxProfit = price - minPrice
            }
        }
        
        return maxProfit
    }
}

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

Задача: 416. Partition Equal Subset Sum
Сложность: medium

Если задан целочисленный массив nums, верните третье максимальное число в этом массиве. Если третьего максимального числа не существует, верните максимальное число.

Пример:

Input: nums = [1,5,11,5]
Output: true

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

1⃣Проверьте, является ли сумма всех элементов массива четной. Если нет, верните false.

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

3⃣Инициализируйте массив для хранения возможных сумм и обновляйте его, проверяя каждое число в массиве.

😎 Решение:

func canPartition(_ nums: [Int]) -> Bool {
    let sum = nums.reduce(0, +)
    if sum % 2 != 0 { return false }
    let target = sum / 2
    var dp = [Bool](repeating: false, count: target + 1)
    dp[0] = true
    
    for num in nums {
        for j in stride(from: target, through: num, by: -1) {
            dp[j] = dp[j] || dp[j - num]
        }
    }
    
    return dp[target]
}

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

Задача: 69. Sqrt(x)
Сложность: easy

Дано неотрицательное целое число x. Верните квадратный корень из x, округлённый вниз до ближайшего целого числа. Возвращаемое целое число также должно быть неотрицательным.

Вы не должны использовать встроенные функции или операторы для возведения в степень.

Например, не следует использовать pow(x, 0.5) в C++ или x ** 0.5 в Python.

Пример:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

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

1⃣Если x < 2, верните x. Установите левую границу left = 2 и правую границу right = x / 2.

2⃣Пока left ≤ right:
Возьмите num = (left + right) / 2 в качестве предположения. Вычислите num × num и сравните его с x:
Если num × num > x, переместите правую границу right = pivot − 1.
В противном случае, если num × num < x, переместите левую границу left = pivot + 1.
В противном случае num × num == x, целочисленный квадратный корень найден, давайте вернем его.

3⃣Верните right.

😎 Решение:

func mySqrt(_ x: Int) -> Int {
    if x < 2 { return x }

    var left = 2
    var right = x / 2
    while left <= right {
        let pivot = left + (right - left) / 2
        let num = pivot * pivot
        if num > x {
            right = pivot - 1
        } else if num < x {
            left = pivot + 1
        } else {
            return pivot
        }
    }
    return right
}

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

Задача: 515. Largest Value in Each Tree Row
Сложность: medium

Дан корень двоичного дерева, верните массив наибольших значений в каждой строке дерева (индексация с 0).

Пример:

Input: root = [1,3,2,5,3,null,9]
Output: [1,3,9]

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

1⃣Если корень дерева равен null (пустое дерево), верните пустой список. Инициализируйте список ans для хранения результатов и очередь с корнем дерева для выполнения поиска в ширину (BFS).

2⃣Выполните BFS, пока очередь не пуста: инициализируйте currMax минимальным значением и сохраните длину очереди в currentLength. Повторите currentLength раз: удалите узел из очереди, обновите currMax, если значение узла больше. Для каждого дочернего узла, если он не равен null, добавьте его в очередь.

3⃣Добавьте currMax в ans. Верните ans.

😎 Решение:

class Solution {
    func largestValues(_ root: TreeNode?) -> [Int] {
        guard let root = root else { return [] }
        
        var ans = [Int]()
        var queue = [root]
        
        while !queue.isEmpty {
            var currentLength = queue.count
            var currMax = Int.min
            
            for _ in 0..<currentLength {
                let node = queue.removeFirst()
                currMax = max(currMax, node.val)
                if let left = node.left {
                    queue.append(left)
                }
                if let right = node.right {
                    queue.append(right)
                }
            }
            
            ans.append(currMax)
        }
        
        return ans
    }
}

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

Задача: 743. Network Delay Time
Сложность: medium

Дана сеть из узлов, помеченных от 1 до n. Также дано times - список времен прохождения сигнала в виде направленных ребер times[i] = (ui, vi, wi), где ui - исходный узел, vi - целевой узел, а wi - время прохождения сигнала от источника до цели. Мы пошлем сигнал из заданного узла k. Верните минимальное время, которое потребуется всем узлам, чтобы получить сигнал. Если все узлы не могут получить сигнал, верните -1.

Пример:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

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

1⃣Представьте граф в виде списка смежности.

2⃣Используйте алгоритм Дейкстры для нахождения кратчайших путей от узла k до всех других узлов.

3⃣Найдите максимальное значение среди кратчайших путей к узлам. Если какой-либо узел недостижим, верните -1.

😎 Решение:

import Foundation

func networkDelayTime(_ times: [[Int]], _ n: Int, _ k: Int) -> Int {
    var graph = [Int: [(Int, Int)]]()
    for i in 1...n {
        graph[i] = []
    }
    for time in times {
        graph[time[0]]?.append((time[1], time[2]))
    }

    var minHeap = [(0, k)]
    var minTime = [Int: Int]()
    for i in 1...n {
        minTime[i] = Int.max
    }
    minTime[k] = 0

    while !minHeap.isEmpty {
        minHeap.sort { $0.0 < $1.0 }
        let (time, node) = minHeap.removeFirst()
        if let neighbors = graph[node] {
            for (neighbor, t) in neighbors {
                let newTime = time + t
                if newTime < minTime[neighbor]! {
                    minTime[neighbor] = newTime
                    minHeap.append((newTime, neighbor))
                }
            }
        }
    }

    let maxTime = minTime.values.max()!
    return maxTime == Int.max ? -1 : maxTime
}

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

Задача: 561. Array Partition
Сложность: easy

Дан массив целых чисел nums из 2n элементов. Разделите эти числа на n пар (a1, b1), (a2, b2), ..., (an, bn) так, чтобы сумма min(ai, bi) для всех i была максимальной. Верните максимальную сумму.

Пример:

Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.

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

1⃣Отсортируйте массив nums в неубывающем порядке.

2⃣Итерируйте через массив, выбирая каждый второй элемент (начиная с первого).

3⃣Суммируйте выбранные элементы и верните эту сумму.

😎 Решение:

class Solution {
    func arrayPairSum(_ nums: [Int]) -> Int {
        let sortedNums = nums.sorted()
        var sum = 0
        for i in stride(from: 0, to: sortedNums.count, by: 2) {
            sum += sortedNums[i]
        }
        return sum
    }
}

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

Задача: 1498. Number of Subsequences That Satisfy the Given Sum Condition
Сложность: medium

Вам дан массив целых чисел nums и целое число target.

Верните количество непустых подпоследовательностей массива nums, таких что сумма минимального и максимального элемента в них меньше или равна target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

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

1⃣Инициализация и подготовка:
Инициализируйте переменные answer равным 0 и n как длину массива nums.
Отсортируйте массив nums.
Подготовьте массив power для хранения степеней двойки до n по модулю 10^9+7.

2⃣Итерация и бинарный поиск:
Для каждого индекса left от 0 до n - 1 выполните бинарный поиск, чтобы найти самый правый индекс right, где nums[right] <= target - nums[left].
Если left <= right, добавьте количество допустимых подпоследовательностей к answer.

3⃣Возврат результата:
Верните answer по модулю 10^9+7.

😎 Решение:

class Solution {
    func numSubseq(_ nums: [Int], _ target: Int) -> Int {
        let mod = 1_000_000_007
        let n = nums.count
        var nums = nums.sorted()
        
        var power = [Int](repeating: 1, count: n)
        for i in 1..<n {
            power[i] = (power[i - 1] * 2) % mod
        }
        
        var answer = 0
        var left = 0
        var right = n - 1
        
        while left <= right {
            if nums[left] + nums[right] <= target {
                answer = (answer + power[right - left]) % mod
                left += 1
            } else {
                right -= 1
            }
        }
        
        return answer
    }
}

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

Задача: 901. Online Stock Span
Сложность: medium

Разработайте алгоритм, который собирает ежедневные котировки цен на некоторые акции и возвращает размах цены этой акции за текущий день. Размах цены акции за один день - это максимальное количество дней подряд (начиная с этого дня и в обратном направлении), в течение которых цена акции была меньше или равна цене этого дня.

Например, если цены акции за последние четыре дня равны [7,2,1,2], а цена акции сегодня равна 2, то размах сегодняшнего дня равен 4, поскольку, начиная с сегодняшнего дня, цена акции была меньше или равна 2 в течение 4 дней подряд.
Также, если цена акции за последние четыре дня равна [7,34,1,2], а цена акции сегодня равна 8, то размах сегодняшнего дня равен 3, так как начиная с сегодняшнего дня цена акции была меньше или равна 8 в течение 3 дней подряд. Реализация класса StockSpanner: StockSpanner() Инициализирует объект класса. int next(int price) Возвращает размах цены акции, учитывая, что сегодняшняя цена равна price.

Пример:

Input
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output
[null, 1, 1, 1, 2, 1, 4, 6]

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

1⃣Инициализировать стек для хранения пар значений (цена, размах) и переменную для текущего индекса.

2⃣Для метода next:
Установить начальный размах текущего дня равным 1.
Пока стек не пуст и верхний элемент стека имеет цену меньше или равную текущей цене:
Добавить размах верхнего элемента стека к текущему размаху.
Удалить верхний элемент стека.

3⃣Добавить текущую цену и размах на вершину стека.
Вернуть текущий размах.

😎 Решение:

class StockSpanner {
    private var stack: [(Int, Int)] = []

    func next(_ price: Int) -> Int {
        var span = 1
        while let last = stack.last, last.0 <= price {
            span += last.1
            stack.removeLast()
        }
        stack.append((price, span))
        return span
    }
}

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

Задача: 1514. Path with Maximum Probability
Сложность: medium

Вам дан неориентированный взвешенный граф из n узлов (индексация с нуля), представленный списком ребер, где edges[i] = [a, b] является неориентированным ребром, соединяющим узлы a и b с вероятностью успешного прохождения этого ребра succProb[i].

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

Если пути от start до end не существует, верните 0. Ваш ответ будет принят, если он отличается от правильного ответа не более чем на 1e-5.

Пример:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.

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

1⃣Инициализируйте массив maxProb как максимальную вероятность достижения каждого узла из начального узла, установите maxProb[start] равным 1.

2⃣Расслабьте все ребра: для каждого ребра (u, v), если найдена более высокая вероятность достижения u через это ребро, обновите max_prob[u] как max_prob[u] = max_prob[v] * path_prob. Если найдена более высокая вероятность достижения v через это ребро, обновите max_prob[v].

3⃣Если нам не удается обновить какой-либо узел с более высокой вероятностью, мы можем остановить итерацию, перейдя к шагу 4. В противном случае повторяйте шаг 2, пока все ребра не будут расслаблены n - 1 раз.
Верните max_prob[end].

😎 Решение

class Solution {
    func maxProbability(_ n: Int, _ edges: [[Int]], _ succProb: [Double], _ start: Int, _ end: Int) -> Double {
        var maxProb = [Double](repeating: 0, count: n)
        maxProb[start] = 1.0

        for _ in 0..<n-1 {
            var hasUpdate = false
            for j in 0..<edges.count {
                let u = edges[j][0]
                let v = edges[j][1]
                let pathProb = succProb[j]
                if maxProb[u] * pathProb > maxProb[v] {
                    maxProb[v] = maxProb[u] * pathProb
                    hasUpdate = true
                }
                if maxProb[v] * pathProb > maxProb[u] {
                    maxProb[u] = maxProb[v] * pathProb
                    hasUpdate = true
                }
            }
            if !hasUpdate {
                break
            }
        }

        return maxProb[end]
    }
}

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

Задача: 295. Find Median from Data Stream
Сложность: hard

Медиана — это среднее значение в упорядоченном списке целых чисел. Если размер списка четный, то медианы нет, и медиана — это среднее арифметическое двух средних значений.

Например, для arr = [2, 3, 4] медиана равна 3.
Например, для arr = [2, 3] медиана равна (2 + 3) / 2 = 2.5.

Реализуйте класс MedianFinder:

MedianFinder() инициализирует объект MedianFinder.
void addNum(int num) добавляет целое число num из потока данных в структуру данных.
double findMedian() возвращает медиану всех элементов на данный момент. Ответы с точностью до 10^-5 от фактического ответа будут приниматься.

Пример:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

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

1⃣Храните числа в контейнере с возможностью изменения размера:
Создайте массив для хранения чисел.

2⃣Добавление нового числа:
Добавьте новое число в массив.

3⃣Вычисление и вывод медианы:
Отсортируйте массив.
Если размер массива нечетный, верните среднее значение массива.
Если размер массива четный, верните среднее арифметическое двух средних значений массива.

😎 Решение:

class MedianFinder {
    private var numbers: [Int] = []

    func addNum(_ num: Int) {
        numbers.append(num)
    }

    func findMedian() -> Double {
        numbers.sort()
        let n = numbers.count
        if n % 2 == 0 {
            return Double(numbers[n / 2 - 1] + numbers[n / 2]) / 2.0
        } else {
            return Double(numbers[n / 2])
        }
    }
}

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

Задача: 214. Shortest Palindrome
Сложность: hard

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

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

Пример:

Input: s = "aacecaaa"
Output: "aaacecaaa"

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

1⃣Создание обратной строки:
Создаем обратную строку rev от исходной строки s.

2⃣Итерация для поиска наибольшего палиндрома:
Перемещаемся по индексу i от 0 до n - 1.
Проверяем, является ли подстрока s от 0 до n - i равной подстроке rev от i до конца строки.
Если находим такое совпадение, возвращаем обратную подстроку от начала rev до i + исходная строка s.

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

😎 Решение:

class Solution {
    func shortestPalindrome(_ s: String) -> String {
        let n = s.count
        let rev = String(s.reversed())
        for i in 0..<n {
            let startIndex = s.index(s.startIndex, offsetBy: 0)
            let endIndex = s.index(s.startIndex, offsetBy: n - i)
            let revStartIndex = rev.index(rev.startIndex, offsetBy: i)
            let revEndIndex = rev.endIndex
            
            if s[startIndex..<endIndex] == rev[revStartIndex..<revEndIndex] {
                let prefix = rev[rev.startIndex..<revStartIndex]
                return prefix + s
            }
        }
        return ""
    }
}

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