Задача: 1496. Path Crossing
Сложность: easy

Дана строка path, где path[i] = 'N', 'S', 'E' или 'W', каждая из которых представляет движение на одну единицу на север, юг, восток или запад соответственно. Вы начинаете с точки (0, 0) на 2D плоскости и идете по пути, указанному в path.

Верните true, если путь пересекает сам себя в какой-либо точке, то есть если вы в какой-то момент окажетесь в месте, которое уже посещали ранее. В противном случае верните false.

Пример:

Input: path = "NESWW"
Output: true
Explanation: Notice that the path visits the origin twice.

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

1⃣Инициализация переменных:
Создать хэш-карту moves, которая сопоставляет символы 'N', 'S', 'E', 'W' с соответствующими значениями.
Инициализировать множество visited с начальной точкой (0, 0).
Установить начальные координаты x = 0 и y = 0.

2⃣Проход по строке path:
Для каждого символа c в path получить значения (dx, dy) из moves[c].
Обновить координаты: добавить dx к x и dy к y.
Проверить, содержится ли текущая точка (x, y) в visited. Если да, вернуть true.
Добавить текущую точку (x, y) в visited.

3⃣Возврат результата:
Если ни одна точка не пересекалась, вернуть false.

😎 Решение:

class Solution {
    func isPathCrossing(_ path: String) -> Bool {
        let moves: [Character: (Int, Int)] = [
            "N": (0, 1), "S": (0, -1),
            "E": (1, 0), "W": (-1, 0)
        ]
        
        var visited: Set<[Int]> = [[0, 0]]
        var x = 0, y = 0
        
        for c in path {
            let move = moves[c]!
            x += move.0
            y += move.1
            let point = [x, y]
            if visited.contains(point) {
                return true
            }
            visited.insert(point)
        }
        
        return false
    }
}

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

Задача: 494. Target Sum
Сложность: medium

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

Вы хотите создать выражение из nums, добавляя один из символов '+' или '-' перед каждым числом в nums, а затем объединяя все числа.
Например, если nums = [2, 1], вы можете добавить '+' перед 2 и '-' перед 1, а затем объединить их, чтобы получить выражение "+2-1".
Верните количество различных выражений, которые можно построить и которые оцениваются в target.

Пример:

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

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

1⃣Инициализация и вызов рекурсивной функции
Создайте переменную для хранения количества решений (count). Вызовите рекурсивную функцию calculate с начальными параметрами (nums, начальный индекс 0, начальная сумма 0, и target).

2⃣Рекурсивная функция calculate
Если текущий индекс равен длине массива, проверьте, равна ли текущая сумма значению target. Если да, увеличьте счетчик решений. В противном случае, вызовите функцию рекурсивно дважды: добавляя и вычитая текущее значение из суммы.

3⃣Возврат результата
После завершения всех рекурсивных вызовов верните значение счетчика решений.

😎 Решение:

class Solution {
    var count = 0
    
    func findTargetSumWays(_ nums: [Int], _ S: Int) -> Int {
        calculate(nums, 0, 0, S)
        return count
    }
    
    func calculate(_ nums: [Int], _ i: Int, _ sum: Int, _ S: Int) {
        if i == nums.count {
            if sum == S {
                count += 1
            }
        } else {
            calculate(nums, i + 1, sum + nums[i], S)
            calculate(nums, i + 1, sum - nums[i], S)
        }
    }
}

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

Задача: 380. Insert Delete GetRandom O(1)
Сложность: medium

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

RandomizedSet(): Инициализирует объект RandomizedSet.
bool insert(int val): Вставляет элемент val в множество, если его там нет. Возвращает true, если элемент отсутствовал, и false в противном случае.
bool remove(int val): Удаляет элемент val из множества, если он присутствует. Возвращает true, если элемент присутствовал, и false в противном случае.
int getRandom(): Возвращает случайный элемент из текущего множества элементов (гарантируется, что по крайней мере один элемент существует при вызове этого метода). Каждый элемент должен иметь равную вероятность быть возвращенным.
Вы должны реализовать функции класса таким образом, чтобы каждая функция работала в среднем за O(1) по времени.

Пример:

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

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

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

2⃣Метод insert(val): Проверить наличие значения в словаре. Если отсутствует, добавить значение в список и обновить словарь с новым индексом.
Метод remove(val): Проверить наличие значения в словаре. Если присутствует, заменить удаляемое значение последним элементом списка, обновить его индекс в словаре, удалить последний элемент из списка и удалить значение из словаря.

3⃣Метод getRandom(): Возвращать случайный элемент из списка, используя встроенную функцию генерации случайных чисел.

😎 Решение:

class RandomizedSet {
    private var dict: [Int: Int]
    private var list: [Int]

    init() {
        dict = [Int: Int]()
        list = [Int]()
    }

    func insert(_ val: Int) -> Bool {
        if dict[val] != nil {
            return false
        }
        dict[val] = list.count
        list.append(val)
        return true
    }

    func remove(_ val: Int) -> Bool {
        guard let index = dict[val] else {
            return false
        }
        let lastElement = list.removeLast()
        if index < list.count {
            list[index] = lastElement
            dict[lastElement] = index
        }
        dict[val] = nil
        return true
    }

    func getRandom() -> Int {
        return list.randomElement()!
    }
}

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

Задача: 205. Isomorphic Strings
Сложность: easy

Даны две строки s и t, определите, являются ли они изоморфными.

Две строки s и t являются изоморфными, если символы в s могут быть заменены для получения t.

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

Пример:

Input: s = "egg", t = "add"
Output: true

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

1⃣Определите два словаря: mapping_s_t для отображения символов из строки s в символы строки t, и mapping_t_s для отображения символов из строки t в символы строки s.

2⃣Итеративно пройдитесь по символам строк s и t. Для каждого символа c1 из s и соответствующего c2 из t, если c1 нет в mapping_s_t и c2 нет в mapping_t_s, добавьте соответствующие отображения; если одно из отображений существует, проверьте, соответствует ли оно ожидаемому значению.

3⃣Если в процессе проверки какое-либо отображение неверно, верните false. Если все проверки пройдены успешно, верните true после окончания итерации по строкам.

😎 Решение:

class Solution {
    func isIsomorphic(_ s: String, _ t: String) -> Bool {
        var mappingStoT = [Character: Character]()
        var mappingTtoS = [Character: Character]()

        let sArray = Array(s)
        let tArray = Array(t)

        for i in 0..<sArray.count {
            let c1 = sArray[i]
            let c2 = tArray[i]

            if mappingStoT[c1] == nil && mappingTtoS[c2] == nil {
                mappingStoT[c1] = c2
                mappingTtoS[c2] = c1
            } else if mappingStoT[c1] != c2 || mappingTtoS[c2] != c1 {
                return false
            }
        }

        return true
    }
}

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

Задача: 383. Ransom Note
Сложность: easy

Даны две строки ransomNote и magazine, верните true, если ransomNote можно составить, используя буквы из magazine, и false в противном случае.

Каждая буква из magazine может быть использована в ransomNote только один раз.

Пример:

Input: ransomNote = "a", magazine = "b"
Output: false

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

1⃣Поскольку строки являются неизменяемым типом, их нельзя изменять, поэтому у них нет операций "вставки" и "удаления".

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

3⃣Повторяйте этот процесс, пока не будут удалены все необходимые символы.

😎 Решение:

func canConstruct(_ ransomNote: String, _ magazine: String) -> Bool {
    var magazine = magazine
    
    for char in ransomNote {
        if let index = magazine.firstIndex(of: char) {
            magazine.remove(at: index)
        } else {
            return false
        }
    }
    return true
}

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

Задача: 1279. Traffic Light Controlled Intersection
Сложность: easy

Здесь есть пересечение двух дорог. Первая дорога - это дорога A, по которой автомобили движутся с севера на юг в направлении 1 и с юга на север в направлении 2. Вторая дорога - дорога B, по которой машины едут с запада на восток в направлении 3 и с востока на запад в направлении 4. На каждой дороге перед перекрестком есть светофор. Зеленый означает, что автомобили могут пересекать перекресток в обоих направлениях. Красный означает, что автомобили в обоих направлениях не могут пересекать перекресток и должны ждать, пока загорится зеленый свет. Светофор не может гореть зеленым одновременно на обеих дорогах. Это значит, что когда на дороге А горит зеленый свет, на дороге Б он красный, а когда на дороге Б горит зеленый свет, на дороге А он красный.
Изначально на дороге A горит зеленый сигнал светофора, а на дороге B - красный. Когда на одной дороге горит зеленый свет, все автомобили могут пересекать перекресток в обоих направлениях, пока на другой дороге не загорится зеленый.Два автомобиля, движущиеся по разным дорогам, не должны пересекать перекресток одновременно. Разработайте систему управления светофором на этом перекрестке без тупиков. Реализуйте функцию void carArrived(carId, roadId, direction, turnGreen, crossCar), где: carId - идентификатор автомобиля, который приехал. roadId - идентификатор дороги, по которой едет автомобиль.
direction - направление движения автомобиля. turnGreen - функция, которую можно вызвать, чтобы переключить светофор на зеленый свет на текущей дороге. crossCar - функция, которую можно вызвать, чтобы позволить текущему автомобилю пересечь перекресток. Ваш ответ считается правильным, если он позволяет избежать тупика на перекрестке.Переключение светофора на зеленый свет на дороге, где он уже был зеленым, считается неправильным ответом.

Пример:

Input: cars = [1,2,3,4,5], directions = [2,4,3,3,1], arrivalTimes = [10,20,30,40,40]
Output: [
"Car 1 Has Passed Road A In Direction 2",    // Traffic light on road A is green, car 1 can cross the intersection.
"Traffic Light On Road B Is Green",          // Car 2 requests green light for road B.
"Car 2 Has Passed Road B In Direction 4",    // Car 2 crosses as the light is green on road B now.
"Car 3 Has Passed Road B In Direction 3",    // Car 3 crosses as the light is green on road B now.
"Traffic Light On Road A Is Green",          // Car 5 requests green light for road A.
"Car 5 Has Passed Road A In Direction 1",    // Car 5 crosses as the light is green on road A now.
"Traffic Light On Road B Is Green",          // Car 4 requests green light for road B. Car 4 blocked until car 5 crosses and then traffic light is green on road B.
"Car 4 Has Passed Road B In Direction 3"     // Car 4 crosses as the light is green on road B now.
]

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

1⃣Если на дороге, по которой едет автомобиль, уже зеленый свет, вызываем функцию crossCar.

2⃣Если на дороге, по которой едет автомобиль, красный свет, вызываем функцию turnGreen, чтобы переключить свет на зеленый, и затем вызываем функцию crossCar.

3⃣Обеспечиваем, что функции turnGreen и crossCar вызываются атомарно для предотвращения гонок и тупиков.

😎 Решение:

import Foundation

class TrafficLight {
    private var greenRoad = 1
    private let lock = NSLock()

    func carArrived(
        _ carId: Int,
        _ roadId: Int,
        _ direction: Int,
        _ turnGreen: () -> Void,
        _ crossCar: () -> Void
    ) {
        lock.lock()
        defer { lock.unlock() }
        if greenRoad != roadId {
            turnGreen()
            greenRoad = roadId
        }
        crossCar()
    }
}

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

Задача: 653. Two Sum IV - Input is a BST
Сложность: easy

Вам дан целочисленный массив nums без дубликатов. Из nums можно рекурсивно построить максимальное двоичное дерево, используя следующий алгоритм: создайте корневой узел, значение которого равно максимальному значению в nums. Рекурсивно постройте левое поддерево по префиксу подмассива слева от максимального значения. Рекурсивно постройте правое поддерево по суффиксу подмассива справа от максимального значения. Верните максимальное двоичное дерево, построенное из nums.

Пример:

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

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

1⃣Выполните обход BST и сохраните все значения узлов в набор.

2⃣Для каждого узла в процессе обхода проверьте, существует ли в наборе значение, равное k минус значение текущего узла.

3⃣Если найдена такая пара, верните true. Если обход завершен и пары не найдены, верните false.

😎 Решение:

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 findTarget(_ root: TreeNode?, _ k: Int) -> Bool {
    var seen = Set<Int>()
    func find(_ node: TreeNode?) -> Bool {
        guard let node = node else { return false }
        if seen.contains(k - node.val) {
            return true
        }
        seen.insert(node.val)
        return find(node.left) || find(node.right)
    }
    return find(root)
}

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

Задача: 727. Minimum Window Subsequence
Сложность: hard

Если в строках s1 и s2 нет такого окна, которое покрывало бы все символы в s2, верните пустую строку "". Если таких окон минимальной длины несколько, возвращается окно с самым левым начальным индексом.

Пример:

Input: s1 = "abcdebdde", s2 = "bde"
Output: "bcde"

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

1⃣Используйте два указателя для определения текущего окна.

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

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

😎 Решение:

func minWindow(_ s1: String, _ s2: String) -> String {
    if s1.isEmpty || s2.isEmpty {
        return ""
    }

    var dictT = [Character: Int]()
    for char in s2 {
        dictT[char, default: 0] += 1
    }

    let required = dictT.count
    var l = 0, r = 0, formed = 0
    var windowCounts = [Character: Int]()
    var ans = (length: Int.max, start: 0, end: 0)
    let s1Array = Array(s1)

    while r < s1Array.count {
        let char = s1Array[r]
        windowCounts[char, default: 0] += 1

        if let count = dictT[char], windowCounts[char] == count {
            formed += 1
        }

        while l <= r && formed == required {
            let char = s1Array[l]

            if r - l + 1 < ans.length {
                ans = (r - l + 1, l, r)
            }

            windowCounts[char, default: 0] -= 1
            if let count = dictT[char], windowCounts[char]! < count {
                formed -= 1
            }

            l += 1
        }

        r += 1
    }

    return ans.length == Int.max ? "" : String(s1Array[ans.start...ans.end])
}

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

Задача: №19. Remove Nth Node From End of List
Сложность: medium

Учитывая заголовок связанного списка, удалите n-й узел из конца списка и верните его заголовок.

Пример:

Input: head = [1,2,3,4,5], n = 2  
Output: [1,2,3,5]  

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

1⃣Создать фиктивный узел, который указывает на head, чтобы упростить удаление первого элемента.

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

3⃣Удалить нужный узел, изменив ссылки, и вернуть новый head.

😎 Решение:

class Solution {
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        let dummy = ListNode(0)
        dummy.next = head
        
        var prev: ListNode? = dummy
        var post: ListNode? = dummy
        
        for _ in 0..<n {
            post = post?.next
        }
        
        while post?.next != nil {
            prev = prev?.next
            post = post?.next
        }
        
        prev!.next = prev!.next!.next
        
        return dummy.next
    }
}

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

Задача: 159. Longest Substring with At Most Two Distinct Characters
Сложность: medium

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

Пример:

Input: s = "eceba"
Output: 3
Explanation: The substring is "ece" which its length is 3.

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

1⃣Возвратить N, если длина строки N меньше 3. Установить оба указателя в начало строки left = 0 и right = 0 и инициализировать максимальную длину подстроки max_len = 2.

2⃣Пока указатель right меньше N:
Если в хэшмапе меньше 3 различных символов, добавить текущий символ s[right] в хэшмап и переместить указатель right вправо.
Если в хэшмапе 3 различных символа, удалить самый левый символ из хэшмапа и переместить указатель left, чтобы скользящее окно содержало только 2 различных символа.

3⃣Обновить max_len.

😎 Решение:

func lengthOfLongestSubstringTwoDistinct(_ s: String) -> Int {
    let n = s.count
    if n < 3 { return n }

    var left = 0
    var right = 0
    var hashmap: [Character: Int] = [:]

    var maxLen = 2

    let sArray = Array(s)
    while right < n {
        hashmap[sArray[right]] = right
        right += 1

        if hashmap.count == 3 {
            let delIdx = hashmap.values.min()!
            hashmap.removeValue(forKey: sArray[delIdx])
            left = delIdx + 1
        }

        maxLen = max(maxLen, right - left)
    }
    return maxLen
}

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

Задача: 410. Split Array Largest Sum
Сложность: easy

Учитывая целочисленный массив nums и целое число k, разбейте nums на k непустых подмассивов так, чтобы наибольшая сумма любого подмассива была минимальна. Верните минимизированную наибольшую сумму разбиения. Подмассив - это смежная часть массива.

Пример:

Input: nums = [7,2,5,10,8], k = 2
Output: 18

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

1⃣Определите границы для бинарного поиска: минимальная сумма равна максимальному элементу массива, максимальная сумма равна сумме всех элементов массива.

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

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

😎 Решение:

func splitArray(_ nums: [Int], _ k: Int) -> Int {
    var left = nums.max()!
    var right = nums.reduce(0, +)
    while left < right {
        let mid = (left + right) / 2
        if canSplit(nums, k, mid) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left
}

func canSplit(_ nums: [Int], _ k: Int, _ maxSum: Int) -> Bool {
    var currentSum = 0
    var subarrays = 1
    for num in nums {
        if currentSum + num > maxSum {
            currentSum = num
            subarrays += 1
            if subarrays > k {
                return false
            }
        } else {
            currentSum += num
        }
    }
    return true
}

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

Задача: №45. Jump Game II
Сложность: medium

Вам предоставляется массив целых чисел nums с индексом 0 и длиной n. Изначально вы располагаетесь в nums[0].
Каждый элемент nums[i] представляет максимальную длину прямого перехода от индекса i.
Возвращает минимальное количество переходов для достижения nums[n - 1].

Пример:

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

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

1⃣Использовать greedy-подход: отслеживать текущий диапазон прыжков.

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

3⃣Остановиться, как только достигнем последнего индекса.

😎 Решение:

class Solution {
    func jump(_ nums: [Int]) -> Int {
        var jumps = 0, farthest = 0, end = 0
        
        for i in 0..<nums.count - 1 {
            farthest = max(farthest, i + nums[i])
            
            if i == end {
                jumps += 1
                end = farthest
            }
        }
        
        return jumps
    }
}

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

Задача: 125. Valid Palindrome
Сложность: easy

Фраза является палиндромом, если после преобразования всех заглавных букв в строчные и удаления всех неалфавитно-цифровых символов она читается одинаково как слева направо, так и справа налево. Алфавитно-цифровые символы включают в себя буквы и цифры.

Для данной строки s верните true, если она является палиндромом, и false в противном случае.

Пример:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

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

1⃣Поскольку входная строка содержит символы, которые нам нужно игнорировать при проверке на палиндром, становится трудно определить реальную середину нашего палиндромического ввода.

2⃣Вместо того, чтобы двигаться от середины наружу, мы можем двигаться внутрь к середине! Если начать перемещаться внутрь, с обоих концов входной строки, мы можем ожидать увидеть те же символы в том же порядке.

3⃣Результирующий алгоритм прост:
1. Установите два указателя, один на каждом конце входной строки.
2. Если ввод является палиндромом, оба указателя должны указывать на эквивалентные символы в любой момент времени.
3. Если это условие не выполняется в какой-либо момент времени, мы прерываемся и возвращаемся раньше.
4. Мы можем просто игнорировать неалфавитно-цифровые символы, продолжая двигаться дальше.
5. Продолжайте перемещение внутрь, пока указатели не встретятся в середине.

😎 Решение:

class Solution {
    func isPalindrome(_ s: String) -> Bool {
        let characters = Array(s.lowercased())
        var i = 0
        var j = characters.count - 1

        while i < j {
            while i < j && !characters[i].isLetter && !characters[i].isNumber {
                i += 1
            }
            while i < j && !characters[j].isLetter && !characters[j].isNumber {
                j -= 1
            }

            if characters[i] != characters[j] {
                return false
            }

            i += 1
            j -= 1
        }

        return true
    }
}

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

Задача: 124. Binary Tree Maximum Path Sum
Сложность: hard

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

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

Пример:

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

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

1⃣Наивная реализация этой идеи заключалась бы в разделении последовательностей на две части и последующем перечислении каждой из подпоследовательностей, хотя это определенно не самое оптимизированное решение.
Для последовательности длиной N у нас было бы N возможных разделений (включая отсутствие разделения), каждый элемент был бы посещен один раз в каждом разделении. В результате общая временная сложность этой наивной реализации составила бы O(N²).

2⃣Мы могли бы сделать лучше, чем наивная реализация O(N²). Что касается алгоритмов разделяй и властвуй,
одна из общих техник, которую мы можем применить для оптимизации временной сложности, называется динамическим программированием (DP), где мы меняем менее повторяющиеся вычисления на некоторое дополнительное пространство.
В алгоритмах динамического программирования обычно мы создаем массив одного или двух измерений для сохранения промежуточных оптимальных результатов. В данной задаче мы бы использовали два массива, один массив сохранял бы результаты последовательности слева направо, а другой массив сохранял бы результаты последовательности справа налево. Для удобства мы могли бы назвать это двунаправленным динамическим программированием.

3⃣Сначала мы обозначаем последовательность цен как Prices[i], с индексом начиная от 0 до N-1. Затем мы определяем два массива, а именно left_profits[i] и right_profits[i].
Как следует из названия, каждый элемент в массиве left_profits[i] будет содержать максимальную прибыль, которую можно получить от выполнения одной транзакции в левой подпоследовательности цен от индекса ноль до i, (т.е. Prices[0], Prices[1], ... Prices[i]).
Например, для подпоследовательности [7, 1, 5] соответствующий left_profits[2] будет равен 4, что означает покупку по цене 1 и продажу по цене 5.
И каждый элемент в массиве right_profits[i] будет содержать максимальную прибыль, которую можно получить от выполнения одной транзакции в правой подпоследовательности цен от индекса i до N-1, (т.е. Prices[i], Prices[i+1], ... Prices[N-1]).
Например, для правой подпоследовательности [3, 6, 4] соответствующий right_profits[3] будет равен 3, что означает покупку по цене 3 и продажу по цене 6.
Теперь, если мы разделим последовательность цен вокруг элемента с индексом i на две подпоследовательности, с левыми подпоследовательностями как Prices[0], Prices[1], ... Prices[i] и правой подпоследовательностью как Prices[i+1], ... Prices[N-1],
то общая максимальная прибыль, которую мы получим от этого разделения (обозначенная как max_profits[i]), может быть выражена следующим образом:
max_profits[i] = left_profits[i] + right_profits[i+1]

😎 Решение:

class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        if prices.count <= 1 {
            return 0
        }

        let length = prices.count
        var leftMin = prices[0]
        var rightMax = prices.last!

        var leftProfits = Array(repeating: 0, count: length)
        var rightProfits = Array(repeating: 0, count: length + 1)

        for l in 1..<length {
            leftProfits[l] = max(leftProfits[l - 1], prices[l] - leftMin)
            leftMin = min(leftMin, prices[l])

            let r = length - 1 - l
            rightProfits[r] = max(rightProfits[r + 1], rightMax - prices[r])
            rightMax = max(rightMax, prices[r])
        }

        var maxProfit = 0
        for i in 0..<length {
            maxProfit = max(maxProfit, leftProfits[i] + rightProfits[i + 1])
        }

        return maxProfit
    }
}

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

Задача: 461. Hamming Distance
Сложность: easy

Расстояние Хэмминга между двумя целыми числами — это количество позиций, в которых соответствующие биты различны.

Даны два целых числа x и y, верните расстояние Хэмминга между ними.

Пример:

Input: x = 3, y = 1
Output: 1

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

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

2⃣Однако, поскольку это задача на LeetCode, использование встроенных функций можно сравнить с "реализацией LinkedList с использованием LinkedList". Поэтому рассмотрим также несколько интересных ручных алгоритмов для подсчета битов.

3⃣Пошаговый подсчет битов:
Выполните побитовое XOR между x и y.
Инициализируйте счетчик bitCount = 0.
Пока число не равно нулю:
Если текущий бит равен 1, увеличьте bitCount.
Сдвиньте число вправо на один бит.
Возвращайте bitCount.

😎 Решение:

class Solution {
    func hammingDistance(_ x: Int, _ y: Int) -> Int {
        return (x ^ y).nonzeroBitCount
    }
}

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

Задача: 232. Implement Queue using Stacks
Сложность: easy

Реализуйте очередь (FIFO) с использованием только двух стеков. Реализованная очередь должна поддерживать все функции обычной очереди (push, peek, pop и empty).

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

void push(int x) добавляет элемент x в конец очереди.
int pop() удаляет элемент из начала очереди и возвращает его.
int peek() возвращает элемент из начала очереди.
boolean empty() возвращает true, если очередь пуста, и false в противном случае.

Пример:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

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

1⃣Добавление элемента: Для метода push(int x) переместите все элементы из стека s1 в стек s2. Добавьте элемент x в стек s2. Затем переместите все элементы обратно из стека s2 в стек s1. Если стек s1 пуст, обновите переменную front значением x.

2⃣Удаление и проверка первого элемента: Для метода pop() удалите элемент из начала очереди, извлекая верхний элемент из стека s1. Обновите переменную front на новый верхний элемент стека s1, если он не пуст. Для метода peek() верните значение переменной front, так как она всегда хранит первый элемент очереди.

3⃣Проверка на пустоту: Для метода empty() верните результат проверки, является ли стек s1 пустым.

😎 Решение:

class MyQueue {
    private var s1: [Int] = []
    private var s2: [Int] = []
    private var front: Int = 0

    func push(_ x: Int) {
        if s1.isEmpty {
            front = x
        }
        while !s1.isEmpty {
            s2.append(s1.removeLast())
        }
        s2.append(x)
        while !s2.isEmpty {
            s1.append(s2.removeLast())
        }
    }

    func pop() -> Int {
        let res = s1.removeLast()
        if !s1.isEmpty {
            front = s1.last!
        }
        return res
    }

    func empty() -> Bool {
        return s1.isEmpty
    }

    func peek() -> Int {
        return front
    }
}

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

Задача: 935. Knight Dialer
Сложность: medium

Шахматный конь обладает уникальным движением: он может перемещаться на две клетки по вертикали и одну клетку по горизонтали, или на две клетки по горизонтали и одну клетку по вертикали (при этом обе клетки образуют форму буквы L). Возможные движения шахматного коня показаны на этой диаграмме: Шахматный конь может двигаться так, как показано на шахматной диаграмме ниже: У нас есть шахматный конь и телефонная панель, как показано ниже, конь может стоять только на числовой клетке (то есть на синей клетке).


Учитывая целое число n, верните, сколько различных телефонных номеров длины n мы можем набрать. Вам разрешается сначала поставить коня на любую цифровую клетку, а затем выполнить n - 1 прыжков, чтобы набрать номер длины n. Все прыжки должны быть правильными прыжками коня. Поскольку ответ может быть очень большим, верните ответ по модулю 10^9 + 7.

Пример:

Input: n = 1
Output: 10

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

1⃣Определить возможные движения коня с каждой цифровой клетки.
Использовать динамическое программирование для хранения количества способов достижения каждой цифровой клетки на каждом шаге.

2⃣Инициализировать массив DP количеством способов набора телефонного номера длины 1 для каждой цифровой клетки (это просто 1).
На каждом шаге обновлять массив DP, переходя по всем возможным движениям коня.

3⃣Вернуть сумму всех значений в массиве DP на последнем шаге.

😎 Решение:

var knightDialer = function(n) {
    const MOD = 10**9 + 7;
    const moves = {
        0: [4, 6],
        1: [6, 8],
        2: [7, 9],
        3: [4, 8],
        4: [0, 3, 9],
        5: [],
        6: [0, 1, 7],
        7: [2, 6],
        8: [1, 3],
        9: [2, 4]
    };
    
    let dp = new Array(10).fill(1);
    
    for (let step = 1; step < n; step++) {
        const newDp = new Array(10).fill(0);
        for (let i = 0; i < 10; i++) {
            for (const move of moves[i]) {
                newDp[move] = (newDp[move] + dp[i]) % MOD;
            }
        }
        dp = newDp;
    }
    
    return dp.reduce((acc, val) => (acc + val) % MOD, 0);
};

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

Задача: 135. Candy
Сложность: hard

В очереди стоят n детей. Каждому ребенку присвоено значение рейтинга, указанное в массиве целых чисел ratings.

Вы раздаете конфеты этим детям с соблюдением следующих требований:

Каждый ребенок должен получить как минимум одну конфету.
Дети с более высоким рейтингом должны получать больше конфет, чем их соседи.
Верните минимальное количество конфет, которое вам нужно иметь, чтобы распределить их среди детей.

Пример:

Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

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

1⃣Инициализация и первичное заполнение массивов:
Создайте два массива: left2right для расчета конфет с учетом только левых соседей и right2left для расчета с учетом только правых соседей. Изначально каждому ученику в обоих массивах присваивается по одной конфете.

2⃣Обход и обновление значений в массивах:
Проходите массив ratings слева направо, увеличивая значение в left2right для каждого ученика, чей рейтинг выше рейтинга его левого соседа.
Затем проходите массив справа налево, увеличивая значение в right2left для каждого ученика, чей рейтинг выше рейтинга его правого соседа.

3⃣Расчет минимального количества конфет:
Для каждого ученика определите максимальное значение конфет между left2right[i] и right2left[i], чтобы соответствовать требованиям к распределению конфет.
Суммируйте полученные значения для всех учеников, чтобы найти минимальное количество конфет, необходимое для соблюдения всех правил.

😎 Решение:

func candy(_ ratings: [Int]) -> Int {
    let len = ratings.count
    var sum = 0
    var left2right = Array(repeating: 1, count: len)
    var right2left = Array(repeating: 1, count: len)

    for i in 1..<len {
        if ratings[i] > ratings[i - 1] {
            left2right[i] = left2right[i - 1] + 1
        }
    }
    for i in stride(from: len - 2, through: 0, by: -1) {
        if ratings[i] > ratings[i + 1] {
            right2left[i] = right2left[i + 1] + 1
        }
    }
    for i in 0..<len {
        sum += max(left2right[i], right2left[i])
    }
    return sum
}

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

Задача: 673. Number of Longest Increasing Subsequence
Сложность: medium

Дан массив целых чисел nums, верните количество самых длинных строго возрастающих подпоследовательностей.

Пример:

Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2

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

1⃣Объявите два массива динамического программирования length и count, и инициализируйте их значениями length[i]=1 и count[i]=1. Итерируйте i от 0 до n−1. Для каждого i итерируйте j от 0 до i−1 и, если nums[j] < nums[i], обновите length[i] и count[i] в зависимости от значений length[j] и count[j].

2⃣Найдите максимальное значение в массиве length и сохраните его в переменной maxLength. Инициализируйте переменную result = 0.

3⃣Итерируйте i от 0 до n−1 и, если length[i] = maxLength, добавьте count[i] к result. Верните result.

😎 Решение:

class Solution {
    func findNumberOfLIS(_ nums: [Int]) -> Int {
        let n = nums.count
        var length = Array(repeating: 1, count: n)
        var count = Array(repeating: 1, count: n)
        
        for i in 0..<n {
            for j in 0..<i {
                if nums[j] < nums[i] {
                    if length[j] + 1 > length[i] {
                        length[i] = length[j] + 1
                        count[i] = 0
                    }
                    if length[j] + 1 == length[i] {
                        count[i] += count[j]
                    }
                }
            }
        }
        
        let maxLength = length.max() ?? 0
        var result = 0
        
        for i in 0..<n {
            if length[i] == maxLength {
                result += count[i]
            }
        }
        
        return result
    }
}

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