Задача: 592. Fraction Addition and Subtraction
Сложность: medium

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

Окончательный результат должен быть несократимой дробью. Если ваш окончательный результат является целым числом, преобразуйте его в формат дроби с знаменателем 1. Таким образом, 2 должно быть преобразовано в 2/1.

Пример:

Input: expression = "-1/2+1/2+1/3"
Output: "1/3"

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

1⃣Начните сканирование строки и разделите её на части, содержащие числители и знаменатели, с учетом знаков.

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

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

😎 Решение:

class Solution {
    func fractionAddition(_ expression: String) -> String {
        var sign = [Character]()
        if expression.first != "-" {
            sign.append("+")
        }
        for char in expression {
            if char == "+" || char == "-" {
                sign.append(char)
            }
        }
        
        var prevNum = 0, prevDen = 1
        var i = 0
        let fractions = expression.split { $0 == "+" || $0 == "-" }
        for sub in fractions {
            if sub.isEmpty { continue }
            let fraction = sub.split(separator: "/").map { Int($0)! }
            let num = fraction[0]
            let den = fraction[1]
            let g = gcd(prevDen, den)
            if sign[i] == "+" {
                prevNum = prevNum * den / g + num * prevDen / g
            } else {
                prevNum = prevNum * den / g - num * prevDen / g
            }
            prevDen = prevDen * den / g
            let gcdValue = gcd(abs(prevNum), prevDen)
            prevNum /= gcdValue
            prevDen /= gcdValue
            i += 1
        }
        
        return "\(prevNum)/\(prevDen)"
    }
    
    private func gcd(_ a: Int, _ b: Int) -> Int {
        return b == 0 ? a : gcd(b, a % b)
    }
}

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

Задача: 478. Generate Random Point in a Circle
Сложность: medium

Дан радиус и положение центра окружности, реализуйте функцию randPoint, которая генерирует равномерно случайную точку внутри окружности.

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

- Solution(double radius, double x_center, double y_center) инициализирует объект с радиусом окружности radius и положением центра (x_center, y_center).
- randPoint() возвращает случайную точку внутри окружности. Точка на окружности считается находящейся внутри окружности. Ответ возвращается в виде массива [x, y].

Пример:

Input
["Solution", "randPoint", "randPoint", "randPoint"]
[[1.0, 0.0, 0.0], [], [], []]
Output
[null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]]

Explanation
Solution solution = new Solution(1.0, 0.0, 0.0);
solution.randPoint(); // return [-0.02493, -0.38077]
solution.randPoint(); // return [0.82314, 0.38945]
solution.randPoint(); // return [0.36572, 0.17248]

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

1⃣ Генерируем равномерно случайные точки в квадрате S с длиной стороны 2R.

2⃣ Сохраняем все точки, которые находятся на расстоянии не более R от центра, и отклоняем все, которые дальше этого расстояния.

3⃣ Повторяем процесс до получения нужного количества точек, учитывая, что примерно 78.5% от всех сгенерированных точек будут приемлемыми, и ожидаемое число попыток до получения приемлемой точки составляет примерно 1.274 раза.

😎 Решение:

import Foundation

class Solution {
    var rad: Double
    var xc: Double
    var yc: Double

    init(_ radius: Double, _ x_center: Double, _ y_center: Double) {
        rad = radius
        xc = x_center
        yc = y_center
    }

    func randPoint() -> [Double] {
        let x0 = xc - rad
        let y0 = yc - rad

        while true {
            let xg = x0 + Double.random(in: 0...(rad * 2))
            let yg = y0 + Double.random(in: 0...(rad * 2))
            if sqrt(pow(xg - xc, 2) + pow(yg - yc, 2)) <= rad {
                return [xg, yg]
            }
        }
    }
}

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

Задача: 273. Integer to English Words
Сложность: hard

Преобразуйте неотрицательное целое число num в его словесное представление на английском языке.

Пример:

Input: num = 123
Output: "One Hundred Twenty Three"

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

1⃣Обработка чисел до 20 и кратных 10 до 90:
Создать массивы или словари для чисел от 1 до 19 и для кратных 10 от 20 до 90.
Если число попадает в эти диапазоны, сразу вернуть соответствующее словесное представление.

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

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

😎 Решение:

class Solution {
    private let belowTwenty = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"]
    private let tens = ["", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]
    private let thousands = ["", "Thousand", "Million", "Billion"]
    
    func numberToWords(_ num: Int) -> String {
        if num == 0 { return "Zero" }
        var num = num
        var result = ""
        var i = 0
        
        while num > 0 {
            if num % 1000 != 0 {
                result = helper(num % 1000) + thousands[i] + " " + result
            }
            num /= 1000
            i += 1
        }
        return result.trimmingCharacters(in: .whitespaces)
    }
    
    private func helper(_ num: Int) -> String {
        if num == 0 { return "" }
        else if num < 20 { return belowTwenty[num] + " " }
        else if num < 100 { return tens[num / 10] + " " + helper(num % 10) }
        else { return belowTwenty[num / 100] + " Hundred " + helper(num % 100) }
    }
}

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

Задача: 1086. High Five
Сложность: easy

Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента.

Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания.

Среднее значение пяти лучших оценок студента вычисляется путем сложения его пяти лучших оценок и деления на 5 с использованием целочисленного деления.

Пример:

Input: items = [[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100]]
Output: [[1,100],[7,100]]

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

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

2⃣Создайте список для хранения результата result. Переберите словарь и для каждого студента отсортируйте его оценки в порядке убывания, возьмите пять лучших оценок, вычислите их среднее значение (с целочисленным делением на 5) и добавьте пару [ID, topFiveAverage] в результат.

3⃣Отсортируйте список result по возрастанию ID студента и верните его.

😎 Решение:

class Solution {
    func highFive(_ items: [[Int]]) -> [[Int]] {
        let K = 5
        let sortedItems = items.sorted { 
            if $0[0] != $1[0] { 
                return $0[0] < $1[0]
            }
            return $0[1] > $1[1]
        }
        
        var solution = [[Int]]()
        var i = 0
        while i < sortedItems.count {
            let id = sortedItems[i][0]
            var sum = 0
            for k in i..<i+K {
                sum += sortedItems[k][1]
            }
            while i < sortedItems.count && sortedItems[i][0] == id {
                i += 1
            }
            solution.append([id, sum / K])
        }
        return solution
    }
}

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

Задача: 771. Jewels and Stones
Сложность: medium

Вам даны строки jewels, представляющие типы камней, которые являются драгоценностями, и stones, представляющие камни, которые у вас есть. Каждый символ в stones является типом камня, который у вас есть. Вы хотите узнать, сколько из камней, которые у вас есть, также являются драгоценностями.

Буквы чувствительны к регистру, поэтому "a" считается другим типом камня, чем "A".

Пример:

Input: jewels = "aA", stones = "aAAbbbb"
Output: 3

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

1⃣Создайте множество из строки jewels для быстрой проверки, является ли камень драгоценностью. Это позволит эффективно проверять принадлежность каждого камня к драгоценностям.

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

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

😎 Решение:

class Solution {
    func numJewelsInStones(_ J: String, _ S: String) -> Int {
        var ans = 0
        for s in S {
            for j in J {
                if j == s {
                    ans += 1
                    break
                }
            }
        }
        return ans
    }
}

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

Задача: 272. Closest Binary Search Tree Value II
Сложность: hard

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

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

Пример:

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

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

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

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

3⃣Вернуть первые k значений из отсортированного массива:
Извлечь первые k элементов из отсортированного массива и вернуть их.

😎 Решение:

class Solution {
    func closestKValues(_ root: TreeNode?, _ target: Double, _ k: Int) -> [Int] {
        var arr = [Int]()
        dfs(root, &arr)
        arr.sort { abs(Double($0) - target) < abs(Double($1) - target) }
        return Array(arr.prefix(k))
    }
    
    private func dfs(_ node: TreeNode?, _ arr: inout [Int]) {
        guard let node = node else { return }
        arr.append(node.val)
        dfs(node.left, &arr)
        dfs(node.right, &arr)
    }
}

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

Задача: 609. Find Duplicate File in System
Сложность: medium

Получив список paths информации о каталоге, включающий путь к каталогу и все файлы с содержимым в этом каталоге, верните все дубликаты файлов в файловой системе по их путям. Вы можете вернуть ответ в любом порядке. Группа дубликатов состоит как минимум из двух файлов с одинаковым содержимым. Одна строка информации о каталоге во входном списке имеет следующий формат: "root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)" Это означает, что в каталоге "root/d1/d2/.../dm" имеется n файлов (f1.txt, f2.txt ... fn.txt) с содержимым (f1_content, f2_content ... fn_content) соответственно. Обратите внимание, что n >= 1 и m >= 0. Если m = 0, это означает, что каталог является только корневым. На выходе получается список групп дублирующихся путей к файлам. Для каждой группы он содержит все пути к файлам, которые имеют одинаковое содержимое. Путь к файлу - это строка, имеющая следующий формат: "каталог_путь/имя_файла.txt".

Пример:

Input: paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)","root 4.txt(efgh)"]
Output: [["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]

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

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

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

3⃣Пройдите по словарю и соберите группы дубликатов, содержащие как минимум два пути.

😎 Решение:

func findDuplicate(_ paths: [String]) -> [[String]] {
    var contentToFilePaths = [String: [String]]()
    
    for path in paths {
        let parts = path.split(separator: " ")
        let root = parts[0]
        
        for i in 1..<parts.count {
            let fileParts = parts[i].split(separator: "(")
            let fileName = String(fileParts[0])
            let content = String(fileParts[1].dropLast())
            
            let filePath = "\(root)/\(fileName)"
            contentToFilePaths[content, default: []].append(filePath)
        }
    }
    
    return contentToFilePaths.values.filter { $0.count > 1 }
}

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

Задача: 255. Verify Preorder Sequence in Binary Search Tree
Сложность: medium

Дан массив уникальных целых чисел preorder. Верните true, если это правильная последовательность обхода в порядке предварительного (preorder) обхода для бинарного дерева поиска.

Пример:

Input: preorder = [5,2,1,3,6]
Output: true

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

1⃣Объявите целое число minLimit с маленьким значением, например, минус бесконечность, и стек.

2⃣Итерируйте по массиву preorder. Для каждого num:
Очистите стек. Пока верх стека меньше num, извлекайте из стека и обновляйте minLimit.
Если num <= minLimit, верните false.
Добавьте num в стек.

3⃣Верните true, если удалось пройти весь массив.

😎 Решение:

class Solution {
    func verifyPreorder(_ preorder: [Int]) -> Bool {
        var minLimit = Int.min
        var stack: [Int] = []
        
        for num in preorder {
            while !stack.isEmpty && stack.last! < num {
                minLimit = stack.removeLast()
            }
            
            if num <= minLimit {
                return false
            }
            
            stack.append(num)
        }
        
        return true
    }
}

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

Задача: 673. Number of Longest Increasing Subsequence
Сложность: medium

Дан массив целых чисел nums, верните количество самых длинных строго возрастающих подпоследовательностей.

Пример:

Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2

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

1⃣Объявите два массива динамического программирования length и count, и инициализируйте их значениями length[i]=1 и count[i]=1. Итерируйте i от 0 до n−1. Для каждого i итерируйте j от 0 до i−1 и, если nums[j] < nums[i], обновите length[i] и count[i] в зависимости от значений length[j] и count[j].

2⃣Найдите максимальное значение в массиве length и сохраните его в переменной maxLength. Инициализируйте переменную result = 0.

3⃣Итерируйте i от 0 до n−1 и, если length[i] = maxLength, добавьте count[i] к result. Верните result.

😎 Решение:

class Solution {
    func findNumberOfLIS(_ nums: [Int]) -> Int {
        let n = nums.count
        var length = Array(repeating: 1, count: n)
        var count = Array(repeating: 1, count: n)
        
        for i in 0..<n {
            for j in 0..<i {
                if nums[j] < nums[i] {
                    if length[j] + 1 > length[i] {
                        length[i] = length[j] + 1
                        count[i] = 0
                    }
                    if length[j] + 1 == length[i] {
                        count[i] += count[j]
                    }
                }
            }
        }
        
        let maxLength = length.max() ?? 0
        var result = 0
        
        for i in 0..<n {
            if length[i] == maxLength {
                result += count[i]
            }
        }
        
        return result
    }
}

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

Задача: 1347. Minimum Number of Steps to Make Two Strings Anagram
Сложность: medium

Даны две строки одинаковой длины s и t. За один шаг вы можете выбрать любой символ строки t и заменить его другим символом.

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

Анаграмма строки — это строка, которая содержит те же символы в другом (или том же) порядке.

Пример:

Input: s = "bab", t = "aba"
Output: 1
Explanation: Replace the first 'a' in t with b, t = "bba" which is anagram of s.

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

1⃣Вычислить разницу частот символов в строках t и s, сохраняя результаты в массиве count.

2⃣Подсчитать количество символов, которые нужно заменить в t, добавляя в ans только положительные значения из массива count.

3⃣Вернуть ans как минимальное количество шагов для превращения t в анаграмму строки s.

😎 Решение:

class Solution {
    func minSteps(_ s: String, _ t: String) -> Int {
        var count = [Int](repeating: 0, count: 26)
        
        for i in s.indices {
            count[Int(t[i].asciiValue! - Character("a").asciiValue!)] += 1
            count[Int(s[i].asciiValue! - Character("a").asciiValue!)] -= 1
        }

        var ans = 0
        for i in 0..<26 {
            ans += max(0, count[i])
        }

        return ans
    }
}

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

Задача: 536. Construct Binary Tree from String
Сложность: medium

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

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

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

Пример:

Input: s = "4(2(3)(1))(6(5))"
Output: [4,2,6,3,1,5]

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

1⃣ Извлечение числа:
Определите функцию getNumber, которая извлекает целое число из текущей строки, начиная с указанного индекса. Учтите знак числа, если он есть.

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

3⃣ Основная функция:
Определите основную функцию str2tree, которая вызывает рекурсивную функцию str2treeInternal и возвращает построенное дерево.

😎 Решение:

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 {
    func str2tree(_ s: String) -> TreeNode? {
        return str2treeInternal(Array(s), 0).node
    }
    
    func getNumber(_ s: [Character], _ index: Int) -> (value: Int, index: Int) {
        var idx = index
        var isNegative = false
        if s[idx] == "-" {
            isNegative = true
            idx += 1
        }
        var number = 0
        while idx < s.count, let digit = s[idx].wholeNumberValue {
            number = number * 10 + digit
            idx += 1
        }
        return (isNegative ? -number : number, idx)
    }
    
    func str2treeInternal(_ s: [Character], _ index: Int) -> (node: TreeNode?, nextIndex: Int) {
        if index >= s.count {
            return (nil, index)
        }
        
        let numberData = getNumber(s, index)
        let value = numberData.value
        var idx = numberData.index
        
        let node = TreeNode(value)
        
        if idx < s.count && s[idx] == "(" {
            let leftData = str2treeInternal(s, idx + 1)
            node.left = leftData.node
            idx = leftData.nextIndex
        }
        
        if idx < s.count && s[idx] == "(" {
            let rightData = str2treeInternal(s, idx + 1)
            node.right = rightData.node
            idx = rightData.nextIndex
        }
        
        return (node, idx < s.count && s[idx] == ")" ? idx + 1 : idx)
    }
}

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

Задача: 554. Brick Wall
Сложность: medium

Перед вами находится прямоугольная кирпичная стена с n рядами кирпичей. В i-м ряду находится несколько кирпичей одинаковой высоты (то есть один юнит), но они могут быть разной ширины. Общая ширина каждого ряда одинакова.

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

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

Пример:

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

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

1⃣Определите общую ширину стены, сложив ширины кирпичей в первом ряду. Создайте массив pos, где pos[i] указывает на текущую позицию в i-ом ряду.

2⃣Пройдите по каждой возможной позиции для вертикальной линии (от 1 до общей ширины стены - 1). Для каждой позиции обновите массив pos, проверяя, пересекает ли линия границу кирпича. Если пересекает, увеличьте значение pos[i].

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

😎 Решение:

class Solution {
    func leastBricks(_ wall: [[Int]]) -> Int {
        var pos = [Int](repeating: 0, count: wall.count)
        var res = Int.max
        var sum = wall[0].reduce(0, +)
        
        while sum != 0 {
            var count = 0
            for i in 0..<wall.count {
                if wall[i][pos[i]] != 0 {
                    count += 1
                } else {
                    pos[i] += 1
                }
                wall[i][pos[i]] -= 1
            }
            sum -= 1
            res = min(res, count)
        }
        
        return res
    }
}

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

Задача: 1245. Tree Diameter
Сложность: medium

Диаметр дерева - это количество ребер в самом длинном пути в этом дереве. Имеется неориентированное дерево из n узлов, помеченных от 0 до n - 1. Вам дан двумерный массив edges, где edges.length == n - 1 и edges[i] = [ai, bi] означает, что между узлами ai и bi в дереве есть неориентированное ребро. Верните диаметр дерева.

Пример:

Input: edges = [[0,1],[0,2]]
Output: 2

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

1⃣Построение графа:
Используем представление графа в виде списка смежности.

2⃣Поиск самой удаленной вершины (DFS1):
Запускаем DFS от произвольной вершины (например, 0) для нахождения самой удаленной вершины от нее.

3⃣Поиск диаметра (DFS2):
Запускаем DFS от найденной на предыдущем шаге самой удаленной вершины и находим самую удаленную вершину от нее. Это расстояние и будет диаметром дерева.reset(playerId):
Устанавливаем счет игрока в 0.

😎 Решение:

class Solution {
    func treeDiameter(_ edges: [[Int]]) -> Int {
        if edges.isEmpty { return 0 }

        var graph = [Int: [Int]]()
        for edge in edges {
            graph[edge[0], default: []].append(edge[1])
            graph[edge[1], default: []].append(edge[0])
        }

        var farthestNode = 0

        func dfs(_ node: Int, _ parent: Int) -> Int {
            var maxDepth = 0
            for neighbor in graph[node]! {
                if neighbor != parent {
                    let depth = dfs(neighbor, node)
                    if depth + 1 > maxDepth {
                        maxDepth = depth + 1
                        farthestNode = neighbor
                    }
                }
            }
            return maxDepth
        }

        _ = dfs(0, -1)
        let startNode = farthestNode

        _ = dfs(startNode, -1)
        return dfs(farthestNode, -1)
    }
}

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

Задача: 848. Shifting Letters
Сложность: medium

Вам дана строка s из строчных букв английского алфавита и целочисленный массив shifts такой же длины.

Назовем shift() буквы следующей буквой в алфавите (с переходом так, что 'z' становится 'a').
Например, shift('a') = 'b', shift('t') = 'u', и shift('z') = 'a'.
Теперь для каждого shifts[i] = x мы хотим сдвинуть первые i + 1 букв строки s на x раз.

Верните итоговую строку после применения всех таких сдвигов к s.

Пример:

Input: s = "abc", shifts = [3,5,9]
Output: "rpl"
Explanation: We start with "abc".
After shifting the first 1 letters of s by 3, we have "dbc".
After shifting the first 2 letters of s by 5, we have "igc".
After shifting the first 3 letters of s by 9, we have "rpl", the answer.

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

1⃣Вычислите общее количество сдвигов для всех символов строки, используя массив shifts.

2⃣Пройдите по строке s и примените вычисленные сдвиги к каждому символу, начиная с первого и уменьшая количество сдвигов на текущем шаге.

3⃣Постройте и верните итоговую строку после всех сдвигов.

😎 Решение:

class Solution {
    func shiftingLetters(_ s: String, _ shifts: [Int]) -> String {
        var sArray = Array(s)
        var totalShifts = shifts.reduce(0, { ($0 + $1) % 26 })
        
        for i in 0..<sArray.count {
            let newCharValue = Int(sArray[i].asciiValue!) - 97 + totalShifts
            sArray[i] = Character(UnicodeScalar((newCharValue % 26 + 97))!)
            totalShifts = (totalShifts - shifts[i]) % 26
        }
        
        return String(sArray)
    }
}

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

Задача: 1360. Number of Days Between Two Dates
Сложность: easy

Напишите программу для подсчета количества дней между двумя датами.

Даты даны в виде строк в формате YYYY-MM-DD, как показано в примерах.

Пример:

Input: date1 = "2019-06-29", date2 = "2019-06-30"
Output: 1

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

1⃣Преобразование строк в даты:
Используйте встроенные функции для преобразования строковых представлений дат в объекты дат.

2⃣Вычисление разницы в днях:
Вычислите разницу между двумя объектами дат в днях.

3⃣Возвращение результата:
Верните абсолютное значение разницы в днях для получения положительного числа.

😎 Решение:

import Foundation

class Solution {
    func daysBetweenDates(_ date1: String, _ date2: String) -> Int {
        let dateFormatter = DateFormatter()
        dateFormatter.dateFormat = "yyyy-MM-dd"
        let d1 = dateFormatter.date(from: date1)!
        let d2 = dateFormatter.date(from: date2)!
        return abs(Calendar.current.dateComponents([.day], from: d1, to: d2).day!)
    }
}

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

Задача: 347. Top K Frequent Elements
Сложность: medium

Дан массив целых чисел nums и целое число k. Верните k самых частых элементов. Вы можете вернуть ответ в любом порядке.

Пример:

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

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

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

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

3⃣Возврат результата:
Верните k самых частых элементов.

😎 Решение:

class Solution {
    func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
        let count = Dictionary(nums.map { ($0, 1) }, uniquingKeysWith: +)
        return Array(count.keys.sorted(by: { count[$0]! > count[$1]! }).prefix(k))
    }
}

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

Задача: 621. Task Scheduler
Сложность: medium

Вам дан массив задач процессора, каждая из которых представлена буквами от A до Z, и время охлаждения, n. Каждый цикл или интервал позволяет завершить одну задачу. Задачи могут быть выполнены в любом порядке, но есть ограничение: одинаковые задачи должны быть разделены не менее чем n интервалами из-за времени охлаждения. Верните минимальное количество интервалов, необходимое для выполнения всех задач.

Пример:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8

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

1⃣Подсчитайте количество каждой задачи и найдите максимальное количество вхождений (maxFreq).

2⃣Вычислите количество интервалов, необходимых для задач с maxFreq: (maxFreq - 1) * (n + 1) + countMaxFreq, где countMaxFreq - количество задач, имеющих maxFreq.

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

😎 Решение:

func leastInterval(_ tasks: [Character], _ n: Int) -> Int {
    var taskCounts = [Character: Int]()
    for task in tasks {
        taskCounts[task, default: 0] += 1
    }
    
    let maxFreq = taskCounts.values.max()!
    let countMaxFreq = taskCounts.values.filter { $0 == maxFreq }.count
    
    return max(tasks.count, (maxFreq - 1) * (n + 1) + countMaxFreq)
}

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

Задача: 1325. Delete Leaves With a Given Value
Сложность: medium

Дано корневое дерево root и целое число target. Удалите все листовые узлы со значением target.

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

Пример:

Input: root = [1,2,3,2,null,2,4], target = 2
Output: [1,null,3,null,4]
Explanation: Leaf nodes in green with value (target = 2) are removed (Picture in left). 
After removing, new nodes become leaf nodes with value (target = 2) (Picture in center).

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

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

2⃣Рекурсивный обход: Выполните обход в постфиксном порядке, чтобы гарантировать обработку всех потомков перед текущим узлом (root):
— Рекурсивно вызовите removeLeafNodes для левого дочернего узла root и обновите левый дочерний узел возвращаемым значением.
— Аналогично, рекурсивно вызовите removeLeafNodes для правого дочернего узла root и обновите правый дочерний узел возвращаемым значением.

3⃣Оценка узла:
— Проверьте, является ли текущий узел root листовым узлом и совпадает ли его значение с target. Если оба условия выполнены, верните null, чтобы эффективно удалить узел, не присоединяя его к родителю.
— Если узел не является листом или не совпадает с target, верните сам root.

😎 Решение

class Solution {
    func removeLeafNodes(_ root: TreeNode?, _ target: Int) -> TreeNode? {
        guard let root = root else { return nil }

        root.left = removeLeafNodes(root.left, target)
        root.right = removeLeafNodes(root.right, target)

        if root.left == nil && root.right == nil && root.val == target {
            return nil
        }

        return root
    }
}

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

Задача: 674. Longest Continuous Increasing Subsequence
Сложность: easy

Дан неотсортированный массив целых чисел nums, верните длину самой длинной непрерывной возрастающей подпоследовательности (т.е. подмассива). Подпоследовательность должна быть строго возрастающей.

Непрерывная возрастающая подпоследовательность определяется двумя индексами l и r (l < r) так, что она имеет вид [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] и для каждого l <= i < r выполняется nums[i] < nums[i + 1].

Пример:

Input: nums = [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3.
Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element
4.

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

1⃣Каждая (непрерывная) возрастающая подпоследовательность не пересекается, и граница каждой такой подпоследовательности возникает, когда nums[i-1] >= nums[i]. В этом случае начинается новая возрастающая подпоследовательность с nums[i], и мы сохраняем такой i в переменной anchor.

2⃣Например, если nums = [7, 8, 9, 1, 2, 3], то anchor начинается с 0 (nums[anchor] = 7) и затем устанавливается на anchor = 3 (nums[anchor] = 1). Независимо от значения anchor, мы записываем кандидата на ответ длиной i - anchor + 1, длина подмассива nums[anchor], nums[anchor+1], ..., nums[i], и наш ответ обновляется соответствующим образом.

3⃣Возвращаем максимальную длину найденной непрерывной возрастающей подпоследовательности.

😎 Решение:

class Solution {
    func findLengthOfLCIS(_ nums: [Int]) -> Int {
        var ans = 0, anchor = 0
        for i in 0..<nums.count {
            if i > 0 && nums[i - 1] >= nums[i] {
                anchor = i
            }
            ans = max(ans, i - anchor + 1)
        }
        return ans
    }
}

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

Задача: 1370. Increasing Decreasing String
Сложность: easy

Дана строка s. Переставьте символы строки, используя следующий алгоритм:

Выберите наименьший символ из s и добавьте его к результату.
Выберите наименьший символ из s, который больше последнего добавленного символа, и добавьте его.
Повторяйте шаг 2, пока не сможете выбрать больше символов.
Выберите наибольший символ из s и добавьте его к результату.
Выберите наибольший символ из s, который меньше последнего добавленного символа, и добавьте его.
Повторяйте шаг 5, пока не сможете выбрать больше символов.
Повторяйте шаги с 1 по 6, пока не выберете все символы из s.
На каждом этапе, если наименьший или наибольший символ появляется более одного раза, вы можете выбрать любое его вхождение и добавить его к результату.

Верните результирующую строку после сортировки s с помощью этого алгоритма.

Пример:

Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

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

1⃣Инициализация и сортировка:
Создайте словарь для подсчета количества каждого символа в строке s. Создайте результирующую строку result.

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

3⃣Проверка завершения:
Повторяйте шаги 2 и 3, пока не будут добавлены все символы из строки s в result.

😎 Решение:

class Solution {
    func sortString(_ s: String) -> String {
        var charCount = [Character: Int]()
        for char in s {
            charCount[char, default: 0] += 1
        }
        
        var result = ""
        while result.count < s.count {
            for char in "abcdefghijklmnopqrstuvwxyz" {
                if let count = charCount[char], count > 0 {
                    result.append(char)
                    charCount[char]! -= 1
                }
            }
            for char in "zyxwvutsrqponmlkjihgfedcba" {
                if let count = charCount[char], count > 0 {
                    result.append(char)
                    charCount[char]! -= 1
                }
            }
        }
        
        return result
    }
}

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