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

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

Задача: 1052. Grumpy Bookstore Owner
Сложность: medium

Есть владелец книжного магазина, магазин которого открыт в течение n минут. Каждую минуту в магазин заходит некоторое количество покупателей. Вам дан целочисленный массив customers длины n, где customers[i] - это номер покупателя, который заходит в магазин в начале i-й минуты, а все покупатели выходят после окончания этой минуты. В некоторые минуты владелец книжного магазина ворчлив. Вам дан двоичный массив grumpy, в котором grumpy[i] равен 1, если владелец книжного магазина ворчлив в течение i-й минуты, и равен 0 в противном случае. Когда владелец книжного магазина ворчлив, покупатели в эту минуту не удовлетворены, в противном случае они удовлетворены. Владелец книжного магазина знает секретную технику, чтобы не ворчать в течение нескольких минут подряд, но может использовать ее только один раз. Верните максимальное количество покупателей, которое может быть удовлетворено в течение дня.

Пример:

Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
Output: 16

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

1⃣Определи общее количество покупателей, которые удовлетворены в минуты, когда владелец магазина не ворчлив.

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

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

😎 Решение:

func maxSatisfied(_ customers: [Int], _ grumpy: [Int], _ minutes: Int) -> Int {
    var totalSatisfied = 0
    var additionalSatisfied = 0
    var maxAdditionalSatisfied = 0
    
    for i in 0..<customers.count {
        if grumpy[i] == 0 {
            totalSatisfied += customers[i]
        } else {
            additionalSatisfied += customers[i]
        }
        
        if i >= minutes {
            if grumpy[i - minutes] == 1 {
                additionalSatisfied -= customers[i - minutes]
            }
        }
        
        maxAdditionalSatisfied = max(maxAdditionalSatisfied, additionalSatisfied)
    }
    
    return totalSatisfied + maxAdditionalSatisfied
}

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

Задача: 343. Integer Break
Сложность: medium

Дано целое число n. Верните true, если оно является степенью числа четыре. В противном случае верните false.

Целое число n является степенью числа четыре, если существует целое число x такое, что n == 4^x.

Пример:

Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

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

1⃣Инициализация и базовый случай:
Создайте массив dp длиной n + 1, где dp[i] будет хранить максимальное произведение для числа i. Инициализируйте массив нулями.

2⃣Вычисление максимального произведения:
Для каждого числа i от 2 до n:
Для каждого числа j от 1 до i // 2:
Обновите dp[i] как максимальное значение между текущим dp[i], произведением j и i - j, и произведением j и dp[i - j].

3⃣Возврат результата:
Верните значение dp[n], которое будет максимальным произведением для числа n.

😎 Решение:

class Solution {
    func integerBreak(_ n: Int) -> Int {
        if n <= 1 {
            return 0
        }
        
        var dp = Array(repeating: 0, count: n + 1)
        
        for i in 2...n {
            for j in 1...(i / 2) {
                dp[i] = max(dp[i],

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

Задача: 1060. Missing Element in Sorted Array
Сложность: medium

Если задан целочисленный массив nums, который отсортирован по возрастанию и все его элементы уникальны, а также задано целое число k, верните k-е недостающее число, начиная с самого левого номера массива.

Пример:

Input: nums = [4,7,9,10], k = 1
Output: 5

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

1⃣Инициализация переменных:
Задать счетчик недостающих чисел и текущее значение, которое будет проверяться на отсутствие в массиве.
Установить указатель для обхода массива.

2⃣Поиск недостающих чисел:
Проходить по массиву, начиная с первого числа, и для каждого значения проверять, является ли текущее значение недостающим.
Увеличивать счетчик недостающих чисел, если текущее значение отсутствует в массиве.
Продолжать проверку до тех пор, пока не будет найдено k-е недостающее число.

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

😎 Решение:

func findKthMissing(_ nums: [Int], _ k: Int) -> Int {
    var missingCount = 0
    var current = nums[0]
    var index = 0
    
    while true {
        if index < nums.count && nums[index] == current {
            index += 1
        } else {
            missingCount += 1
            if missingCount == k {
                return current
            }
        }
        current += 1
    }
}

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

Задача: 1323. Maximum 69 Number
Сложность: easy

Дано положительное целое число num, состоящее только из цифр 6 и 9.

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

Пример:

Input: num = 9669
Output: 9969
Explanation: 
Changing the first digit results in 6669.
Changing the second digit results in 9969.
Changing the third digit results in 9699.
Changing the fourth digit results in 9666.
The maximum number is 9969.

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

1⃣Преобразуйте входное целое число num в итерируемый и изменяемый объект num_obj.

2⃣Пройдитесь по num_obj и, если найдете цифру 6, замените её на 9 и прекратите итерацию.

3⃣Верните целое число, преобразованное из измененного num_obj.

😎 Решение

class Solution {
    func maximum69Number (_ num: Int) -> Int {
        var numArray = Array(String(num))
        for i in 0..<numArray.count {
            if numArray[i] == "6" {
                numArray[i] = "9"
                break
            }
        }
        return Int(String(numArray))!
    }
}

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

Задача: 320. Generalized Abbreviation
Сложность: medium

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

Например, "abcde" можно сократить следующим образом:

"a3e" ("bcd" заменено на "3")
"1bcd1" ("a" и "e" заменены на "1")
"5" ("abcde" заменено на "5")
"abcde" (без замены подстрок)
Однако следующие аббревиатуры недействительны:

"23" ("ab" заменено на "2" и "cde" заменено на "3") недействительно, так как выбранные подстроки смежные.
"22de" ("ab" заменено на "2" и "bc" заменено на "2") недействительно, так как выбранные подстроки перекрываются.
Дано слово word, верните список всех возможных обобщенных аббревиатур слова. Верните ответ в любом порядке.

Пример:

Input: word = "a"
Output: ["1","a"]

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

1⃣Создание битовых масок
Каждая аббревиатура имеет одно к одному соответствие с n-битным двоичным числом x, где n - длина слова. Используйте эти числа в качестве чертежей для построения соответствующих аббревиатур.

2⃣Генерация аббревиатур
Для числа x просканируйте его бит за битом, чтобы определить, какие символы следует сохранить, а какие - сократить. Если бит равен 1, сохраните соответствующий символ, если 0 - замените его на счетчик.

3⃣Перебор всех комбинаций
Для каждого числа от 0 до 2^n - 1 используйте его битовое представление для создания соответствующей аббревиатуры. Сканируйте число x побитово, извлекая его последний бит с помощью b = x & 1 и сдвигая x вправо на один бит x >>= 1.

😎 Решение:

class Solution {
    func generateAbbreviations(_ word: String) -> [String] {
        var ans = [String]()
        for x in 0..<(1 << word.count) {
            ans.append(abbr(word, x))
        }
        return ans
    }

    private func abbr(_ word: String, _ x: Int) -> String {
        var builder = ""
        var k = 0
        var x = x
        for i in 0..<word.count {
            if (x & 1) == 0 {
                if k != 0 {
                    builder += "\(k)"
                    k = 0
                }
                builder.append(word[word.index(word.startIndex, offsetBy: i)])
            } else {
                k += 1
            }
            x >>= 1
        }
        if k != 0 {
            builder += "\(k)"
        }
        return builder
    }
}

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

Задача: 1087. Brace Expansion
Сложность: medium

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

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

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

Пример:

Input: s = "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]

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

1⃣Вызовите функцию findAllWords(String, Integer) с данной строкой s и значением startPos равным 0. startPos представляет текущую позицию в строке s. Если строка, которую нужно рассмотреть, пуста (startPos == s.length()), верните список, содержащий пустую строку.

2⃣Вызовите функцию storeFirstOptions с строкой s, целым числом startPos и пустым списком firstOptions. Найдите набор символов, начиная с позиции startPos, и сохраните их в списке firstOptions. Это может быть один символ или все символы между скобками. Отсортируйте список firstOptions. Верните обновленное значение startPos, которое теперь указывает на первый индекс следующей группы символов в строке s, которую мы будем рассматривать. Сохраните это значение в переменной remStringStartPos. Сделайте рекурсивный вызов функции findAllWords(String, Integer) с строкой s и remStringStartPos. Сохраните возвращенный список слов в переменной wordsWithRemString.

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

😎 Решение:

class Solution {
    func storeFirstOptions(_ s: String, _ startPos: inout Int, _ firstOptions: inout [Character]) {
        let sArray = Array(s)
        if sArray[startPos] != "{" {
            firstOptions.append(sArray[startPos])
        } else {
            startPos += 1
            while sArray[startPos] != "}" {
                if sArray[startPos].isLowercase {
                    firstOptions.append(sArray[startPos])
                }
                startPos += 1
            }
            firstOptions.sort()
        }
        startPos += 1
    }
    
    func findAllWords(_ s: String, _ startPos: Int) -> [String] {
        if startPos == s.count {
            return [""]
        }
        
        var firstOptions = [Character]()
        var newStartPos = startPos
        storeFirstOptions(s, &newStartPos, &firstOptions)
        let wordsWithRemString = findAllWords(s, newStartPos)
        
        var expandedWords = [String]()
        for c in firstOptions {
            for word in wordsWithRemString {
                expandedWords.append(String(c) + word)
            }
        }
        return expandedWords
    }
    
    func expand(_ s: String) -> [String] {
        return findAllWords(s, 0)
    }
}

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