Задача: 167. Two Sum II - Input Array Is Sorted
Сложность: medium
-
Дан массив целых чисел numbers, индексированный с 1, который уже отсортирован в неубывающем порядке. Найдите два числа так, чтобы их сумма составляла заданное целевое число. Пусть эти два числа будут numbers[index1] и numbers[index2], где 1 <= index1 < index2 <= numbers.length.

Верните индексы этих двух чисел, index1 и index2, увеличенные на один, в виде массива из двух элементов [index1, index2].

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

Ваше решение должно использовать только константное дополнительное пространство.

Пример:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

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

1⃣Инициализация указателей:
Используйте два указателя: один (left) начинается с начала массива, а другой (right) - с конца.

2⃣Поиск решения:
Сравните сумму элементов, на которые указывают left и right, с целевым значением target.
Если сумма равна target, верните индексы этих элементов как решение.
Если сумма меньше target, увеличьте left (так как массив отсортирован и увеличение left увеличивает сумму).
Если сумма больше target, уменьшите right (чтобы уменьшить сумму).

3⃣Продолжение до нахождения решения:
Перемещайте указатели left и right, повторяя сравнение, пока не будет найдено решение.
Учитывая, что задача гарантирует существование ровно одного решения, этот метод всегда найдет ответ.

😎 Решение:

class Solution {
    func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
        var low = 0
        var high = numbers.count - 1
        while low < high {
            let sum = numbers[low] + numbers[high]
            if sum == target {
                return [low + 1, high + 1]
            } else if sum < target {
                low += 1
            } else {
                high -= 1
            }
        }
        return [-1, -1]
    }
}

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

Задача: 563. Binary Tree Tilt
Сложность: easy

Дано корневое значение бинарного дерева. Вернуть сумму значений наклонов всех узлов дерева.

Наклон узла дерева - это абсолютная разница между суммой всех значений узлов левого поддерева и всех значений узлов правого поддерева. Если у узла нет левого потомка, то сумма значений узлов левого поддерева считается равной 0. То же правило применяется, если у узла нет правого потомка.

Пример:

Input: root = [1,2,3]
Output: 1
Explanation: 
Tilt of node 2 : |0-0| = 0 (no children)
Tilt of node 3 : |0-0| = 0 (no children)
Tilt of node 1 : |2-3| = 1 (left subtree is just left child, so sum is 2; right subtree is just right child, so sum is 3)
Sum of every tilt : 0 + 0 + 1 = 1

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

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

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

3⃣Верните общую сумму наклонов всех узлов.

😎 Решение:

class Solution {
    func longestLine(_ mat: [[Int]]) -> Int {
        if mat.isEmpty || mat[0].isEmpty {
            return 0
        }
        
        let m = mat.count
        let n = mat[0].count
        var maxLength = 0
        
        var horizontal = Array(repeating: Array(repeating: 0, count: n), count: m)
        var vertical = Array(repeating: Array(repeating: 0, count: n), count: m)
        var diagonal = Array(repeating: Array(repeating: 0, count: n), count: m)
        var antiDiagonal = Array(repeating: Array(repeating: 0, count: n), count: m)
        
        for i in 0..<m {
            for j in 0..<n {
                if mat[i][j] == 1 {
                    horizontal[i][j] = (j > 0 ? horizontal[i][j-1] : 0) + 1
                    vertical[i][j] = (i > 0 ? vertical[i-1][j] : 0) + 1
                    diagonal[i][j] = (i > 0 && j > 0 ? diagonal[i-1][j-1] : 0) + 1
                    antiDiagonal[i][j] = (i > 0 && j < n - 1 ? antiDiagonal[i-1][j+1] : 0) + 1
                    
                    maxLength = max(maxLength, horizontal[i][j], vertical[i][j], diagonal[i][j], antiDiagonal[i][j])
                }
            }
        }
        
        return maxLength
    }
}

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

Задача: 842. Split Array into Fibonacci Sequence
Сложность: medium

Вам дана строка цифр num, такая как "123456579". Мы можем разделить её на последовательность, похожую на Фибоначчи [123, 456, 579].
Формально, последовательность, похожая на Фибоначчи, это список f неотрицательных целых чисел, таких что:
0 <= f[i] < 2^31 (то есть каждое число помещается в 32-битный знаковый целый тип),
f.length >= 3, и
f[i] + f[i + 1] == f[i + 2] для всех 0 <= i < f.length - 2.
Обратите внимание, что при разделении строки на части каждая часть не должна иметь лишних ведущих нулей, за исключением случая, если эта часть является числом 0.

Верните любую последовательность, похожую на Фибоначчи, из строки num, или верните [] если это невозможно.

Пример:

Input: num = "1101111"
Output: [11,0,11,11]
Explanation: The output [110, 1, 111] would also be accepted.

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

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

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

3⃣Если последовательность Фибоначчи найдена, верните её, иначе продолжайте перебор.

😎 Решение:

class Solution {
    func splitIntoFibonacci(_ S: String) -> [Int] {
        let N = S.count
        let sArray = Array(S)
        
        for i in 0..<min(10, N) {
            if sArray[0] == "0" && i > 0 { break }
            let a = Int(String(sArray[0...i]))!
            if a >= Int32.max { break }

            outerLoop: for j in (i+1)..<min(i+10, N) {
                if sArray[i+1] == "0" && j > i+1 { break }
                let b = Int(String(sArray[i+1...j]))!
                if b >= Int32.max { break }

                var fib = [a, b]
                var k = j + 1
                while k < N {
                    let next = fib[fib.count - 2] + fib[fib.count - 1]
                    if next > Int32.max { break }
                    let nextS = String(next)
                    if sArray[k...].starts(with: Array(nextS)) {
                        k += nextS.count
                        fib.append(next)
                    } else {
                        continue outerLoop
                    }
                }
                if fib.count >= 3 { return fib }
            }
        }

        return []
    }
}

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

Задача: 1005. Maximize Sum Of Array After K Negations
Сложность: easy

Учитывая целочисленный массив nums и целое число k, измените массив следующим образом: выберите индекс i и замените nums[i] на -nums[i]. Вы должны применить этот процесс ровно k раз. Вы можете выбрать один и тот же индекс i несколько раз. Верните наибольшую возможную сумму массива после его модификации таким образом.

Пример:

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

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

1⃣Сортировка массива:
Отсортируйте массив nums по возрастанию, чтобы наибольшее количество раз менять самые маленькие (отрицательные) значения на их противоположные.

2⃣Модификация массива:
Пройдитесь по отсортированному массиву и замените k наименьших значений на их противоположные (умножьте на -1). Если встретите 0, прекратите дальнейшие изменения, так как изменение 0 на -0 не имеет смысла.

3⃣Проверка остатка изменений:
Если после первого прохода остались изменения (k нечетное), то найдите минимальное значение в измененном массиве и еще раз поменяйте его знак. Это обеспечит максимальную сумму.

😎 Решение:

class Solution {
    func largestSumAfterKNegations(_ nums: [Int], _ k: Int) -> Int {
        var nums = nums.sorted()
        var k = k
        
        for i in 0..<nums.count {
            if k > 0 && nums[i] < 0 {
                nums[i] = -nums[i]
                k -= 1
            }
        }
        
        if k % 2 == 1 {
            nums.sort()
            nums[0] = -nums[0]
        }
        
        return nums.reduce(0, +)
    }
}

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

Задача: 746. Min Cost Climbing Stairs
Сложность: easy

Вам дан целочисленный массив cost, где cost[i] - стоимость i-й ступеньки на лестнице. После оплаты стоимости вы можете подняться на одну или две ступеньки. Вы можете начать со ступеньки с индексом 0 или со ступеньки с индексом 1. Верните минимальную стоимость достижения вершины этажа.

Пример:

Input: cost = [10,15,20]
Output: 15

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

1⃣Создать массив dp, где dp[i] хранит минимальную стоимость достижения i-й ступеньки.

2⃣Инициализировать dp[0] и dp[1] как cost[0] и cost[1] соответственно. Заполнить dp используя минимальную стоимость подъема с предыдущих ступенек.

3⃣Вернуть минимальную стоимость достижения вершины.

😎 Решение:

func minCostClimbingStairs(_ cost: [Int]) -> Int {
    var dp = cost
    for i in 2..<cost.count {
        dp[i] += min(dp[i - 1], dp[i - 2])
    }
    return min(dp[cost.count - 1], dp[cost.count - 2])
}

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

Задача: 482. License Key Formatting
Сложность: easy

Вам дан лицензионный ключ, представленный в виде строки s, которая состоит только из буквенно-цифровых символов и тире. Строка разделена на n + 1 групп с помощью n тире. Вам также дано целое число k.

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

Верните переформатированный лицензионный ключ.

Пример:

Input: s = "5F3Z-2e-9-w", k = 4
Output: "5F3Z-2E9W"
Explanation: The string s has been split into two parts, each part has 4 characters.
Note that the two extra dashes are not needed and can be removed.

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

1⃣Инициализация
Установите count в 0 для подсчета символов в текущей группе. Установите ans в пустую строку для хранения конечного результата.

2⃣Итерация по входной строке в обратном порядке
Пропускайте символы '-'. Если текущий символ не '-', добавьте его в ans и увеличьте count на 1. Если count достигает k, добавьте '-' в ans и сбросьте count.

3⃣Завершение
Проверьте, есть ли в конце строки ans тире, и удалите его, если оно есть. Переверните строку ans и верните её.

😎 Решение:

class Solution {
    func licenseKeyFormatting(_ s: String, _ k: Int) -> String {
        var count = 0
        var ans = ""
        
        for char in s.reversed() {
            if char != "-" {
                ans.append(char.uppercased())
                count += 1
                if count == k {
                    ans.append("-")
                    count = 0
                }
            }
        }
        
        if ans.last == "-" {
            ans.removeLast()
        }
        
        return String(ans.reversed())
    }
}

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

Задача: 28. Find the Index of the First Occurrence in a String
Сложность: easy

Учитывая две строки needle (игла) и haystack (стог сена), верните индекс первого вхождения needle в haystack или -1, если needle не является частью haystack.

Пример:

Input: haystack = "hello", needle = "ll"  
Output: 2  

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

1⃣Используем метод range(of:) для поиска первого вхождения needle в haystack.

2⃣Если подстрока найдена, вычисляем индекс начала с помощью distance(from:to:).

3⃣Если подстрока не найдена, возвращаем -1.

😎Решение:

func findNeedleInHaystack(_ haystack: String, _ needle: String) -> Int {
    if let range = haystack.range(of: needle) {
        return haystack.distance(from: haystack.startIndex, to: range.lowerBound)
    } else {
        return -1
    }
}

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

Задача: 132. Palindrome Partitioning II
Сложность: Hard

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

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

Пример:

Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

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

1⃣Определение задачи и начальные условия:
Алгоритм обратного отслеживания реализуется путём рекурсивного изучения кандидатов-подстрок. Мы определяем рекурсивный метод findMinimumCut, который находит минимальное количество разрезов для подстроки, начинающейся с индекса start и заканчивающейся на индексе end.
Чтобы найти минимальное количество разрезов, мы также должны знать минимальное количество разрезов, которые были найдены ранее для других разделений на палиндромы. Эта информация отслеживается в переменной minimumCut.
Начальное значение minimumCut будет равно максимально возможному количеству разрезов в строке, что равно длине строки минус один (т.е. разрез между каждым символом).

2⃣Генерация подстрок и рекурсивный поиск:
Теперь, когда мы знаем начальные и конечные индексы, мы должны сгенерировать все возможные подстроки, начиная с индекса start. Для этого мы будем держать начальный индекс постоянным. currentEndIndex обозначает конец текущей подстроки.

3⃣Условие палиндрома и рекурсивное разделение:
Если текущая подстрока является палиндромом, мы сделаем разрез после currentEndIndex и рекурсивно найдем минимальный разрез для оставшейся строки

😎 Решение:

class Solution {
    func minCut(_ s: String) -> Int {
        return findMinimumCut(s, 0, s.count - 1, s.count - 1)
    }

    private func findMinimumCut(_ s: String, _ start: Int, _ end: Int, _ minimumCut: Int) -> Int {
        if start == end || isPalindrome(s, start, end) {
            return 0
        }
        var minimumCut = minimumCut
        for currentEndIndex in start...end {
            if isPalindrome(s, start, currentEndIndex) {
                minimumCut = min(minimumCut, 1 + findMinimumCut(s, currentEndIndex + 1, end, minimumCut))
            }
        }
        return minimumCut
    }

    private func isPalindrome(_ s: String, _ start: Int, _ end: Int) -> Bool {
        var start = start
        var end = end
        let characters = Array(s)
        while start < end {
            if characters[start] != characters[end] {
                return false
            }
            start += 1
            end -= 1
        }
        return true
    }
}
class Solution {
    func minCut(_ s: String) -> Int {
        return findMinimumCut(s, 0, s.count - 1, s.count - 1)
    }

    private func findMinimumCut(_ s: String, _ start: Int, _ end: Int, _ minimumCut: Int) -> Int {
        if start == end || isPalindrome(s, start, end) {
            return 0
        }
        var minimumCut = minimumCut
        for currentEndIndex in start...end {
            if isPalindrome(s, start, currentEndIndex) {
                minimumCut = min(minimumCut, 1 + findMinimumCut(s, currentEndIndex + 1, end, minimumCut))
            }
        }
        return minimumCut
    }

    private func isPalindrome(_ s: String, _ start: Int, _ end: Int) -> Bool {
        var start = start
        var end = end
        let characters = Array(s)
        while start < end {
            if characters[start] != characters[end] {
                return false
            }
            start += 1
            end -= 1
        }
        return true
    }
}

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

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

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

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

Скобки для дочерних узлов: Если у узла есть хотя бы один дочерний узел (левый или правый), его дочерние узлы должны быть представлены в скобках. Конкретно:

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

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

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

Пример:

Input: root = [1,2,3,4]
Output: "1(2(4))(3)"
Explanation: Originally, it needs to be "1(2(4)())(3()())", but you need to omit all the empty parenthesis pairs. And it will be "1(2(4))(3)".

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

1⃣Инициализация и рекурсия
Начинаем с корневого узла бинарного дерева и выполняем прямой обход (preorder traversal) с использованием рекурсии. Для каждого узла добавляем его значение к строке результата.

2⃣Обработка дочерних узлов
Случай 1: Если у узла есть оба дочерних узла (левый и правый), оборачиваем результаты прямого обхода для обоих дочерних узлов в скобки. Случай 2: Если у узла нет дочерних узлов, пропускаем скобки для них. Случай 3: Если у узла есть только левый дочерний узел, обходим его и добавляем результат в скобках, пропуская пустые скобки для правого дочернего узла. Случай 4: Если у узла есть только правый дочерний узел, добавляем пустые скобки для левого дочернего узла и обходим правый дочерний узел, добавляя его результат в скобках.

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

😎 Решение:

class Solution {
    func tree2str(_ t: TreeNode?) -> String {
        var res = ""
        dfs(t, &res)
        return res
    }

    func dfs(_ t: TreeNode?, _ res: inout String) {
        guard let t = t else { return }
        res += "\(t.val)"
        if t.left == nil && t.right == nil { return }
        res += "("
        dfs(t.left, &res)
        res += ")"
        if t.right != nil {
            res += "("
            dfs(t.right, &res)
            res += ")"
        }
    }
}

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

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

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

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

Пример:

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

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

1⃣Определяем функцию обратного отслеживания под названием backtrack(first, curr), которая принимает индекс первого элемента, который нужно добавить, и текущую комбинацию в качестве аргументов.

2⃣Если текущая комбинация завершена, мы добавляем её в итоговый вывод.

3⃣В противном случае перебираем индексы i от first до длины всей последовательности n, добавляем элемент nums[i] в текущую комбинацию curr, продолжаем добавлять больше чисел в комбинацию: backtrack(i + 1, curr) и возвращаемся, удаляя nums[i] из curr.

😎 Решение:

func subsets(_ nums: [Int]) -> [[Int]] {
    var output = [[Int]]()
    let n = nums.count

    func backtrack(_ first: Int = 0, _ curr: [Int], _ k: Int) {
        if curr.count == k {
            output.append(curr)
            return
        }
        for i in first..<n {
            backtrack(i + 1, curr + [nums[i]], k)
        }
    }

    for k in 0...n {
        backtrack(0, [], k)
    }
    return output
}

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

Задача: 648. Replace Words
Сложность: medium

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

Пример:

Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

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

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

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

3⃣Замените слово найденным корнем и соберите обновленное предложение.

😎 Решение:

func replaceWords(_ roots: [String], _ sentence: String) -> String {
    let rootSet = Set(roots)
    
    func replace(_ word: String) -> String {
        for i in 1...word.count {
            let prefix = String(word.prefix(i))
            if rootSet.contains(prefix) {
                return prefix
            }
        }
        return word
    }
    
    return sentence.split(separator: " ").map { replace(String($0)) }.joined(separator: " ")
}

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

Задача: 58. Length of Last Word
Сложность: easy

Дана строка s, состоящая из слов и пробелов. Верните длину последнего слова в строке.

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

Пример:

Input: s = "Hello World"
Output: 5
Explanation: The last word is "World" with length 5.

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

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

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

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

😎 Решение:

class Solution {
    func lengthOfLastWord(_ s: String) -> Int {
        var p = s.count - 1
        // Trim the trailing spaces
        while p >= 0 && s[s.index(s.startIndex, offsetBy: p)] == ' ' {
            p -= 1
        }
        // Compute the length of the last word
        var length = 0
        while p >= 0 && s[s.index(s.startIndex, offsetBy: p)] != ' ' {
            p -= 1
            length += 1
        }
        return length
    }
}

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

Задача: 541. Reverse String II
Сложность: easy

Дана строка s и целое число k, переверните первые k символов для каждых 2k символов, начиная с начала строки.

Если осталось меньше k символов, переверните все. Если осталось меньше 2k, но больше или равно k символов, переверните первые k символов и оставьте остальные как есть.

Пример:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

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

1⃣Разворачиваем каждый блок из 2k символов непосредственно. Каждый блок начинается с кратного 2k: например, 0, 2k, 4k, 6k и так далее.

2⃣Будьте внимательны, если символов недостаточно, блок может не быть перевернут.

3⃣Для разворота блока символов с позиции i до j, меняем местами символы на позициях i++ и j--.

😎 Решение:

class Solution {
    func reverseStr(_ s: String, _ k: Int) -> String {
        var a = Array(s)
        var start = 0
        while start < a.count {
            var i = start
            var j = min(start + k - 1, a.count - 1)
            while i < j {
                a.swapAt(i, j)
                i += 1
                j -= 1
            }
            start += 2 * k
        }
        return String(a)
    }
}

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

Задача: 741. Cherry Pickup
Сложность: hard

Вам дана сетка n x n, представляющая поле вишен. Каждая клетка - одно из трех возможных целых чисел. 0 означает, что клетка пуста, и вы можете пройти через нее, 1 означает, что клетка содержит вишню, которую вы можете сорвать и пройти через нее, или -1 означает, что клетка содержит шип, который преграждает вам путь. Верните максимальное количество вишен, которое вы можете собрать, следуя следующим правилам: Начиная с позиции (0, 0) и достигая (n - 1, n - 1) путем перемещения вправо или вниз через допустимые клетки пути (клетки со значением 0 или 1).
После достижения (n - 1, n - 1) вернитесь в (0, 0), двигаясь влево или вверх по клеткам с действительными путями. Проходя через клетку пути, содержащую вишню, вы поднимаете ее, и клетка становится пустой клеткой 0. Если между (0, 0) и (n - 1, n - 1) нет действительного пути, то вишни собрать нельзя.

Пример:

Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5

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

1⃣Используйте динамическое программирование для подсчета максимального количества вишен, которые можно собрать при движении от (0, 0) до (n - 1, n - 1).

2⃣Примените еще один проход с использованием динамического программирования для движения обратно от (n - 1, n - 1) до (0, 0), чтобы учитывать вишни, собранные на обратном пути.

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

😎 Решение:

func cherryPickup(_ grid: [[Int]]) -> Int {
    let n = grid.count
    var dp = Array(repeating: Array(repeating: Array(repeating: Int.min, count: n), count: n), count: n)
    dp[0][0][0] = grid[0][0]
    
    for k in 1...(2 * (n - 1)) {
        for i1 in max(0, k - n + 1)...min(n - 1, k) {
            for i2 in max(0, k - n + 1)...min(n - 1, k) {
                let j1 = k - i1
                let j2 = k - i2
                if j1 < n && j2 < n && grid[i1][j1] != -1 && grid[i2][j2] != -1 {
                    var maxCherries = Int.min
                    if i1 > 0 && i2 > 0 { maxCherries = max(maxCherries, dp[i1 - 1][i2 - 1][k - 1]) }
                    if i1 > 0 { maxCherries = max(maxCherries, dp[i1 - 1][i2][k - 1]) }
                    if i2 > 0 { maxCherries = max(maxCherries, dp[i1][i2 - 1][k - 1]) }
                    maxCherries = max(maxCherries, dp[i1][i2][k - 1])
                    if maxCherries != Int.min {
                        dp[i1][i2][k] = maxCherries + grid[i1][j1]
                        if i1 != i2 { dp[i1][i2][k] += grid[i2][j2] }
                    }
                }
            }
        }
    }
    
    return max(0, dp[n - 1][n - 1][2 * (n - 1)])
}

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

Задача: 319. Bulb Switcher
Сложность: medium

Есть n лампочек, которые изначально выключены. Сначала вы включаете все лампочки, затем выключаете каждую вторую лампочку.

На третьем раунде вы переключаете каждую третью лампочку (включаете, если она выключена, или выключаете, если она включена). На i-ом раунде вы переключаете каждую i-ую лампочку. На n-ом раунде вы переключаете только последнюю лампочку.

Верните количество лампочек, которые будут включены после n раундов.

Пример:

Input: n = 3
Output: 1
Explanation: At first, the three bulbs are [off, off, off].
After the first round, the three bulbs are [on, on, on].
After the second round, the three bulbs are [on, off, on].
After the third round, the three bulbs are [on, off, off]. 
So you should return 1 because there is only one bulb is on.
Explanation: The two words can be "abcw", "xtfn".

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

1⃣Инициализация
Лампочка остается включенной, если она переключалась нечетное количество раз. Лампочка будет переключаться на каждом делителе её номера.

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

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

😎 Решение:

class Solution {
    func bulbSwitch(_ n: Int) -> Int {
        return Int(Double(n).squareRoot())
    }
}

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

Задача: 401. Binary Watch
Сложность: easy

Бинарные часы имеют 4 светодиода сверху для представления часов (0-11) и 6 светодиодов снизу для представления минут (0-59). Каждый светодиод представляет ноль или единицу, при этом младший разряд находится справа.

Пример:

Input: turnedOn = 1
Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

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

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

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

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

😎 Решение:

class Solution {
    func readBinaryWatch(_ turnedOn: Int) -> [String] {
        var results = [String]()
        for h in 0..<12 {
            for m in 0..<60 {
                if (h.nonzeroBitCount + m.nonzeroBitCount) == turnedOn {
                    results.append(String(format: "%d:%02d", h, m))
                }
            }
        }
        return results
    }
}

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

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

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