Задача: 92. Reverse Linked List II
Сложность: medium

Дан указатель на начало односвязного списка и два целых числа left и right, где left <= right. Необходимо перевернуть узлы списка, начиная с позиции left и заканчивая позицией right, и вернуть измененный список.

Пример:

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

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

1⃣Определяем рекурсивную функцию, которая будет отвечать за переворачивание части односвязного списка. Назовем эту функцию recurse. Функция принимает три параметра: m, начальную точку переворота, n, конечную точку переворота, и указатель right, который начинается с узла n в связанном списке и движется назад вместе с откатом рекурсии. Если это пока не ясно, следующие диаграммы помогут.

2⃣Также у нас есть указатель left, который начинается с узла m в связанном списке и движется вперед. В Python мы должны использовать глобальную переменную для этого, которая изменяется с каждым вызовом рекурсии. В других языках, где изменения, сделанные в вызовах функций, сохраняются, мы можем рассматривать этот указатель как дополнительную переменную для функции recurse.
В рекурсивном вызове, учитывая m, n и right, мы проверяем, равно ли n единице. Если это так, дальше двигаться не нужно.

3⃣До тех пор, пока мы не достигнем n = 1, мы продолжаем двигать указатель right на один шаг вперед, после чего делаем рекурсивный вызов с уменьшенным на один значением n. В то же время мы продолжаем двигать указатель left вперед до тех пор, пока m не станет равным 1. Когда мы говорим, что указатель движется вперед, мы имеем в виду pointer.next.
Таким образом, мы откатываемся, как только n достигает 1. В этот момент указатель right находится на последнем узле подсписка, который мы хотим перевернуть, и left уже достиг первого узла этого подсписка. Тогда мы меняем данные и перемещаем указатель left на один шаг вперед с помощью left = left.next. Нам нужно, чтобы это изменение сохранялось в процессе отката.
Оттуда при каждом откате указатель right движется на один шаг назад. Это и есть та симуляция, о которой мы всё время говорили. Обратное движение симулируется откатом.
Мы прекращаем обмены, когда right == left, что происходит, если размер подсписка нечетный, или right.next == left, что происходит в процессе отката для четного подсписка, когда указатель right пересекает left. Мы используем глобальный булевый флаг для остановки обменов, как только эти условия выполнены.

😎 Решение:

class ListNode {
    var val: Int
    var next: ListNode?

    init(_ val: Int, _ next: ListNode? = nil) {
        self.val = val
        self.next = next
    }
}

class Solution {
    private var left: ListNode?
    private var stop = false

    func reverseBetween(_ head: ListNode?, _ m: Int, _ n: Int) -> ListNode? {
        if head == nil { return nil }

        left = head
        var right = head
        stop = false

        recurseAndReverse(right, m, n)
        return head
    }

    private func recurseAndReverse(_ right: ListNode?, _ m: Int, _ n: Int) {
        if n == 1 { return }

        if let next = right?.next {
            recurseAndReverse(next, m - 1, n - 1)
        }

        if left === right || right?.next === left {
            stop = true
        }

        if !stop {
            let temp = left?.val
            left?.val = right?.val
            right?.val = temp

            left = left?.next
        }
    }
}
class ListNode {
    var val: Int
    var next: ListNode?

    init(_ val: Int, _ next: ListNode? = nil) {
        self.val = val
        self.next = next
    }
}

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

Задача: 270. Closest Binary Search Tree Value
Сложность: easy

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

Пример:

Input: root = [4,2,5,1,3], target = 3.714286
Output: 4

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

1⃣Построить массив с помощью inorder обхода:
Выполнить inorder обход дерева и собрать элементы в отсортированный массив.

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

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

😎 Решение:

class Solution {
    func closestValue(_ root: TreeNode?, _ target: Double) -> Int {
        var closest = root!.val
        var node = root
        while node != nil {
            if abs(Double(node!.val) - target) < abs(Double(closest) - target) {
                closest = node!.val
            } else if abs(Double(node!.val) - target) == abs(Double(closest) - target) {
                closest = min(node!.val, closest)
            }
            node = target < Double(node!.val) ? node!.left : node!.right
        }
        return closest
    }
}

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

Задача: 1345. Jump Game IV
Сложность: hard

Дан массив целых чисел arr, изначально вы находитесь на первом индексе массива.

За один шаг вы можете прыгнуть с индекса i на индекс:

- i + 1, где: i + 1 < arr.length.
- i - 1, где: i - 1 >= 0.
- j, где: arr[i] == arr[j] и i != j.

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

Обратите внимание, что нельзя прыгать за пределы массива в любой момент времени.

Пример:

Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.

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

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

2⃣Выполнять BFS: для каждого индекса текущего слоя проверять соседние индексы (i + 1, i - 1 и все j, где arr[i] == arr[j]), добавляя непосещенные индексы в очередь следующего слоя.

3⃣Повторять шаг 2, увеличивая счетчик шагов до достижения последнего индекса или пока не закончится очередь.

😎 Решение:

class Solution {
    func minJumps(_ arr: [Int]) -> Int {
        let n = arr.count
        if n <= 1 { return 0 }

        var graph = [Int: [Int]]()
        for i in 0..<n {
            graph[arr[i], default: []].append(i)
        }

        var curs = [0]
        var visited = Set([0])
        var step = 0

        while !curs.isEmpty {
            var nex = [Int]()

            for node in curs {
                if node == n - 1 { return step }

                for child in graph[arr[node], default: []] {
                    if !visited.contains(child) {
                        visited.insert(child)
                        nex.append(child)
                    }
                }

                graph[arr[node]] = []

                if node + 1 < n && !visited.contains(node + 1) {
                    visited.insert(node + 1)
                    nex.append(node + 1)
                }
                if node - 1 >= 0 && !visited.contains(node - 1) {
                    visited.insert(node - 1)
                    nex.append(node - 1)
                }
            }

            curs = nex
            step += 1
        }

        return -1
    }
}

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

Задача: 141. Linked List Cycle
Сложность: easy

Дана переменная head, которая является началом связного списка. Определите, содержит ли связный список цикл.

Цикл в связном списке существует, если существует узел в списке, до которого можно добраться снова, последовательно следуя по указателю next. Внутренне переменная pos используется для обозначения индекса узла, к которому подключен указатель next последнего узла. Обратите внимание, что pos не передается в качестве параметра.

Верните true, если в связном списке есть цикл. В противном случае верните false.

Пример:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

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

1⃣Инициализация структуры данных:
Создайте хеш-таблицу (или множество) для хранения ссылок на узлы, чтобы отслеживать уже посещённые узлы.

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

3⃣Проверка на цикл:
Если текущий узел равен null, это означает, что вы достигли конца списка, и список не имеет циклов. В этом случае верните false.
Если текущий узел уже содержится в хеш-таблице, это означает, что вы вернулись к ранее посещённому узлу, и, следовательно, в списке присутствует цикл. Верните true.
Если ни одно из этих условий не выполнено, добавьте текущий узел в хеш-таблицу и продолжите обход списка.

😎 Решение:

class ListNode {
    var val: Int
    var next: ListNode?
    
    init(_ val: Int, _ next: ListNode? = nil) {
        self.val = val
        self.next = next
    }
}

class Solution {
    func hasCycle(_ head: ListNode?) -> Bool {
        var nodesSeen = Set<ListNode>()
        var current = head
        
        while current != nil {
            if nodesSeen.contains(current!) {
                return true
            }
            nodesSeen.insert(current!)
            current = current?.next
        }
        return false
    }
}

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

Задача: 280. Wiggle Sort
Сложность: medium

Дан целочисленный массив nums, упорядочьте его так, чтобы nums[0] <= nums[1] >= nums[2] <= nums[3]....

Вы можете считать, что входной массив всегда имеет допустимый ответ.

Пример:

Input: nums = [3,5,2,1,6,4]
Output: [3,5,1,6,2,4]
Explanation: [1,6,2,5,3,4] is also accepted.

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

1⃣Итерируйтесь по каждому элементу с индексом i в массиве nums, начиная с 0 и до nums.length - 2, так как последний элемент не имеет следующего элемента для обмена.

2⃣Проверьте, является ли i четным и nums[i] > nums[i + 1]. Если это так, поменяйте местами nums[i] и nums[i + 1].

3⃣Проверьте, является ли i нечетным и nums[i] < nums[i + 1]. Если это так, поменяйте местами nums[i] и nums[i + 1].

😎 Решение:

class Solution {
    func swap(_ nums: inout [Int], _ i: Int, _ j: Int) {
        let temp = nums[i]
        nums[i] = nums[j]
        nums[j] = temp
    }

    func wiggleSort(_ nums: inout [Int]) {
        for i in 0..<nums.count - 1 {
            if (i % 2 == 0 && nums[i] > nums[i + 1]) || (i % 2 == 1 && nums[i] < nums[i + 1]) {
                swap(&nums, i, i + 1)
            }
        }
    }
}

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

Задача: 94. Binary Tree Inorder Traversal
Сложность: easy

Дан корень бинарного дерева. Верните обход значений его узлов в симметричном порядке.
Пример:
Input: root = [1,null,2,3] Output: [1,3,2]

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

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

2⃣Сначала обходим левое поддерево

3⃣Затем добавляем значение текущего узла и обходим правое поддерево

😎 Решение:

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

class Solution {
    func inorderTraversal(_ root: TreeNode?) -> [Int] {
        var res = [Int]()
        helper(root, &res)
        return res
    }
    
    private func helper(_ root: TreeNode?, _ res: inout [Int]) {
        guard let root = root else { return }
        helper(root.left, &res)
        res.append(root.val)
        helper(root.right, &res)
    }
}

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

Задача: 1274. Number of Ships in a Rectangle
Сложность: hard

(Эта задача является интерактивной.) Каждый корабль находится в целочисленной точке моря, представленной картезианской плоскостью, и каждая целочисленная точка может содержать не более 1 корабля. У вас есть функция Sea.hasShips(topRight, bottomLeft), которая принимает две точки в качестве аргументов и возвращает true, если в прямоугольнике, представленном этими двумя точками, есть хотя бы один корабль, включая на границе. Учитывая две точки: правый верхний и левый нижний углы прямоугольника, верните количество кораблей в этом прямоугольнике. Гарантируется, что в прямоугольнике находится не более 10 кораблей. Решения, содержащие более 400 обращений к hasShips, будут оцениваться как "Неправильный ответ". Кроме того, любые решения, пытающиеся обойти судью, приведут к дисквалификации.

Пример:

Input: 
ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]
Output: 3

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

1⃣Разделите текущий прямоугольник на четыре меньших прямоугольника

2⃣Рекурсивно проверьте наличие кораблей в каждом из четырех подпрямоугольников, используя функцию hasShips

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

😎 Решение:

class Solution {
    func countShips(_ sea: Sea, _ topRight: Point, _ bottomLeft: Point) -> Int {
        if !sea.hasShips(topRight, bottomLeft) {
            return 0
        }
        if topRight.x == bottomLeft.x && topRight.y == bottomLeft.y {
            return 1
        }
        let midX = (topRight.x + bottomLeft.x) / 2
        let midY = (topRight.y + bottomLeft.y) / 2
        return countShips(sea, Point(midX, midY), bottomLeft) +
               countShips(sea, topRight, Point(midX + 1, midY + 1)) +
               countShips(sea, Point(midX, topRight.y), Point(bottomLeft.x, midY + 1)) +
               countShips(sea, Point(topRight.x, midY), Point(midX + 1, bottomLeft.y))
    }
}

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

Задача: 1234. Replace the Substring for Balanced String
Сложность: medium

Вам дана строка s длины n, содержащая только четыре вида символов: 'Q', 'W', 'E' и 'R'. Строка считается сбалансированной, если каждый из ее символов встречается n / 4 раз, где n - длина строки. Верните минимальную длину подстроки, которую можно заменить любой другой строкой той же длины, чтобы сделать s сбалансированной. Если s уже сбалансирована, верните 0.

Пример:

Input: s = "QWER"
Output: 0

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

1⃣Проверка баланса:
Сначала проверим, сбалансирована ли строка s. Если да, то возвращаем 0.

2⃣Подсчет частоты символов:
Подсчитаем количество каждого символа в строке s.

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

😎 Решение:

class Solution {
    func balancedString(_ s: String) -> Int {
        var count = [Character: Int]()
        for char in s { count[char, default: 0] += 1 }
        let target = s.count / 4

        func isBalanced() -> Bool {
            for char in "QWER" {
                if count[char, default: 0] > target {
                    return false
                }
            }
            return true
        }

        if isBalanced() { return 0 }

        let chars = Array(s)
        var minLength = s.count
        var left = 0

        for right in 0..<s.count {
            count[chars[right]]! -= 1
            while isBalanced() {
                minLength = min(minLength, right - left + 1)
                count[chars[left]]! += 1
                left += 1
            }
        }

        return minLength
    }
}

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

Задача: 189. Rotate Array
Сложность: medium

Для целочисленного массива nums, поверните массив вправо на k шагов, где k — неотрицательное число.

Пример:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

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

1⃣Создаем дополнительный массив, в который будем помещать каждый элемент исходного массива на его новую позицию. Элемент на позиции i в исходном массиве будет размещен на индексе (i+k) % длина массива.

2⃣Копируем элементы из нового массива в исходный массив, сохраняя новый порядок элементов.

3⃣Заменяем исходный массив полученным результатом, завершая процесс поворота массива.

😎 Решение:

class Solution {
    func rotate(_ nums: inout [Int], _ k: Int) {
        let n = nums.count
        var a = Array(repeating: 0, count: n)
        for i in 0..<n {
            a[(i + k) % n] = nums[i]
        }
        for i in 0..<n {
            nums[i] = a[i]
        }
    }
}

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

Задача: 413. Arithmetic Slices
Сложность: medium

Целочисленный массив называется арифметическим, если он состоит не менее чем из трех элементов и если разность между любыми двумя последовательными элементами одинакова. Например, [1,3,5,7,9], [7,7,7] и [3,-1,-5,-9] являются арифметическими последовательностями. Если задан целочисленный массив nums, верните количество арифметических подмассивов массива nums. Подмассив - это непрерывная подпоследовательность массива.

Пример:

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

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

1⃣Пройдите по массиву, инициализируя два указателя: начальный и текущий. Начните с первой пары элементов.

2⃣Для каждой пары элементов проверяйте, сохраняется ли разность между последовательными элементами. Если да, увеличивайте длину текущей арифметической последовательности. Если нет, сбрасывайте начальную позицию и начинайте новую последовательность.

3⃣Суммируйте количество найденных арифметических подмассивов, учитывая, что для каждого арифметического подмассива длины len, количество таких подмассивов равно (len - 2).

😎 Решение:

func numberOfArithmeticSlices(_ nums: [Int]) -> Int {
    guard nums.count >= 3 else { return 0 }
    var count = 0
    var currentLength = 0
    for i in 2..<nums.count {
        if nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2] {
            currentLength += 1
            count += currentLength
        } else {
            currentLength = 0
        }
    }
    return count
}

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

Задача: 835. Image Overlap
Сложность: medium

Вам даны два изображения, img1 и img2, представленные как бинарные квадратные матрицы размером n x n. Бинарная матрица содержит только 0 и 1 в качестве значений.
Мы можем сдвигать одно изображение как угодно, перемещая все биты 1 влево, вправо, вверх и/или вниз на любое количество единиц. Затем мы помещаем его поверх другого изображения. После этого мы можем вычислить перекрытие, подсчитав количество позиций, на которых в обоих изображениях есть 1.

Также обратите внимание, что при сдвиге не допускается никакое вращение. Любые биты 1, которые перемещаются за пределы границ матрицы, стираются.

Верните максимальное возможное перекрытие.

Пример:

Input: img1 = [[1,1,0],[0,1,0],[0,1,0]], img2 = [[0,0,0],[0,1,1],[0,0,1]]
Output: 3
Explanation: We translate img1 to right by 1 unit and down by 1 unit.

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

1⃣Определите функцию shiftAndCount(xShift, yShift, M, R), которая смещает матрицу M относительно матрицы R на координаты (xShift, yShift) и подсчитывает количество единиц в зоне перекрытия.

2⃣Организуйте цикл по всем возможным комбинациям координат смещения (xShift, yShift).

3⃣На каждой итерации вызывайте функцию shiftAndCount() дважды для обоих направлений смещения и обновляйте максимальное количество перекрытий.

😎 Решение:

class Solution {
    func shiftAndCount(_ xShift: Int, _ yShift: Int, _ M: [[Int]], _ R: [[Int]]) -> Int {
        var leftShiftCount = 0, rightShiftCount = 0
        var rRow = 0
        for mRow in yShift..<M.count {
            var rCol = 0
            for mCol in xShift..<M.count {
                if M[mRow][mCol] == 1 && M[mRow][mCol] == R[rRow][rCol] {
                    leftShiftCount += 1
                }
                if M[mRow][rCol] == 1 && M[mRow][rCol] == R[rRow][mCol] {
                    rightShiftCount += 1
                }
                rCol += 1
            }
            rRow += 1
        }
        return max(leftShiftCount, rightShiftCount)
    }

    func largestOverlap(_ A: [[Int]], _ B: [[Int]]) -> Int {
        var maxOverlaps = 0
        for yShift in 0..<A.count {
            for xShift in 0..<A.count {
                maxOverlaps = max(maxOverlaps, shiftAndCount(xShift, yShift, A, B))
                maxOverlaps = max(maxOverlaps, shiftAndCount(xShift, yShift, B, A))
            }
        }
        return maxOverlaps
    }
}

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

Задача: 174. Dungeon Game
Сложность: hard

Демоны поймали принцессу и заперли её в самой нижней правой комнате подземелья. Подземелье состоит из комнат, расположенных в форме сетки размером m x n. Наш отважный рыцарь изначально находится в комнате в верхнем левом углу и должен пробиться через подземелье, чтобы спасти принцессу.

Рыцарь имеет начальный запас здоровья, представленный положительным целым числом. Если в какой-то момент его уровень здоровья упадет до 0 или ниже, он умирает мгновенно.

Некоторые комнаты охраняются демонами (представлены отрицательными числами), так что рыцарь теряет здоровье, входя в эти комнаты; другие комнаты либо пусты (обозначены как 0), либо содержат магические сферы, которые увеличивают здоровье рыцаря (представлены положительными числами).

Чтобы как можно скорее добраться до принцессы, рыцарь решает двигаться только вправо или вниз на каждом шаге.

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

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

Пример:

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.

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

1⃣Определение матрицы dp:
Создайте матрицу dp размером с подземелье, где элемент dp[row][col] указывает минимальное количество здоровья, необходимое рыцарю, чтобы начать путь из ячейки dungeon[row][col] и достигнуть цели (нижней правой ячейки).

2⃣Инициализация и заполнение dp:
Начните с правого нижнего угла подземелья и идите в обратном направлении — справа налево и снизу вверх. Для каждой ячейки вычислите соответствующее значение в dp:
Если возможно, шаг вправо из текущей ячейки подземелья требует right_health здоровья.
Если возможно, шаг вниз из текущей ячейки подземелья требует down_health здоровья.
Возьмите минимальное значение из right_health и down_health для dp[row][col].
Если ни один из вышеперечисленных вариантов не доступен (то есть вы находитесь в ячейке назначения), учитывайте два подслучая:
Если в ячейке магический шар, достаточно 1 единицы здоровья.
Если в ячейке демон, рыцарю необходимо иметь единицу здоровья плюс урон, который может нанести демон.

3⃣Результат вычислений:
Значение в dp[0][0] будет указывать на минимальное количество здоровья, необходимое рыцарю, чтобы начать свой путь из верхней левой ячейки подземелья и успешно спасти принцессу, учитывая все угрозы на его пути.

😎 Решение:

func calculateMinimumHP(dungeon: [[Int]]) -> Int {
    let rows = dungeon.count
    let cols = dungeon[0].count
    var dp = Array(repeating: Array(repeating: Int.max, count: cols), count: rows)

    func getMinHealth(currCell: Int, nextRow: Int, nextCol: Int) -> Int {
        guard nextRow < rows, nextCol < cols else { return Int.max }
        let nextCell = dp[nextRow][nextCol]
        return max(1, nextCell - currCell)
    }

    for row in stride(from: rows - 1, through: 0, by: -1) {
        for col in stride(from: cols - 1, through: 0, by: -1) {
            let currCell = dungeon[row][col]
            let rightHealth = getMinHealth(currCell: currCell, nextRow: row, nextCol: col + 1)
            let downHealth = getMinHealth(currCell: currCell, nextRow: row + 1, nextCol: col)
            let nextHealth = min(rightHealth, downHealth)
            let minHealth = nextHealth != Int.max ? nextHealth : (currCell >= 0 ? 1 : 1 - currCell)
            dp[row][col] = minHealth
        }
    }

    return dp[0][0]
}

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

Задача: 1002. Find Common Characters
Сложность: easy

Если задан массив строк words, верните массив всех символов, которые встречаются во всех строках внутри слов (включая дубликаты). Вы можете вернуть ответ в любом порядке.

Пример:

Input: words = ["bella","label","roller"]
Output: ["e","l","l"]

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

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

2⃣Обработка каждого слова:
Для каждого слова создайте временный массив для хранения частоты каждого символа в этом слове.
Обновите основной частотный массив, сравнивая его с временным массивом и сохраняя минимальные частоты каждого символа.

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

😎 Решение:

class Solution {
    func commonChars(_ words: [String]) -> [String] {
        var min_freq = [Int](repeating: Int.max, count: 26)
        
        for word in words {
            var freq = [Int](repeating: 0, count: 26)
            for char in word {
                freq[Int(char.asciiValue! - Character("a").asciiValue!)] += 1
            }
            for i in 0..<26 {
                min_freq[i] = min(min_freq[i], freq[i])
            }
        }
        
        var result = [String]()
        for i in 0..<26 {
            for _ in 0..<min_freq[i] {
                result.append(String(UnicodeScalar(i + Int(Character("a").asciiValue!))!))
            }
        }
        return result
    }
}

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

Задача: 560. Subarray Sum Equals K
Сложность: medium

Дан массив целых чисел nums и целое число k, вернуть общее количество подмассивов, сумма которых равна k.

Подмассив - это непрерывная непустая последовательность элементов внутри массива.

Пример:

Input: nums = [1,1,1], k = 2
Output: 2

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

1⃣Самый простой метод - рассмотреть каждый возможный подмассив данного массива nums.

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

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

😎 Решение:

class Solution {
    func subarraySum(_ nums: [Int], _ k: Int) -> Int {
        var count = 0
        for start in 0..<nums.count {
            for end in (start + 1)...nums.count {
                var sum = 0
                for i in start..<end {
                    sum += nums[i]
                }
                if sum == k {
                    count += 1
                }
            }
        }
        return count
    }
}

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

Задача: 369. Plus One Linked List
Сложность: hard

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

Цифры хранятся таким образом, что самая значимая цифра находится в начале списка.

Пример:

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

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

1⃣Инициализируйте стражевой узел как ListNode(0) и установите его как новую голову списка: sentinel.next = head. Найдите крайний правый элемент, не равный девяти.

2⃣Увеличьте найденную цифру на единицу и установите все следующие девятки в ноль.

3⃣Верните sentinel, если его значение было установлено на 1, иначе верните head (sentinel.next).

😎 Решение:

class ListNode {
    var val: Int
    var next: ListNode?
    init(_ val: Int) { self.val = val; self.next = nil }
}

class Solution {
    func plusOne(_ head: ListNode?) -> ListNode? {
        let sentinel = ListNode(0)
        sentinel.next = head
        var notNine = sentinel

        var current = head
        while current != nil {
            if current!.val != 9 {
                notNine = current!
            }
            current = current!.next
        }

        notNine.val += 1
        notNine = notNine.next

        while notNine != nil {
            notNine!.val = 0
            notNine = notNine!.next
        }

        return sentinel.val == 0 ? sentinel.next : sentinel
    }
}

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

Задача: 1376. Time Needed to Inform All Employees
Сложность: medium

В компании работает n сотрудников, каждому из которых присвоен уникальный идентификатор от 0 до n - 1. Руководитель компании имеет идентификатор headID.

У каждого сотрудника есть один непосредственный начальник, указанный в массиве manager, где manager[i] — это непосредственный начальник i-го сотрудника, manager[headID] = -1. Также гарантируется, что отношения подчинения образуют древовидную структуру.

Руководитель компании хочет сообщить всем сотрудникам компании срочную новость. Он сообщит своим непосредственным подчиненным, а они сообщат своим подчиненным и так далее, пока все сотрудники не узнают о срочной новости.

i-й сотрудник нуждается в informTime[i] минутах, чтобы сообщить всем своим непосредственным подчиненным (т.е. через informTime[i] минут все его непосредственные подчиненные могут начать распространять новость).

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

Пример:

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.

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

1⃣Создайте список смежности adjList; индекс i будет хранить смежные узлы для сотрудника с идентификатором i.

2⃣Итерируйте по сотрудникам от 0 до N - 1, и для каждого сотрудника i добавляйте ребро manager[i] -> i, если manager[i] не равен -1.

3⃣Начните выполнение DFS с узла headID и временем 0 для каждого узла как curr. Обновите максимальное время maxTime, сравнив его с текущим временем. Итерируйте по смежным узлам curr и для каждого смежного узла выполните DFS с временем time + informTime[curr]. Когда DFS завершится, верните maxTime.

😎 Решение:

class Solution {
    var maxTime = Int.min
    
    func DFS(_ adjList: [[Int]], _ informTime: [Int], _ curr: Int, _ time: Int) {
        maxTime = max(maxTime, time)
        for adjacent in adjList[curr] {
            DFS(adjList, informTime, adjacent, time + informTime[curr])
        }
    }
    
    func numOfMinutes(_ n: Int, _ headID: Int, _ manager: [Int], _ informTime: [Int]) -> Int {
        var adjList = Array(repeating: [Int](), count: n)
        for i in 0..<n {
            if manager[i] != -1 {
                adjList[manager[i]].append(i)
            }
        }
        DFS(adjList, informTime, headID, 0)
        return maxTime
    }
}

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

Задача: 358. Rearrange String k Distance Apart
Сложность: hard

Дана строка s и целое число k, переставьте символы в s так, чтобы одинаковые символы находились на расстоянии не менее k друг от друга. Если невозможно переставить строку, верните пустую строку "".

Пример:

Input: s = "aabbcc", k = 3
Output: "abcabc"
Explanation: The same letters are at least a distance of 3 from each other.

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

1⃣Создайте словарь частот для символов строки и определите максимальную частоту.

2⃣Разделите символы на группы по частоте и создайте сегменты для размещения символов.

3⃣Распределите оставшиеся символы по сегментам, проверяя условия, и объедините сегменты в итоговую строку.

😎 Решение:

class Solution {
    func rearrangeString(_ s: String, _ k: Int) -> String {
        var freqs = [Character: Int]()
        var maxFreq = 0
        
        for char in s {
            freqs[char, default: 0] += 1
            maxFreq = max(maxFreq, freqs[char]!)
        }

        var mostChars = Set<Character>()
        var secondChars = Set<Character>()
        
        for (char, freq) in freqs {
            if freq == maxFreq {
                mostChars.insert(char)
            } else if freq == maxFreq - 1 {
                secondChars.insert(char)
            }
        }

        var segments = [String](repeating: "", count: maxFreq)

        for char in mostChars {
            for i in 0..<maxFreq {
                segments[i].append(char)
            }
        }
        for char in secondChars {
            for i in 0..<maxFreq-1 {
                segments[i].append(char)
            }
        }

        var segmentId = 0
        for (char, freq) in freqs {
            if mostChars.contains(char) || secondChars.contains(char) {
                continue
            }
            for _ in 0..<freq {
                segments[segmentId].append(char)
                segmentId = (segmentId + 1) % (maxFreq - 1)
            }
        }

        for i in 0..<maxFreq-1 {
            if segments[i].count < k {
                return ""
            }
        }

        return segments.joined()
    }
}

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

Задача: 645. Set Mismatch
Сложность: easy

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

Пример:

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

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

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

2⃣Определите отсутствующее число, используя сумму чисел от 1 до n и текущую сумму массива.

3⃣Верните дублированное и отсутствующее числа в виде массива.

😎 Решение:

func findErrorNums(_ nums: [Int]) -> [Int] {
    var numSet = Set<Int>()
    var duplicate = -1
    let n = nums.count
    for num in nums {
        if numSet.contains(num) {
            duplicate = num
        }
        numSet.insert(num)
    }
    let missing = (n * (n + 1)) / 2 - numSet.reduce(0, +)
    return [duplicate, missing]
}

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

Задача: 179. Largest Number
Сложность: medium

Дан список неотрицательных целых чисел nums. Организуйте их таким образом, чтобы они составляли наибольшее число и верните его.

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

Пример:

Input: nums = [10,2]
Output: "210"

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

1⃣Преобразование и сортировка: Преобразовать каждое число в строку и отсортировать массив строк с использованием специального компаратора, который для двух строк 𝑎 и b сравнивает результаты конкатенации 𝑎+𝑏 и 𝑏+𝑎.

2⃣Проверка на нули: Если после сортировки первый элемент массива равен "0", вернуть "0", так как все числа в массиве нули.

3⃣Формирование результата: Конкатенировать отсортированные строки для формирования наибольшего числа и вернуть это число в виде строки.

😎 Решение:

class Solution {
    func largestNumber(_ nums: [Int]) -> String {
        let strNums = nums.map { String($0) }
        let sortedNums = strNums.sorted { $0 + $1 > $1 + $0 }
        if sortedNums[0] == "0" {
            return "0"
        }
        return sortedNums.joined()
    }
}

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

Задача: 852. Peak Index in a Mountain Array
Сложность: medium

Вам дан целочисленный массив горы arr длины n, где значения увеличиваются до пикового элемента, а затем уменьшаются.

Верните индекс пикового элемента.

Ваша задача — решить это с временной сложностью O(log(n)).

Пример:

Input: arr = [0,1,0]

Output: 1

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

1⃣Создайте целочисленную переменную i и инициализируйте её значением 0.

2⃣Используя цикл while, проверьте, если текущий элемент, на который указывает i, меньше следующего элемента на индексе i + 1. Если arr[i] < arr[i + 1], увеличьте i на 1.

3⃣В противном случае, если arr[i] > arr[i + 1], верните i.

😎 Решение:

class Solution {
    func peakIndexInMountainArray(_ arr: [Int]) -> Int {
        var i = 0
        while arr[i] < arr[i + 1] {
            i += 1
        }
        return i
    }
}

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

Задача: 1209. Remove All Adjacent Duplicates in String II
Сложность: medium

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

Пример:

Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation: 
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"

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

1⃣Инициализировать медленный указатель j значением 0 и стек counts для хранения количества одинаковых символов.

2⃣Перемещать быстрый указатель i по строке s:
Копировать s[i] в s[j].
Если s[j] совпадает с s[j - 1], увеличить значение на вершине стека.
Иначе добавить 1 в стек.
Если количество символов равно k, уменьшить j на k и извлечь из стека.

3⃣Вернуть первые j символов строки.

😎 Решение:

class Solution {
    func removeDuplicates(_ s: String, _ k: Int) -> String {
        var counts = [Int]()
        var sa = Array(s)
        var j = 0
        
        for i in 0..<sa.count {
            sa[j] = sa[i]
            if j == 0 || sa[j] != sa[j - 1] {
                counts.append(1)
            } else {
                let incremented = counts.removeLast() + 1
                if incremented == k {
                    j -= k
                } else {
                    counts.append(incremented)
                }
            }
            j += 1
        }
        return String(sa[..<j])
    }
}

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