Задача: 1531. String Compression II
Сложность: hard

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

Найдите минимальную длину сжатой версии строки s после удаления не более k символов.

Пример:

Input: s = "aaabcccd", k = 2
Output: 4
Explanation: Compressing s without deleting anything will give us "a3bc3d" of length 6. Deleting any of the characters 'a' or 'c' would at most decrease the length of the compressed string to 5, for instance delete 2 'a' then we will have s = "abcccd" which compressed is abc3d. Therefore, the optimal way is to delete 'b' and 'd', then the compressed version of s will be "a3c3" of length 4.

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

1⃣Обходим символы строки слева направо, решая для каждого символа, включать его в сжатую строку или нет. Это создает состояния (строка, оставшиеся для включения символы), которые можно представить в виде бинарного дерева, где левые потомки означают включение символов, а правые — их пропуск. Многочисленные повторяющиеся подзадачи указывают на необходимость использования динамического программирования.

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

3⃣Связываем состояния друг с другом: удаление нового символа увеличивает i на один и уменьшает k на один; включение нового символа оставляет длину сжатия неизменной (кроме случаев, когда частота последнего символа 1, 9 или 99) или увеличивает длину на один, если новый символ не равен последнему символу сжатия.

😎 Решение

class Solution {
    private var memo = [Int: Int]()
    private let add: Set<Int> = [1, 9, 99]

    func getLengthOfOptimalCompression(_ s: String, _ k: Int) -> Int {
        return dp(Array(s), 0, Character(UnicodeScalar(97 + 26)!), 0, k)
    }

    private func dp(_ s: [Character], _ idx: Int, _ lastChar: Character, _ lastCharCount: Int, _ k: Int) -> Int {
        if k < 0 {
            return Int.max / 2
        }

        if idx == s.count {
            return 0
        }

        let key = idx * 101 * 27 * 101 + Int(lastChar.asciiValue! - Character("a").asciiValue!) * 101 * 101 + lastCharCount * 101 + k

        if let cachedResult = memo[key] {
            return cachedResult
        }

        let deleteChar = dp(s, idx + 1, lastChar, lastCharCount, k - 1)
        let keepChar: Int
        if s[idx] == lastChar {
            keepChar = dp(s, idx + 1, lastChar, lastCharCount + 1, k) + (add.contains(lastCharCount) ? 1 : 0)
        } else {
            keepChar = dp(s, idx + 1, s[idx], 1, k) + 1
        }

        let res = min(keepChar, deleteChar)
        memo[key] = res

        return res
    }
}

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

Задача: 1394. Find Lucky Integer in an Array
Сложность: easy

Дан массив целых чисел arr. Счастливое число — это число, частота которого в массиве равна его значению.

Верните наибольшее счастливое число в массиве. Если счастливого числа нет, верните -1.

Пример:

Input: arr = [1,2,2,3,3,3]
Output: 3
Explanation: 1, 2 and 3 are all lucky numbers, return the largest of them.

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

1⃣Создайте хэш-карту для подсчёта частоты каждого числа в массиве.

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

3⃣Верните наибольшее счастливое число или -1, если таких чисел нет.

😎 Решение:

class Solution {
    func findLucky(_ arr: [Int]) -> Int {
        var counts = [Int: Int]()
        for num in arr {
            counts[num, default: 0] += 1
        }
        
        var largestLuckyNumber = -1
        for (key, value) in counts {
            if key == value {
                largestLuckyNumber = max(largestLuckyNumber, key)
            }
        }
        
        return largestLuckyNumber
    }
}

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

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

Дано целое число columnNumber, верните соответствующий заголовок столбца, как он отображается в таблице Excel.

Например:
A -> 1
B -> 2
C -> 3
Z -> 26
AA -> 27
AB -> 28

Пример:

Input: columnNumber = 1
Output: "A"

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

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

2⃣Циклическое преобразование числа в буквы:
Пока columnNumber больше 0, выполняйте следующие действия:
Вычтите 1 из columnNumber для корректировки индекса (Excel использует 1-индексацию).
Найдите символ, соответствующий остатку от деления columnNumber на 26, и добавьте его в начало строки ans.
Присвойте columnNumber значение от деления columnNumber на 26

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

😎 Решение:

class Solution {
    func convertToTitle(_ columnNumber: Int) -> String {
        var columnNumber = columnNumber
        var ans = ""

        while columnNumber > 0 {
            columnNumber -= 1
            ans = "\(Character(UnicodeScalar(columnNumber % 26 + Int("A".unicodeScalars.first!.value))!))" + ans
            columnNumber /= 26
        }

        return ans
    }
}

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

Задача: 841. Keys and Rooms
Сложность: medium

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

Дан массив rooms, где rooms[i] — это набор ключей, которые вы можете получить, если посетите комнату i. Верните true, если вы можете посетить все комнаты, или false в противном случае.

Пример:

Input: rooms = [[1],[2],[3],[]]
Output: true
Explanation: 
We visit room 0 and pick up key 1.
We then visit room 1 and pick up key 2.
We then visit room 2 and pick up key 3.
We then visit room 3.
Since we were able to visit every room, we return true.

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

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

2⃣Поместите ключ от комнаты 0 в стек и отметьте комнату 0 как посещенную.

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

😎 Решение:

class Solution {
    func canVisitAllRooms(_ rooms: [[Int]]) -> Bool {
        var seen = [Bool](repeating: false, count: rooms.count)
        seen[0] = true
        var stack = [0]

        while !stack.isEmpty {
            let node = stack.removeLast()
            for nei in rooms[node] {
                if !seen[nei] {
                    seen[nei] = true
                    stack.append(nei)
                }
            }
        }

        return !seen.contains(false)
    }
}

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

Задача: 1000. Minimum Cost to Merge Stones
Сложность: hard

Имеется n кучек камней, расположенных в ряд. В i-й куче находятся камни stones[i]. Ход состоит в объединении ровно k последовательных куч в одну кучу, и стоимость этого хода равна общему количеству камней в этих k кучах. Верните минимальную стоимость объединения всех куч камней в одну кучу. Если это невозможно, верните -1.

Пример:

Input: stones = [3,2,4,1], k = 2
Output: 20

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

1⃣Проверка на возможность объединения:
Проверьте, можно ли объединить все кучи в одну, если количество куч n не равно 1 по модулю k-1. Если нет, верните -1.

2⃣Инициализация и динамическое программирование:
Создайте таблицу dp для хранения минимальных затрат на объединение подмассивов камней.
Используйте таблицу prefix для хранения префиксных сумм камней, чтобы быстро вычислять сумму камней в подмассиве.

3⃣Заполнение таблицы dp:
Заполните таблицу dp минимальными затратами на объединение подмассивов камней, используя динамическое программирование.
Для каждого подмассива длиной от k до n, найдите минимальную стоимость его объединения.

😎 Решение:

class Solution {
    func mergeStones(_ stones: [Int], _ k: Int) -> Int {
        let n = stones.count
        if (n - 1) % (k - 1) != 0 {
            return -1
        }

        var prefix = [Int](repeating: 0, count: n + 1)
        for i in 0..<n {
            prefix[i + 1] = prefix[i] + stones[i]
        }

        var dp = [[Int]](repeating: [Int](repeating: 0, count: n), count: n)
        for m in stride(from: k, through: n, by: 1) {
            for i in 0...n - m {
                let j = i + m - 1
                dp[i][j] = Int.max
                for t in stride(from: i, to: j, by: k - 1) {
                    dp[i][j] = min(dp[i][j], dp[i][t] + dp[t + 1][j])
                }
                if (j - i) % (k - 1) == 0 {
                    dp[i][j] += prefix[j + 1] - prefix[i]
                }
            }
        }

        return dp[0][n - 1]
    }
}

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

Задача: 117. Populating Next Right Pointers in Each Node II
Сложность: medium

Вам дано бинарное дерево:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Заполните каждый указатель next, чтобы он указывал на следующий правый узел. Если следующего правого узла нет, указатель next должен быть установлен в NULL.

Изначально все указатели next установлены в NULL.

Пример:

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

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

1⃣Инициализируйте очередь Q, которая будет использоваться во время обхода. Существует несколько способов реализации обхода в ширину, особенно когда дело доходит до определения уровня конкретного узла. Можно добавить в очередь пару (узел, уровень), и каждый раз, когда мы добавляем детей узла, мы добавляем (node.left, parent_level+1) и (node.right, parent_level+1). Этот подход может оказаться неэффективным для нашего алгоритма, так как нам нужны все узлы на одном уровне, и потребуется дополнительная структура данных.

2⃣Более эффективный с точки зрения памяти способ разделения узлов одного уровня - использовать разграничение между уровнями. Обычно мы вставляем в очередь элемент NULL, который обозначает конец предыдущего уровня и начало следующего. Это отличный подход, но он все равно потребует некоторого объема памяти, пропорционального количеству уровней в дереве.

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

while (!Q.empty())
{
    size = Q.size()
    for i in range 0..size
    {
        node = Q.pop()
        Q.push(node.left)
        Q.push(node.right)
    }
}

Мы начинаем с добавления корня дерева в очередь. Так как на уровне 0 есть только один узел, нам не нужно устанавливать какие-либо соединения, и мы можем перейти к циклу while.

😎 Решение:

import Foundation

class Node {
    var value: Int
    var left: Node?
    var right: Node?
    var next: Node?

    init(_ value: Int) {
        self.value = value
    }
}

class Solution {
    func connect(_ root: Node?) -> Node? {
        guard let root = root else { return nil }
        
        var queue: [Node] = [root]
        
        while !queue.isEmpty {
            let size = queue.count
            for i in 0..<size {
                let node = queue.removeFirst()
                if i < size - 1 {
                    node.next = queue.first
                }
                
                if let leftChild = node.left {
                    queue.append(leftChild)
                }
                if let rightChild = node.right {
                    queue.append(rightChild)
                }
            }
        }
        
        return root
    }
}

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

Задача: 104. Maximum Depth of Binary Tree
Сложность: easy

Дан корень бинарного дерева, верните его максимальную глубину.

Максимальная глубина бинарного дерева — это количество узлов вдоль самого длинного пути от корневого узла до самого удалённого листового узла.

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: 3

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

1⃣Можно обойти дерево, используя стратегию поиска в глубину (DFS) или поиска в ширину (BFS).

2⃣Для данной задачи подойдет несколько способов.

3⃣Здесь мы демонстрируем решение, реализованное с использованием стратегии DFS и рекурсии.

😎 Решение:

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

func maxDepth(_ root: TreeNode?) -> Int {
    guard let root = root else {
        return 0
    }
    let leftHeight = maxDepth(root.left)
    let rightHeight = maxDepth(root.right)
    return 1 + max(leftHeight, rightHeight)
}

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

Задача: 292. Nim Game
Сложность: easy

Вы играете в следующую игру Nim со своим другом:

Изначально на столе лежит куча камней.
Вы и ваш друг поочередно делаете ходы, и вы ходите первым.
Каждый ход игрок, чей ход, будет убирать от 1 до 3 камней из кучи.
Тот, кто убирает последний камень, становится победителем.
Дано n, количество камней в куче. Верните true, если вы можете выиграть игру, предполагая, что и вы, и ваш друг играете оптимально, иначе верните false.

Пример:

Input: n = 4
Output: false
Explanation: These are the possible outcomes:
1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
3. You remove 3 stones. Your friend removes the last stone. Your friend wins.
In all outcomes, your friend wins.

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

1⃣Определите базовый случай:
Если количество камней n меньше или равно 3, вы всегда можете выиграть, убрав все камни. В этом случае верните true.

2⃣Анализ оставшихся камней:
Если количество камней n делится на 4 без остатка (n % 4 == 0), вы не можете выиграть, так как независимо от вашего хода ваш друг всегда сможет оставить вам кратное 4 количество камней. В этом случае верните false.

3⃣Выигрышная стратегия:
Если количество камней n не кратно 4 (n % 4 != 0), вы можете выиграть, оставляя вашему другу кратное 4 количество камней после вашего хода. В этом случае верните true.

😎 Решение:

class Solution {
    func canWinNim(_ n: Int) -> Bool {
        return n % 4 != 0
    }
}

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

Задача: 24. Swap Nodes in Pairs
Сложность: medium

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

Пример:

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

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

1⃣Используем фиктивный узел (dummy), чтобы упростить обработку головы списка.

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

3⃣Продвигаемся дальше на два узла и повторяем процесс до конца списка.

😎Решение:

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

func swapPairs(_ head: ListNode?) -> ListNode? {
    let dummy = ListNode(0)
    dummy.next = head
    var current: ListNode? = dummy
    
    while current?.next != nil && current?.next?.next != nil {
        let first = current?.next
        let second = current?.next?.next
        
        first?.next = second?.next
        second?.next = first
        current?.next = second
        
        current = first
    }
    
    return dummy.next
}

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

Задача: 399. Evaluate Division
Сложность: medium

Вам дан массив пар переменных equations и массив вещественных чисел values, где equations[i] = [Ai, Bi] и values[i] представляют уравнение Ai / Bi = values[i]. Каждая Ai или Bi - это строка, представляющая одну переменную. Вам также даны некоторые запросы, где queries[j] = [Cj, Dj] представляет j-й запрос, в котором вы должны найти ответ для Cj / Dj = ?. Верните ответы на все запросы. Если ни один ответ не может быть определен, верните -1.0. Замечание: входные данные всегда действительны. Можно предположить, что вычисление запросов не приведет к делению на ноль и что противоречия нет. Примечание: Переменные, которые не встречаются в списке уравнений, являются неопределенными, поэтому для них ответ не может быть определен.

Пример:

Input: equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]

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

1⃣Создание графа:
Представьте каждую переменную как узел в графе.
Используйте уравнения для создания ребер между узлами, где каждое ребро имеет вес, равный значению уравнения (Ai / Bi = values[i]).
Создайте также обратные ребра с обратным весом (Bi / Ai = 1 / values[i]).

2⃣Поиск пути:
Для каждого запроса используйте поиск в глубину (DFS) или поиск в ширину (BFS) для поиска пути от Cj до Dj.
Если путь найден, вычислите произведение весов вдоль пути, чтобы найти значение Cj / Dj.
Если путь не найден, верните -1.0.

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

😎 Решение:

class Solution {
    func calcEquation(_ equations: [[String]], _ values: [Double], _ queries: [[String]]) -> [Double] {
        var graph = [String: [String: Double]]()

        for (i, equation) in equations.enumerated() {
            let A = equation[0], B = equation[1]
            let value = values[i]
            graph[A, default: [String: Double]()][B] = value
            graph[B, default: [String: Double]()][A] = 1.0 / value
        }

        func bfs(_ start: String, _ end: String) -> Double {
            guard let _ = graph[start], let _ = graph[end] else { return -1.0 }
            var queue = [(start, 1.0)]
            var visited = Set<String>()
            
            while !queue.isEmpty {
                let (current, curProduct) = queue.removeFirst()
                if current == end { return curProduct }
                visited.insert(current)
                for (neighbor, value) in graph[current, default: [String: Double]()] {
                    if !visited.contains(neighbor) {
                        queue.append((neighbor, curProduct * value))
                    }
                }
            }
            return -1.0
        }

        var results = [Double]()
        for query in queries {
            let C = query[0], D = query[1]
            results.append(bfs(C, D))
        }
        return results
    }
}

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

Задача: 98. Validate Binary Search Tree
Сложность: medium

Дан корень бинарного дерева. Определите, является ли это дерево допустимым бинарным деревом поиска (BST).

Допустимое BST определяется следующим образом:

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

Пример:

Input: root = [2,1,3]
Output: true

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

1⃣Давайте воспользуемся порядком узлов при симметричном обходе (inorder traversal):

Левый -> Узел -> Правый.

Постордер:

Здесь узлы перечисляются в порядке их посещения, и вы можете следовать последовательности 1-2-3-4-5 для сравнения различных стратегий.

Порядок "Левый -> Узел -> Правый" при симметричном обходе означает, что для BST каждый элемент должен быть меньше следующего.

2⃣Следовательно, алгоритм с временной сложностью O(N) и пространственной сложностью O(N) может быть простым:

Вычислить список симметричного обхода inorder.

Проверить, меньше ли каждый элемент в списке inorder следующего за ним.

Постордер:

3⃣Нужно ли сохранять весь список симметричного обхода?

На самом деле, нет. Достаточно последнего добавленного элемента inorder, чтобы на каждом шаге убедиться, что дерево является BST (или нет). Следовательно, можно объединить оба шага в один и уменьшить используемое пространство.

😎 Решение:

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 {
    private var prev: Int?
    
    private func inorder(_ root: TreeNode?) -> Bool {
        guard let root = root else {
            return true
        }
        
        if !inorder(root.left) {
            return false
        }
        
        if let prev = prev, root.val <= prev {
            return false
        }
        prev = root.val
        
        return inorder(root.right)
    }
    
    func isValidBST(_ root: TreeNode?) -> Bool {
        prev = nil  // Reset previous value
        return inorder(root)
    }
}

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

Задача: 1359. Count All Valid Pickup and Delivery Options
Сложность: hard

Дано n заказов, каждый из которых состоит из услуги забора и доставки.

Посчитайте все возможные допустимые последовательности забора/доставки, такие что доставка(i) всегда идет после забора(i).

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

Пример:

Input: n = 1
Output: 1
Explanation: Unique order (P1, D1), Delivery 1 always is after of Pickup 1.

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

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

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

3⃣Возвращение результата:
Верните результат для n заказов, применяя модуль 10^9 + 7 для предотвращения переполнения.

😎 Решение:

class Solution {
    func countOrders(_ n: Int) -> Int {
        let MOD = 1_000_000_007
        var dp = [Int](repeating: 0, count: n + 1)
        dp[0] = 1
        
        for i in 1...n {
            dp[i] = dp[i - 1] * (2 * i - 1) * i % MOD
        }
        
        return dp[n]
    }
}

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

Задача: 1481. Least Number of Unique Integers after K Removals
Сложность: medium

Дан массив целых чисел arr и целое число k. Найдите минимальное количество уникальных целых чисел после удаления ровно k элементов.

Пример:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

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

1⃣Инициализация и построение частотного массива:
Создайте хеш-таблицу для отслеживания частот элементов массива arr.
Итеративно увеличивайте частоту элементов в хеш-таблице.

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

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

😎 Решение:

class Solution {
    func findLeastNumOfUniqueInts(_ arr: [Int], _ k: Int) -> Int {
        var freqMap = [Int: Int]()
        for num in arr {
            freqMap[num, default: 0] += 1
        }
        
        var frequencies = Array(freqMap.values)
        frequencies.sort()
        
        var elementsRemoved = 0
        for i in 0..<frequencies.count {
            elementsRemoved += frequencies[i]
            if elementsRemoved > k {
                return frequencies.count - i
            }
        }
        
        return 0
    }
}

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

Задача: 240. Search a 2D Matrix II
Сложность: medium

Напишите эффективный алгоритм, который ищет значение target в матрице целых чисел размером m на n. У этой матрицы есть следующие свойства:

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

Пример:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

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

1⃣Проверка матрицы: Перед началом поиска убедитесь, что матрица не пуста и не содержит null.

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

3⃣Бинарный поиск и завершение: Продолжайте бинарный поиск до тех пор, пока не исчерпаете все диагонали (в этом случае возвращается False) или пока не найдете целевое значение (в этом случае возвращается True). Функция бинарного поиска должна уметь работать как с рядами, так и с колонками матрицы.

😎 Решение:

class Solution {
    private func binarySearch(_ matrix: [[Int]], _ target: Int, _ start: Int, _ vertical: Bool) -> Bool {
        var lo = start
        var hi = vertical ? matrix[0].count - 1 : matrix.count - 1

        while hi >= lo {
            let mid = (lo + hi) / 2
            if vertical {
                if matrix[start][mid] < target {
                    lo = mid + 1
                } else if matrix[start][mid] > target {
                    hi = mid - 1
                } else {
                    return true
                }
            } else {
                if matrix[mid][start] < target {
                    lo = mid + 1
                } else if matrix[mid][start] > target {
                    hi = mid - 1
                } else {
                    return true
                }
            }
        }
        return false
    }

    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        if matrix.isEmpty || matrix[0].isEmpty {
            return false
        }

        let shorterDim = min(matrix.count, matrix[0].count)
        for i in 0..<shorterDim {
            if binarySearch(matrix, target, i, true) || binarySearch(matrix, target, i, false) {
                return true
            }
        }
        return false
    }
}

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

⚡️ В сети начали массово сливать курсы и книги известных онлайн школ по айти

Вот отсортированная база с тонной материала (постепенно пополняется):

(363 видео, 87 книги) — Python
(415 видео, 68 книги) — Frontend
(143 видео, 33 книги) — ИБ/Хакинг
(352 видео, 89 книги) — С/С++/C#
(343 видео, 87 книги) — Java/QA
(176 видео, 32 книги) — Git/Linux
(174 видео, 91 книги) — DevOps
(167 видео, 53 книги) — PHP/1С
(227 видео, 83 книги) — SQL/БД
(114 видео, 77 книги) — Сисадмин
(107 видео, 43 книги) — BA/SA
(181 видео, 32 книги) — Go/Rust
(167 видео, 43 книги) — Kotlin/Swift
(112 видео, 24 книги) — Flutter
(137 видео, 93 книги) — DS/ML
(113 видео, 82 книги) — GameDev
(183 видео, 37 книги) — Дизайн
(136 видео, 33 книги) — PM/HR

Скачивать ничего не нужно — все выложили в Telegram

Задача: 657. Robot Return to Origin
Сложность: easy

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

Вам дана строка moves, представляющая последовательность движений робота, где moves[i] представляет его i-ое движение. Допустимые движения: 'R' (вправо), 'L' (влево), 'U' (вверх) и 'D' (вниз).

Верните true, если робот возвращается в исходную точку после завершения всех своих движений, или false в противном случае.

Примечание: направление, в котором "смотрит" робот, не имеет значения. 'R' всегда будет перемещать робота на один шаг вправо, 'L' всегда будет перемещать его на один шаг влево и т.д. Также предполагается, что величина перемещения робота одинакова для каждого хода.

Пример:

Input: moves = "UD"
Output: true

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

1⃣Инициализация координат:
Начните с координат (0, 0).

2⃣Обработка движений:
Пройдите по строке moves и обновляйте координаты в зависимости от движения:
'R' увеличивает координату x на 1.
'L' уменьшает координату x на 1.
'U' увеличивает координату y на 1.
'D' уменьшает координату y на 1.

3⃣Проверка конечных координат:
Если после всех движений координаты снова равны (0, 0), верните true. В противном случае, верните false.

😎 Решение:

class Solution {
    func judgeCircle(_ moves: String) -> Bool {
        var x = 0
        var y = 0
        for move in moves {
            switch move {
                case "R": x += 1
                case "L": x -= 1
                case "U": y += 1
                case "D": y -= 1
                default: break
            }
        }
        return x == 0 && y == 0
    }
}

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

Задача: 623. Add One Row to Tree
Сложность: medium

Учитывая корень бинарного дерева и два целых числа val и depth, добавьте ряд узлов со значением val на заданную глубину depth. Обратите внимание, что корневой узел находится на глубине 1. Правило добавления таково: учитывая целое число depth, для каждого ненулевого узла дерева cur на глубине depth - 1 создайте два узла дерева со значением val в качестве левого поддерева корня cur и правого поддерева корня.
Оригинальное левое поддерево cur должно быть левым поддеревом нового корня левого поддерева. Оригинальное правое поддерево cur должно быть правым поддеревом нового корня правого поддерева. Если глубина == 1, то есть глубина - 1 вообще не существует, создайте узел дерева со значением val как новый корень всего оригинального дерева, а оригинальное дерево - левое поддерево нового корня.

Пример:

Input: root = [4,2,6,3,1,5], val = 1, depth = 2
Output: [4,1,1,2,null,null,6,3,1,5]

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

1⃣Если depth равна 1, создайте новый корень со значением val и сделайте текущий корень левым поддеревом нового корня.

2⃣Используйте обход в ширину (BFS) для поиска всех узлов на глубине depth - 1.

3⃣Для каждого узла на глубине depth - 1, вставьте новые узлы со значением val в качестве левого и правого поддеревьев, сохраняя исходные поддеревья.

😎 Решение:

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

func addOneRow(_ root: TreeNode?, _ val: Int, _ depth: Int) -> TreeNode? {
    if depth == 1 {
        return TreeNode(val, root, nil)
    }
    
    var queue: [TreeNode] = []
    if let root = root {
        queue.append(root)
    }
    var currentDepth = 1
    
    while !queue.isEmpty {
        if currentDepth == depth - 1 {
            for node in queue {
                node.left = TreeNode(val, node.left, nil)
                node.right = TreeNode(val, nil, node.right)
            }
            break
        }
        currentDepth += 1
        var nextQueue: [TreeNode] = []
        for node in queue {
            if let left = node.left {
                nextQueue.append(left)
            }
            if let right = node.right {
                nextQueue.append(right)
            }
        }
        queue = nextQueue
    }
    
    return root
}

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