Задача: 1219. Path with Maximum Gold
Сложность: medium

В золотом руднике размером m x n каждая ячейка содержит целое число, представляющее количество золота в этой ячейке, или 0, если она пуста.

Верните максимальное количество золота, которое вы можете собрать при следующих условиях:
- Каждый раз, когда вы находитесь в ячейке, вы собираете всё золото из этой ячейки.
- Из вашей позиции вы можете сделать один шаг влево, вправо, вверх или вниз.
- Вы не можете посещать одну и ту же ячейку более одного раза.
- Никогда не посещайте ячейку с 0 золотом.
- Вы можете начинать и прекращать сбор золота с любой позиции в сетке, которая содержит золото.

Пример:

Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
 [5,8,7],
 [0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.

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

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

2⃣Функция DFS и обратный трек:
Реализуйте функцию dfsBacktrack для поиска пути с максимальным золотом с помощью DFS и обратного трека.
Обрабатывайте базовый случай, проверяя выход за пределы сетки или ячейки без золота.
Пометьте текущую ячейку как посещённую и сохраните её значение.
Исследуйте каждую из четырёх смежных ячеек и обновите максимальное количество золота, если найден лучший путь.
Сбросьте текущую ячейку до её исходного значения для дальнейших исследований.

3⃣Поиск максимального золота:
Используйте вложенные циклы для каждой ячейки в сетке, чтобы найти максимальное количество золота, начиная с этой ячейки, с помощью функции dfsBacktrack.
Обновите maxGold при нахождении лучшего пути.
Верните maxGold.

😎 Решение:

class Solution {
    let directions = [0, 1, 0, -1, 0]

    func getMaximumGold(_ grid: [[Int]]) -> Int {
        var grid = grid
        let rows = grid.count
        let cols = grid[0].count
        var maxGold = 0

        for row in 0..<rows {
            for col in 0..<cols {
                maxGold = max(maxGold, dfsBacktrack(&grid, rows, cols, row, col))
            }
        }
        return maxGold
    }

    func dfsBacktrack(_ grid: inout [[Int]], _ rows: Int, _ cols: Int, _ row: Int, _ col: Int) -> Int {
        if row < 0 || col < 0 || row >= rows || col >= cols || grid[row][col] == 0 {
            return 0
        }
        let originalVal = grid[row][col]
        grid[row][col] = 0
        var maxGold = 0

        for i in 0..<4 {
            maxGold = max(maxGold, dfsBacktrack(&grid, rows, cols, row + directions[i], col + directions[i + 1]))
        }

        grid[row][col] = originalVal
        return maxGold + originalVal
    }
}

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

Задача: 1273. Delete Tree Nodes
Сложность: medium

Дерево, укорененное в узле 0, задано следующим образом: количество узлов - nodes; значение i-го узла - value[i]; родитель i-го узла - parent[i]. Удалите все поддеревья, сумма значений узлов которых равна нулю. Верните количество оставшихся узлов в дереве.

Пример:

Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]
Output: 2

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

1⃣Постройте дерево из заданных узлов, значений и родителей.

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

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

😎 Решение:

class Solution {
    func deleteTreeNodes(_ nodes: Int, _ parent: [Int], _ value: [Int]) -> Int {
        var tree = [Int: [Int]]()
        for i in 0..<nodes {
            tree[parent[i], default: []].append(i)
        }

        func dfs(_ node: Int) -> (Int, Int) {
            var totalSum = value[node]
            var totalCount = 1
            if let children = tree[node] {
                for child in children {
                    let (childSum, childCount) = dfs(child)
                    totalSum += childSum
                    totalCount += childCount
                }
            }
            return totalSum == 0 ? (0, 0) : (totalSum, totalCount)
        }

        return dfs(0).1
    }
}

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

Задача: 422. Valid Word Square
Сложность: easy

Дан массив строк words, верните true, если он образует правильный квадрат слов.

Последовательность строк образует правильный квадрат слов, если k-я строка и k-й столбец читаются одинаково, где 0 <= k < max(numRows, numColumns).

Пример:

Input: words = ["abcd","bnrt","crmy","dtye"]
Output: true
Explanation:
The 1st row and 1st column both read "abcd".
The 2nd row and 2nd column both read "bnrt".
The 3rd row and 3rd column both read "crmy".
The 4th row and 4th column both read "dtye".
Therefore, it is a valid word square.

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

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

2⃣Итерация по массиву words, определение максимальной длины слова для cols, проверка, что количество строк равно количеству столбцов. Если условие не выполняется, возвращаем false.

3⃣Для каждого столбца col от 0 до cols - 1, формируем строку newWord из символов на позиции (row, col) для каждой строки. Сохраняем newWord в массиве newWords. В конце, если newWords и words равны, возвращаем true, иначе false.

😎 Решение:

class Solution {
    func validWordSquare(_ words: [String]) -> Bool {
        var cols = 0
        let rows = words.count
        var newWords = [String]()
        
        for word in words {
            cols = max(cols, word.count)
        }

        if cols != words[0].count || rows != cols {
            return false
        }

        for col in 0..<cols {
            var newWord = ""
            for row in 0..<rows {
                if col < words[row].count {
                    newWord.append(words[row][words[row].index(words[row].startIndex, offsetBy: col)])
                }
            }
            newWords.append(newWord)
        }

        return words == newWords
    }
}

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

Задача: 1382. Balance a Binary Search Tree
Сложность: medium

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

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

Пример:

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2] is also correct.

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

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

2⃣Выполнение обхода в порядке возрастания. Обойдите бинарное дерево поиска (BST) и заполните список inorder значениями узлов в отсортированном порядке.

3⃣Перестроение сбалансированного BST. Определите рекурсивную функцию createBalancedBST, которая принимает список inorder, начальный индекс и конечный индекс в качестве параметров. Если начальный индекс больше конечного, верните null (или эквивалент). Вычислите средний индекс как середину текущего диапазона. Создайте новый узел дерева со значением в среднем индексе. Рекурсивно создайте левое поддерево, используя левую половину текущего диапазона. Рекурсивно создайте правое поддерево, используя правую половину текущего диапазона. Верните корень вновь построенного сбалансированного BST.

😎 Решение:

class Solution {
    func balanceBST(_ root: TreeNode?) -> TreeNode? {
        if root == nil { return nil }

        let vineHead = TreeNode(0)
        vineHead.right = root
        var current: TreeNode? = vineHead

        while current?.right != nil {
            if current?.right?.left != nil {
                rightRotate(current, current?.right)
            } else {
                current = current?.right
            }
        }

        var nodeCount = 0
        current = vineHead.right
        while current != nil {
            nodeCount += 1
            current = current?.right
        }

        var m = Int(pow(2.0, floor(log2(Double(nodeCount + 1))))) - 1
        makeRotations(vineHead, nodeCount - m)
        while m > 1 {
            m /= 2
            makeRotations(vineHead, m)
        }

        let balancedRoot = vineHead.right
        return balancedRoot
    }

    private func rightRotate(_ parent: TreeNode?, _ node: TreeNode?) {
        let tmp = node?.left
        node?.left = tmp?.right
        tmp?.right = node
        parent?.right = tmp
    }

    private func leftRotate(_ parent: TreeNode?, _ node: TreeNode?) {
        let tmp = node?.right
        node?.right = tmp?.left
        tmp?.left = node
        parent?.right = tmp
    }

    private func makeRotations(_ vineHead: TreeNode?, _ count: Int) {
        var current = vineHead
        for _ in 0..<count {
            let tmp = current?.right
            leftRotate(current, tmp)
            current = current?.right
        }
    }
}

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

Задача: 84. Largest Rectangle in Histogram
Сложность: hard

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

Пример:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

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

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

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

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

😎 Решение:

func largestRectangleArea(_ heights: [Int]) -> Int {
    var maxArea = 0
    for i in 0..<heights.count {
        for j in i..<heights.count {
            var minHeight = Int.max
            for k in i...j {
                minHeight = min(minHeight, heights[k])
            }
            maxArea = max(maxArea, minHeight * (j - i + 1))
        }
    }
    return maxArea
}

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

Задача: 921. Minimum Add to Make Parentheses Valid
Сложность: medium

Строка со скобками допустима тогда и только тогда, когда: это пустая строка, ее можно записать как AB (A, совмещенное с B), где A и B - допустимые строки, или ее можно записать как (A), где A - допустимая строка. Вам дана строка s со скобками. За один ход вы можете вставить скобку в любую позицию строки. Например, если s = "()))", вы можете вставить открывающую скобку в виде "(()))" или закрывающую скобку в виде "())))". Верните минимальное количество ходов, необходимое для того, чтобы сделать s допустимой.

Пример:

Input: n = 3, goal = 3, k = 1
Output: 6

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

1⃣Инициализировать два счетчика open_needed и close_needed.

2⃣Пройти по строке s символ за символом:
Если текущий символ - открывающая скобка (, увеличьте open_needed.
Если текущий символ - закрывающая скобка ), проверьте:
Если open_needed больше 0, уменьшите open_needed.
Иначе увеличьте close_needed.

3⃣Суммируйте значения open_needed и close_needed, чтобы получить минимальное количество вставок.

😎 Решение:

class Solution {
    func minAddToMakeValid(_ s: String) -> Int {
        var openNeeded = 0
        var closeNeeded = 0
        
        for char in s {
            if char == "(" {
                openNeeded += 1
            } else if char == ")" {
                if openNeeded > 0 {
                    openNeeded -= 1
                } else {
                    closeNeeded += 1
                }
            }
        }
        return openNeeded + closeNeeded
    }
}

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

Задача: 26. Remove Duplicates from Sorted Array
Сложность: easy

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

Пример:

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

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

1⃣Используем указатель k для отслеживания позиции, куда вставлять уникальные элементы.

2⃣Проходим по массиву, начиная со второго элемента, и сравниваем с предыдущим.

3⃣Если элемент новый, записываем его на позицию k и увеличиваем k.

😎Решение:

func removeDuplicates(_ nums: inout [Int]) -> Int {
    if nums.isEmpty { return 0 }
    
    var k = 1
    
    for i in 1..<nums.count {
        if nums[i] != nums[k - 1] {
            nums[k] = nums[i]
            k += 1
        }
    }
    
    return k
}

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

Задача: 62. Unique Paths
Сложность: medium

На сетке размером m на n находится робот. Изначально робот расположен в верхнем левом углу (то есть, в клетке grid[0][0]). Робот пытается добраться до нижнего правого угла (то есть, в клетку grid[m - 1][n - 1]). Робот может двигаться только вниз или вправо в любой момент времени.

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

Тестовые случаи сгенерированы таким образом, что ответ будет меньше или равен 2 * 10^9.

Пример:

Input: m = 3, n = 7
Output: 28

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

1⃣Инициализировать двумерный массив d[m][n] = количество путей. Сначала установить количество путей равным 1 для первой строки и первого столбца. Для упрощения можно инициализировать весь двумерный массив единицами.

2⃣Проитерировать по всем "внутренним" ячейкам: d[col][row] = d[col - 1][row] + d[col][row - 1].

3⃣Вернуть d[m - 1][n - 1].

😎 Решение:

class Solution {
    func uniquePaths(_ m: Int, _ n: Int) -> Int {
        var d = Array(repeating: Array(repeating: 1, count: n), count: m)
        
        for col in 1..<m {
            for row in 1..<n {
                d[col][row] = d[col - 1][row] + d[col][row - 1]
            }
        }
        
        return d[m - 1][n - 1]
    }
}

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

Задача: 1008. Construct Binary Search Tree from Preorder Traversal
Сложность: medium

Дается массив целых чисел preorder, который представляет собой обход BST (т.е, гарантируется, что для заданных тестовых случаев всегда можно найти дерево двоичного поиска с заданными требованиями. Дерево двоичного поиска - это двоичное дерево, в котором для каждого узла любой потомок Node.left имеет значение строго меньше, чем Node.val, а любой потомок Node.right имеет значение строго больше, чем Node.val. При обходе бинарного дерева в предварительном порядке сначала выводится значение узла, затем обход Node.left, затем обход Node.right.

Пример:

Input: preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

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

1⃣Инициализация переменных и функций:
Создайте класс узла дерева TreeNode с атрибутами val, left и right.
Инициализируйте индекс, который будет отслеживать текущую позицию в массиве preorder.

2⃣Рекурсивная функция для построения дерева:
Создайте рекурсивную функцию constructBST с аргументами preorder, lower и upper, которые будут ограничивать значения узлов для текущей ветви дерева.
Если текущий индекс выходит за границы массива preorder, верните null.
Получите текущее значение из preorder и проверьте, находится ли оно в пределах допустимого диапазона [lower, upper]. Если нет, верните null.

3⃣Создание узла и рекурсивное построение поддеревьев:
Создайте новый узел с текущим значением и увеличьте индекс.
Рекурсивно вызовите функцию constructBST для создания левого поддерева с обновленным верхним пределом (upper равным значению текущего узла).
Рекурсивно вызовите функцию constructBST для создания правого поддерева с обновленным нижним пределом (lower равным значению текущего узла).
Верните созданный узел.

😎 Решение:

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}

class Solution {
    var index = 0
    
    func bstFromPreorder(_ preorder: [Int]) -> TreeNode? {
        return constructBST(preorder, Int.min, Int.max)
    }
    
    func constructBST(_ preorder: [Int], _ lower: Int, _ upper: Int) -> TreeNode? {
        if index == preorder.count {
            return nil
        }
        
        let val = preorder[index]
        if val < lower || val > upper {
            return nil
        }
        
        index += 1
        let root = TreeNode(val)
        root.left = constructBST(preorder, lower, val)
        root.right = constructBST(preorder, val, upper)
        return root
    }
}

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

Задача: 845. Longest Mountain in Array
Сложность: medium

Вы можете вспомнить, что массив arr является горным массивом тогда и только тогда, когда:
длина массива arr >= 3
Существует индекс i (счёт начинается с 0) такой, что:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Дан целочисленный массив arr, верните длину самой длинной подпоследовательности, которая является горной. Верните 0, если такой подпоследовательности нет.

Пример:

Input: arr = [2,1,4,7,3,2,5]
Output: 5
Explanation: The largest mountain is [1,4,7,3,2] which has length 5.

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

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

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

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

😎 Решение:

class Solution {
    func longestMountain(_ arr: [Int]) -> Int {
        let n = arr.count
        var ans = 0
        var base = 0

        while base < n {
            var end = base
            if end + 1 < n && arr[end] < arr[end + 1] {
                while end + 1 < n && arr[end] < arr[end + 1] {
                    end += 1
                }
                if end + 1 < n && arr[end] > arr[end + 1] {
                    while end + 1 < n && arr[end] > arr[end + 1] {
                        end += 1
                    }
                    ans = max(ans, end - base + 1)
                }
            }
            base = max(end, base + 1)
        }

        return ans
    }
}

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

Задача: 1535. Find the Winner of an Array Game
Сложность: medium

Дан целочисленный массив arr из различных целых чисел и целое число k.

Игра будет проводиться между первыми двумя элементами массива (т.е. arr[0] и arr[1]). В каждом раунде игры мы сравниваем arr[0] с arr[1], большее число побеждает и остается на позиции 0, а меньшее число перемещается в конец массива. Игра заканчивается, когда одно число выигрывает k подряд раундов.

Верните число, которое выиграет игру.

Гарантируется, что у игры будет победитель.

Пример:

Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
Explanation: Let's see the rounds of the game:
Round |       arr       | winner | win_count
  1   | [2,1,3,5,4,6,7] | 2      | 1
  2   | [2,3,5,4,6,7,1] | 3      | 1
  3   | [3,5,4,6,7,1,2] | 5      | 1
  4   | [5,4,6,7,1,2,3] | 5      | 2
So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.

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

1⃣Инициализируйте maxElement как максимальный элемент в arr, queue как очередь с элементами массива, кроме первого, curr = arr[0] и winstreak = 0.

2⃣Пока очередь не пуста (или используйте бесконечный цикл), извлеките opponent из начала очереди. Если curr > opponent, добавьте opponent в конец очереди и увеличьте winstreak на 1. В противном случае добавьте curr в конец очереди, установите curr = opponent и winstreak = 1.

3⃣Если winstreak = k или curr = maxElement, верните curr. Код никогда не должен достигать этой точки, так как гарантированно есть победитель. Верните любое значение.

😎 Решение

class Solution {
    func getWinner(_ arr: [Int], _ k: Int) -> Int {
        var maxElement = arr[0]
        var queue = Array(arr[1...])
        
        for element in arr[1...] {
            maxElement = max(maxElement, element)
        }
        
        var curr = arr[0]
        var winstreak = 0
        
        while !queue.isEmpty {
            let opponent = queue.removeFirst()
            
            if curr > opponent {
                queue.append(opponent)
                winstreak += 1
            } else {
                queue.append(curr)
                curr = opponent
                winstreak = 1
            }
            
            if winstreak == k || curr == maxElement {
                return curr
            }
        }
        
        return -1
    }
}

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

Задача: 917. Reverse Only Letters
Сложность: easy

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

Пример:

Input: s = "ab-cd"
Output: "dc-ba"

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

1️⃣Создать массив для хранения только английских букв из строки s.

2️⃣Перевернуть массив с английскими буквами.
Пройти по строке s и заменить каждую английскую букву на соответствующую из перевернутого массива.

3️⃣Вернуть результат.

😎 Решение:

class Solution {
    func reverseOnlyLetters(_ s: String) -> String {
        var letters = [Character]()
        for char in s {
            if char.isLetter {
                letters.append(char)
            }
        }
        letters.reverse()
        var result = [Character]()
        var idx = 0
        
        for char in s {
            if char.isLetter {
                result.append(letters[idx])
                idx += 1
            } else {
                result.append(char)
            }
        }
        
        return String(result)
    }
}

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

Задача: 108. Convert Sorted Array to Binary Search Tree
Сложность: easy

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

Пример:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

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

1⃣Инициализация функции помощника: Реализуйте функцию помощника helper(left, right), которая строит двоичное дерево поиска (BST) из элементов массива nums между индексами left и right.
Если left > right, это означает, что элементов для построения поддерева нет, возвращаем None.

2⃣Выбор корня и разделение массива:
Выберите элемент в середине для корня: p = (left + right) // 2.
Инициализируйте корень: root = TreeNode(nums[p]).

3⃣Рекурсивное построение поддеревьев:
Рекурсивно стройте левое поддерево: root.left = helper(left, p - 1).
Рекурсивно стройте правое поддерево: root.right = helper(p + 1, right).
В качестве результата возвращайте helper(0, len(nums) - 1), начиная с корня дерева.

😎 Решение:

class Solution {
    func sortedArrayToBST(_ nums: [Int]) -> TreeNode? {
        return helper(nums, 0, nums.count - 1)
    }
    
    private func helper(_ nums: [Int], _ left: Int, _ right: Int) -> TreeNode? {
        if left > right {
            return nil
        }
        let p = (left + right) / 2
        let root = TreeNode(nums[p])
        root.left = helper(nums, left, p - 1)
        root.right = helper(nums, p + 1, right)
        return root
    }
}

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

Задача: 838. Push Dominoes
Сложность: medium

Есть n домино, выстроенные в линию, и каждое домино стоит вертикально. Вначале мы одновременно толкаем некоторые домино либо влево, либо вправо.
Через каждую секунду каждое падающее влево домино толкает соседнее домино слева. Точно так же домино, падающие вправо, толкают соседние домино, стоящие справа.
Когда вертикальное домино оказывается под воздействием падающих домино с обеих сторон, оно остаётся неподвижным из-за баланса сил.

В рамках этой задачи мы будем считать, что падающее домино не передаёт дополнительную силу падающему или уже упавшему домино.
Вам дано строковое представление начального состояния домино:
dominoes[i] = 'L', если i-е домино толкнули влево,
dominoes[i] = 'R', если i-е домино толкнули вправо, и
dominoes[i] = '.', если i-е домино не было толкнуто.
Верните строку, представляющую конечное состояние.

Пример:

Input: dominoes = ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."

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

1⃣Пройдите по строке и сохраните индексы и символы не пустых домино в массивы.

2⃣Добавьте фиктивные домино 'L' в начале и 'R' в конце для упрощения логики.

3⃣Обработайте промежутки между соседними домино, обновляя их состояния согласно правилам.

😎 Решение:

class Solution {
    func pushDominoes(_ dominoes: String) -> String {
        let N = dominoes.count
        var indexes = [Int](-1)
        var symbols = [Character]("L")
        let domArray = Array(dominoes)
        
        for i in 0..<N {
            if domArray[i] != "." {
                indexes.append(i)
                symbols.append(domArray[i])
            }
        }
        
        indexes.append(N)
        symbols.append("R")
        
        var ans = Array(dominoes)
        for idx in 0..<indexes.count - 1 {
            let i = indexes[idx], j = indexes[idx + 1]
            let x = symbols[idx], y = symbols[idx + 1]
            if x == y {
                for k in (i + 1)..<j {
                    ans[k] = x
                }
            } else if x == "R" && y == "L" {
                for k in (i + 1)..<j {
                    if k - i == j - k {
                        ans[k] = "."
                    } else if k - i < j - k {
                        ans[k] = "R"
                    } else {
                        ans[k] = "L"
                    }
                }
            }
        }
        
        return String(ans)
    }
}

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

Задача: 1503. Last Moment Before All Ants Fall Out of a Plank
Сложность: medium

У нас есть деревянная доска длиной n единиц. Некоторые муравьи ходят по доске, каждый муравей движется со скоростью 1 единица в секунду. Некоторые муравьи движутся влево, другие движутся вправо.

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

Когда муравей достигает одного из концов доски в момент времени t, он сразу же падает с доски.

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

Пример:

Input: n = 4, left = [4,3], right = [0,1]
Output: 4
Explanation: In the image above:
-The ant at index 0 is named A and going to the right.
-The ant at index 1 is named B and going to the right.
-The ant at index 3 is named C and going to the left.
-The ant at index 4 is named D and going to the left.
The last moment when an ant was on the plank is t = 4 seconds. After that, it falls immediately out of the plank. (i.e., We can say that at t = 4.0000000001, there are no ants on the plank).

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

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

2⃣Итерация по массиву left и обновление ans значением num, если оно больше текущего значения ans.

3⃣Итерация по массиву right и обновление ans значением n - num, если оно больше текущего значения ans. Верните значение ans.

😎 Решение

class Solution {
    func getLastMoment(_ n: Int, _ left: [Int], _ right: [Int]) -> Int {
        var ans = 0
        for num in left {
            ans = max(ans, num)
        }
        for num in right {
            ans = max(ans, n - num)
        }
        return ans
    }
}

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

Задача: 1048. Longest String Chain
Сложность: easy

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

Например, "abc" является предшественником "abac", а "cba" не является предшественником "bcad". Цепочка слов - это последовательность слов [word1, word2, ..., wordk] с k >= 1, где word1 является предшественником word2, word2 является предшественником word3 и так далее. Одиночное слово тривиально является цепочкой слов с k == 1. Верните длину самой длинной возможной цепочки слов со словами, выбранными из заданного списка слов.

Пример:

Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4

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

1⃣Отсортируй список слов по длине.

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

3⃣Верни максимальную длину среди всех цепочек.

😎 Решение:

func longestStrChain(_ words: [String]) -> Int {
    let sortedWords = words.sorted { $0.count < $1.count }
    var dp = [String: Int]()
    var longestChain = 1
    
    for word in sortedWords {
        dp[word] = 1
        for i in word.indices {
            var predecessor = word
            predecessor.remove(at: i)
            if let count = dp[predecessor] {
                dp[word] = max(dp[word]!, count + 1)
            }
        }
        longestChain = max(longestChain, dp[word]!)
    }
    
    return longestChain
}

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

Задача: 1335. Minimum Difficulty of a Job Schedule
Сложность: hard

Вы хотите составить расписание списка заданий на d дней. Задания зависят друг от друга (т.е. чтобы выполнить задание i, вы должны закончить все задания j, где 0 <= j < i).

Вы должны выполнять как минимум одно задание каждый день. Сложность расписания заданий — это сумма сложностей каждого дня из d дней. Сложность дня — это максимальная сложность задания, выполненного в этот день.

Вам дан массив целых чисел jobDifficulty и целое число d. Сложность i-го задания равна jobDifficulty[i].

Верните минимальную сложность расписания заданий. Если вы не можете найти расписание для заданий, верните -1.

Пример:

Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7 

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

1⃣Определение состояния:
Индекс i (индекс первой задачи на сегодняшний день в массиве jobDifficulty) и день d (количество оставшихся дней) будут определять состояние динамического программирования. min_diff(i, d) обозначает минимальную сложность при начале с i-й задачи с оставшимися d днями. min_diff(0, d) будет окончательным ответом, так как он представляет начало с начала массива задач и завершение всех задач за ровно d дней.

2⃣Функция перехода состояния:
Задача с индексом j будет первой задачей на следующий день, следовательно, задачи, которые должны быть завершены сегодня, это все задачи с индексами между i и j, то есть jobDifficulty[i
]. Поскольку сложность дня — это максимальная сложность выполненной в этот день задачи, к сумме сложностей задач будет добавляться максимум из jobDifficulty[i
]. Формулируем функцию перехода состояния следующим образом: min_diff(i, d) = min_diff(j, d - 1) + max(jobDifficulty[i
]) для всех j > i.

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

😎 Решение

class Solution {
    func minDifficulty(_ jobDifficulty: [Int], _ d: Int) -> Int {
        let n = jobDifficulty.count
        if n < d { return -1 }
        
        var mem = Array(repeating: Array(repeating: -1, count: d + 1), count: n)
        
        func minDiff(_ i: Int, _ daysRemaining: Int) -> Int {
            if mem[i][daysRemaining] != -1 {
                return mem[i][daysRemaining]
            }
            
            if daysRemaining == 1 {
                return jobDifficulty[i...].max()!
            }
            
            var res = Int.max
            var dailyMaxJobDiff = 0
            
            for j in i..<n - daysRemaining + 1 {
                dailyMaxJobDiff = max(dailyMaxJobDiff, jobDifficulty[j])
                res = min(res, dailyMaxJobDiff + minDiff(j + 1, daysRemaining - 1))
            }
            
            mem[i][daysRemaining] = res
            return res
        }
        
        return minDiff(0, d)
    }
}

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