資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究在 C++ 中查詢具有給定元素移除規則的陣列的最小可能大小
在這個問題中，我們給定一個包含 n 個數字的陣列和一個整數 k。我們的任務是查詢具有給定元素移除規則的陣列的最小可能大小。
問題描述 - 我們需要最小化陣列中的元素數量。透過使用以下刪除操作，每次可以移除的元素數量為 3。如果三個元素滿足兩個給定條件，則可以進行移除，
條件 1 - 三個元素應該是相鄰的。>
條件 2 - 兩個相鄰元素之間的差值為 k，即 arr[i + 1] = arr[i] + k 且 arr[i+2] = arr[i+1] + k。
讓我們舉個例子來理解這個問題，
輸入
{4, 6, 8, 4, 1, 5 }, k = 2輸出
3
解釋
可以進行一次刪除操作，索引為 0、1、2。
解決方案方法
這個問題有點棘手，因為可能存在間接的刪除操作，這些操作可以在執行一次刪除操作後才能看到。例如，我們刪除索引 5、6、7 處的元素。在此刪除操作之後，新陣列可能包含元素 3、4、5，現在它們滿足刪除條件。此類具有重疊子問題的問題可以使用動態規劃方法解決。為此，我們將維護一個 DP[] 矩陣來儲存子問題的結果，以便以後在需要時訪問它們，這稱為記憶化。
程式說明我們解決方案的工作原理，
示例
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
int DP[MAX][MAX];
int calcMinSize(int arr[], int start, int end, int k){
if (DP[start][end] != -1)
return DP[start][end];
if ( (end-start + 1) < 3)
return end-start +1;
int minSize = 1 + calcMinSize(arr, start+1, end, k);
for (int i = start+1; i<=end-1; i++){
for (int j = i+1; j <= end; j++ ){
if (arr[i] == (arr[start] + k) && arr[j] == (arr[start] +
2*k) && calcMinSize(arr, start+1, i-1, k) == 0 && calcMinSize(arr, i+1, j- 1, k) == 0) {
minSize = min(minSize, calcMinSize(arr, j+1, end, k));
}
}
}
return (DP[start][end] = minSize);
}
int main() {
int arr[] = {4, 6, 8, 4, 1, 5 };
int n = sizeof(arr)/sizeof(arr[0]);
int k = 2;
memset(DP, -1, sizeof(DP));
cout<<"The minimum possible size of the array after removal is "<<calcMinSize(arr, 0, n-1, k);
return 0;
}輸出
The minimum possible size of the array after removal is 3
更新於： 2021 年 3 月 12 日
494 次檢視
廣告