Задача: 411. Minimum Unique Word Abbreviation
Сложность: hard

Строку можно сократить, заменив любое количество не смежных подстрок их длинами. Например, строка "substitution" может быть сокращена как (но не ограничиваясь этим):

"s10n" ("s ubstitutio n") "sub4u4" ("sub stit u tion") "12" ("substitution") "su3i1u2on" ("su bst i t u ti on") "substitution" (без замен подстрок) Обратите внимание, что "s55n" ("s ubsti tutio n") не является правильным сокращением "substitution", поскольку замененные подстроки являются смежными.

Длина аббревиатуры - это количество букв, которые не были заменены, плюс количество подстрок, которые были заменены. Например, аббревиатура "s10n" имеет длину 3 (2 буквы + 1 подстрока), а "su3i1u2on" - 9 (6 букв + 3 подстроки). Учитывая целевую строку target и массив строк dictionary, верните аббревиатуру target с наименьшей возможной длиной, которая не является аббревиатурой ни одной строки в словаре. Если существует несколько самых коротких аббревиатур, верните любую из них.

Пример:

Input: target = "apple", dictionary = ["blade"]
Output: "a4"

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

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

2⃣Сгенерируйте все возможные аббревиатуры для строки target.

3⃣Найдите самую короткую аббревиатуру для target, которая отсутствует в множестве аббревиатур словаря.

😎 Решение:

func generateAbbreviations(_ word: String) -> Set<String> {
    var result = Set<String>()
    generateAbbreviationsHelper(Array(word), "", 0, 0, &result)
    return result
}

func generateAbbreviationsHelper(_ word: [Character], _ current: String, _ pos: Int, _ count: Int, _ result: inout Set<String>) {
    if pos == word.count {
        result.insert(current + (count > 0 ? String(count) : ""))
        return
    }
    generateAbbreviationsHelper(word, current, pos + 1, count + 1, &result)
    generateAbbreviationsHelper(word, current + (count > 0 ? String(count) : "") + String(word[pos]), pos + 1, 0, &result)
}

func minAbbreviation(_ target: String, _ dictionary: [String]) -> String {
    let targetAbbrs = generateAbbreviations(target)
    var dictAbbrs = Set<String>()
    for word in dictionary {
        dictAbbrs.formUnion(generateAbbreviations(word))
    }
    let validAbbrs = targetAbbrs.subtracting(dictAbbrs)
    return validAbbrs.sorted(by: { $0.count < $1.count }).first!
}

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

Задача: 25. Reverse Nodes in k-Group
Сложность: hard

Учитывая заголовок связанного списка, поменяйте местами узлы списка k за раз и верните измененный список.

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

Вы не можете изменять значения в узлах списка, можно изменять только сами узлы.

Пример:

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

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

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

2⃣Используем фиктивный узел (dummy) для удобного управления указателями.

3⃣Переворачиваем группы по k узлов, изменяя связи в списке.

😎Решение:

class ListNode {
    var val: Int
    var next: ListNode?
    init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
    if head == nil || k == 1 {
        return head
    }
    
    let dummy = ListNode(0)
    dummy.next = head
    var current: ListNode? = dummy
    var next: ListNode?
    var prev: ListNode? = dummy
    
    var count = 0
    while current?.next != nil {
        current = current?.next
        count += 1
    }
    
    while count >= k {
        current = prev?.next
        next = current?.next
        for _ in 1..<k {
            current?.next = next?.next
            next?.next = prev?.next
            prev?.next = next
            next = current?.next
        }
        prev = current
        count -= k
    }
    
    return dummy.next
}

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

Задача: 1372. Longest ZigZag Path in a Binary Tree
Сложность: medium

Вам дан корень бинарного дерева.

Зигзагообразный путь для бинарного дерева определяется следующим образом:

Выберите любой узел в бинарном дереве и направление (вправо или влево).
Если текущее направление вправо, перейдите к правому дочернему узлу текущего узла; иначе перейдите к левому дочернему узлу.
Измените направление с вправо на влево или с влево на вправо.
Повторяйте второй и третий шаги, пока не сможете двигаться по дереву.
Длина зигзагообразного пути определяется как количество посещенных узлов минус 1 (один узел имеет длину 0).

Верните длину самого длинного зигзагообразного пути, содержащегося в этом дереве.

Пример:

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

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

1⃣Рекурсивная функция DFS:
Создайте рекурсивную функцию dfs, которая будет выполнять обход дерева и отслеживать текущую длину зигзагообразного пути и направление движения (влево или вправо).

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

3⃣Рекурсивный вызов для левого и правого дочерних узлов:
Рекурсивно вызывайте функцию dfs для левого и правого дочерних узлов с обновленными параметрами длины и направления.

😎 Решение:

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 {
    var maxLength = 0

    func longestZigZag(_ root: TreeNode?) -> Int {
        dfs(root, true, 0)
        dfs(root, false, 0)
        return maxLength
    }

    func dfs(_ node: TreeNode?, _ isLeft: Bool, _ length: Int) {
        guard let node = node else { return }
        maxLength = max(maxLength, length)
        if isLeft {
            dfs(node.left, false, length + 1)
            dfs(node.right, true, 1)
        } else {
            dfs(node.right, true, length + 1)
            dfs(node.left, false, 1)
        }
    }
}

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

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

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

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

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

Задача: 1512. Number of Good Pairs
Сложность: easy

Дан массив целых чисел nums, верните количество хороших пар.

Пара (i, j) называется хорошей, если nums[i] == nums[j] и i < j.

Пример:

Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.

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

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

2⃣Итерируйте i от 0 до nums.length:
Итерируйте j от i + 1 до nums.length:
Если nums[i] == nums[j], увеличьте ans на 1.

3⃣Верните ans.

😎 Решение

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

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

Задача: 403. Frog Jump
Сложность: hard

Если задана строка num, представляющая неотрицательное целое число num, и целое число k, верните наименьшее возможное целое число после удаления k цифр из num.

Пример:

Input: stones = [0,1,3,5,6,8,12,17]
Output: true

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

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

2⃣Итерация по камням
Пройдитесь по каждому камню и для каждого возможного прыжка (k-1, k, k+1) проверьте, если он ведет на существующий камень.
Если такой камень существует, добавьте его в набор возможных прыжков.

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

😎 Решение:

class Solution {
    func canCross(_ stones: [Int]) -> Bool {
        var dp = [Int: Set<Int>]()
        for stone in stones {
            dp[stone] = Set<Int>()
        }
        dp[0]?.insert(0)
        
        for stone in stones {
            for jump in dp[stone]! {
                for step in jump - 1...jump + 1 {
                    if step > 0, let _ = dp[stone + step] {
                        dp[stone + step]?.insert(step)
                    }
                }
            }
        }
        
        return !(dp[stones.last!]!.isEmpty)
    }
}

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

Задача: 632. Smallest Range Covering Elements from K Lists
Сложность: hard

У вас есть k списков отсортированных целых чисел в неубывающем порядке. Найдите наименьший диапазон, в который входит хотя бы одно число из каждого из k списков. Мы определяем, что диапазон [a, b] меньше диапазона [c, d], если b - a < d - c или a < c, если b - a == d - c.

Пример:

Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20,24]

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

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

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

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

😎 Решение:

import Foundation

struct Element: Comparable {
    let value: Int
    let row: Int
    let col: Int
    
    static func < (lhs: Element, rhs: Element) -> Bool {
        return lhs.value < rhs.value
    }
}

class Solution {
    func smallestRange(_ nums: [[Int]]) -> [Int] {
        var minHeap = [Element]()
        var maxValue = Int.min
        
        for i in 0..<nums.count {
            let element = Element(value: nums[i][0], row: i, col: 0)
            minHeap.append(element)
            maxValue = max(maxValue, nums[i][0])
        }
        
        minHeap.sort()
        
        var rangeStart = 0
        var rangeEnd = Int.max
        
        while minHeap.count == nums.count {
            let minElement = minHeap.removeFirst()
            if maxValue - minElement.value < rangeEnd - rangeStart {
                rangeStart = minElement.value
                rangeEnd = maxValue
            }
            
            if minElement.col + 1 < nums[minElement.row].count {
                let newValue = nums[minElement.row][minElement.col + 1]
                let newElement = Element(value: newValue, row: minElement.row, col: minElement.col + 1)
                minHeap.append(newElement)
                maxValue = max(maxValue, newValue)
                minHeap.sort()
            }
        }
        
        return [rangeStart, rangeEnd]
    }
}

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

Задача: 711. Number of Distinct Islands II
Сложность: hard

Вам дана двоичная матричная сетка m x n. Остров - это группа 1 (представляющая сушу), соединенных в четырех направлениях (горизонтальном или вертикальном). Можно предположить, что все четыре края сетки окружены водой. Остров считается одинаковым с другим, если они имеют одинаковую форму, или имеют одинаковую форму после поворота (только на 90, 180 или 270 градусов) или отражения (влево/вправо или вверх/вниз). Верните количество разных островов.

Пример:

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

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

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

2⃣Нормализуйте форму острова, применив все возможные повороты и отражения, чтобы найти каноническую форму.

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

😎 Решение:

class Solution {
    func numDistinctIslands2(_ grid: [[Int]]) -> Int {
        var grid = grid
        var uniqueIslands = Set<[[(Int, Int)]]>()
        
        func dfs(_ i: Int, _ j: Int) -> [(Int, Int)] {
            var shape = [(Int, Int)]()
            var stack = [(i, j)]
            while !stack.isEmpty {
                let (x, y) = stack.removeLast()
                if x >= 0 && x < grid.count && y >= 0 && y < grid[0].count && grid[x][y] == 1 {
                    grid[x][y] = 0
                    shape.append((x - i, y - j))
                    stack.append((x + 1, y))
                    stack.append((x - 1, y))
                    stack.append((x, y + 1))
                    stack.append((x, y - 1))
                }
            }
            return shape
        }
        
        func normalize(_ shape: [(Int, Int)]) -> [[(Int, Int)]] {
            var shapes = Array(repeating: [(Int, Int)](), count: 8)
            for (x, y) in shape {
                shapes[0].append((x, y))
                shapes[1].append((x, -y))
                shapes[2].append((-x, y))
                shapes[3].append((-x, -y))
                shapes[4].append((y, x))
                shapes[5].append((y, -x))
                shapes[6].append((-y, x))
                shapes[7].append((-y, -x))
            }
            for i in 0..<8 {
                shapes[i].sort(by: { $0.0 == $1.0 ? $0.1 < $1.1 : $0.0 < $1.0 })
            }
            return shapes
        }
        
        for i in 0..<grid.count {
            for j in 0..<grid[0].count {
                if grid[i][j] == 1 {
                    let shape = dfs(i, j)
                    let normalizedShape = normalize(shape)
                    if let minShape = normalizedShape.min(by: { $0.lexicographicallyPrecedes($1) }) {
                        uniqueIslands.insert(minShape)
                    }
                }
            }
        }
        
        return uniqueIslands.count
    }
}

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

Задача: 566. Reshape the Matrix
Сложность: easy

В MATLAB есть удобная функция под названием reshape, которая может преобразовать матрицу размером m x n в новую матрицу с другим размером r x c, сохраняя исходные данные.

Вам дана матрица m x n mat и два целых числа r и c, представляющие количество строк и столбцов желаемой преобразованной матрицы.

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

Если операция преобразования с заданными параметрами возможна и допустима, выведите новую преобразованную матрицу; в противном случае выведите исходную матрицу.

Пример:

Input: mat = [[1,2],[3,4]], r = 1, c = 4
Output: [[1,2,3,4]]

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

1⃣Проверить, можно ли преобразовать матрицу с заданными параметрами r и c. Это возможно, если произведение m * n равно произведению r * c. Если преобразование невозможно, вернуть исходную матрицу.

2⃣Создать новый массив для хранения преобразованной матрицы. Перебрать все элементы исходной матрицы и вставить их в новый массив в порядке обхода строк.

3⃣Вернуть преобразованную матрицу, если преобразование возможно, иначе вернуть исходную матрицу.

😎 Решение:

class Solution {
    func matrixReshape(_ mat: [[Int]], _ r: Int, _ c: Int) -> [[Int]] {
        let m = mat.count
        let n = mat[0].count
        if m * n != r * c {
            return mat
        }
        var reshapedMatrix = Array(repeating: Array(repeating: 0, count: c), count: r)
        var row = 0
        var col = 0
        for i in 0..<m {
            for j in 0..<n {
                reshapedMatrix[row][col] = mat[i][j]
                col += 1
                if col == c {
                    col = 0
                    row += 1
                }
            }
        }
        return reshapedMatrix
    }
}

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

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

Ты поднимаешься по лестнице. Чтобы добраться до вершины, нужно преодолеть n ступенек.

Каждый раз ты можешь подняться на 1 или 2 ступеньки. Сколькими различными способами ты можешь добраться до вершины?

Пример:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

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

1⃣В этом методе грубой силы мы рассматриваем все возможные комбинации шагов, то есть 1 и 2, на каждом шаге.

2⃣На каждом шаге мы вызываем функцию climbStairs для шага 1 и шага 2, и возвращаем сумму возвращаемых значений обеих функций.

3⃣Формула вызова функции: climbStairs(i, n) = climbStairs(i+1, n) + climbStairs(i+2, n), где i определяет текущий шаг, а n — целевой шаг.

😎 Решение:

func climbStairs(_ n: Int) -> Int {
    return climbStairsHelper(0, n)
}

func climbStairsHelper(_ i: Int, _ n: Int) -> Int {
    if i > n {
        return 0
    }
    if i == n {
        return 1
    }
    return climbStairsHelper(i + 1, n) + climbStairsHelper(i + 2, n)
}

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

Задача: 1502. Can Make Arithmetic Progression From Sequence
Сложность: easy

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

Дан массив чисел arr, верните true, если массив можно переставить так, чтобы он образовал арифметическую прогрессию. В противном случае верните false.

Пример:

Input: arr = [3,5,1]
Output: true
Explanation: We can reorder the elements as [1,3,5] or [5,3,1] with differences 2 and -2 respectively, between each consecutive elements.

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

1⃣Отсортируйте массив arr.

2⃣Запишите разницу первой пары элементов: diff = arr[1] - arr[0].

3⃣Итерируйтесь по отсортированному массиву начиная с i = 2, проверяя, равна ли разница каждой пары элементов значению diff. Если нет, верните False. Если итерация завершена без нахождения различий, верните True.

😎 Решение

class Solution {
    func canMakeArithmeticProgression(_ arr: [Int]) -> Bool {
        let arr = arr.sorted()
        let diff = arr[1] - arr[0]
        
        for i in 2..<arr.count {
            if arr[i] - arr[i - 1] != diff {
                return false
            }
        }
        
        return true
    }
}

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

Задача: 525. Contiguous Array
Сложность: medium

Дан бинарный массив nums. Верните максимальную длину непрерывного подмассива с равным количеством 0 и 1.

Пример:

Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.

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

1⃣Инициализируйте переменную count для отслеживания разности между количеством 1 и 0, и переменную max_length для хранения максимальной длины подмассива. Создайте хеш-таблицу map для хранения первых встреч каждого значения count. Добавьте начальное значение (0, -1) в хеш-таблицу.

2⃣Итеративно пройдите по массиву nums. На каждой итерации обновляйте значение count (увеличивайте на 1 для 1 и уменьшайте на 1 для 0). Если текущее значение count уже существует в хеш-таблице, вычислите длину подмассива между текущим индексом и индексом из хеш-таблицы. Обновите max_length, если текущий подмассив длиннее.

3⃣Если текущее значение count не существует в хеш-таблице, добавьте его с текущим индексом. После завершения итерации верните max_length.

😎 Решение:

class Solution {
    func findMaxLength(_ nums: [Int]) -> Int {
        var countMap: [Int: Int] = [0: -1]
        var maxLength = 0
        var count = 0
        
        for i in 0..<nums.count {
            count += (nums[i] == 1 ? 1 : -1)
            
            if let prevIndex = countMap[count] {
                maxLength = max(maxLength, i - prevIndex)
            } else {
                countMap[count] = i
            }
        }
        
        return maxLength
    }
}

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

Задача: 1074. Number of Submatrices That Sum to Target
Сложность: hard

Дана матрица и целевое значение. Верните количество непустых подматриц, сумма элементов которых равна целевому значению.

Подматрица x1, y1, x2, y2 — это набор всех ячеек matrix[x][y] с x1 <= x <= x2 и y1 <= y <= y2.

Две подматрицы (x1, y1, x2, y2) и (x1', y1', x2', y2') различны, если у них есть какая-то различающаяся координата: например, если x1 != x1'.

Пример:

Input: matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
Output: 4
Explanation: The four 1x1 submatrices that only contain 0.

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

1⃣Инициализируйте результат: count = 0. Вычислите количество строк: r = len(matrix) и количество столбцов: c = len(matrix[0]). Вычислите двумерную префиксную сумму ps, выделив еще одну строку и еще один столбец для нулевых значений.

2⃣Итерируйте по строкам: r1 от 1 до r и r2 от r1 до r. Внутри этого двойного цикла фиксируйте левые и правые границы строк и инициализируйте хэш-таблицу для хранения префиксных сумм. Итерируйте по столбцам от 1 до c + 1, вычислите текущую префиксную сумму 1D curr_sum и увеличьте count на количество матриц, сумма которых равна target.

3⃣Добавьте текущую префиксную сумму 1D в хэш-таблицу. Когда все итерации завершены, верните count.

😎 Решение:

class Solution {
    func numSubmatrixSumTarget(_ matrix: [[Int]], _ target: Int) -> Int {
        let r = matrix.count, c = matrix[0].count
        var ps = Array(repeating: Array(repeating: 0, count: c + 1), count: r + 1)
        
        for i in 1...r {
            for j in 1...c {
                ps[i][j] = ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1] + matrix[i - 1][j - 1]
            }
        }
        
        var count = 0
        var currSum: Int
        var h = [Int: Int]()
        
        for r1 in 1...r {
            for r2 in r1...r {
                h.removeAll()
                h[0] = 1
                for col in 1...c {
                    currSum = ps[r2][col] - ps[r1 - 1][col]
                    count += h[currSum - target, default: 0]
                    h[currSum, default: 0] += 1
                }
            }
        }
        
        return count
    }
}

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

Задача: 1006. Clumsy Factorial
Сложность: medium

Факториал целого положительного числа n - это произведение всех целых положительных чисел, меньших или равных n. Например, факториал(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1.
Мы составляем неуклюжий факториал, используя целые числа в порядке убывания, заменяя операции умножения на фиксированную последовательность операций с умножением "*", делением "/", сложением "+" и вычитанием "-" в этом порядке. Например, clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1. Однако эти операции по-прежнему применяются с использованием обычного порядка операций арифметики. Мы выполняем все шаги умножения и деления перед шагами сложения и вычитания, а шаги умножения и деления выполняются слева направо. Кроме того, деление, которое мы используем, является делением с полом, так что 10 * 9 / 8 = 90 / 8 = 11. Учитывая целое число n, верните неуклюжий факториал n.

Пример:

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

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

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

2⃣Выполнение операций в цикле:
Создайте цикл, который будет обрабатывать числа от n до 1 в порядке убывания.
В цикле выполняйте операции *, /, +, и - последовательно.
Обновляйте текущий результат на каждом шаге в зависимости от остатка от деления текущего индекса на 4.

3⃣Учет оставшихся операций и возврат результата:
После завершения цикла добавьте или вычтите оставшиеся числа (если есть) к результату.
Верните окончательный результат.

😎 Решение:

class Solution {
    func clumsy(_ n: Int) -> Int {
        if n == 0 { return 0 }
        if n == 1 { return 1 }
        if n == 2 { return 2 * 1 }
        if n == 3 { return 3 * 2 / 1 }
        
        var res = n * (n - 1) / (n - 2)
        var n = n - 3
        if n > 0 { res += n }
        n -= 1
        
        while n > 0 {
            res -= n * (n - 1) / (n - 2)
            n -= 3
            if n > 0 { res += n }
            n -= 1
        }
        
        return res
    }
}

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

Задача: 926. Flip String to Monotone Increasing
Сложность: medium

Двоичная строка является монотонно возрастающей, если она состоит из некоторого количества 0 (возможно, ни одного), за которым следует некоторое количество 1 (также возможно, ни одного). Вам дана двоичная строка s. Вы можете перевернуть s[i], изменив ее значение с 0 на 1 или с 1 на 0.

Пример:

Input: s = "00110"
Output: 1

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

1⃣Создать массив left для подсчета количества операций, чтобы сделать подстроку до текущего индекса монотонной (только 0).

2⃣Создать массив right для подсчета количества операций, чтобы сделать подстроку после текущего индекса монотонной (только 1).
Пройти по строке и заполнить массивы left и right.

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

😎 Решение:

class Solution {
    func minFlipsMonoIncr(_ s: String) -> Int {
        let n = s.count
        var left = [Int](repeating: 0, count: n + 1)
        var right = [Int](repeating: 0, count: n + 1)
        let sArray = Array(s)
        
        for i in 0..<n {
            left[i + 1] = left[i] + (sArray[i] == "1" ? 1 : 0)
        }
        
        for i in (0..<n).reversed() {
            right[i] = right[i + 1] + (sArray[i] == "0" ? 1 : 0)
        }
        
        var result = Int.max
        for i in 0...n {
            result = min(result, left[i] + right[i])
        }
        return result
    }
}

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

Задача: 1533. Find the Index of the Large Integer
Сложность: medium

У нас есть целочисленный массив arr, в котором все элементы равны, кроме одного элемента, который больше остальных. Вам не будет предоставлен прямой доступ к массиву, вместо этого у вас будет API ArrayReader, который имеет следующие функции:

int compareSub(int l, int r, int x, int y): где 0 <= l, r, x, y < ArrayReader.length(), l <= r и x <= y. Функция сравнивает сумму подмассива arr[l..r] с суммой подмассива arr[x..y] и возвращает:
1, если arr[l] + arr[l+1] + ... + arr[r] > arr[x] + arr[x+1] + ... + arr[y].
0, если arr[l] + arr[l+1] + ... + arr[r] == arr[x] + arr[x+1] + ... + arr[y].
-1, если arr[l] + arr[l+1] + ... + arr[r] < arr[x] + arr[x+1] + ... + arr[y].

int length(): Возвращает размер массива.

Вам разрешено вызывать compareSub() не более 20 раз. Вы можете предположить, что обе функции работают за O(1) время.

Верните индекс массива arr, который содержит наибольший элемент.

Пример:

Input: arr = [7,7,7,7,10,7,7,7]
Output: 4
Explanation: The following calls to the API
reader.compareSub(0, 0, 1, 1) // returns 0 this is a query comparing the sub-array (0, 0) with the sub array (1, 1), (i.e. compares arr[0] with arr[1]).
Thus we know that arr[0] and arr[1] doesn't contain the largest element.
reader.compareSub(2, 2, 3, 3) // returns 0, we can exclude arr[2] and arr[3].
reader.compareSub(4, 4, 5, 5) // returns 1, thus for sure arr[4] is the largest element in the array.
Notice that we made only 3 calls, so the answer is valid.

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

1⃣Установите left = 0 и length = reader.length. left - это самый левый индекс нашего поискового пространства, а length - это размер нашего поискового пространства. Индекс большего числа всегда должен находиться в пределах [left, left + length).

2⃣Пока length > 1:
— Обновите length до length / 2.
— Установите cmp равным reader.compareSub(left, left + length - 1, left + length, left + length + length - 1).
— Если cmp равно 0, верните left + length + length, так как оставшийся элемент является большим числом. Это возможно только если текущее поисковое пространство имеет нечетную длину, поэтому если у нас четная длина, мы не беспокоимся об этом случае.
— Если cmp равно -1, увеличьте left на length.
— Если cmp равно 1, ничего не делайте, так как наш left остается прежним и мы уже разделили length на 2.

3⃣Верните left. Это стандартная процедура для бинарного поиска, когда если поиск завершается без возврата, то левая граница указывает на ответ.

😎 Решение

class Solution {
    func getIndex(_ reader: ArrayReader) -> Int {
        var left = 0
        var length = reader.length()
        while length > 1 {
            length /= 2
            let cmp = reader.compareSub(left, left + length - 1, left + length, left + 2 * length - 1)
            if cmp == 0 {
                return left + 2 * length
            }
            if cmp < 0 {
                left += length
            }
        }
        return left
    }
}

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

Задача: 929. Unique Email Addresses
Сложность: easy

Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом.

Пример:

Input: emails = ["[email protected]","[email protected]","[email protected]"]
Output: 2

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

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

2⃣Для каждого адреса в emails:
Разделить адрес на локальное и доменное имя по символу '@'.
Обработать локальное имя:
Удалить все точки '.'.
Обрезать часть после символа '+'.
Объединить обработанное локальное имя и доменное имя.
Добавить результат в множество уникальных адресов.

3⃣Вернуть количество уникальных адресов в множестве.

😎 Решение:

class Solution {
    func numUniqueEmails(_ emails: [String]) -> Int {
        var uniqueEmails = Set<String>()
        for email in emails {
            let parts = email.split(separator: "@")
            var local = parts[0].split(separator: "+")[0].replacingOccurrences(of: ".", with: "")
            uniqueEmails.insert("\(local)@\(parts[1])")
        }
        return uniqueEmails.count
    }
}

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

Задача: 753. Cracking the Safe
Сложность: medium

Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно.
После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода.

Пример:

Input: n = 1, k = 2
Output: "10"

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

1⃣Создайте граф, где каждая вершина представляет собой строку длины n-1, а каждое ребро между двумя вершинами представляет собой добавление одной из цифр из диапазона [0, k-1].

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

3⃣Составьте итоговую строку, которая включает начальную вершину и все добавленные цифры.

😎 Решение:

func crackSafe(_ n: Int, _ k: Int) -> String {
    var seen = Set<String>()
    var result = [Character]()

    func dfs(_ node: String) {
        for x in 0..<k {
            let neighbor = node + String(x)
            if !seen.contains(neighbor) {
                seen.insert(neighbor)
                dfs(String(neighbor.dropFirst()))
                result.append(Character(String(x)))
            }
        }
    }

    let startNode = String(repeating: "0", count: n - 1)
    dfs(startNode)
    return startNode + String(result)
}

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

Задача: 237. Delete Node in a Linked List
Сложность: medium

Дан односвязный список с головой head, и требуется удалить узел node в этом списке.

Вам дан узел node, который нужно удалить. У вас нет доступа к первому узлу head.

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

Удалите данный узел. Обратите внимание, что под удалением узла мы не подразумеваем его удаление из памяти. Мы имеем в виду:

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

Пример:

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

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

1⃣Копирование данных: Скопируйте значение из следующего узла (node.next) в текущий узел (node). Таким образом, текущий узел будет иметь значение, которое было в следующем узле.

2⃣Обновление указателя: Обновите указатель next текущего узла, чтобы он ссылался на узел, следующий за узлом node.next. Это effectively удалит следующий узел из списка.

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

😎 Решение:

class Solution {
    func deleteNode(_ node: ListNode?) {
        node?.val = node?.next?.val ?? 0
        node?.next = node?.next?.next
    }
}

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

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

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

Если нет общего временного слота, который удовлетворяет требованиям, верните пустой массив.

Формат временного слота — это массив из двух элементов [start, end], представляющий инклюзивный временной диапазон от start до end.

Гарантируется, что никакие два доступных временных слота одного и того же человека не пересекаются друг с другом. То есть для любых двух временных слотов [start1, end1] и [start2, end2] одного и того же человека либо start1 > end2, либо start2 > end1.

Пример:

Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8
Output: [60,68]

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

1⃣Отсортируйте оба массива slots1 и slots2 по времени начала.

2⃣Инициализируйте два указателя, указывающие на начало slots1 и slots2 соответственно.

3⃣Перебирайте, пока указатель1 не достигнет конца slots1 или указатель2 не достигнет конца slots2:
Найдите общий слот между slots1[pointer1] и slots2[pointer2].
Если общий слот больше или равен duration, верните результат.
В противном случае найдите слот, который заканчивается раньше, и передвиньте указатель.
Если общий слот не найден, верните пустой массив.

😎 Решение:

class Solution {
    func minAvailableDuration(_ slots1: [[Int]], _ slots2: [[Int]], _ duration: Int) -> [Int] {
        let slots1 = slots1.sorted { $0[0] < $1[0] }
        let slots2 = slots2.sorted { $0[0] < $1[0] }
        
        var pointer1 = 0
        var pointer2 = 0
        
        while pointer1 < slots1.count && pointer2 < slots2.count {
            let intersectLeft = max(slots1[pointer1][0], slots2[pointer2][0])
            let intersectRight = min(slots1[pointer1][1], slots2[pointer2][1])
            
            if intersectRight - intersectLeft >= duration {
                return [intersectLeft, intersectLeft + duration]
            }
            
            if slots1[pointer1][1] < slots2[pointer2][1] {
                pointer1 += 1
            } else {
                pointer2 += 1
            }
        }
        return []
    }
}

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