Задача: 68. Text Justification
Сложность: hard

Дан массив строк words и ширина maxWidth. Необходимо отформатировать текст таким образом, чтобы каждая строка содержала ровно maxWidth символов и была полностью (слева и справа) выровнена.

Слова следует упаковывать жадным способом; то есть стараться поместить как можно больше слов в каждую строку. Дополнительные пробелы ' ' следует добавлять по мере необходимости, чтобы каждая строка имела ровно maxWidth символов.

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

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

Примечание:
Слово определяется как последовательность символов, не содержащих пробелы.
Длина каждого слова гарантированно больше 0 и не превышает maxWidth.
Входной массив words содержит хотя бы одно слово.

Пример:

Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Output:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]

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

1⃣Создайте два вспомогательных метода getWords и createLine, описанные выше.

2⃣Инициализируйте список ответов ans и целочисленную переменную i для итерации по входным данным. Используйте цикл while для перебора входных данных. Каждая итерация в цикле while будет обрабатывать одну строку в ответе.

3⃣Пока i < words.length, выполните следующие шаги:
Получите слова, которые должны быть в текущей строке, как currentLine = getWords(i).
Увеличьте i на currentLine.length.
Создайте строку, вызвав createLine(line, i), и добавьте её в ans.
Верните ans.

😎 Решение:

func fullJustify(_ words: [String], _ maxWidth: Int) -> [String] {
    var ans = [String]()
    var i = 0

    while i < words.count {
        let currentLine = getWords(&i, words, maxWidth)
        ans.append(createLine(currentLine, i, words, maxWidth))
    }
    return ans

    func getWords(_ i: inout Int, _ words: [String], _ maxWidth: Int) -> [String] {
        var currentLine = [String]()
        var currLength = 0
        while i < words.count && currLength + words[i].count <= maxWidth {
            currentLine.append(words[i])
            currLength += words[i].count + 1
            i += 1
        }
        return currentLine
    }

    func createLine(_ line: [String], _ i: Int, _ words: [String], _ maxWidth: Int) -> String {
        var baseLength = -1
        for word in line {
            baseLength += word.count + 1
        }
        let extraSpaces = maxWidth - baseLength
        var result = line
        if line.count == 1 || i == words.count {
            return line.joined(separator: " ") + String(repeating: " ", count: extraSpaces)
        }
        let wordCount = line.count - 1
        let spacesPerWord = extraSpaces / wordCount
        let needsExtraSpace = extraSpaces % wordCount
        for j in 0..<needsExtraSpace {
            result[j] += " "
        }
        for j in 0..<wordCount {
            result[j] += String(repeating: " ", count: spacesPerWord)
        }
        return result.joined(separator: " ")
    }
}

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

Задача: 679. 24 Game
Сложность: hard

Дан массив целых чисел cards длиной 4. У вас есть четыре карты, каждая из которых содержит число в диапазоне от 1 до 9. Вам нужно расположить числа на этих картах в математическом выражении, используя операторы ['+', '-', '*', '/'] и скобки '(' и ')' так, чтобы получить значение 24.

Вы ограничены следующими правилами:

Оператор деления '/' представляет собой реальное деление, а не целочисленное деление.
Например, 4 / (1 - 2 / 3) = 4 / (1 / 3) = 12.
Каждая операция выполняется между двумя числами. В частности, мы не можем использовать '-' как унарный оператор.
Например, если cards = [1, 1, 1, 1], выражение "-1 - 1 - 1 - 1" не допускается.
Вы не можете объединять числа вместе.
Например, если cards = [1, 2, 1, 2], выражение "12 + 12" недопустимо.
Вернуть true, если вы можете получить такое выражение, которое оценивается в 24, и false в противном случае.

Пример:

Input: cards = [4,1,8,7]
Output: true
Explanation: (8-4) * (7-1) = 24

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

1⃣Создайте функцию generatePossibleResults(a, b), которая возвращает массив результатов всех возможных математических операций над двумя числами.

2⃣ Создайте функцию checkIfResultReached(list), чтобы проверить, можем ли мы достичь результата 24, используя текущий массив list. Сначала проверьте базовые условия: если размер массива равен 1, верните true, если результат равен 24, иначе верните false.

3⃣Если размер массива больше 1, выберите любые два числа из списка, выполните все математические операции над ними, создайте новый список с обновленными элементами и снова вызовите рекурсивную функцию с этим новым списком. Если ни одна комбинация не приводит к результату 24, верните false. Вызовите checkIfResultReached с исходным списком карт.

😎 Решение:

class Solution {
    func generatePossibleResults(_ a: Double, _ b: Double) -> [Double] {
        var res = [a + b, a - b, b - a, a * b]
        if a != 0 {
            res.append(b / a)
        }
        if b != 0 {
            res.append(a / b)
        }
        return res
    }
    
    func checkIfResultReached(_ list: [Double]) -> Bool {
        if list.count == 1 {
            return abs(list[0] - 24) <= 0.1
        }
        
        for i in 0..<list.count {
            for j in i + 1..<list.count {
                var newList = [Double]()
                for k in 0..<list.count {
                    if k != i && k != j {
                        newList.append(list[k])
                    }
                }
                
                for res in generatePossibleResults(list[i], list[j]) {
                    newList.append(res)
                    if checkIfResultReached(newList) {
                        return true
                    }
                    newList.removeLast()
                }
            }
        }
        return false
    }
    
    func judgePoint24(_ cards: [Int]) -> Bool {
        let list = cards.map { Double($0) }
        return checkIfResultReached(list)
    }
}

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

Задача: 155. Min Stack
Сложность: medium

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

Реализуйте класс MinStack:
MinStack() инициализирует объект стека.
void push(int val) добавляет элемент val в стек.
void pop() удаляет элемент на вершине стека.
int top() возвращает верхний элемент стека.
int getMin() извлекает минимальный элемент в стеке.

Вы должны реализовать решение с временной сложностью O(1) для каждой функции.

Пример:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

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

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

2⃣Работа со стеком:
Метод push(int val): добавьте элемент val в стек. При добавлении элемента обновите вспомогательную структуру данных, которая отслеживает минимальные значения на каждом уровне стека. Это позволит сохранить константное время выполнения для операции getMin().
Метод pop(): удалите элемент из вершины стека. При этом также необходимо обновить структуру, которая отслеживает минимальные значения, чтобы она корректно отражала новое состояние стека после удаления элемента.

3⃣Доступ к элементам:
Метод top(): возвращайте верхний элемент стека. В языках, таких как Python, это можно сделать, обратившись к последнему элементу списка через индекс -1 (например, self.stack[-1]).
Метод getMin(): извлекайте минимальный элемент стека. Благодаря дополнительной структуре данных, поддерживающей отслеживание минимальных значений на каждом уровне стека, этот метод также выполняется за константное время.

😎 Решение:

func last<T>(_ array: [T]) -> T? {
    return array.last
}

class MinStack {
    private var stack: [(value: Int, min: Int)] = []

    func push(_ x: Int) {
        if stack.isEmpty {
            stack.append((x, x))
            return
        }
        
        let currentMin = stack.last!.min
        stack.append((x, min(currentMin, x)))
    }

    func pop() {
        stack.popLast()
    }

    func top() -> Int? {
        return stack.last?.value
    }

    func getMin() -> Int? {
        return stack.last?.min
    }
}

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

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

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

Пример:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

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

1⃣Инициализируйте массив dp длиной nums.length, все элементы которого равны 1. dp[i] представляет длину самой длинной возрастающей подпоследовательности, которая заканчивается элементом с индексом i.


2⃣Итерируйтесь от i = 1 до i = nums.length - 1. В каждой итерации используйте второй цикл for для итерации от j = 0 до j = i - 1 (все элементы перед i). Для каждого элемента перед i, проверьте, меньше ли этот элемент, чем nums[i]. Если да, установите dp[i] = max(dp[i], dp[j] + 1).


3⃣Верните максимальное значение из dp.

😎 Решение:

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

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

Задача: 916. Word Subsets
Сложность: medium

Вам даны два массива строк words1 и words2. Строка b является подмножеством строки a, если каждая буква в b встречается в ней, включая кратность. Например, "wrr" является подмножеством "warrior", но не является подмножеством "world". Строка a из words1 является универсальной, если для каждой строки b в words2, b является подмножеством a. Верните массив всех универсальных строк в words1. Вы можете вернуть ответ в любом порядке.

Пример:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
Output: ["facebook","google","leetcode"]

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

1⃣Подсчитать максимальное количество каждой буквы в каждом слове из words2.

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

3⃣Вернуть массив слов из words1, которые удовлетворяют этому условию.

😎 Решение:

class Solution {
    func wordSubsets(_ words1: [String], _ words2: [String]) -> [String] {
        var maxCount = [Character: Int]()
        
        for word in words2 {
            var count = [Character: Int]()
            for char in word {
                count[char, default: 0] += 1
            }
            for (char, cnt) in count {
                maxCount[char] = max(maxCount[char, default: 0], cnt)
            }
        }
        
        var result = [String]()
        for word in words1 {
            var count = [Character: Int]()
            for char in word {
                count[char, default: 0] += 1
            }
            if maxCount.allSatisfy({ count[$0.key, default: 0] >= $0.value }) {
                result.append(word)
            }
        }
        
        return result
    }
}

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

Задача: 959. Regions Cut By Slashes
Сложность: medium

n x n сетка состоит из квадратов размером 1 x 1, где каждый квадрат 1 x 1 содержит '/', '', или пустое пространство ' '. Эти символы делят квадрат на смежные области.

Дана сетка grid, представленная в виде строкового массива. Верните количество областей.

Обратите внимание, что обратные слеши экранированы, поэтому '' представлен как '\'.

Пример:

Input: grid = [" /","/ "]
Output: 2

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

1⃣Создайте 4*N*N узлов для каждой ячейки сетки и соедините их в соответствии с описанием.

2⃣Используйте структуру объединения-поиска (DSU), чтобы найти количество связанных компонентов.

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

😎 Решение:

class DSU {
    var parent: [Int]
    
    init(_ N: Int) {
        parent = Array(0..<N)
    }
    
    func find(_ x: Int) -> Int {
        if parent[x] != x {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }
    
    func union(_ x: Int, _ y: Int) {
        parent[find(x)] = find(y)
    }
}

class Solution {
    func regionsBySlashes(_ grid: [String]) -> Int {
        let N = grid.count
        let dsu = DSU(4 * N * N)
        
        for r in 0..<N {
            for c in 0..<N {
                let root = 4 * (r * N + c)
                let val = Array(grid[r])[c]
                
                if val != "\\" {
                    dsu.union(root + 0, root + 1)
                    dsu.union(root + 2, root + 3)
                }
                if val != "/" {
                    dsu.union(root + 0, root + 2)
                    dsu.union(root + 1, root + 3)
                }
                
                if r + 1 < N {
                    dsu.union(root + 3, (root + 4 * N) + 0)
                }
                if r - 1 >= 0 {
                    dsu.union(root + 0, (root - 4 * N) + 3)
                }
                if c + 1 < N {
                    dsu.union(root + 2, (root + 4) + 1)
                }
                if c - 1 >= 0 {
                    dsu.union(root + 1, (root - 4) + 2)
                }
            }
        }
        
        var ans = 0
        for x in 0..<(4 * N * N) {
            if dsu.find(x) == x {
                ans += 1
            }
        }
        
        return ans
    }
}

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

Задача: 236. Lowest Common Ancestor of a Binary Tree
Сложность: medium

Дано бинарное дерево. Найдите наименьший общий предок (LCA) двух заданных узлов в дереве.

Согласно определению LCA на Википедии: "Наименьший общий предок определяется между двумя узлами p и q как наименьший узел в дереве T, который имеет как p, так и q в качестве потомков (где мы допускаем, что узел может быть потомком самого себя)."

Пример:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

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

1⃣Начало обхода дерева с корня: Начните обход дерева с корневого узла. Если текущий узел является одним из узлов p или q, установите переменную mid в значение True и продолжите поиск другого узла в левой и правой ветвях.

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

3⃣Определение LCA: Если в любой момент обхода дерева две из трех переменных (left, right или mid) становятся True, это означает, что найден наименьший общий предок (LCA) для узлов p и q.

😎 Решение:

class Solution {
    private var ans: TreeNode?

    init() {
        self.ans = nil
    }

    private func recurseTree(_ currentNode: TreeNode?, _ p: TreeNode, _ q: TreeNode) -> Bool {
        guard let currentNode = currentNode else { return false }

        let left = recurseTree(currentNode.left, p, q) ? 1 : 0
        let right = recurseTree(currentNode.right, p, q) ? 1 : 0
        let mid = (currentNode === p || currentNode === q) ? 1 : 0

        if mid + left + right >= 2 {
            self.ans = currentNode
        }

        return (mid + left + right > 0)
    }

    func lowestCommonAncestor(_ root: TreeNode?, _ p: TreeNode, _ q: TreeNode) -> TreeNode? {
        _ = recurseTree(root, p, q)
        return self.ans
    }
}

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

Задача: 212. Word Search II
Сложность: hard

Дана m на n доска символов и список строк words, верните все слова, находящиеся на доске.

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

Пример:

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]

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

1⃣Построение Trie:
Постройте структуру Trie из слов в словаре. Trie будет использоваться для процесса сопоставления позже.

2⃣Запуск обхода в глубину (Backtracking) с каждой ячейки:
Начните обход доски с каждой ячейки. Если существует слово в словаре, которое начинается с буквы в данной ячейке, начните рекурсивный вызов функции backtracking(cell).

3⃣Обход соседних ячеек:
В функции backtracking(cell) исследуйте соседние ячейки (i.e. neighborCell) вокруг текущей ячейки для следующего рекурсивного вызова backtracking(neighborCell).
На каждом вызове проверяйте, соответствует ли последовательность букв, которую мы прошли до сих пор, какому-либо слову в словаре, используя структуру Trie, построенную в начале.

😎 Решение:

class TrieNode {
    var children = [Character: TrieNode]()
    var word: String? = nil
}

class Solution {
    private var board: [[Character]] = []
    private var result = [String]()

    func findWords(_ board: [[Character]], _ words: [String]) -> [String] {
        let root = TrieNode()
        for word in words {
            var node = root
            for letter in word {
                if node.children[letter] == nil {
                    node.children[letter] = TrieNode()
                }
                node = node.children[letter]!
            }
            node.word = word
        }

        self.board = board
        for row in 0..<board.count {
            for col in 0..<board[0].count {
                if root.children[board[row][col]] != nil {
                    backtracking(row, col, root)
                }
            }
        }

        return result
    }

    private func backtracking(_ row: Int, _ col: Int, _ parent: TrieNode) {
        let letter = board[row][col]
        guard let currNode = parent.children[letter] else { return }

        if let word = currNode.word {
            result.append(word)
            currNode.word = nil
        }

        board[row][col] = "#"

        let rowOffset = [-1, 0, 1, 0]
        let colOffset = [0, 1, 0, -1]
        for i in 0..<4 {
            let newRow = row + rowOffset[i]
            let newCol = col + colOffset[i]
            if newRow >= 0, newRow < board.count, newCol >= 0, newCol < board[0].count, currNode.children[board[newRow][newCol]] != nil {
                backtracking(newRow, newCol, currNode)
            }
        }

        board[row][col] = letter

        if currNode.children.isEmpty {
            parent.children[letter] = nil
        }
    }
}

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

Задача: 590. N-ary Tree Postorder Traversal
Сложность: easy

Дано корневое дерево с n-арной структурой, верните обход дерева в постфиксном порядке для значений его узлов.

Сериализация входных данных 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: [2,6,14,11,7,3,12,8,4,13,9,10,5,1]

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

1⃣Инициализируйте стек для хранения узлов и список для хранения значений узлов в обратном порядке.

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

3⃣В конце верните список значений узлов.

😎 Решение:

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

class Solution {
    func postorder(_ root: Node?) -> [Int] {
        guard let root = root else { return [] }
        var stack: [Node] = [root]
        var output: [Int] = []
        
        while !stack.isEmpty {
            let node = stack.removeLast()
            output.insert(node.val, at: 0)
            for child in node.children {
                stack.append(child)
            }
        }
        return output
    }
}

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

Задача: 605. Can Place Flowers
Сложность: easy

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

Дан целочисленный массив flowerbed, содержащий 0 и 1, где 0 означает пустой участок, а 1 — занятый участок, и целое число n. Верните true, если n новых цветов можно посадить на клумбе, не нарушая правила о соседних цветах, и false в противном случае.

Пример:

Input: flowerbed = [1,0,0,0,1], n = 1
Output: true

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

1⃣Решение очень простое. Мы можем определить максимальное количество дополнительных цветов, count, которые можно посадить для данного расположения клумбы. Для этого мы проходим по всем элементам массива flowerbed и находим те элементы, которые равны 0 (означает пустую позицию).

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

3⃣Если полученное количество count больше или равно n, требуемому количеству цветов для посадки, мы можем посадить n цветов на пустые места, иначе - нет.

😎 Решение:

class Solution {
    func canPlaceFlowers(_ flowerbed: [Int], _ n: Int) -> Bool {
        var flowerbed = flowerbed
        var count = 0
        for i in 0..<flowerbed.count {
            if flowerbed[i] == 0 {
                let emptyLeft = i == 0 || flowerbed[i - 1] == 0
                let emptyRight = i == flowerbed.count - 1 || flowerbed[i + 1] == 0
                if emptyLeft && emptyRight {
                    flowerbed[i] = 1
                    count += 1
                }
            }
        }
        return count >= n
    }
}

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

Задача: 436. Find Right Interval
Сложность: medium

Дан массив интервалов, где intervals[i] = [starti, endi] и каждый starti уникален.

Правый интервал для интервала i - это интервал j, такой что startj >= endi и startj минимален. Обратите внимание, что i может быть равен j.

Верните массив индексов правых интервалов для каждого интервала i. Если правого интервала для интервала i не существует, то поставьте -1 в индекс i.

Пример:

Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.

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

1⃣Интуиция за этим подходом такова: если мы будем поддерживать два массива - intervals, который отсортирован по начальным точкам, и endIntervals, который отсортирован по конечным точкам. Когда мы выбираем первый интервал (или, скажем, i-ый интервал) из массива endIntervals, мы можем определить подходящий интервал, удовлетворяющий критериям правого интервала, просматривая интервалы в массиве intervals слева направо, так как массив intervals отсортирован по начальным точкам. Допустим, индекс выбранного элемента из массива intervals окажется j.

2⃣Теперь, когда мы выбираем следующий интервал (скажем, (i+1)-ый интервал) из массива endIntervals, нам не нужно начинать сканирование массива intervals с первого индекса. Вместо этого мы можем начать прямо с индекса j, где мы остановились в последний раз в массиве intervals. Это потому, что конечная точка, соответствующая endIntervals[i+1], больше, чем та, которая соответствует endIntervals[i], и ни один из интервалов из intervals[k], таких что 0 < k < j, не удовлетворяет критериям правого соседа с endIntervals[i], а значит, и с endIntervals[i+1] тоже.

3⃣Если в какой-то момент мы достигнем конца массива, т.е. j = intervals.length, и ни один элемент, удовлетворяющий критериям правого интервала, не будет доступен в массиве intervals, мы ставим -1 в соответствующую запись res. То же самое касается всех оставшихся элементов массива endIntervals, конечные точки которых даже больше, чем у предыдущего интервала. Также мы используем хеш-таблицу hash изначально, чтобы сохранить индексы, соответствующие интервалам, даже после сортировки.

😎 Решение:

class Solution {
    func findRightInterval(_ intervals: [[Int]]) -> [Int] {
        var endIntervals = intervals
        var hash = [Int: Int]()
        for i in 0..<intervals.count {
            hash[intervals[i][0]] = i
        }
        intervals.sort { $0[0] < $1[0] }
        endIntervals.sort { $0[1] < $1[1] }
        var j = 0
        var res = [Int](repeating: 0, count: intervals.count)
        for i in 0..<endIntervals.count {
            while j < intervals.count && intervals[j][0] < endIntervals[i][1] {
                j += 1
            }
            res[hash[endIntervals[i][0]]!] = j == intervals.count ? -1 : hash[intervals[j][0]]!
        }
        return res
    }
}

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

Задача: 1338. Reduce Array Size to The Half
Сложность: medium

Дан массив целых чисел arr. Вы можете выбрать набор чисел и удалить все вхождения этих чисел из массива.

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

Пример:

Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has a size greater than half of the size of the old array.

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

1⃣Отсортировать массив и создать список подсчета количества вхождений каждого числа.

2⃣Отсортировать список подсчета в порядке убывания.

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

😎 Решение:

class Solution {
    func minSetSize(_ arr: [Int]) -> Int {
        var arr = arr
        arr.sort()
        
        var counts: [Int] = []
        var currentRun = 1
        for i in 1..<arr.count {
            if arr[i] == arr[i - 1] {
                currentRun += 1
                continue
            }
            counts.append(currentRun)
            currentRun = 1
        }
        counts.append(currentRun)
        
        counts.sort(by: >)
        
        var numbersRemovedFromArr = 0
        var setSize = 0
        for count in counts {
            numbersRemovedFromArr += count
            setSize += 1   
            if numbersRemovedFromArr >= arr.count / 2 {
                break
            }
        }
        
        return setSize
    }
}

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

Задача: 311. Sparse Matrix Multiplication
Сложность: medium

Даны две разреженные матрицы mat1 размером m x k и mat2 размером k x n. Верните результат перемножения матриц mat1 x mat2. Вы можете предположить, что умножение всегда возможно.

Пример:

Input: mat1 = [[1,0,0],[-1,0,3]], mat2 = [[7,0,0],[0,0,0],[0,0,1]]
Output: [[7,0,0],[-7,0,3]]

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

1⃣Инициализация результирующей матрицы
Создайте результирующую матрицу result размером m x n, заполненную нулями.

2⃣Хранение ненулевых элементов
Пройдите по каждой строке матрицы mat1 и сохраните индексы и значения ненулевых элементов в хеш-карте mat1_map. Пройдите по каждой колонке матрицы mat2 и сохраните индексы и значения ненулевых элементов в хеш-карте mat2_map.

3⃣Вычисление произведения
Для каждой строки i в mat1 и для каждой колонки j в mat2: Если в mat1_map есть ненулевой элемент в строке i и в mat2_map есть ненулевой элемент в колонке j с одинаковым индексом k, добавьте произведение этих элементов к result[i][j].

😎 Решение:

class Solution {
    func multiply(_ mat1: [[Int]], _ mat2: [[Int]]) -> [[Int]] {
        let n = mat1.count
        let k = mat1[0].count
        let m = mat2[0].count
        
        var ans = Array(repeating: Array(repeating: 0, count: m), count: n)
        
        for rowIndex in 0..<n {
            for elementIndex in 0..<k {
                if mat1[rowIndex][elementIndex] != 0 {
                    for colIndex in 0..<m {
                        ans[rowIndex][colIndex] += mat1[rowIndex][elementIndex] * mat2[elementIndex][colIndex]
                    }
                }
            }
        }
        
        return ans
    }
}

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

Задача: 1406. Stone Game III
Сложность: hard

Алиса и Боб продолжают свои игры с кучами камней. Камни расположены в ряд, и каждый камень имеет ассоциированное значение, которое представлено целым числом в массиве stoneValue.
Алиса и Боб ходят по очереди, начиная с Алисы. В свой ход каждый игрок может взять 1, 2 или 3 камня из первых оставшихся камней в ряду.

Счет каждого игрока равен сумме значений взятых камней. Изначально счет каждого игрока равен 0.
Цель игры — закончить с наивысшим счетом, и победителем становится игрок с наивысшим счетом, при этом возможна ничья. Игра продолжается, пока все камни не будут взяты.

Предположим, что Алиса и Боб играют оптимально.
Верните "Alice", если Алиса выиграет, "Bob", если выиграет Боб, или "Tie", если они закончат игру с одинаковым счетом.

Пример:

Input: stoneValue = [1,2,3,7]
Output: "Bob"
Explanation: Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.

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

1⃣Инициализируйте массив dp размером n+1 и установите dp[n] в 0.

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

3⃣Определите победителя, сравнивая dp[0] с 0: если больше, победит Алиса; если меньше, победит Боб; если равно, будет ничья.

😎 Решение:

class Solution {
    func stoneGameIII(_ stoneValue: [Int]) -> String {
        let n = stoneValue.count
        var dp = [Int](repeating: 0, count: n + 1)
        for i in stride(from: n - 1, through: 0, by: -1) {
            dp[i] = stoneValue[i] - dp[i + 1]
            if i + 2 <= n {
                dp[i] = max(dp[i], stoneValue[i] + stoneValue[i + 1] - dp[i + 2])
            }
            if i + 3 <= n {
                dp[i] = max(dp[i], stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] - dp[i + 3])
            }
        }
        if dp[0] > 0 {
            return "Alice"
        } else if dp[0] < 0 {
            return "Bob"
        } else {
            return "Tie"
        }
    }
}

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

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

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

Задача: 213. House Robber II
Сложность: medium

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

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

Пример:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

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

1⃣Обработка базовых случаев:
Если в массиве nums нет домов, возвращаем 0.
Если в массиве nums только один дом, возвращаем значение этого дома.

2⃣Разделение задачи на две подзадачи:
Находим максимальную сумму для подмассива домов от первого до предпоследнего, вызывая функцию rob_simple с параметрами 0 и nums.count - 2.
Находим максимальную сумму для подмассива домов от второго до последнего, вызывая функцию rob_simple с параметрами 1 и nums.count - 1.

3⃣Сравнение результатов и возврат максимального значения:
Возвращаем максимальное значение из двух полученных результатов.

😎 Решение:

class Solution {
    func rob(_ nums: [Int]) -> Int {
        if nums.isEmpty { return 0 }
        if nums.count == 1 { return nums[0] }

        let max1 = rob_simple(nums, 0, nums.count - 2)
        let max2 = rob_simple(nums, 1, nums.count - 1)

        return max(max1, max2)
    }

    func rob_simple(_ nums: [Int], _ start: Int, _ end: Int) -> Int {
        var t1 = 0
        var t2 = 0

        for i in start...end {
            let temp = t1
            let current = nums[i]
            t1 = max(current + t2, t1)
            t2 = temp
        }

        return t1
    }
}

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

Задача: 912. Sort an Array
Сложность: medium

Задав массив целых чисел nums, отсортируйте массив по возрастанию и верните его. Вы должны решить задачу без использования встроенных функций за время O(nlog(n)) и с минимально возможной пространственной сложностью.

Пример:

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

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

1⃣Используем алгоритм "Сортировка слиянием" (Merge Sort), который обеспечивает время выполнения O(n log n) и минимально возможную пространственную сложность для стабильного сортировочного алгоритма.

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

3⃣Слить две отсортированные половины.

😎 Решение:

func mergeSort(_ nums: inout [Int]) {
    if nums.count > 1 {
        let mid = nums.count / 2
        var left_half = Array(nums[0..<mid])
        var right_half = Array(nums[mid..<nums.count])

        mergeSort(&left_half)
        mergeSort(&right_half)

        var i = 0, j = 0, k = 0
        while i < left_half.count && j < right_half.count {
            if left_half[i] < right_half[j] {
                nums[k] = left_half[i]
                i += 1
            } else {
                nums[k] = right_half[j]
                j += 1
            }
            k += 1
        }

        while i < left_half.count {
            nums[k] = left_half[i]
            i += 1
            k += 1
        }

        while j < right_half.count {
            nums[k] = right_half[j]
            j += 1
            k += 1
        }
    }
}

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

Задача: 1473. Paint House III
Сложность: hard

Есть ряд из m домов в маленьком городе, каждый дом должен быть покрашен одним из n цветов (обозначены от 1 до n), некоторые дома, которые были покрашены прошлым летом, не должны быть перекрашены.

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

Например: дома = [1,2,2,3,3,2,1,1] содержат 5 соседств [{1}, {2,2}, {3,3}, {2}, {1,1}].
Дан массив домов, матрица m x n стоимости и целое число target, где:
houses[i]: цвет дома i, и 0, если дом ещё не покрашен.
cost[i][j]: стоимость покраски дома i в цвет j + 1.
Верните минимальную стоимость покраски всех оставшихся домов таким образом, чтобы было ровно target соседств. Если это невозможно, верните -1.

Пример:

Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 9
Explanation: Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.

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

1⃣Инициализация и базовые случаи:
Создайте класс Solution и массив memo для мемоизации результатов. Установите MAX_COST как максимально возможную стоимость плюс 1.
Создайте метод findMinCost, который проверяет базовые случаи:
- если все дома пройдены, возвращайте 0, если количество соседств равно target, иначе возвращайте MAX_COST.
- если количество соседств больше target, возвращайте MAX_COST.
Если результат уже вычислен, возвращайте его из memo.

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

3⃣Метод minCost:
Запустите метод findMinCost с начальными параметрами и верните результат. Если результат равен MAX_COST, верните -1.

😎 Решение:

class Solution {
    let MAX_COST = 1000001
    var memo = [[[Int?]]](repeating: [[Int?]](repeating: [Int?](repeating: nil, count: 22), count: 102), count: 102)
    
    func findMinCost(_ houses: [Int], _ cost: [[Int]], _ targetCount: Int, _ currIndex: Int, _ neighborhoodCount: Int, _ prevHouseColor: Int) -> Int {
        if currIndex == houses.count {
            return neighborhoodCount == targetCount ? 0 : MAX_COST
        }
        
        if neighborhoodCount > targetCount {
            return MAX_COST
        }
        
        if let memoValue = memo[currIndex][neighborhoodCount][prevHouseColor] {
            return memoValue
        }
        
        var minCost = MAX_COST
        
        if houses[currIndex] != 0 {
            let newNeighborhoodCount = neighborhoodCount + (houses[currIndex] != prevHouseColor ? 1 : 0)
            minCost = findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, houses[currIndex])
        } else {
            for color in 1...cost[0].count {
                let newNeighborhoodCount = neighborhoodCount + (color != prevHouseColor ? 1 : 0)
                let currCost = cost[currIndex][color - 1] + findMinCost(houses, cost, targetCount, currIndex + 1, newNeighborhoodCount, color)
                minCost = min(minCost, currCost)
            }
        }
        
        memo[currIndex][neighborhoodCount][prevHouseColor] = minCost
        return minCost
    }
    
    func minCost(_ houses: [Int], _ cost: [[Int]], _ m: Int, _ n: Int, _ target: Int) -> Int {
        let answer = findMinCost(houses, cost, target, 0, 0, 0)
        return answer == MAX_COST ? -1 : answer
    }
}

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

Задача: 775. Global and Local Inversions
Сложность: medium

Дан массив целых чисел nums длиной n, который представляет собой перестановку всех чисел в диапазоне [0, n - 1].

Число глобальных инверсий — это количество различных пар (i, j), где:

0 <= i < j < n
nums[i] > nums[j]
Число локальных инверсий — это количество индексов i, где:

0 <= i < n - 1
nums[i] > nums[i + 1]
Верните true, если количество глобальных инверсий равно количеству локальных инверсий.

Пример:

Input: nums = [1,0,2]
Output: true
Explanation: There is 1 global inversion and 1 local inversion.

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

1⃣Локальная инверсия также является глобальной инверсией. Таким образом, нам нужно проверить, есть ли в нашей перестановке какие-либо нелокальные инверсии (A[i] > A[j], i < j) с j - i > 1.

2⃣Для этого мы можем перебрать каждый индекс i и проверить, есть ли индекс j, такой что j > i + 1 и nums[i] > nums[j]. Если такой индекс найден, это будет означать наличие нелокальной инверсии.

3⃣Если для всех индексов i условие выше не выполняется, это значит, что количество глобальных инверсий равно количеству локальных инверсий, и мы возвращаем true. В противном случае, если хотя бы одна нелокальная инверсия найдена, мы возвращаем false.

😎 Решение:

class Solution {
    func isIdealPermutation(_ A: [Int]) -> Bool {
        let N = A.count
        for i in 0..<N {
            for j in i+2..<N {
                if A[i] > A[j] { 
                    return false 
                }
            }
        }
        return true
    }
}

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

Задача: 1269. Number of Ways to Stay in the Same Place After Some Steps
Сложность: hard

У вас есть указатель на индекс 0 в массиве размера arrLen. На каждом шаге вы можете перемещаться на 1 позицию влево, на 1 позицию вправо в массиве или оставаться на том же месте (указатель ни в коем случае не должен находиться за пределами массива). Учитывая два целых числа steps и arrLen, верните количество способов, при которых указатель все еще находится на индексе 0 после ровно шагов. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.

Пример:

Input: steps = 3, arrLen = 2
Output: 4

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

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

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

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

😎 Решение:

class Solution {
    func numWays(_ steps: Int, _ arrLen: Int) -> Int {
        let mod = 1_000_000_007
        let max_pos = min(arrLen - 1, steps)
        var dp = [Int](repeating: 0, count: max_pos + 1)
        dp[0] = 1
        for _ in 0..<steps {
            var new_dp = [Int](repeating: 0, count: max_pos + 1)
            for i in 0...max_pos {
                new_dp[i] = dp[i] % mod
                if i > 0 {
                    new_dp[i] = (new_dp[i] + dp[i - 1]) % mod
                }
                if i < max_pos {
                    new_dp[i] = (new_dp[i] + dp[i + 1]) % mod
                }
            }
            dp = new_dp
        }
        return dp[0]
    }
}

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