Сложность: hard
Даны два целочисленных массива arr1 и arr2. Верните минимальное количество операций (возможно, ноль), необходимых для того, чтобы сделать arr1 строго возрастающим.
В одной операции вы можете выбрать два индекса 0 <= i < arr1.length и 0 <= j < arr2.length и выполнить присваивание arr1[i] = arr2[j].
Если нет способа сделать arr1 строго возрастающим, верните -1.
Пример:
Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].
👨💻 Алгоритм:
1⃣Сначала отсортируйте массив arr2 и инициализируйте хэш-таблицу dp для хранения промежуточных результатов. Определите функцию dfs(i, prev), которая вычисляет минимальное количество операций для сортировки массива arr1, начиная с индекса i, при условии, что предыдущий элемент равен prev. Если результат для (i, prev) уже существует в dp, то просто верните сохраненное значение.
2⃣Внутри функции dfs инициализируйте переменную cost значением float('inf'). Если arr1[i] больше, чем prev, обновите значение cost результатом вызова dfs(i + 1, arr1[i]). Используйте бинарный поиск, чтобы найти индекс idx наименьшего значения в arr2, которое больше prev. Если такой индекс существует, обновите значение cost результатом минимального значения между текущим значением cost и 1 + dfs(i + 1, arr2[idx]).
3⃣После всех вычислений обновите dp[(i, prev)] значением cost и верните cost. В конце вызовите dfs(0, -1) и верните его значение, если оно не равно float('inf'); в противном случае верните -1.
😎 Решение:
class Solution:
def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
arr2 = sorted(set(arr2))
dp = {}
def dfs(i, prev):
if i == len(arr1):
return 0
if (i, prev) in dp:
return dp[(i, prev)]
cost = 2001
if arr1[i] > prev:
cost = dfs(i + 1, arr1[i])
idx = bisect.bisect_right(arr2, prev)
if idx < len(arr2):
cost = min(cost, 1 + dfs(i + 1, arr2[idx]))
dp[(i, prev)] = cost
return cost
result = dfs(0, -1)
return result if result < 2001 else -1
Ставь 👍 и забирай 📚 Базу знаний