Swift | LeetCode

Задача: 1062. Longest Repeating Substring
Сложность: medium

Дана строка s. Вернуть длину самой длинной повторяющейся подстроки. Если повторяющаяся подстрока отсутствует, вернуть 0.

Пример:

Input: s = "abcd"
Output: 0
Explanation: There is no repeating substring.

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

1⃣Перемещайте скользящее окно длиной L по строке длиной N.

2⃣Проверьте, находится ли строка в скользящем окне в хэш-наборе уже виденных строк. Если да, то повторяющаяся подстрока находится здесь. Если нет, сохраните строку из скользящего окна в хэш-наборе.

3⃣Очевидный недостаток этого подхода — большое потребление памяти в случае длинных строк.

😎 Решение:

class Solution {
    func search(_ L: Int, _ n: Int, _ S: String) -> Int {
        var seen = Set<String>()
        for start in 0...(n - L) {
            let tmp = String(S[S.index(S.startIndex, offsetBy: start)..<S.index(S.startIndex, offsetBy: start + L)])
            if seen.contains(tmp) { return start }
            seen.insert(tmp)
        }
        return -1
    }

    func longestRepeatingSubstring(_ S: String) -> Int {
        let n = S.count
        var left = 1, right = n
        while left <= right {
            let L = left + (right - left) / 2
            if search(L, n, S) != -1 {
                left = L + 1
            } else {
                right = L - 1
            }
        }
        return left - 1
    }
}

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

Задача: 714. Best Time to Buy and Sell Stock with Transaction Fee
Сложность: medium

Вам дан массив prices, где prices[i] - это цена данной акции в i-й день, и целое число fee, представляющее собой комиссию за сделку. Найдите максимальную прибыль, которую вы можете получить. Вы можете совершить сколько угодно сделок, но за каждую сделку вам придется заплатить комиссию. Примечание: Вы не можете совершать несколько сделок одновременно (то есть вы должны продать акции, прежде чем купить их снова). Комиссия за сделку взимается только один раз за каждую покупку и продажу акций.

Пример:

Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8

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

1⃣Инициализируйте две переменные: cash, представляющую максимальную прибыль без наличия акций, и hold, представляющую максимальную прибыль с наличием акций.

2⃣Пройдите по каждому элементу массива prices и обновите значения cash и hold, используя текущую цену и комиссию.

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

😎 Решение:

func maxProfit(_ prices: [Int], _ fee: Int) -> Int {
    var cash = 0
    var hold = -prices[0]
    for price in prices {
        cash = max(cash, hold + price - fee)
        hold = max(hold, cash - price)
    }
    return cash
}

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

Задача: 31. Next Permutation
Сложность: medium

Перестановка массива целых чисел — это упорядочивание его элементов в последовательность или линейный порядок.

Следующая перестановка массива целых чисел — это следующая лексикографически большая перестановка его чисел. Если такое упорядочивание невозможно, массив должен быть переупорядочен в наименьший возможный порядок (отсортирован по возрастанию).

Пример:

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

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

1⃣Найти первое число nums[i], которое меньше nums[i+1], двигаясь справа налево.

2⃣Найти наименьшее число справа от nums[i], которое больше него, и поменять их местами.

3⃣Перевернуть все элементы после i, чтобы получить наименьшую возможную лексикографическую перестановку.

😎Решение:

func nextPermutation(_ nums: inout [Int]) {
    var i = nums.count - 2
    while i >= 0 && nums[i + 1] <= nums[i] {
        i -= 1
    }
    if i >= 0 {
        var j = nums.count - 1
        while nums[j] <= nums[i] {
            j -= 1
        }
        nums.swapAt(i, j)
    }
    reverse(nums: &nums, start: i + 1)
}

func reverse(nums: inout [Int], start: Int) {
    var i = start
    var j = nums.count - 1
    while i < j {
        nums.swapAt(i, j)
        i += 1
        j -= 1
    }
}

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

Задача: 1428. Leftmost Column with at Least a One
Сложность: medium

Строково-отсортированная бинарная матрица означает, что все элементы равны 0 или 1, и каждая строка матрицы отсортирована в неубывающем порядке.
Дана строково-отсортированная бинарная матрица binaryMatrix, верните индекс (начиная с 0) самого левого столбца, содержащего 1. Если такого индекса не существует, верните -1.
Вы не можете напрямую обращаться к бинарной матрице. Вы можете получить доступ к матрице только через интерфейс BinaryMatrix:
- BinaryMatrix.get(row, col) возвращает элемент матрицы с индексом (row, col) (начиная с 0).
- BinaryMatrix.dimensions() возвращает размеры матрицы в виде списка из 2 элементов [rows, cols], что означает, что матрица имеет размер rows x cols.

Отправки, делающие более 1000 вызовов к BinaryMatrix.get, будут оценены как неправильный ответ. Кроме того, любые решения, пытающиеся обойти проверку, будут дисквалифицированы.

Для пользовательского тестирования вводом будет вся бинарная матрица mat. Вы не будете иметь прямого доступа к бинарной матрице.

Пример:

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

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

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

2⃣Повторяйте поиск до тех пор, пока указатели не выйдут за границы матрицы:
Если текущий элемент равен 0, сдвигайте указатель строки вниз.
Если текущий элемент равен 1, сдвигайте указатель столбца влево.

3⃣Если указатель столбца остается на последнем столбце, значит, все элементы матрицы равны 0, и верните -1. В противном случае верните индекс самого левого столбца с 1.

😎 Решение:

class Solution {
    func leftMostColumnWithOne(_ binaryMatrix: BinaryMatrix) -> Int {
        let dimensions = binaryMatrix.dimensions()
        let rows = dimensions[0]
        let cols = dimensions[1]
        
        var currentRow = 0
        var currentCol = cols - 1
        
        while currentRow < rows && currentCol >= 0 {
            if binaryMatrix.get(currentRow, currentCol) == 0 {
                currentRow += 1
            } else {
                currentCol -= 1
            }
        }
        
        return (currentCol == cols - 1) ? -1 : currentCol + 1
    }
}

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

Задача: 59. Spiral Matrix II
Сложность: medium

Дано положительное целое число n. Сгенерируйте матрицу n на n, заполненную элементами от 1 до n^2 в спиральном порядке.

Пример:

Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]

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

1⃣Определение направлений движения:
Для обхода матрицы используются четыре направления, формирующие слои. Создается массив dir, который хранит изменения координат x и y для каждого направления. Например, при движении слева направо (направление №1) координата x остается неизменной, а y увеличивается (x=0, y=1). При движении справа налево (направление №3) x остается неизменным, а y уменьшается (x=0, y=-1).

2⃣Перемещение по матрице:
Переменные row и col представляют текущие координаты x и y соответственно. Они обновляются в зависимости от направления движения. Применяется предварительно определенный массив dir с изменениями координат x и y для каждого из четырех направлений.

3⃣Изменение направления:
Направление изменяется, когда следующая строка или столбец в определенном направлении имеют ненулевое значение, что указывает на то, что они уже были пройдены. Переменная d представляет текущий индекс направления. Переход к следующему направлению в массиве dir осуществляется с использованием формулы (d+1)%4. Это позволяет вернуться к направлению 1 после завершения одного полного круга от направления 1 до направления 4.

😎 Решение:

class Solution {
    func floorMod(_ x: Int, _ y: Int) -> Int {
        return ((x % y) + y) % y
    }

    func generateMatrix(_ n: Int) -> [[Int]] {
        var result = Array(repeating: Array(repeating: 0, count: n), count: n)
        var cnt = 1
        let dir = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        var d = 0
        var row = 0
        var col = 0
        while cnt <= n * n {
            result[row][col] = cnt
            cnt += 1
            let r = floorMod(row + dir[d].0, n)
            let c = floorMod(col + dir[d].1, n)
            if result[r][c] != 0 {
                d = (d + 1) % 4
            }
            row += dir[d].0
            col += dir[d].1
        }
        return result
    }
}

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

Задача: 638. Shopping Offers
Сложность: medium

В магазине LeetCode Store есть n предметов для продажи. Каждый товар имеет свою цену. Однако существуют специальные предложения, и специальное предложение состоит из одного или нескольких различных видов товаров с распродажной ценой. Вам дан целочисленный массив price, где price[i] - цена i-го товара, и целочисленный массив needs, где needs[i] - количество штук i-го товара, который вы хотите купить. Вам также дан массив special, где special[i] имеет размер n + 1, где special[i][j] - количество штук j-го товара в i-м предложении, а special[i][n] (т.е., Возвращает наименьшую цену, которую вы можете заплатить за определенный товар из заданных, где вы могли бы оптимально использовать специальные предложения. Вам не разрешается покупать больше товаров, чем вы хотите, даже если это снизит общую цену. Вы можете использовать любое из специальных предложений столько раз, сколько захотите.

Пример:

Input: price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2]
Output: 14

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

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

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

3⃣Выбор минимальной стоимости: Сравните стоимость при использовании специальных предложений и стоимость при покупке товаров по индивидуальным ценам, выбирая минимальную стоимость.

😎 Решение:

class Solution {
    func shoppingOffers(_ price: [Int], _ special: [[Int]], _ needs: [Int]) -> Int {
        var memo = [String: Int]()
        return dfs(price, special, needs, &memo)
    }
    
    private func dfs(_ price: [Int], _ special: [[Int]], _ needs: [Int], _ memo: inout [String: Int]) -> Int {
        let key = needs.map(String.init).joined(separator: ",")
        if let cached = memo[key] {
            return cached
        }
        
        var minPrice = zip(price, needs).map(*).reduce(0, +)
        
        for offer in special {
            var newNeeds = [Int]()
            var valid = true
            for i in 0..<needs.count {
                if needs[i] < offer[i] {
                    valid = false
                    break
                }
                newNeeds.append(needs[i] - offer[i])
            }
            if valid {
                minPrice = min(minPrice, offer.last! + dfs(price, special, newNeeds, &memo))
            }
        }
        
        memo[key] = minPrice
        return minPrice
    }
}

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

Задача: 348. Design Tic-Tac-Toe
Сложность: medium

Предположим, что следующие правила относятся к игре в крестики-нолики на доске размером n x n между двумя игроками:

Ход гарантированно является допустимым и делается на пустом поле.
Как только достигается выигрышное условие, дальнейшие ходы запрещены.
Игрок, который успешно размещает n своих меток в горизонтальном, вертикальном или диагональном ряду, выигрывает игру.
Реализуйте класс TicTacToe:

TicTacToe(int n) Инициализирует объект с размером доски n.
int move(int row, int col, int player) Указывает, что игрок с идентификатором player делает ход в ячейке (row, col) на доске. Ход гарантированно является допустимым, и два игрока ходят по очереди. Возвращает:
0, если после хода победителя нет.
1, если после хода игрок 1 является победителем.
2, если после хода игрок 2 является победителем.

Пример:

Input
["TicTacToe", "move", "move", "move", "move", "move", "move", "move"]
[[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]]
Output
[null, 0, 0, 0, 0, 0, 0, 1]

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

1⃣Инициализация:
Создайте массивы rows и cols для отслеживания количества маркеров в каждой строке и столбце соответственно.
Создайте переменные diagonal и antiDiagonal для отслеживания количества маркеров на главной и побочной диагоналях соответственно.
Инициализируйте размер доски n.

2⃣Выполнение хода:
Увеличьте счетчики в rows, cols, diagonal и antiDiagonal в зависимости от текущего хода.
Если текущий ход игрока попадает на диагонали, обновите соответствующие переменные diagonal и antiDiagonal.

3⃣Проверка победы:
Проверьте, достиг ли один из счетчиков в rows, cols, diagonal или antiDiagonal значения n (размер доски). Если да, верните идентификатор игрока как победителя.
Если ни одно из условий победы не выполнено, верните 0, что означает отсутствие победителя после текущего хода.

😎 Решение:

class TicTacToe {
    private var rows: [Int]
    private var cols: [Int]
    private var diagonal: Int
    private var antiDiagonal: Int
    private var n: Int

    init(_ n: Int) {
        self.n = n
        rows = [Int](repeating: 0, count: n)
        cols = [Int](repeating: 0, count: n)
        diagonal = 0
        antiDiagonal = 0
    }

    func move(_ row: Int, _ col: Int, _ player: Int) -> Int {
        let add = player == 1 ? 1 : -1
        rows[row] += add
        cols[col] += add
        if row == col {
            diagonal += add
        }
        if row + col == n - 1 {
            antiDiagonal += add
        }
        if abs(rows[row]) == n || abs(cols[col]) == n || abs(diagonal) == n || abs(antiDiagonal) == n {
            return player
        }
        return 0
    }
}

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

Задача: 187. Repeated DNA Sequences
Сложность: medium

ДНК состоит из серии нуклеотидов, обозначаемых как 'A', 'C', 'G' и 'T'.

Например, "ACGAATTCCG" — это последовательность ДНК.
При изучении ДНК полезно определять повторяющиеся последовательности внутри молекулы ДНК.

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

Пример:

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]

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

1⃣Перебираем начальные позиции последовательности от 1 до 𝑁−𝐿, где 𝑁 — длина строки, а 𝐿 — длина подстроки (в данном случае 10):
Если начальная позиция 𝑠𝑡𝑎𝑟𝑡==0, вычисляем хеш первой последовательности 𝑠[0:𝐿].
В противном случае вычисляем скользящий хеш из предыдущего значения хеша.

2⃣Проверяем хеш в хешсете:
Если хеш уже существует в хешсете, значит, мы нашли повторяющуюся последовательность, и пора обновить вывод.
В противном случае добавляем хеш в хешсет.

3⃣Возвращаем список вывода, содержащий все повторяющиеся последовательности.

😎 Решение:

class Solution {
    func findRepeatedDnaSequences(_ s: String) -> [String] {
        let L = 10, n = s.count
        if n <= L { return [] }
        let a = 4, aL = Int(pow(Double(a), Double(L)))
        var toInt = ["A": 0, "C": 1, "G": 2, "T": 3]
        var nums = s.map { toInt[String($0)]! }
        var h = 0
        var seen = Set<Int>()
        var output = Set<String>()
        for start in 0..<(n - L + 1) {
            if start != 0 {
                h = h * a - nums[start - 1] * aL + nums[start + L - 1]
            } else {
                for i in 0..<L {
                    h = h * a + nums[i]
                }
            }
            if seen.contains(h) {
                output.insert(String(s.dropFirst(start).prefix(L)))
            }
            seen.insert(h)
        }
        return Array(output)
    }
}

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

Задача: 338. Counting Bits
Сложность: easy

Дано целое число n, верните массив ans длиной n + 1, такой что для каждого i (0 <= i <= n), ans[i] будет равняться количеству единиц в двоичном представлении числа i.

Пример:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

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

1⃣ Инициализация массива:
Создайте массив ans длиной n + 1, заполненный нулями. Этот массив будет содержать количество единиц в двоичном представлении каждого числа от 0 до n.

2⃣ Итерация и вычисление:
Пройдите в цикле по всем числам от 1 до n. Для каждого числа x используйте битовую операцию x & (x - 1), чтобы убрать последнюю установленную биту, и добавьте 1 к значению ans для этого результата. Это количество единиц в двоичном представлении числа x.

3⃣ Возврат результата:
Верните заполненный массив ans, который содержит количество единиц для каждого числа от 0 до n.

😎 Решение:

class Solution {
    func countBits(_ num: Int) -> [Int] {
        var ans = [Int](repeating: 0, count: num + 1)
        for x in 1...num {
            ans[x] = ans[x & (x - 1)] + 1
        }
        return ans
    }
}

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

Задача: 834. Sum of Distances in Tree
Сложность: hard

Есть неориентированное связное дерево с n узлами, пронумерованными от 0 до n - 1, и n - 1 ребрами.

Вам даны целое число n и массив edges, где edges[i] = [ai, bi] указывает, что существует ребро между узлами ai и bi в дереве.

Верните массив answer длиной n, где answer[i] — это сумма расстояний между i-м узлом в дереве и всеми другими узлами.

Пример:

Input: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Output: [8,12,6,10,10,10]
Explanation: The tree is shown above.
We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
equals 1 + 1 + 2 + 2 + 2 = 8.
Hence, answer[0] = 8, and so on.

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

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

2⃣На основе полученных данных рассчитайте сумму расстояний для корня дерева.

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

😎 Решение:

class Solution {
    var ans: [Int] = []
    var count: [Int] = []
    var graph: [[Int]] = []
    var N: Int = 0

    func sumOfDistancesInTree(_ N: Int, _ edges: [[Int]]) -> [Int] {
        self.N = N
        graph = Array(repeating: [], count: N)
        ans = Array(repeating: 0, count: N)
        count = Array(repeating: 1, count: N)

        for edge in edges {
            graph[edge[0]].append(edge[1])
            graph[edge[1]].append(edge[0])
        }

        dfs(0, -1)
        dfs2(0, -1)
        return ans
    }

    func dfs(_ node: Int, _ parent: Int) {
        for child in graph[node] {
            if child != parent {
                dfs(child, node)
                count[node] += count[child]
                ans[node] += ans[child] + count[child]
            }
        }
    }

    func dfs2(_ node: Int, _ parent: Int) {
        for child in graph[node] {
            if child != parent {
                ans[child] = ans[node] - count[child] + N - count[child]
                dfs2(child, node)
            }
        }
    }
}

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

Задача: 378. Kth Smallest Element in a Sorted Matrix
Сложность: medium

Дана матрица размером n x n, где каждая строка и каждый столбец отсортированы в порядке возрастания. Верните k-й наименьший элемент в матрице.

Заметьте, что это k-й наименьший элемент в отсортированном порядке, а не k-й уникальный элемент.

Вы должны найти решение с использованием памяти лучше, чем O(n²).

Пример:

Input: matrix = [[-5]], k = 1
Output: -5

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

1⃣Инициализировать мин-кучу H. В нашем решении мы будем рассматривать каждую строку как отдельный список. Поскольку столбцы также отсортированы, мы можем рассматривать каждый столбец как отдельный список.

2⃣Взять первые элементы из min(N, K) строк, где N представляет количество строк, и добавить каждый из этих элементов в кучу. Важно знать, к какой строке и столбцу принадлежит элемент, чтобы в дальнейшем перемещаться по соответствующему списку.

3⃣Мин-куча будет содержать тройки информации (значение, строка, столбец). Куча будет упорядочена по значениям, и мы будем использовать номера строк и столбцов для добавления следующего элемента, если текущий элемент будет удален из кучи.

😎 Решение:

class MyHeapNode {
    var row: Int
    var column: Int
    var value: Int

    init(_ value: Int, _ row: Int, _ column: Int) {
        self.value = value
        self.row = row
        self.column = column
    }
}

class Solution {
    func kthSmallest(_ matrix: [[Int]], _ k: Int) -> Int {
        let N = matrix.count
        var minHeap = PriorityQueue<MyHeapNode> { $0.value < $1.value }

        for r in 0..<min(N, k) {
            minHeap.enqueue(MyHeapNode(matrix[r][0], r, 0))
        }

        var element: MyHeapNode = minHeap.peek()!
        var k = k
        while k > 0 {
            element = minHeap.dequeue()!
            let r = element.row, c = element.column

            if c < N - 1 {
                minHeap.enqueue(MyHeapNode(matrix[r][c + 1], r, c + 1))
            }
            k -= 1
        }

        return element.value
    }
}

struct PriorityQueue<Element: Equatable> {
    private var elements: [Element]
    private let priorityFunction: (Element, Element) -> Bool

    init(priorityFunction: @escaping (Element, Element) -> Bool) {
        self.elements = []
        self.priorityFunction = priorityFunction
    }

    var isEmpty: Bool {
        return elements.isEmpty
    }

    func peek() -> Element? {
        return elements.first
    }

    mutating func enqueue(_ element: Element) {
        elements.append(element)
        siftUp(elementAtIndex: elements.count - 1)
    }

    mutating func dequeue() -> Element? {
        guard !isEmpty else { return nil }
        if elements.count == 1 {
            return elements.removeLast()
        } else {
            let value = elements[0]
            elements[0] = elements.removeLast()
            siftDown(elementAtIndex: 0)
            return value
        }
    }

    private mutating func siftUp(elementAtIndex index: Int) {
        let parent = parentIndex(of: index)
        guard !isRoot(index), isHigherPriority(at: index, than: parent) else { return }
        swapElement(at: index, with: parent)
        siftUp(elementAtIndex: parent)
    }

    private mutating func siftDown(elementAtIndex index: Int) {
        let childIndex = highestPriorityIndex(for: index)
        if index == childIndex { return }
        swapElement(at: index, with: childIndex)
        siftDown(elementAtIndex: childIndex)
    }

    private func isRoot(_ index: Int) -> Bool {
        return index == 0
    }

    private func leftChildIndex(of index: Int) -> Int {
        return 2 * index + 1
    }

    private func rightChildIndex(of index: Int) -> Int {
        return 2 * index + 2
    }

    private func parentIndex(of index: Int) -> Int {
        return (index - 1) / 2
    }

    private func isHigherPriority(at firstIndex: Int, than secondIndex: Int) -> Bool {
        return priorityFunction(elements[firstIndex], elements[secondIndex])
    }

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

Задача: 920. Number of Music Playlists
Сложность: hard

В вашем плеере есть n разных песен. Во время путешествия вы хотите прослушать goal песен (не обязательно разных). Чтобы избежать скуки, вы создадите плейлист таким образом, чтобы: каждая песня играла хотя бы один раз. Песня может быть проиграна снова только в том случае, если было проиграно k других песен. Учитывая n, цель и k, верните количество возможных плейлистов, которые вы можете создать. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.

Пример:

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

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

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

2⃣Инициализировать dp[0][0] = 1, что означает, что существует один способ создать плейлист длины 0 с 0 песнями.
Заполнить массив dp, используя два случая:
Добавление новой песни, которая не была проиграна раньше: dp[i][j] += dp[i-1][j-1] * (n - j + 1)
Повторное проигрывание песни, если было проиграно k других песен: dp[i][j] += dp[i-1][j] * max(j - k, 0)

3⃣Ответ находится в dp[goal][n].

😎 Решение:

class Solution {
    func numMusicPlaylists(_ n: Int, _ goal: Int, _ k: Int) -> Int {
        let MOD = 1_000_000_007
        var dp = Array(repeating: Array(repeating: 0, count: n + 1), count: goal + 1)
        dp[0][0] = 1
        
        for i in 1...goal {
            for j in 1...n {
                dp[i][j] = dp[i-1][j-1] * (n - j + 1) % MOD
                if j > k {
                    dp[i][j] = (dp[i][j] + dp[i-1][j] * (j - k) % MOD) % MOD
                }
            }
        }
        
        return dp[goal][n]
    }
}

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

Задача: 713. Subarray Product Less Than K
Сложность: medium

Если задан массив целых чисел nums и целое число k, верните количество смежных подмассивов, в которых произведение всех элементов в подмассиве строго меньше k.

Пример:

Input: nums = [10,5,2,6], k = 100
Output: 8

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

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

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

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

😎 Решение:

func numSubarrayProductLessThanK(_ nums: [Int], _ k: Int) -> Int {
    if k <= 1 {
        return 0
    }
    var product = 1
    var count = 0
    var left = 0
    for right in 0..<nums.count {
        product *= nums[right]
        while product >= k {
            product /= nums[left]
            left += 1
        }
        count += right - left + 1
    }
    return count
}

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

Задача: 969. Pancake Sorting
Сложность: medium

Дан массив целых чисел arr, отсортируйте массив, выполняя серию переворотов блинов.

При одном перевороте блина мы выполняем следующие шаги:

Выбираем целое число k, где 1 <= k <= arr.length.
Переворачиваем подмассив arr[0...k-1] (индексация с 0).
Например, если arr = [3,2,1,4] и мы выполнили переворот блина, выбрав k = 3, мы переворачиваем подмассив [3,2,1], так что arr = [1,2,3,4] после переворота блина при k = 3.

Верните массив значений k, соответствующих последовательности переворотов блинов, которая сортирует arr. Любой допустимый ответ, который сортирует массив за количество переворотов не более чем 10 * arr.length, будет считаться правильным.

Пример:

Input: arr = [3,2,4,1]
Output: [4,2,4,3]
Explanation: 
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: arr = [3, 2, 4, 1]
After 1st flip (k = 4): arr = [1, 4, 2, 3]
After 2nd flip (k = 2): arr = [4, 1, 2, 3]
After 3rd flip (k = 4): arr = [3, 2, 1, 4]
After 4th flip (k = 3): arr = [1, 2, 3, 4], which is sorted.

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

1⃣Вдохновляясь пузырьковой сортировкой, начнем с реализации функции flip(list, k), которая выполняет переворот блина на префиксе list[0
] (в Python).

2⃣Основной алгоритм выполняет цикл по значениям списка, начиная с наибольшего.

3⃣На каждом этапе определяем значение для сортировки (назовем его value_to_sort), которое является числом, которое мы будем ставить на место на этом этапе. Затем находим индекс value_to_sort. Если value_to_sort еще не на своем месте, выполняем максимум два переворота блинов, как объяснено в интуиции. В конце этапа value_to_sort будет на своем месте.

😎 Решение:

class Solution {
    func pancakeSort(_ A: [Int]) -> [Int] {
        var A = A
        var ans = [Int]()

        for valueToSort in stride(from: A.count, to: 0, by: -1) {
            let index = find(A, valueToSort)
            if index == valueToSort - 1 { continue }
            if index != 0 {
                ans.append(index + 1)
                flip(&A, index + 1)
            }
            ans.append(valueToSort)
            flip(&A, valueToSort)
        }

        return ans
    }

    private func flip(_ sublist: inout [Int], _ k: Int) {
        var i = 0
        while i < k / 2 {
            let temp = sublist[i]
            sublist[i] = sublist[k - i - 1]
            sublist[k - i - 1] = temp
            i += 1
        }
    }

    private func find(_ a: [Int], _ target: Int) -> Int {
        for i in 0..<a.count {
            if a[i] == target {
                return i
            }
        }
        return -1
    }
}

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

Задача: 860. Lemonade Change
Сложность: easy

На лимонадной стойке каждый лимонад стоит $5. Покупатели стоят в очереди, чтобы купить лимонад, и заказывают по одному (в порядке, указанном в массиве bills). Каждый покупатель покупает только один лимонад и платит либо $5, $10, либо $20. Вы должны предоставить правильную сдачу каждому покупателю, чтобы чистая сделка была такой, что покупатель платит $5.

Обратите внимание, что изначально у вас нет никакой сдачи.

Дан целочисленный массив bills, где bills[i] — купюра, которой платит i-й покупатель. Верните true, если вы можете предоставить каждому покупателю правильную сдачу, или false в противном случае.

Пример:

Input: bills = [5,5,5,10,20]
Output: true
Explanation: 
From the first 3 customers, we collect three $5 bills in order.
From the fourth customer, we collect a $10 bill and give back a $5.
From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.

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

1⃣Инициализируем переменные для хранения количества пятерок и десяток. Если покупатель платит $5, добавляем эту купюру в наш запас.

2⃣Если покупатель платит $10, проверяем наличие пятерки для сдачи. Если пятерки нет, возвращаем false. В противном случае, уменьшаем количество пятерок и увеличиваем количество десяток.

3⃣Если покупатель платит $20, сначала пытаемся дать сдачу десяткой и пятеркой. Если это невозможно, проверяем наличие трех пятерок. Если не можем дать сдачу, возвращаем false. После обработки всех покупателей, возвращаем true.

😎 Решение:

class Solution {
    func lemonadeChange(_ bills: [Int]) -> Bool {
        var five = 0, ten = 0
        for bill in bills {
            if bill == 5 {
                five += 1
            } else if bill == 10 {
                if five == 0 { return false }
                five -= 1
                ten += 1
            } else {
                if five > 0 && ten > 0 {
                    five -= 1
                    ten -= 1
                } else if five >= 3 {
                    five -= 3
                } else {
                    return false
                }
            }
        }
        return true
    }
}

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

Задача: 424. Longest Repeating Character Replacement
Сложность: medium

Вам дана строка s и целое число k. Вы можете выбрать любой символ строки и заменить его на любой другой заглавный английский символ. Вы можете выполнить эту операцию не более k раз.

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

Пример:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

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

1⃣Определите диапазон поиска. Минимальная длина подстроки с одинаковыми символами всегда равна 1 (назовем ее min), а максимальная длина подстроки может быть равна длине данной строки (назовем ее max). Ответ будет лежать в диапазоне [min, max] (включительно).

2⃣Инициализируйте две переменные lo и hi для бинарного поиска. lo всегда указывает на длину допустимой строки, а hi - на недопустимую длину. Изначально lo равно 1, а hi равно max+1.

3⃣Выполните бинарный поиск, чтобы найти максимальное значение lo, которое представляет самую длинную допустимую подстроку. В конце lo будет содержать ответ, а hi будет на единицу больше lo.

😎 Решение:

class Solution {
    func characterReplacement(_ s: String, _ k: Int) -> Int {
        var lo = 1
        var hi = s.count + 1

        while lo + 1 < hi {
            let mid = lo + (hi - lo) / 2
            if canMakeValidSubstring(s, mid, k) {
                lo = mid
            } else {
                hi = mid
            }
        }
        return lo
    }

    private func canMakeValidSubstring(_ s: String, _ substringLength: Int, _ k: Int) -> Bool {
        var freqMap = [Int](repeating: 0, count: 26)
        var maxFrequency = 0
        let sArray = Array(s)
        var start = 0

        for end in 0..<sArray.count {
            freqMap[Int(sArray[end].asciiValue! - Character("A").asciiValue!)] += 1

            if end + 1 - start > substringLength {
                freqMap[Int(sArray[start].asciiValue! - Character("A").asciiValue!)] -= 1
                start += 1
            }

            maxFrequency = max(maxFrequency, freqMap[Int(sArray[end].asciiValue! - Character("A").asciiValue!)])
            if substringLength - maxFrequency <= k {
                return true
            }
        }
        return false
    }
}

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

Пожизненная PRO подписка на easyoffer по цене одного года.

Акция до 20 февраля. Покупаешь сейчас один раз – пользуешься всю жизнь без лимита, включая все будущие функции.

Запланированные новые фичи на ближайшие пол года:
1. Агрегатор вакансий
2. Улучшение резюме, чтобы проходить ATS системы
3. Генерация уникального резюме и сопроводительного письма под вакансию

Покупай на https://easyoffer.ru/

Задача: 1167. Minimum Cost to Connect Sticks
Сложность: medium

У вас есть несколько палочек с положительными целыми длинами. Эти длины даны в виде массива sticks, где sticks[i] — длина i-й палочки.

Вы можете соединить любые две палочки длиной x и y в одну палочку, заплатив стоимость x + y. Вы должны соединить все палочки, пока не останется только одна палочка.

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

Пример:

Input: sticks = [5]
Output: 0
Explanation: There is only one stick, so you don't need to do anything. The total cost is 0.

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

1⃣Всегда выбирайте две самые маленькие палочки для соединения и продолжайте делать это, пока не останется только одна палочка. Рассмотрим 4 палочки следующих длин: sticks=[a1, a2, a3, a4]. Попробуем соединить их слева направо. После первого соединения у нас будет: sticks=[(a1 + a2), a3, a4], стоимость=(a1 + a2). После второго соединения у нас будет: sticks=[(a1 + a2 + a3), a4], стоимость=(a1 + a2)+(a1 + a2 + a3). И, наконец, последняя палочка будет выглядеть так: sticks=[(a1 + a2 + a3 + a4)], стоимость=(a1 + a2)+(a1 + a2 + a3)+(a1 + a2 + a3 + a4).

2⃣Итоговая стоимость может быть переписана следующим образом: стоимость=(3a1 + 3a2 + 2a3 + a4). Как видим, палочки, которые соединяются первыми, включаются в итоговую стоимость больше, чем те, которые выбираются позже. Следовательно, оптимально сначала выбирать меньшие палочки, чтобы получить наименьшую стоимость.

3⃣Для выполнения следующих задач будет оптимальна структура данных min heap (которая обычно реализуется как PriorityQueue в большинстве языков): получить две самые маленькие палочки (stick1 и stick2) из массива; добавить одну палочку (stick1 + stick2) обратно в массив. Эта структура данных дает сложность O(logN) для обеих операций.

😎 Решение

class Solution {
    func connectSticks(_ sticks: [Int]) -> Int {
        var totalCost = 0
        var pq = PriorityQueue(sticks)
        while pq.count > 1 {
            let cost = pq.dequeue()! + pq.dequeue()!
            totalCost += cost
            pq.enqueue(cost)
        }
        
        return totalCost
    }
}
struct PriorityQueue<T: Comparable> {
    private var heap: [T]

    init(_ elements: [T] = []) {
        self.heap = elements
        heapify()
    }
    var count: Int { heap.count }
    mutating func enqueue(_ element: T) {
        heap.append(element)
        siftUp(heap.count - 1)
    }
    mutating func dequeue() -> T? {
        guard !heap.isEmpty else { return nil }
        if heap.count == 1 { return heap.removeFirst() }
        heap.swapAt(0, heap.count - 1)
        let removed = heap.removeLast()
        siftDown(0)
        return removed
    }
    private mutating func heapify() {
        for index in (0..<(heap.count / 2)).reversed() {
            siftDown(index)
        }
    }
    private mutating func siftUp(_ index: Int) {
        var childIndex = index
        let child = heap[childIndex]
        var parentIndex = (childIndex - 1) / 2
        while childIndex > 0 && child < heap[parentIndex] {
            heap[childIndex] = heap[parentIndex]
            childIndex = parentIndex
            parentIndex = (childIndex - 1) / 2
        }
        heap[childIndex] = child
    }
    private mutating func siftDown(_ index: Int) {
        var parentIndex = index
        while true {
            let leftChildIndex = 2 * parentIndex + 1
            let rightChildIndex = 2 * parentIndex + 2
            var optionalParentIndex = parentIndex
            if leftChildIndex < heap.count && heap[leftChildIndex] < heap[optionalParentIndex] {
                optionalParentIndex = leftChildIndex
            }
            if rightChildIndex < heap.count && heap[rightChildIndex] < heap[optionalParentIndex] {
                optionalParentIndex = rightChildIndex
            }
            if optionalParentIndex == parentIndex { return }
            heap.swapAt(parentIndex, optionalParentIndex)
            parentIndex = optionalParentIndex
        }
    }
}

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

Задача: 188. Best Time to Buy and Sell Stock IV
Сложность: hard

Дан массив целых чисел prices, где prices[i] - это цена данной акции в i-й день, и целое число k.

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

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

Пример:

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

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

1⃣Инициализация DP массива: Инициализируйте трехмерный массив dp, где dp[i][j][l] представляет максимальную прибыль на конец i-го дня с j оставшимися транзакциями и l акциями в портфеле. Начните с dp[0][0][0] = 0 (нет прибыли без акций и транзакций) и dp[0][1][1] = -prices[0] (покупка первой акции).

2⃣Вычисление переходов: Для каждого дня и каждого возможного количества транзакций вычислите возможные действия: держать акцию, не держать акцию, купить акцию, если j > 0, или продать акцию. Обновляйте dp с использованием:
dp[i][j][1] = max(dp[i−1][j][1], dp[i−1][j−1][0] - prices[i]) (максимум между удержанием акции и покупкой новой).
dp[i][j][0] = max(dp[i−1][j][0], dp[i−1][j][1] + prices[i]) (максимум между неудержанием акции и продажей).

3⃣Расчет результатов: По завершении всех дней, возвращайте максимальное значение dp[n-1][j][0] для всех j от 0 до k, что представляет максимальную прибыль без удержания акций на последний день. Обработайте специальный случай, когда 𝑘×2≥𝑛, чтобы избежать лишних расчетов.

😎 Решение:

class Solution {
    func maxProfit(_ k: Int, _ prices: [Int]) -> Int {
        let n = prices.count
        if n <= 0 || k <= 0 { return 0 }
        if k * 2 >= n {
            return prices.dropFirst().enumerated().reduce(0) { $0 + max(0, prices[$1.offset + 1] - prices[$1.offset]) }
        }
        var dp = Array(repeating: Array(repeating: [Int.min / 2, Int.min / 2], count: k + 1), count: n)
        dp[0][0][0] = 0
        dp[0][1][1] = -prices[0]

        for i in 1..<n {
            for j in 0...k {
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i])
                if j > 0 {
                    dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i])
                }
            }
        }
        return dp[n - 1].map { $0[0] }.max() ?? 0
    }
}

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

Задача: №18. 4Sum
Сложность: medium

Учитывая массив nums из n целых чисел, верните массив всех уникальных четверок [nums[a], nums[b], nums[c], nums[d]] таких, что:
- 0 <= a, b, c, d < n
- a, b, c и d различны.
- nums[a] + nums[b] + nums[c] + nums[d] == target

Вы можете вернуть ответ в любом порядке.

Пример:

Input: nums = [1,0,-1,0,-2,2], target = 0  
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]  

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

1⃣Отсортировать массив для удобного пропуска дубликатов и эффективного поиска.

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

3⃣Обрабатывать дубликаты, чтобы избежать повторяющихся четверок.

😎 Решение:

class Solution {
    func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
        let len = nums.count
        guard len >= 4 else { return [] }
        
        var result = [[Int]]()
        let sort = nums.sorted()
        
        for a in 0..<(len - 3) {
            if a > 0, sort[a] == sort[a - 1] { continue }
            for b in (a + 1)..<(len - 2) {
                if b > a + 1, sort[b] == sort[b - 1] { continue }
                
                var c = b + 1, d = len - 1
                while c < d {
                    let sum = sort[a] + sort[b] + sort[c] + sort[d]
                    if sum == target {
                        result.append([sort[a], sort[b], sort[c], sort[d]])
                        repeat { c += 1 } while c < d && sort[c] == sort[c - 1]
                        repeat { d -= 1 } while c < d && sort[d] == sort[d + 1]
                    } else if sum < target {
                        c += 1
                    } else {
                        d -= 1
                    }
                }
            }
        }
        return result
    }
}

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