#hard
Задача: 644. Maximum Average Subarray II

Вам дан целочисленный массив nums, состоящий из n элементов, и целое число k. Найдите смежный подмассив, длина которого больше или равна k и который имеет максимальное среднее значение, и верните это значение. Принимается любой ответ с погрешностью вычислений менее 10-5.

Пример:

Input: nums = [1,12,-5,-6,50,3], k = 4
Output: 12.75000

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

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

😎 Решение:

func findMaxAverage(_ nums: [Int], _ k: Int) -> Double {
    var currSum = nums[0..<k].reduce(0, +)
    var maxSum = currSum
    for i in k..<nums.count {
        currSum += nums[i] - nums[i - k]
        if currSum > maxSum {
            maxSum = currSum
        }
    }
    return Double(maxSum) / Double(k)
}

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

#hard
Задача: 656. Coin Path

Вам дан целочисленный массив монет (1-индексированный) длины n и целое число maxJump. Вы можете перейти на любой индекс i массива coins, если coins[i] != -1 и вы должны заплатить coins[i] при посещении индекса i. Кроме того, если вы в данный момент находитесь на индексе i, вы можете перейти только на любой индекс i + k, где i + k <= n и k - значение в диапазоне [1, maxJump]. Изначально вы находитесь на индексе 1 (coins[1] не -1). Вы хотите найти путь, который достигнет индекса n с минимальной стоимостью. Верните целочисленный массив индексов, которые вы посетите в таком порядке, чтобы достичь индекса n с минимальной стоимостью. Если существует несколько путей с одинаковой стоимостью, верните лексикографически наименьший такой путь. Если невозможно достичь индекса n, возвращается пустой массив. Путь p1 = [Pa1, Pa2, ..., Pax] длины x лексикографически меньше, чем p2 = [Pb1, Pb2, ..., Pbx] длины y, если и только если при первом j, где Paj и Pbj отличаются, Paj < Pbj; если такого j нет, то x < y.

Пример:

Input: coins = [1,2,4,-1,2], maxJump = 2
Output: [1,3,5]

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

1⃣Используйте динамическое программирование для нахождения минимальной стоимости до каждого индекса, начиная с первого.
2⃣Храните путь до каждого индекса для отслеживания наименьшего лексикографического пути.
3⃣Используя полученную информацию, восстановите путь с минимальной стоимостью до последнего индекса.

😎 Решение:

import Foundation

func minCostPath(_ coins: [Int], _ maxJump: Int) -> [Int] {
    let n = coins.count
    if coins[0] == -1 { return [] }
    
    var dp = [Int](repeating: Int.max, count: n)
    dp[0] = coins[0]
    var path = Array(repeating: [Int](), count: n)
    path[0] = [1]
    
    var heap = [(cost: Int, index: Int)]()
    heap.append((coins[0], 0))
    
    while !heap.isEmpty {
        heap.sort(by: { $0.cost < $1.cost })
        let (current_cost, i) = heap.removeFirst()
        if current_cost > dp[i] { continue }
        for k in 1...maxJump {
            if i + k < n && coins[i + k] != -1 {
                let new_cost = current_cost + coins[i + k]
                if new_cost < dp[i + k] || (new_cost == dp[i + k] && path[i] + [i + k + 1] < path[i + k]) {
                    dp[i + k] = new_cost
                    path[i + k] = path[i] + [i + k + 1]
                    heap.append((new_cost, i + k))
                }
            }
        }
    }
    
    return dp[n - 1] == Int.max ? [] : path[n - 1]
}

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

#hard
Задача: 679. 24 Game

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

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

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

Пример:

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

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

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

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

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

😎 Решение:

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

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

#hard
Задача: 363. Max Sum of Rectangle No Larger Than K

Дана матрица размером m x n и целое число k, вернуть максимальную сумму прямоугольника в матрице, такая что его сумма не превышает k.

Гарантируется, что будет прямоугольник с суммой, не превышающей k.

Пример:

Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation: Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).

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

1⃣Создать вспомогательную функцию updateResult, которая будет находить максимальную сумму подмассива в одномерном массиве, не превышающую k.

2⃣Преобразовать каждую подматрицу в одномерный массив и применить к ней функцию updateResult.

3⃣Вернуть максимальную найденную сумму.

😎 Решение:

class Solution {
    var result = Int.min

    func updateResult(_ nums: [Int], _ k: Int) {
        var sum = 0
        var sortedSum = Set<Int>()
        sortedSum.insert(0)

        for num in nums {
            sum += num
            if let x = sortedSum.first(where: { $0 >= sum - k }) {
                result = max(result, sum - x)
            }
            sortedSum.insert(sum)
        }
    }

    func maxSumSubmatrix(_ matrix: [[Int]], _ k: Int) -> Int {
        let rows = matrix.count
        let cols = matrix[0].count
        var rowSum = [Int](repeating: 0, count: cols)

        for i in 0..<rows {
            rowSum = [Int](repeating: 0, count: cols)
            for row in i..<rows {
                for col in 0..<cols {
                    rowSum[col] += matrix[row][col]
                }
                updateResult(rowSum, k)
                if result == k {
                    return result
                }
            }
        }
        return result
    }
}

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

#hard
Задача: 446. Arithmetic Slices II - Subsequence


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

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

Например, [1, 3, 5, 7, 9], [7, 7, 7, 7] и [3, -1, -5, -9] являются арифметическими последовательностями.
Например, [1, 1, 2, 5, 7] не является арифметической последовательностью.
Подпоследовательность массива - это последовательность, которая может быть образована путем удаления некоторых элементов (возможно, ни одного) из массива.

Например, [2, 5, 10] является подпоследовательностью [1, 2, 1, 2, 4, 1, 5, 10].
Тестовые случаи сгенерированы таким образом, что ответ помещается в 32-битное целое число.

Пример:

Input: nums = [2,4,6,8,10]
Output: 7
Explanation: All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

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

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

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

3⃣Возвращаем количество всех арифметических подпоследовательностей.

😎 Решение:

class Solution {
    var n = 0
    var ans = 0
    
    func dfs(_ dep: Int, _ A: [Int], _ cur: [Int]) {
        var cur = cur
        if dep == n {
            if cur.count < 3 {
                return
            }
            for i in 1..<cur.count {
                if cur[i] - cur[i - 1] != cur[1] - cur[0] {
                    return
                }
            }
            ans += 1
            return
        }
        dfs(dep + 1, A, cur)
        cur.append(A[dep])
        dfs(dep + 1, A, cur)
    }
    
    func numberOfArithmeticSlices(_ A: [Int]) -> Int {
        n = A.count
        ans = 0
        dfs(0, A, [])
        return ans
    }
}

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

#hard
Задача: 591. Tag Validator

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

Фрагмент кода считается корректным, если соблюдаются все следующие правила:
Код должен быть заключен в корректный закрытый тег. В противном случае код некорректен.
Закрытый тег (не обязательно корректный) имеет точно следующий формат: <TAG_NAME>TAG_CONTENT</TAG_NAME>. Среди них <TAG_NAME> — это начальный тег, а </TAG_NAME> — конечный тег. TAG_NAME в начальном и конечном тегах должен быть одинаковым. Закрытый тег корректен, если и только если TAG_NAME и TAG_CONTENT корректны.
Корректное TAG_NAME содержит только заглавные буквы и имеет длину в диапазоне [1, 9]. В противном случае TAG_NAME некорректен.
Корректное TAG_CONTENT может содержать другие корректные закрытые теги, cdata и любые символы (см. примечание 1), КРОМЕ неподходящих <, неподходящих начальных и конечных тегов, и неподходящих или закрытых тегов с некорректным TAG_NAME. В противном случае TAG_CONTENT некорректен.
Начальный тег неподходящий, если нет конечного тега с тем же TAG_NAME, и наоборот. Однако нужно также учитывать проблему несбалансированных тегов, когда они вложены.
< неподходящий, если не удается найти последующий >. И когда вы находите < или </, все последующие символы до следующего > должны быть разобраны как TAG_NAME (не обязательно корректный).
cdata имеет следующий формат: <![CDATA[CDATA_CONTENT]]>. Диапазон CDATA_CONTENT определяется как символы между <![CDATA[ и первым последующим ]]>.
CDATA_CONTENT может содержать любые символы. Функция cdata заключается в том, чтобы запретить валидатору разбирать CDATA_CONTENT, поэтому даже если в нем есть символы, которые могут быть разобраны как тег (корректный или некорректный), вы должны рассматривать их как обычные символы.

Пример:

Input: code = "<DIV>This is the first line <![CDATA[<div>]]></DIV>"
Output: true

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

1⃣Инициализируйте стек для отслеживания открытых тегов и флаг для определения наличия тегов. Используйте регулярное выражение для проверки корректности TAG_NAME, TAG_CONTENT и CDATA.

2⃣Пройдитесь по строке, проверяя каждый символ. Если встретите <, определите тип тега (начальный, конечный или CDATA). Обновите стек и индексы в зависимости от найденного типа.

3⃣В конце проверьте, что стек пуст (все теги корректно закрыты) и верните результат.

😎 Решение:

import Foundation

class Solution {
    var stack = [String]()
    var containsTag = false

    func isValidTagName(_ s: String, _ ending: Bool) -> Bool {
        if ending {
            if !stack.isEmpty && stack.last == s {
                stack.removeLast()
            } else {
                return false
            }
        } else {
            containsTag = true
            stack.append(s)
        }
        return true
    }

    func isValid(_ code: String) -> Bool {
        let regex = "<[A-Z]{0,9}>([^<]*(<((\\/?[A-Z]{1,9}>)|(!\\[CDATA\\[(.*?)]]>)))?)*"
        if !NSPredicate(format: "SELF MATCHES %@", regex).evaluate(with: code) {
            return false
        }

        var i = 0
        while i < code.count {
            var ending = false
            if stack.isEmpty && containsTag {
                return false
            }
            if code[i] == "<" {
                if code[i + 1] == "!" {
                    i = code.range(of: "]]>", range: i + 1..<code.count)?.lowerBound ?? code.count
                    continue
                }
                if code[i + 1] == "/" {
                    i += 1
                    ending = true
                }
                let closeIndex = code.range(of: ">", range: i + 1..<code.count)?.lowerBound ?? code.count
                if closeIndex == code.count || !isValidTagName(String(code[i + 1..<closeIndex]), ending) {
                    return false
                }
                i = closeIndex
            }
            i += 1
        }
        return stack.isEmpty
    }
}

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

#hard
Задача: 765. Couples Holding Hands

Есть n пар, сидящих на 2n местах, расположенных в ряд, и они хотят держаться за руки.

Люди и места представлены массивом целых чисел row, где row[i] — это ID человека, сидящего на i-м месте. Пары пронумерованы по порядку: первая пара — (0, 1), вторая пара — (2, 3) и так далее, до последней пары — (2n - 2, 2n - 1).

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

Пример:

Input: row = [0,2,1,3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

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

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

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

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

😎 Решение:

class Solution {
    var N: Int = 0
    var pairs: [[Int]] = []
    
    func minSwapsCouples(_ row: [Int]) -> Int {
        N = row.count / 2
        pairs = Array(repeating: Array(repeating: 0, count: 2), count: N)
        for i in 0..<N {
            pairs[i][0] = row[2 * i] / 2
            pairs[i][1] = row[2 * i + 1] / 2
        }
        return solve(0)
    }
    
    func swap(_ a: Int, _ b: Int, _ c: Int, _ d: Int) {
        let t = pairs[a][b]
        pairs[a][b] = pairs[c][d]
        pairs[c][d] = t
    }
    
    func solve(_ i: Int) -> Int {
        if i == N { return 0 }
        let x = pairs[i][0], y = pairs[i][1]
        if x == y { return solve(i + 1) }
        
        var jx = 0, kx = 0, jy = 0, ky = 0
        for j in (i + 1)..<N {
            for k in 0...1 {
                if pairs[j][k] == x { jx = j; kx = k }
                if pairs[j][k] == y { jy = j; ky = k }
            }
        }
        
        swap(i, 1, jx, kx)
        let ans1 = 1 + solve(i + 1)
        swap(i, 1, jx, kx)
        
        swap(i, 0, jy, ky)
        let ans2 = 1 + solve(i + 1)
        swap(i, 0, jy, ky)
        
        return min(ans1, ans2)
    }
}

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

#hard
Задача: 711. Number of Distinct Islands II

Вам дана двоичная матричная сетка 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
    }
}

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

#hard
Задача: 715. Range Module

Модуль Range - это модуль, который отслеживает диапазоны чисел. Создайте структуру данных для отслеживания диапазонов, представленных в виде полуоткрытых интервалов, и запросов к ним. Полуоткрытый интервал [left, right) обозначает все вещественные числа x, где left <= x < right. Реализуйте класс RangeModule: RangeModule() Инициализирует объект структуры данных. void addRange(int left, int right) Добавляет полуоткрытый интервал [left, right), отслеживая каждое вещественное число в этом интервале. Добавление интервала, который частично перекрывает отслеживаемые в данный момент числа, должно добавить все числа в интервале [left, right), которые еще не отслеживаются. boolean queryRange(int left, int right) Возвращает true, если каждое действительное число в интервале [left, right) отслеживается в данный момент, и false в противном случае. void removeRange(int left, int right) Прекращает отслеживание каждого действительного числа, отслеживаемого в данный момент в полуоткрытом интервале [left, right).

Пример:

Input
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
Output
[null, null, null, true, false, true]

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

1⃣Инициализируйте класс RangeModule с пустым списком диапазонов.

2⃣Для метода addRange(left, right) добавьте новый диапазон, объединяя его с существующими перекрывающимися диапазонами. Для метода queryRange(left, right) проверьте, полностью ли данный диапазон содержится в отслеживаемых диапазонах.

3⃣Для метода removeRange(left, right) удалите указанный диапазон, разбивая существующие диапазоны на соответствующие части.

😎 Решение:

class RangeModule {

    private var ranges: [(Int, Int)]

    init() {
        ranges = []
    }

    func addRange(_ left: Int, _ right: Int) {
        var newRanges = [(Int, Int)]()
        var i = 0
        while i < ranges.count && ranges[i].1 < left {
            newRanges.append(ranges[i])
            i += 1
        }
        while i < ranges.count && ranges[i].0 <= right {
            left = min(left, ranges[i].0)
            right = max(right, ranges[i].1)
            i += 1
        }
        newRanges.append((left, right))
        while i < ranges.count {
            newRanges.append(ranges[i])
            i += 1
        }
        ranges = newRanges
    }

    func queryRange(_ left: Int, _ right: Int) -> Bool {
        for (l, r) in ranges {
            if l <= left && right <= r {
                return true
            }
        }
        return false
    }

    func removeRange(_ left: Int, _ right: Int) {
        var newRanges = [(Int, Int)]()
        for (l, r) in ranges {
            if l < left {
                newRanges.append((l, min(r, left)))
            }
            if right < r {
                newRanges.append((max(l, right), r))
            }
        }
        ranges = newRanges
    }
}

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

#hard
Задача: 774. Minimize Max Distance to Gas Station

Вам дан массив целых чисел stations, который представляет позиции автозаправочных станций на оси x. Вам также дано целое число k.

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

Определим penalty() как максимальное расстояние между соседними автозаправочными станциями после добавления k новых станций.

Верните наименьшее возможное значение penalty(). Ответы, отличающиеся от фактического ответа не более чем на 10^-6, будут приняты.

Пример:

Input: stations = [1,2,3,4,5,6,7,8,9,10], k = 9
Output: 0.50000

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

1⃣Пусть i-й интервал равен deltas[i] = stations[i+1] - stations[i]. Мы хотим найти dp[n+1][k] как рекурсию. Мы можем поставить x автозаправочных станций в интервал n+1 с наилучшим расстоянием deltas[n+1] / (x+1), затем оставшиеся интервалы можно решить с ответом dp[n][k-x]. Ответ — это минимум среди всех x.

2⃣Из этой рекурсии мы можем разработать решение с использованием динамического программирования. Инициализируем двумерный массив dp, где dp[i][j] будет хранить минимальное возможное значение penalty при добавлении j автозаправочных станций на первые i интервалов.

3⃣Заполняем dp таблицу начиная с базового случая, когда нет добавленных станций. Затем для каждого интервала и количества добавленных станций вычисляем минимальное значение penalty, используя вышеописанную рекурсию. Итоговый ответ будет находиться в dp[n][k], где n — количество интервалов, а k — количество добавляемых станций.

😎 Решение:

class Solution {
    func minmaxGasDist(_ stations: [Int], _ K: Int) -> Double {
        let N = stations.count
        var deltas = [Double](repeating: 0, count: N-1)
        for i in 0..<N-1 {
            deltas[i] = Double(stations[i+1] - stations[i])
        }

        var dp = [[Double]](repeating: [Double](repeating: 0, count: K+1), count: N-1)
        for i in 0...K {
            dp[0][i] = deltas[0] / Double(i+1)
        }

        for p in 1..<N-1 {
            for k in 0...K {
                var bns = Double.greatestFiniteMagnitude
                for x in 0...k {
                    bns = min(bns, max(deltas[p] / Double(x+1), dp[p-1][k-x]))
                }
                dp[p][k] = bns
            }
        }

        return dp[N-2][K]
    }
}

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