資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中使陣列嚴格遞增
假設我們有兩個陣列 arr1 和 arr2，它們可以儲存整數。我們必須找到使 arr1 嚴格遞增所需的最小操作次數。在這裡，我們可以選擇兩個索引 0 <= i < n 和 0 <= j < m 並執行賦值 arr1[i] = arr2[j]（n 和 m 分別是 arr1 和 arr2 的大小）
如果我們無法使陣列 arr1 嚴格遞增，則返回 -1。
因此，如果輸入類似於 arr1 = [1,5,3,7,8]，arr2 = [1,3,2,5]，則輸出將為 1，因為我們可以將 5 替換為 2，然後陣列將為 [1,2,3,7,8]。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式 solve()，它將接收一個數組 arr1、一個數組 arr2、i、j、prev 和一個二維陣列 dp，
如果 i >= arr1 的大小，則：
返回 1
j 為從 arr2[j] 及其上方的 arr2 的子陣列的第一個元素
如果 dp[i, j] 不等於 -1，則：
返回 dp[i, j]
ret := arr2 的大小 + 1
如果 prev < arr1[i]，則：
ret := ret 和 solve(arr1, arr2, i + 1, j, arr1[i], dp) 的最小值
如果 j < arr2 的大小，則：
ret := ret 和 1 + solve(arr1, arr2, i + 1, j, arr2[j], dp) 的最小值
返回 dp[i, j] = ret
從主方法中執行以下操作：
對陣列 arr2 進行排序
n := arr1 的大小
m := arr2 的大小
定義一個大小為 2005 x 2005 的二維陣列 dp 並將其填充為 -1
ret := solve(arr1, arr2, 0, 0, -inf, dp)
返回（如果 ret > arr2 的大小，則返回 -1，否則返回 ret - 1）
讓我們看看以下實現以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector<int>& arr1, vector<int>& arr2, int i, int j, int prev, vector<vector<int> >& dp){
if (i >= arr1.size())
return 1;
j = upper_bound(arr2.begin() + j, arr2.end(), prev) - arr2.begin();
if (dp[i][j] != -1)
return dp[i][j];
int ret = arr2.size() + 1;
if (prev < arr1[i]) {
ret = min(ret, solve(arr1, arr2, i + 1, j, arr1[i], dp));
}
if (j < arr2.size()) {
ret = min(ret, 1 + solve(arr1, arr2, i + 1, j, arr2[j], dp));
}
return dp[i][j] = ret;
}
int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2){
sort(arr2.begin(), arr2.end());
int n = arr1.size();
int m = arr2.size();
vector<vector<int> > dp(2005, vector<int>(2005, -1));
int ret = solve(arr1, arr2, 0, 0, INT_MIN, dp);
return ret > arr2.size() ? -1 : ret - 1;
}
};
main(){
Solution ob;
vector<int> v = {1,5,3,7,8}, v1 = {1,3,2,5};
cout << (ob.makeArrayIncreasing(v,v1));
}輸入
{1,5,3,7,8}, {1,3,2,5}輸出
1
299 次瀏覽
