Задача: 1503. Last Moment Before All Ants Fall Out of a Plank
Сложность: medium

У нас есть деревянная доска длиной n единиц. Некоторые муравьи ходят по доске, каждый муравей движется со скоростью 1 единица в секунду. Некоторые муравьи движутся влево, другие движутся вправо.

Когда два муравья, движущиеся в разных направлениях, встречаются в какой-то точке, они меняют свои направления и продолжают двигаться дальше. Предполагается, что изменение направлений не занимает дополнительного времени.

Когда муравей достигает одного из концов доски в момент времени t, он сразу же падает с доски.

Дано целое число n и два целых массива left и right, обозначающие позиции муравьев, движущихся влево и вправо соответственно. Верните момент, когда последний(е) муравей(и) падает(ют) с доски.

Пример:

Input: n = 4, left = [4,3], right = [0,1]
Output: 4
Explanation: In the image above:
-The ant at index 0 is named A and going to the right.
-The ant at index 1 is named B and going to the right.
-The ant at index 3 is named C and going to the left.
-The ant at index 4 is named D and going to the left.
The last moment when an ant was on the plank is t = 4 seconds. After that, it falls immediately out of the plank. (i.e., We can say that at t = 4.0000000001, there are no ants on the plank).

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

1⃣Инициализируйте переменную ans значением 0.

2⃣Итерация по массиву left и обновление ans значением num, если оно больше текущего значения ans.

3⃣Итерация по массиву right и обновление ans значением n - num, если оно больше текущего значения ans. Верните значение ans.

😎 Решение

class Solution {
    func getLastMoment(_ n: Int, _ left: [Int], _ right: [Int]) -> Int {
        var ans = 0
        for num in left {
            ans = max(ans, num)
        }
        for num in right {
            ans = max(ans, n - num)
        }
        return ans
    }
}

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

Задача: 1315. Sum of Nodes with Even-Valued Grandparent
Сложность: medium

Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0.

A grandparent of a node is the parent of its parent if it exists.

Пример:

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.

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

1⃣Создайте целочисленную переменную n и инициализируйте её размером строки s. Создайте строковую переменную sReverse и установите её значение как обратную строку s.

2⃣Создайте двумерный массив memo размером n + 1 на n + 1, где memo[i][j] будет содержать длину наибольшей общей подпоследовательности, учитывая первые i символов строки s и первые j символов строки sReverse. Инициализируйте массив значением -1.

3⃣Верните n - lcs(s, sReverse, n, n, memo), где lcs - это рекурсивный метод с четырьмя параметрами: первая строка s1, вторая строка s2, длина подстроки от начала s1, длина подстроки от начала s2 и memo. Метод возвращает длину наибольшей общей подпоследовательности в подстроках s1 и s2. В этом методе выполните следующее:
Если m == 0 или n == 0, это означает, что одна из двух подстрок пуста, поэтому верните 0.
Если memo[m][n] != -1, это означает, что мы уже решили эту подзадачу, поэтому верните memo[m][n].
Если последние символы подстрок совпадают, добавьте 1 и найдите длину наибольшей общей подпоследовательности, исключив последний символ обеих подстрок. Верните memo[i][j] = 1 + lcs(s1, s2, m - 1, n - 1, memo).
В противном случае, если последние символы не совпадают, рекурсивно найдите наибольшую общую подпоследовательность в обеих подстроках, исключив их последние символы по одному. Верните memo[i][j] = max(lcs(s1, s2, m - 1, n, memo), lcs(s1, s2, m, n - 1, memo)).

😎 Решение

class Solution {
    lcs(s1, s2, m, n, memo) {
        if (m == 0 || n == 0) {
            return 0;
        }
        if (memo[m][n] !== -1) {
            return memo[m][n];
        }
        if (s1[m - 1] === s2[n - 1]) {
            memo[m][n] = 1 + this.lcs(s1, s2, m - 1, n - 1, memo);
        } else {
            memo[m][n] = Math.max(this.lcs(s1, s2, m - 1, n, memo), this.lcs(s1, s2, m, n - 1, memo));
        }
        return memo[m][n];
    }

    minInsertions(s) {
        const n = s.length;
        const sReverse = s.split('').reverse().join('');
        const memo = Array.from({ length: n + 1 }, () => Array(n + 1).fill(-1));
        return n - this.lcs(s, sReverse, n, n, memo);
    }
}

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

Задача: 1041. Robot Bounded In Circle
Сложность: medium

На бесконечной плоскости робот изначально стоит в точке (0, 0) и обращен лицом на север. Обратите внимание, что: северное направление - это положительное направление оси y. южное направление - это отрицательное направление оси y. восточное направление - это положительное направление оси x. западное направление - это отрицательное направление оси x. робот может получить одну из трех команд: "G": идти прямо 1 единицу. "L": повернуть на 90 градусов влево (т.е, "R": повернуть на 90 градусов вправо (т. е. по часовой стрелке). Робот выполняет данные инструкции по порядку и повторяет их до бесконечности. Возвращается true тогда и только тогда, когда в плоскости существует окружность, такая, что робот никогда не покидает ее.

Пример:

Input: instructions = "GGLLGG"
Output: true

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

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

2⃣Изменение направления:
Робот может двигаться на север (0), восток (1), юг (2), или запад (3). Эти направления можно моделировать с помощью векторов (dx, dy): север (0, 1), восток (1, 0), юг (0, -1), запад (-1, 0).

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

😎 Решение:

class Solution {
    func isRobotBounded(_ instructions: String) -> Bool {
        let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        var x = 0
        var y = 0
        var direction = 0
        
        for instruction in instructions {
            if instruction == "G" {
                x += directions[direction].0
                y += directions[direction].1
            } else if instruction == "L" {
                direction = (direction + 3) % 4
            } else if instruction == "R" {
                direction = (direction + 1) % 4
            }
        }
        
        return (x == 0 && y == 0) || direction != 0
    }
}

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

Задача: 946. Validate Stack Sequences
Сложность: medium

Вам дан целочисленный массив nums. За один ход вы можете выбрать индекс i, где 0 <= i < nums.length, и увеличить nums[i] на 1. Верните минимальное количество ходов, чтобы каждое значение в nums было уникальным. Тестовые примеры генерируются так, чтобы ответ умещался в 32-битное целое число.

Пример:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true

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

1⃣Инициализировать пустой стек.
Использовать указатель j для отслеживания текущей позиции в массиве popped.

2⃣Пройти по каждому элементу в массиве pushed:
Добавить элемент в стек.
Проверить верхний элемент стека:
Если он совпадает с текущим элементом в popped, удалить элемент из стека и увеличить указатель j.

3⃣В конце вернуть true, если указатель j достиг конца массива popped, иначе вернуть false.

😎 Решение:

class Solution {
    func validateStackSequences(_ pushed: [Int], _ popped: [Int]) -> Bool {
        var stack = [Int]()
        var j = 0
        for x in pushed {
            stack.append(x)
            while !stack.isEmpty && j < popped.count && stack.last == popped[j] {
                stack.removeLast()
                j += 1
            }
        }
        return j == popped.count
    }
}

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

Задача: 219. Contains Duplicate II
Сложность: easy

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

Пример:

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

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

1⃣Создайте пустое множество set.

2⃣Пройдитесь по массиву nums:
Если текущий элемент уже есть в множестве, верните true.
Добавьте текущий элемент в множество.
Если размер множества больше k, удалите элемент, который был добавлен k шагов назад.

3⃣Если не найдены дублирующиеся элементы на расстоянии k или менее, верните false.

😎 Решение:

class Solution {
    func containsNearbyDuplicate(_ nums: [Int], _ k: Int) -> Bool {
        var set = Set<Int>()
        for i in 0..<nums.count {
            if set.contains(nums[i]) {
                return true
            }
            set.insert(nums[i])
            if set.count > k {
                set.remove(nums[i - k])
            }
        }
        return false
    }
}

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

Задача: 1328. Break a Palindrome
Сложность: medium

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

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

Строка a лексикографически меньше строки b (одинаковой длины), если в первой позиции, где они отличаются, у строки a символ строго меньше соответствующего символа в строке b. Например, "abcc" лексикографически меньше "abcd", потому что первой различающейся позицией является четвертая, и 'c' меньше, чем 'd'.

Пример:

Input: palindrome = "abccba"
Output: "aaccba"
Explanation: There are many ways to make "abccba" not a palindrome, such as "zbccba", "aaccba", and "abacba".
Of all the ways, "aaccba" is the lexicographically smallest.

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

1⃣Если длина строки равна 1, верните пустую строку, так как невозможно создать непалиндромическую строку в этом случае.

2⃣Итерируйтесь по строке слева до середины строки: если символ не равен 'a', измените его на 'a' и верните строку.

3⃣Если вы прошли всю левую часть строки и все еще не получили непалиндромическую строку, это означает, что строка состоит только из 'a'. Следовательно, измените последний символ на 'b' и верните полученную строку.

😎 Решение

class Solution {
    func breakPalindrome(_ palindrome: String) -> String {
        var palindromeArray = Array(palindrome)
        let length = palindromeArray.count
        
        if length == 1 {
            return ""
        }
        
        for i in 0..<length / 2 {
            if palindromeArray[i] != "a" {
                palindromeArray[i] = "a"
                return String(palindromeArray)
            }
        }
        
        palindromeArray[length - 1] = "b"
        return String(palindromeArray)
    }
}

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

Задача: 556. Next Greater Element III
Сложность: medium

Мы можем перемешать строку s, чтобы получить строку t, используя следующий алгоритм:

Дано положительное целое число n. Найдите наименьшее целое число, которое имеет точно такие же цифры, как и число n, и больше самого числа n по значению. Если такого положительного целого числа не существует, верните -1.

Учтите, что возвращенное число должно помещаться в 32-битное целое число. Если существует допустимый ответ, но он не помещается в 32-битное целое число, верните -1.

Пример:

Input: n = 12
Output: 21

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

1⃣Нахождение и перестановка цифр
Преобразуйте число n в массив цифр. Найдите первую цифру, которая нарушает убывающий порядок (с конца массива). Назовем её индексом i. Найдите первую цифру, которая больше digits[i-1] (с конца массива). Назовем её индексом j. Поменяйте местами цифры на позициях i-1 и j.

2⃣Обратный порядок оставшихся цифр
Обратный порядок части массива от индекса i до конца, чтобы получить наименьшую перестановку, которая больше исходной.

3⃣Проверка результата и преобразование обратно в число
Преобразуйте массив цифр обратно в число. Если число превышает 32-битный предел, верните -1. В противном случае верните полученное число.

😎 Решение:

class Solution {
    private func swap(_ s: String, _ i0: Int, _ i1: Int) -> String {
        if i0 == i1 {
            return s
        }
        var chars = Array(s)
        chars.swapAt(i0, i1)
        return String(chars)
    }

    private var list = [String]()
    
    private func permute(_ a: String, _ l: Int, _ r: Int) {
        if l == r {
            list.append(a)
        } else {
            var a = a
            for i in l...r {
                a = swap(a, l, i)
                permute(a, l + 1, r)
                a = swap(a, l, i)
            }
        }
    }

    func nextGreaterElement(_ n: Int) -> Int {
        let s = String(n)
        permute(s, 0, s.count - 1)
        list.sort()
        if let index = list.firstIndex(of: s), index < list.count - 1 {
            if let result = Int(list[index + 1]), result <= Int32.max {
                return result
            }
        }
        return -1
    }
}

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

Задача: 188. Best Time to Buy and Sell Stock IV
Сложность: hard

Дан массив целых чисел prices, где prices[i] - это цена данной акции в i-й день, и целое число k.

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

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

Пример:

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

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

1⃣Инициализация DP массива: Инициализируйте трехмерный массив dp, где dp[i][j][l] представляет максимальную прибыль на конец i-го дня с j оставшимися транзакциями и l акциями в портфеле. Начните с dp[0][0][0] = 0 (нет прибыли без акций и транзакций) и dp[0][1][1] = -prices[0] (покупка первой акции).

2⃣Вычисление переходов: Для каждого дня и каждого возможного количества транзакций вычислите возможные действия: держать акцию, не держать акцию, купить акцию, если j > 0, или продать акцию. Обновляйте dp с использованием:
dp[i][j][1] = max(dp[i−1][j][1], dp[i−1][j−1][0] - prices[i]) (максимум между удержанием акции и покупкой новой).
dp[i][j][0] = max(dp[i−1][j][0], dp[i−1][j][1] + prices[i]) (максимум между неудержанием акции и продажей).

3⃣Расчет результатов: По завершении всех дней, возвращайте максимальное значение dp[n-1][j][0] для всех j от 0 до k, что представляет максимальную прибыль без удержания акций на последний день. Обработайте специальный случай, когда 𝑘×2≥𝑛, чтобы избежать лишних расчетов.

😎 Решение:

class Solution {
    func maxProfit(_ k: Int, _ prices: [Int]) -> Int {
        let n = prices.count
        if n <= 0 || k <= 0 { return 0 }
        if k * 2 >= n {
            return prices.dropFirst().enumerated().reduce(0) { $0 + max(0, prices[$1.offset + 1] - prices[$1.offset]) }
        }
        var dp = Array(repeating: Array(repeating: [Int.min / 2, Int.min / 2], count: k + 1), count: n)
        dp[0][0][0] = 0
        dp[0][1][1] = -prices[0]

        for i in 1..<n {
            for j in 0...k {
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i])
                if j > 0 {
                    dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i])
                }
            }
        }
        return dp[n - 1].map { $0[0] }.max() ?? 0
    }
}

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

Задача: 561. Array Partition
Сложность: easy

Дан массив целых чисел nums из 2n элементов. Разделите эти числа на n пар (a1, b1), (a2, b2), ..., (an, bn) так, чтобы сумма min(ai, bi) для всех i была максимальной. Верните максимальную сумму.

Пример:

Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
So the maximum possible sum is 4.

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

1⃣Отсортируйте массив nums в неубывающем порядке.

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

3⃣Суммируйте выбранные элементы и верните эту сумму.

😎 Решение:

class Solution {
    func arrayPairSum(_ nums: [Int]) -> Int {
        let sortedNums = nums.sorted()
        var sum = 0
        for i in stride(from: 0, to: sortedNums.count, by: 2) {
            sum += sortedNums[i]
        }
        return sum
    }
}

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

Задача: 726. Number of Atoms
Сложность: hard

Если задана строковая формула, представляющая химическую формулу, верните количество атомов. Атомный элемент всегда начинается с прописного символа, затем ноль или более строчных букв, представляющих его название. Если количество больше 1, за ним может следовать одна или более цифр, представляющих количество элементов. Например, "H2O" и "H2O2" возможны, а "H1O2" невозможен. Две формулы объединяются вместе, чтобы получить другую формулу. Например, "H2O2He3Mg4" также является формулой.
Формула, заключенная в круглые скобки, и счет (по желанию) также являются формулами. Например, "(H2O2)" и "(H2O2)3" являются формулами.
Возвращает количество всех элементов в виде строки в следующем виде: первое имя (в отсортированном порядке), затем его количество (если это количество больше 1), затем второе имя (в отсортированном порядке), затем его количество (если это количество больше 1) и т. д. Тестовые примеры генерируются таким образом, чтобы все значения в выводе помещались в 32-битное целое число.

Пример:

Input: formula = "H2O"
Output: "H2O"

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

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

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

3⃣После завершения обработки строки, объедините все словари из стека и отсортируйте результат.

😎 Решение:

import Foundation

func countOfAtoms(_ formula: String) -> String {
    var stack = [Dictionary<String, Int>]()
    stack.append(Dictionary<String, Int>())
    let formula = Array(formula)
    var i = 0
    let n = formula.count
    
    while i < n {
        if formula[i] == "(" {
            stack.append(Dictionary<String, Int>())
            i += 1
        } else if formula[i] == ")" {
            let top = stack.removeLast()
            i += 1
            var multiplicity = 0
            while i < n && formula[i].isNumber {
                multiplicity = multiplicity * 10 + Int(String(formula[i]))!
                i += 1
            }
            multiplicity = multiplicity == 0 ? 1 : multiplicity
            for (name, count) in top {
                stack[stack.count - 1][name, default: 0] += count * multiplicity
            }
        } else {
            var start = i
            i += 1
            while i < n && formula[i].isLowercase {
                i += 1
            }
            let name = String(formula[start..<i])
            start = i
            var multiplicity = 0
            while i < n && formula[i].isNumber {
                multiplicity = multiplicity * 10 + Int(String(formula[i]))!
                i += 1
            }
            multiplicity = multiplicity == 0 ? 1 : multiplicity
            stack[stack.count - 1][name, default: 0] += multiplicity
        }
    }
    
    let last = stack.removeLast()
    var result = ""
    for key in last.keys.sorted() {
        result += key
        if last[key]! > 1 {
            result += "\(last[key]!)"
        }
    }
    return result
}

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

Задача: 1490. Clone N-ary Tree
Сложность: medium

Дан корень N-арного дерева, верните глубокую копию (клон) дерева.
Каждый узел в N-арном дереве содержит значение (val) типа int и список (List[Node]) его детей.

class Node {
    public int val;
    public List<Node> children;
}

Сериализация входных данных N-арного дерева представлена в порядке обхода по уровням, каждая группа детей разделена значением null (см. примеры).

Пример:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]

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

1⃣Базовый случай:
Проверить, является ли входной узел null. Если да, вернуть null.

2⃣Копирование узла:
Создать новый узел с таким же значением, как у входного узла.

3⃣Рекурсивное клонирование детей:
Рекурсивно клонировать каждого ребёнка входного узла и добавить клонированных детей в список детей нового узла.
Вернуть клонированный узел.

😎 Решение:

class Node {
    public var val: Int
    public var children: [Node]
    public init(_ val: Int) {
        self.val = val
        self.children = []
    }
}

class Solution {
    func cloneTree(_ root: Node?) -> Node? {
        guard let root = root else {
            return nil
        }

        let nodeCopy = Node(root.val)
        for child in root.children {
            nodeCopy.children.append(cloneTree(child)!)
        }
        return nodeCopy
    }
}

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

Задача: 1064. Fixed Point
Сложность: easy

Дан массив различных целых чисел arr, отсортированный в порядке возрастания. Верните наименьший индекс i, который удовлетворяет условию arr[i] == i. Если такого индекса нет, верните -1.

Пример:

Input: arr = [-10,-5,0,3,7]
Output: 3
Explanation: For the given array, arr[0] = -10, arr[1] = -5, arr[2] = 0, arr[3] = 3, thus the output is 3.

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

1⃣Инициализируйте значение left как 0, right как N - 1 и answer как -1.

2⃣Пока размер области поиска не равен нулю, то есть left <= right, выполните следующие шаги: найдите mid как mid = (left + right) / 2. Сравните arr[mid] и mid: если arr[mid] = mid, сохраните mid в answer и перейдите в левую часть, изменив right на mid - 1; если arr[mid] < mid, перейдите в правую часть, изменив left на mid + 1; если arr[mid] > mid, перейдите в левую часть, изменив right на mid - 1.

3⃣Верните answer.

😎 Решение:

class Solution {
    func fixedPoint(_ arr: [Int]) -> Int {
        var left = 0
        var right = arr.count - 1
        var answer = -1
        
        while left <= right {
            let mid = (left + right) / 2
            
            if arr[mid] == mid {
                answer = mid
                right = mid - 1
            } else if arr[mid] < mid {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        
        return answer
    }
}

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

Задача: 186. Reverse Words in a String II
Сложность: medium

Дан массив символов s, переверните порядок слов.

Слово определяется как последовательность символов, не являющихся пробелами. Слова в s будут разделены одним пробелом.

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

Пример:

Input: s = ["a"]
Output: ["a"]

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

1⃣Перевернуть всю строку: применить функцию reverse, которая переворачивает весь массив символов от начала до конца.

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

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

😎 Решение:

class Solution {
    func reverseWords(_ s: inout [Character]) {
        s.reverse()
        var start = 0
        let n = s.count
        var end = 0

        while start < n {
            while end < n && s[end] != " " {
                end += 1
            }
            s[start..<end].reverse()
            end += 1
            start = end
        }
    }
}

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

Задача: 652. Find Duplicate Subtrees
Сложность: medium

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

Пример:

Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]

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

1⃣Выполните обход дерева и используйте сериализацию для представления каждого поддерева.

2⃣Храните все сериализованные представления поддеревьев в хэш-таблице и отслеживайте частоту их появления.

3⃣Найдите поддеревья, которые появляются более одного раза, и верните корневые узлы этих поддеревьев.

😎 Решение:

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

func findDuplicateSubtrees(_ root: TreeNode?) -> [TreeNode?] {
    var count = [String: Int]()
    var result = [TreeNode?]()
    
    @discardableResult
    func serialize(_ node: TreeNode?) -> String {
        guard let node = node else { return "#" }
        let serial = "\(node.val),\(serialize(node.left)),\(serialize(node.right))"
        count[serial, default: 0] += 1
        if count[serial] == 2 {
            result.append(node)
        }
        return serial
    }
    
    serialize(root)
    return result
}

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

Задача: 941. Valid Mountain Array
Сложность: easy

Задав массив целых чисел arr, верните true тогда и только тогда, когда он является допустимым горным массивом. Напомним, что arr является горным массивом тогда и только тогда, когда: arr.length >= 3 Существует некоторое i с 0 < i < arr.length - 1 такое, что: arr[0] < arr[1] < ... < arr[i - 1] < arr[i] arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Пример:

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

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

1⃣Убедиться, что длина массива не меньше 3.

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

3⃣Вернуть true, если оба условия выполнены, иначе вернуть false.

😎 Решение:

class Solution {
    func validMountainArray(_ arr: [Int]) -> Bool {
        if arr.count < 3 {
            return false
        }
        
        var i = 1
        while i < arr.count && arr[i] > arr[i - 1] {
            i += 1
        }
        
        if i == 1 || i == arr.count {
            return false
        }
        
        while i < arr.count && arr[i] < arr[i - 1] {
            i += 1
        }
        
        return i == arr.count
    }
}

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

Задача: 1103. Distribute Candies to People
Сложность: easy

Мы распределяем некоторое количество конфет ряду из n = num_people человек следующим образом:
Сначала даем 1 конфету первому человеку, 2 конфеты второму человеку и так далее, пока не дадим n конфет последнему человеку.
Затем мы возвращаемся к началу ряда, давая n + 1 конфету первому человеку, n + 2 конфеты второму человеку и так далее, пока не дадим 2 * n конфет последнему человеку.

Этот процесс повторяется (мы каждый раз даем на одну конфету больше и возвращаемся к началу ряда после достижения конца), пока у нас не закончатся конфеты. Последний человек получит все оставшиеся конфеты (не обязательно на одну больше, чем в предыдущий раз).

Верните массив (длиной num_people и суммой candies), который представляет собой окончательное распределение конфет.

Пример:

Input: candies = 7, num_people = 4
Output: [1,2,3,1]
Explanation:
On the first turn, ans[0] += 1, and the array is [1,0,0,0].
On the second turn, ans[1] += 2, and the array is [1,2,0,0].
On the third turn, ans[2] += 3, and the array is [1,2,3,0].
On the fourth turn, ans[3] += 1 (because there is only one candy left), and the final array is [1,2,3,1].

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

1⃣Вычислите количество людей, получивших полные подарки, и оставшиеся конфеты:
p = floor(sqrt(2C+0.25)-0.5)
remainig = C - p(p+1)/2

2⃣Вычислите количество полных циклов и распределите конфеты:
rows = p // n
d[i]= i*rows + n*rows*(rows-1)/2

3⃣Добавьте конфеты за дополнительный неполный цикл и оставшиеся конфеты:
d[i]+=i+n⋅rows для первых p%n людей
d[p%n]+=remaining
Верните распределение конфет d


😎 Решение:

class Solution {
    func distributeCandies(_ candies: Int, _ num_people: Int) -> [Int] {
        let n = num_people
        let p = Int((sqrt(2 * Double(candies) + 0.25) - 0.5))
        let remaining = candies - (p + 1) * p / 2
        let rows = p / n
        let cols = p % n
        
        var d = [Int](repeating: 0, count: n)
        for i in 0..<n {
            d[i] = (i + 1) * rows + (rows * (rows - 1) / 2) * n
            if i < cols {
                d[i] += i + 1 + rows * n
            }
        }
        d[cols] += remaining
        return d
    }
}

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

Задача: 1066. Campus Bikes II
Сложность: medium

На кампусе, представленном в виде двумерной сетки, есть n рабочих и m велосипедов, где n <= m. Каждый рабочий и велосипед имеют координаты на этой сетке.

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

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

Манхэттенское расстояние между двумя точками p1 и p2 вычисляется как Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Пример:

Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]

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

1⃣Для каждого рабочего, начиная с рабочего с индексом 0, пройдите по всем велосипедам и назначьте велосипед рабочему, если он доступен (visited[bikeIndex] = false). После назначения велосипеда отметьте его как недоступный (visited[bikeIndex] = true). Добавьте Манхэттенское расстояние от этого назначения к общей текущей сумме расстояний, представленной currDistanceSum, и выполните рекурсивный вызов для следующего рабочего.

2⃣Когда рекурсивный вызов завершится, сделайте велосипед снова доступным, установив visited[bikeIndex] в false. Если мы назначили велосипеды всем рабочим, сравните currDistanceSum с smallestDistanceSum и обновите smallestDistanceSum соответственно.

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

😎 Решение:

class Solution {
    function indexPairs($text, $words) {
        $wordsSet = array_flip($words);
        $ans = [];
        
        for ($i = 0; $i < strlen($text); $i++) {
            for ($j = $i; $j < strlen($text); $j++) {
                if (isset($wordsSet[substr($text, $i, $j - $i + 1)])) {
                    $ans[] = [$i, $j];
                }
            }
        }
        return $ans;
    }
}

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

Задача: 678. Valid Parenthesis String
Сложность: medium

Создайте карту, которая позволяет выполнять следующие действия:

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

Дана строка s, содержащая только три типа символов: '(', ')' и '*'. Вернуть true, если s является допустимой.

Следующие правила определяют допустимую строку:

Любая открывающая скобка '(' должна иметь соответствующую закрывающую скобку ')'.
Любая закрывающая скобка ')' должна иметь соответствующую открывающую скобку '('.
Открывающая скобка '(' должна идти перед соответствующей закрывающей скобкой ')'.
'*' может рассматриваться как одна закрывающая скобка ')', одна открывающая скобка '(' или пустая строка "".

Пример:

Input: s = "()"
Output: true
Example 2:

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

1⃣Инициализировать 2D вектор memo размером s.size() x s.size() - 1, представляющий неинициализированное состояние. Вызвать вспомогательную функцию isValidString с начальными параметрами index = 0, openCount = 0 и строкой s. Вернуть результат isValidString.

2⃣Вспомогательная функция isValidString. Базовый случай: если index достиг конца строки (index == s.size.), вернуть true, если openCount равен 0 (все скобки сбалансированы), и false в противном случае. Проверить, был ли результат для текущего index и openCount уже вычислен (мемоизирован) в memo. Если да, вернуть мемоизированный результат. Инициализировать isValid как false. Если текущий символ s[index] равен '*': Попробовать трактовать '*' как '(' и вызвать isValidString рекурсивно с index + 1 и openCount + 1. Если рекурсивный вызов вернет true, обновить isValid на true. Если openCount не равен нулю, попробовать трактовать '*' как ')' и вызвать isValidString рекурсивно с index + 1 и openCount - 1. Если рекурсивный вызов вернет true, обновить isValid на true. Попробовать трактовать '*' как пустой символ и вызвать isValidString рекурсивно с index + 1 и тем же openCount. Если рекурсивный вызов вернет true, обновить isValid на true.

3⃣Продолжение функции isValidString. Если текущий символ s[index] равен '(': Вызвать isValidString рекурсивно с index + 1 и openCount + 1. Обновить isValid с результатом рекурсивного вызова. Если текущий символ s[index] равен ')': Если openCount не равен нулю (есть открытые скобки), вызвать isValidString рекурсивно с index + 1 и openCount - 1. Обновить isValid с результатом рекурсивного вызова. Мемоизировать результат isValid в memo[index][openCount]. Вернуть isValid.

😎 Решение:

class Solution {
    func checkValidString(_ s: String) -> Bool {
        var memo = Array(repeating: Array(repeating: -1, count: s.count), count: s.count)
        return isValidString(0, 0, s, &memo)
    }
    
    private func isValidString(_ index: Int, _ openCount: Int, _ str: String, _ memo: inout [[Int]]) -> Bool {
        if index == str.count {
            return openCount == 0
        }
        
        if memo[index][openCount] != -1 {
            return memo[index][openCount] == 1
        }
        
        var isValid = false
        let currentIndex = str.index(str.startIndex, offsetBy: index)
        
        if str[currentIndex] == "*" {
            isValid = isValidString(index + 1, openCount + 1, str, &memo)
            if openCount > 0 {
                isValid = isValid || isValidString(index + 1, openCount - 1, str, &memo)
            }
            isValid = isValid || isValidString(index + 1, openCount, str, &memo)
        } else if str[currentIndex] == "(" {
            isValid = isValidString(index + 1, openCount + 1, str, &memo)
        } else if openCount > 0 {
            isValid = isValidString(index + 1, openCount - 1, str, &memo)
        }
        
        memo[index][openCount] = isValid ? 1 : 0
        return isValid
    }
}

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

Задача: 1133. Largest Unique Number
Сложность: easy

Вам Дан целочисленный массив nums, верните наибольшее целое число, которое встречается только один раз. Если ни одно целое число не встречается один раз, верните -1.

Пример:

Input: nums = [5,7,3,9,4,9,8,3,1]
Output: 8
Explanation: The maximum integer in the array is 9 but it is repeated. The number 8 occurs only once, so it is the answer.

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

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

2⃣Пройдите по массиву и заполните хеш-таблицу количеством каждого числа.

3⃣Инициализируйте результат значением -1. Пройдите по хеш-таблице и если значение ключа равно 1, установите результат равным максимальному значению между ключом и текущим результатом. Верните результат.

😎 Решение:

class Solution {
    func largestUniqueNumber(_ nums: [Int]) -> Int {
        var count = [Int: Int]()
        
        for num in nums {
            count[num, default: 0] += 1
        }
        
        var result = -1
        for (key, value) in count {
            if value == 1 {
                result = max(result, key)
            }
        }
        
        return result
    }
}

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

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

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

Задача: 1357. Apply Discount Every n Orders
Сложность: medium

В супермаркете, который посещает множество покупателей, товары представлены двумя параллельными массивами целых чисел products и prices, где i-й товар имеет идентификатор products[i] и цену prices[i].

Когда покупатель оплачивает товар, его счет представлен двумя параллельными массивами целых чисел product и amount, где j-й приобретенный товар имеет идентификатор product[j], а amount[j] - количество купленного товара. Их промежуточный итог рассчитывается как сумма каждого amount[j] * (цена j-го товара).

Супермаркет решил провести распродажу. Каждому n-му покупателю, оплачивающему свои покупки, будет предоставлена скидка в процентах. Сумма скидки задается параметром discount, и покупатель получит скидку в discount процентов от своего промежуточного итога. Формально, если их промежуточный итог составляет bill, то они фактически заплатят bill * ((100 - discount) / 100).

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

Cashier(int n, int discount, int[] products, int[] prices): инициализирует объект с параметрами n, discount, а также массивами товаров и их цен.
double getBill(int[] product, int[] amount): возвращает итоговую сумму счета с примененной скидкой (если применима). Ответы, отличающиеся от фактического значения не более чем на 10^-5, будут приняты.

Пример:

Input
["Cashier","getBill","getBill","getBill","getBill","getBill","getBill","getBill"]
[[3,50,[1,2,3,4,5,6,7],[100,200,300,400,300,200,100]],[[1,2],[1,2]],[[3,7],[10,10]],[[1,2,3,4,5,6,7],[1,1,1,1,1,1,1]],[[4],[10]],[[7,3],[10,10]],[[7,5,3,1,6,4,2],[10,10,10,9,9,9,7]],[[2,3,5],[5,3,2]]]
Output
[null,500.0,4000.0,800.0,4000.0,4000.0,7350.0,2500.0]

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

1⃣Инициализация объекта:
Создайте класс Cashier с конструктором, который принимает параметры n, discount, products и prices. В конструкторе инициализируйте необходимые переменные и создайте словарь для сопоставления идентификаторов продуктов с их ценами.

2⃣Обработка каждого счета:
Создайте метод getBill, который принимает массивы product и amount.
Вычислите промежуточный итог счета, умножая количество каждого продукта на его цену и суммируя результаты.
Увеличьте счетчик клиентов. Если клиент является n-м по счету, примените скидку к промежуточному итогу.

3⃣Верните итоговую сумму счета.

😎 Решение:

class Cashier {
    private let n: Int
    private let discount: Int
    private var productsPrices: [Int: Int]
    private var customerCount: Int

    init(_ n: Int, _ discount: Int, _ products: [Int], _ prices: [Int]) {
        self.n = n
        self.discount = discount
        self.customerCount = 0
        self.productsPrices = Dictionary(uniqueKeysWithValues: zip(products, prices))
    }

    func getBill(_ product: [Int], _ amount: [Int]) -> Double {
        customerCount += 1
        var bill = 0.0

        for (index, prod) in product.enumerated() {
            bill += Double(productsPrices[prod]! * amount[index])
        }

        if customerCount % n == 0 {
            bill *= Double(100 - discount) / 100.0
        }

        return bill
    }
}

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