Задача: 1171. Remove Zero Sum Consecutive Nodes from Linked List
Сложность: medium

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

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

Пример:

Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.

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

1⃣Инициализируйте новый узел ListNode с именем front со значением 0, у которого поле next указывает на head, и узел start, указывающий на front.

2⃣Обрабатывайте все узлы в связанном списке, пока start != null. Инициализируйте переменную prefixSum значением 0 и узел ListNode с именем end, указывающий на start.next. Обрабатывайте остальные узлы в связанном списке, пока end != null: добавьте значение узла end к prefixSum. Если prefixSum равен 0, установите соединение от узла start к последнему узлу после последовательности с суммой ноль, установив start.next равным end.next. Установите end равным end.next.

3⃣Установите start равным start.next. Верните front.next. Узел front указывает на голову конечного связанного списка.

😎 Решение

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

class Solution {
    func removeZeroSumSublists(_ head: ListNode?) -> ListNode? {
        let front = ListNode(0, head)
        var start: ListNode? = front

        while start != nil {
            var prefixSum = 0
            var end = start?.next

            while end != nil {
                prefixSum += end!.val
                if prefixSum == 0 {
                    start?.next = end?.next
                }
                end = end?.next
            }

            start = start?.next
        }
        return front.next
    }
}

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

Задача: 157. Read N Characters Given Read4
Сложность: easy

Предположим, что у вас есть файл, и вы можете читать файл только с помощью данного метода read4. Реализуйте метод для чтения n символов.

Метод read4:
API read4 читает четыре последовательных символа из файла, затем записывает эти символы в массив буфера buf4.
Возвращаемое значение — количество фактически прочитанных символов.
Обратите внимание, что у read4 есть собственный указатель файла, аналогично FILE *fp в C.

Определение read4:
Параметр: char[] buf4
Возвращает: int

buf4[] — это назначение, а не источник. Результаты из read4 будут скопированы в buf4[].

Метод read:
Используя метод read4, реализуйте метод read, который читает n символов из файла и сохраняет их в массиве буфера buf. Учтите, что вы не можете напрямую манипулировать файлом.
Возвращаемое значение — количество фактически прочитанных символов.

Определение read:
Параметры: char[] buf, int n
Возвращает: int

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

Примечание:
Учтите, что вы не можете напрямую манипулировать файлом. Файл доступен только для чтения с помощью read4, но не для read.
Функция read будет вызываться только один раз для каждого тестового случая.
Вы можете предполагать, что массив буфера назначения, buf, гарантированно имеет достаточно места для хранения n символов.

Пример:

Input: file = "abc", n = 4
Output: 3
Explanation: After calling your read method, buf should contain "abc". We read a total of 3 characters from the file, so return 3.
Note that "abc" is the file's content, not buf. buf is the destination buffer that you will have to write the results to.

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

1⃣Инициализация и подготовка:
Инициализируйте переменные: copiedChars = 0 для подсчета скопированных символов и readChars = 4 для подсчета прочитанных символов из файла. Начальное значение readChars установлено в 4, что позволяет использовать условие readChars != 4 в качестве маркера конца файла (EOF).
Создайте внутренний буфер из 4 символов: buf4.

2⃣Чтение и копирование символов:
Пока количество скопированных символов меньше N (copiedChars < n) и еще есть символы в файле (readChars == 4):
Прочитайте символы из файла во внутренний буфер buf4 с помощью метода read4(buf4).
Копируйте символы из внутреннего буфера buf4 в основной буфер buf по одному. Увеличивайте copiedChars после каждого скопированного символа.

3⃣Завершение процесса:
Если количество скопированных символов достигло N (copiedChars == n), прервите процесс копирования.
Верните copiedChars как результат функции, указывающий на количество успешно скопированных символов в основной буфер buf.

😎 Решение:

class Solution {
    func read(_ buf: inout [Character], _ n: Int) -> Int {
        var copiedChars = 0
        var readChars = 4
        var buf4 = [Character](repeating: " ", count: 4)
        
        while copiedChars < n && readChars == 4 {
            readChars = read4(&buf4)
            
            for i in 0..<readChars {
                if copiedChars == n { return copiedChars }
                buf[copiedChars] = buf4[i]
                copiedChars += 1
            }
        }
        return copiedChars
    }

    private func read4(_ buf4: inout [Character]) -> Int {
        return 0
    }
}

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

Задача: 719. Find K-th Smallest Pair Distance
Сложность: hard

Расстояние между парой целых чисел a и b определяется как абсолютная разность между a и b. Учитывая целочисленный массив nums и целое число k, верните k-е наименьшее расстояние среди всех пар nums[i] и nums[j], где 0 <= i < j < nums.length.

Пример:

Input: nums = [1,3,1], k = 1
Output: 0

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

1⃣Отсортируйте массив nums.

2⃣Определите минимальное и максимальное возможные расстояния.

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

😎 Решение:

func smallestDistancePair(_ nums: [Int], _ k: Int) -> Int {
    let nums = nums.sorted()
    
    func countPairs(_ mid: Int) -> Int {
        var count = 0, j = 0
        for i in 0..<nums.count {
            while j < nums.count && nums[j] - nums[i] <= mid {
                j += 1
            }
            count += j - i - 1
        }
        return count
    }
    
    var left = 0, right = nums.last! - nums.first!
    while left < right {
        let mid = (left + right) / 2
        if countPairs(mid) < k {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

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

Задача: 1094. Car Pooling
Сложность: medium

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

Дан целочисленный параметр capacity и массив поездок trips, где trips[i] = [numPassengersi, fromi, toi] указывает, что на i-й поездке numPassengersi пассажиров должны быть забраны на позиции fromi и высажены на позиции toi. Позиции заданы как количество километров на восток от начальной точки автомобиля.

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

Пример:

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false

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

1⃣Простая идея заключается в том, чтобы пройти от начала до конца и проверить, превышает ли фактическая вместимость capacity.

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

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

😎 Решение:

class Solution {
    func carPooling(_ trips: [[Int]], _ capacity: Int) -> Bool {
        var timestamp: [Int: Int] = [:]
        for trip in trips {
            timestamp[trip[1], default: 0] += trip[0]
            timestamp[trip[2], default: 0] -= trip[0]
        }
        let sortedTimestamps = timestamp.keys.sorted()
        var usedCapacity = 0
        for time in sortedTimestamps {
            usedCapacity += timestamp[time]!
            if usedCapacity > capacity {
                return false
            }
        }
        return true
    }
}

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

Задача: 283. Move Zeroes
Сложность: easy

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

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

Пример:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

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

1⃣Инициализация указателей:
Инициализируйте два указателя: lastNonZeroFoundAt для отслеживания позиции последнего ненулевого элемента и cur для итерации по массиву.

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

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

😎 Решение:

class Solution {
    func moveZeroes(_ nums: inout [Int]) {
        var lastNonZeroFoundAt = 0
        for cur in 0..<nums.count {
            if nums[cur] != 0 {
                nums.swapAt(lastNonZeroFoundAt, cur)
                lastNonZeroFoundAt += 1
            }
        }
    }
}

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

Задача: 1247. Minimum Swaps to Make Strings Equal
Сложность: hard

Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать.

Пример:

Input: arr = [1,2]
Output: 2

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

1⃣Подсчет несоответствующих пар:
Пройдите по строкам s1 и s2, чтобы подсчитать количество пар xy и yx. Пара xy возникает, когда s1[i] равно 'x', а s2[i] равно 'y'. Пара yx возникает, когда s1[i] равно 'y', а s2[i] равно 'x'.

2⃣Проверка четности:
Если сумма количества пар xy и yx нечетная, то невозможно сделать строки равными, поскольку каждая замена уменьшает сумму несоответствующих пар на 2. В этом случае верните -1.

3⃣Вычисление минимального количества замен:
Если количество пар xy четное и количество пар yx четное, то каждые две пары xy и каждые две пары yx можно обменять за один ход. Поэтому минимальное количество замен равно xy // 2 + yx // 2.
Если количество пар xy нечетное и количество пар yx нечетное, то мы можем обменять одну пару xy и одну пару yx за два хода. Поэтому минимальное количество замен равно xy // 2 + yx // 2 + 2.

😎 Решение:

class Solution {
    func minimumSwap(_ s1: String, _ s2: String) -> Int {
        var xy = 0, yx = 0
        for (a, b) in zip(s1, s2) {
            if a == "x" && b == "y" {
                xy += 1
            } else if a == "y" && b == "x" {
                yx += 1
            }
        }
        if (xy + yx) % 2 != 0 {
            return -1
        }
        return xy / 2 + yx / 2 + (xy % 2) * 2
    }
}

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

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

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