Задача: 641. Design Circular Deque
Сложность: medium

Разработайте свою реализацию круговой двусторонней очереди (deque). Реализуйте класс MyCircularDeque: MyCircularDeque(int k) Инициализирует deque с максимальным размером k. boolean insertFront() Добавляет элемент в переднюю часть Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean insertLast() Добавляет элемент в заднюю часть Deque. Возвращает true, если операция выполнена успешно, или false в противном случае. boolean deleteFront() Удаляет элемент из передней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean deleteLast() Удаляет элемент из задней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. int getFront() Возвращает передний элемент из Deque. Возвращает -1, если Deque пуст. int getRear() Возвращает последний элемент из Deque. Возвращает -1, если Deque пуст. boolean isEmpty() Возвращает true, если Deque пуст, или false в противном случае. boolean isFull() Возвращает true, если Deque полон, или false в противном случае.

Пример:

Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]

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

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

2⃣Операции вставки: Реализуйте методы вставки элементов в переднюю и заднюю части очереди с учетом кольцевой структуры.

3⃣Операции удаления: Реализуйте методы удаления элементов из передней и задней частей очереди с учетом кольцевой структуры и методы для получения переднего и заднего элементов очереди.

😎 Решение:

class MyCircularDeque {
    private var deque: [Int]
    private var front: Int
    private var rear: Int
    private var size: Int
    private var capacity: Int

    init(_ k: Int) {
        self.capacity = k
        self.deque = [Int](repeating: 0, count: k)
        self.front = 0
        self.rear = 0
        self.size = 0
    }

    func insertFront(_ value: Int) -> Bool {
        if isFull() {
            return false
        }
        front = (front - 1 + capacity) % capacity
        deque[front] = value
        size += 1
        return true
    }

    func insertLast(_ value: Int) -> Bool {
        if isFull() {
            return false
        }
        deque[rear] = value
        rear = (rear + 1) % capacity
        size += 1
        return true
    }

    func deleteFront() -> Bool {
        if isEmpty() {
            return false
        }
        front = (front + 1) % capacity
        size -= 1
        return true
    }

    func deleteLast() -> Bool {
        if isEmpty() {
            return false
        }
        rear = (rear - 1 + capacity) % capacity
        size -= 1
        return true
    }

    func getFront() -> Int {
        if isEmpty() {
            return -1
        }
        return deque[front]
    }

    func getRear() -> Int {
        if isEmpty() {
            return -1
        }
        return deque[(rear - 1 + capacity) % capacity]
    }

    func isEmpty() -> Bool {
        return size == 0
    }

    func isFull() -> Bool {
        return size == capacity
    }
}

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

Задача: 1166. Design File System
Сложность: medium

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

Формат пути - это одна или несколько конкатенированных строк в форме: /, за которой следует одна или несколько строчных английских букв. Например, "/leetcode" и "/leetcode/problems" - допустимые пути, в то время как пустая строка "" и "/" не допустимы.

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

- bool createPath(string path, int value) создает новый путь и связывает с ним значение, если это возможно, и возвращает true. Возвращает false, если путь уже существует или его родительский путь не существует.
- int get(string path) возвращает значение, связанное с путем, или возвращает -1, если путь не существует.

Пример:

Input: 
["FileSystem","createPath","get"]
[[],["/a",1],["/a"]]
Output: 
[null,true,1]
Explanation: 
FileSystem fileSystem = new FileSystem();

fileSystem.createPath("/a", 1); // return true
fileSystem.get("/a"); // return 1

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

1⃣Инициализируйте словарь или HashMap под названием paths, который будет использовать ключ в виде пути, переданного в нашу функцию create, и значение, переданное этой функции.

2⃣Для функции create выполняем три шага. Сначала выполняем базовую проверку валидности пути. Проверяем, является ли путь пустым, "/" или если путь уже существует в нашем словаре. Если любое из этих условий выполнено, просто возвращаем false. Затем получаем родительский путь предоставленного пути и проверяем его наличие в словаре. Если родительский путь не существует, возвращаем false, иначе продолжаем.

3⃣Наконец, вставляем предоставленный путь и значение в словарь и возвращаем true. Для функции get просто возвращаем значение по умолчанию -1, если путь не существует в словаре. В противном случае возвращаем фактическое значение.

😎 Решение

class FileSystem {
    var paths: [String: Int]

    init() {
        self.paths = [String: Int]()
    }

    func createPath(_ path: String, _ value: Int) -> Bool {
        if path.isEmpty || (path.count == 1 && path == "/") || self.paths[path] != nil {
            return false
        }
        
        let delimIndex = path.lastIndex(of: "/")!
        let parent = String(path[..<delimIndex])
        
        if parent.count > 1 && self.paths[parent] == nil {
            return false
        }
        
        self.paths[path] = value
        return true
    }

    func get(_ path: String) -> Int {
        return self.paths[path] ?? -1
    }
}

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

Задача: 334. Increasing Triplet Subsequence
Сложность: medium

Дан массив целых чисел nums. Верните true, если существуют такие три индекса (i, j, k), что i < j < k и nums[i] < nums[j] < nums[k]. Если таких индексов не существует, верните false.

Пример:

Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

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

1⃣Инициализация переменных:
Создайте две переменные first_num и second_num и установите их значение на максимальное целое значение (Integer.MAX_VALUE или аналогичный максимум для выбранного языка программирования). Эти переменные будут хранить минимальные значения, необходимые для проверки существования возрастающей тройки.

2⃣Итерация по массиву:
Пройдите по каждому элементу массива nums. Для каждого элемента выполните следующие проверки:
- если текущий элемент меньше или равен first_num, обновите first_num текущим элементом.
- иначе, если текущий элемент меньше или равен second_num, обновите second_num текущим элементом.
- иначе, если текущий элемент больше second_num, это означает, что найдена возрастающая тройка, поэтому верните true.

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

😎 Решение:

class Solution {
    func increasingTriplet(_ nums: [Int]) -> Bool {
        var firstNum = Int.max
        var secondNum = Int.max
        
        for n in nums {
            if n <= firstNum {
                firstNum = n
            } else if n <= secondNum {
                secondNum = n
            } else {
                return true
            }
        }
        return false
    }
}

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

Задача: 527. Word Abbreviation
Сложность: hard

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

Правила сокращения строки следующие:
Первоначальное сокращение для каждого слова: первый символ, затем количество символов между первым и последним символом, затем последний символ.
Если более одного слова имеют одинаковое сокращение, выполните следующее:
Увеличьте префикс (символы в первой части) каждого из их сокращений на 1.
Например, начнем с слов ["abcdef", "abndef"], оба изначально сокращены как "a4f". Последовательность операций будет следующей: ["a4f", "a4f"] -> ["ab3f", "ab3f"] -> ["abc2f", "abn2f"].
Эта операция повторяется до тех пор, пока каждое сокращение не станет уникальным.
В конце, если сокращение не сделало слово короче, оставьте его в исходном виде.

Пример:

Input: words = ["like","god","internal","me","internet","interval","intension","face","intrusion"]
Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]

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

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

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

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

😎 Решение:

class Solution {
    func wordsAbbreviation(_ words: [String]) -> [String] {
        let n = words.count
        var ans = Array(repeating: "", count: n)
        var prefix = Array(repeating: 0, count: n)

        for i in 0..<n {
            ans[i] = abbrev(words[i], 0)
        }

        for i in 0..<n {
            while true {
                var dupes = Set<Int>()
                for j in (i+1)..<n {
                    if ans[i] == ans[j] {
                        dupes.insert(j)
                    }
                }

                if dupes.isEmpty { break }
                dupes.insert(i)
                for k in dupes {
                    ans[k] = abbrev(words[k], prefix[k] + 1)
                    prefix[k] += 1
                }
            }
        }

        return ans
    }

    private func abbrev(_ word: String, _ i: Int) -> String {
        let n = word.count
        if n - i <= 3 { return word }
        let start = word.prefix(i + 1)
        let end = word.suffix(1)
        return "\(start)\(n - i - 2)\(end)"
    }
}

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

Задача: 30. Substring with Concatenation of All Words
Сложность: hard

Вам дана строка s и массив строк words. Все строки в words имеют одинаковую длину.

Объединенная строка — это строка, которая в точности содержит все строки любой перестановки words.

Возвращает массив начальных индексов всех объединенных подстрок в s.

Пример:

Input: s = "barfoothefoobarman", words = ["foo","bar"]  
Output: [0,9]  

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

1⃣Определяем длину слова len и количество слов cnt.

2⃣Создаем словарь wf с частотами слов в words.

3⃣Проходим по строке s, проверяя подстроки длиной cnt * len.

😎Решение:

class Solution {
    func findSubstring(_ s: String, _ words: [String]) -> [Int] {
        let len = words.first!.count
        let cnt = words.count

        guard s.count >= cnt * len else { return [] }
        
        let s = Array(s)
        let words = words.map(Array.init)
        let wf = words.reduce(into: [[Character]: Int]()) { $0[$1, default: 0] += 1 }
        let ws = Set(words)
        var res = [Int]()

        for i in 0...(s.count - cnt * len) {
            var sf = [[Character]: Int]()
            var j = i

            for _ in 0..<cnt {
                let w = Array(s[j..<j + len])
                guard ws.contains(w) else { break }

                let old = sf[w, default: 0]
                guard old + 1 <= wf[w]! else { break }

                sf[w] = old + 1
                j += len
            }

            guard j == i + cnt * len, sf == wf else { continue }
            res.append(i)
        }

        return res
    }
}

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

Задача: 1140. Stone Game II
Сложность: medium

Алиса и Боб продолжают свои игры с кучами камней. Есть несколько куч, расположенных в ряд, и в каждой куче положительное количество камней piles[i]. Цель игры - закончить с наибольшим количеством камней.
Алиса и Боб ходят по очереди, начиная с Алисы. Изначально M = 1.
В свой ход каждый игрок может взять все камни из первых X оставшихся куч, где 1 <= X <= 2M. Затем, мы устанавливаем M = max(M, X).
Игра продолжается до тех пор, пока все камни не будут взяты.
Предполагая, что Алиса и Боб играют оптимально, верните максимальное количество камней, которые может получить Алиса.

Пример:

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger. 

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

1⃣Создать рекурсивную функцию f, которая принимает три параметра: p (игрок), i (индекс текущей кучи), и m (максимальное количество куч, которые можно взять за ход). Если i равен длине массива кучи, вернуть 0 (базовый случай рекурсии). Если значение уже вычислено ранее (dp[p][i][m] != -1), вернуть его.

2⃣Инициализировать переменную s как количество камней, взятых текущим игроком за ход, и переменную res для хранения результата текущего состояния. Если ход Боба, инициализировать res большим числом, так как Боб хочет минимизировать результат. Если ход Алисы, инициализировать res маленьким числом, так как Алиса хочет максимизировать результат.

3⃣Итеративно обновлять значение res в зависимости от того, чей ход, и обновлять значения в dp[p][i][m]. В конце вернуть res.

😎 Решение:

class Solution {
    func stoneGameII(_ piles: [Int]) -> Int {
        var dp = Array(repeating: Array(repeating: Array(repeating: -1, count: piles.count + 1), count: piles.count + 1), count: 2)
        
        func f(_ p: Int, _ i: Int, _ m: Int) -> Int {
            if i == piles.count {
                return 0
            }
            if dp[p][i][m] != -1 {
                return dp[p][i][m]
            }
            var res = p == 1 ? Int.max : -1
            var s = 0
            for x in 1...min(2 * m, piles.count - i) {
                s += piles[i + x - 1]
                if p == 0 {
                    res = max(res, s + f(1, i + x, max(m, x)))
                } else {
                    res = min(res, f(0, i + x, max(m, x)))
                }
            }
            dp[p][i][m] = res
            return res
        }
        
        return f(0, 0, 1)
    }
}

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

Задача: 282. Expression Add Operators
Сложность: hard

Дана строка num, содержащая только цифры, и целое число target. Верните все возможные варианты вставки бинарных операторов '+', '-', и/или '*' между цифрами строки num так, чтобы результирующее выражение вычислялось в значение target.

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

Пример:

Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]
Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.

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

1⃣Инициализация и рекурсивный вызов:
Создайте класс Solution с полями для хранения результирующих выражений, строки цифр и целевого значения.
Инициализируйте эти поля в методе addOperators и запустите рекурсивный метод для генерации всех возможных выражений.

2⃣Рекурсивная генерация выражений:
В методе recurse на каждом шаге рассматривайте текущий индекс, предыдущий операнд, текущий операнд и текущее значение выражения.
Обрабатывайте все возможные операторы: без оператора (расширение текущего операнда), сложение, вычитание и умножение. На каждом шаге обновляйте текущее значение и выражение.

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

😎 Решение:

class Solution {
    var answer = [String]()
    var digits = ""
    var target: Int64 = 0

    func recurse(_ index: Int, _ previousOperand: Int64, _ currentOperand: Int64, _ value: Int64, _ ops: inout [String]) {
        if index == digits.count {
            if value == target && currentOperand == 0 {
                answer.append(ops.joined())
            }
            return
        }

        let nums = Array(digits)
        let currentDigit = Int64(String(nums[index]))!
        let currentOperand = currentOperand * 10 + currentDigit
        let currentValRep = String(currentOperand)

        if currentOperand > 0 {
            recurse(index + 1, previousOperand, currentOperand, value, &ops)
        }

        ops.append("+")
        ops.append(currentValRep)
        recurse(index + 1, currentOperand, 0, value + currentOperand, &ops)
        ops.removeLast(2)

        if !ops.isEmpty {
            ops.append("-")
            ops.append(currentValRep)
            recurse(index + 1, -currentOperand, 0, value - currentOperand, &ops)
            ops.removeLast(2)

            ops.append("*")
            ops.append(currentValRep)
            recurse(index + 1, currentOperand * previousOperand, 0, value - previousOperand + (currentOperand * previousOperand), &ops)
            ops.removeLast(2)
        }
    }

    func addOperators(_ num: String, _ target: Int) -> [String] {
        if num.isEmpty {
            return []
        }

        self.target = Int64(target)
        self.digits = num
        self.answer = []
        var ops = [String]()
        recurse(0, 0, 0, 0, &ops)
        return answer
    }
}

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

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

Пример:

Input: columnTitle = "A"
Output: 1

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

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

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

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

😎 Решение:

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

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

    return dp[n][k]
}

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

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

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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