#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
    }
}

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