資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++程式：查詢音樂音符的最大可實現多樣性
假設我們有一個包含n個元素的字串S。Amal的歌曲包含n個音符，我們將將其視為正整數。歌曲的多樣性是它包含的不同音符的數量。我們想要使它更加多樣化。我們不能隨意更改歌曲。相反，對於歌曲中的每個n個音符，她可以保留其原樣或將其增加1。給定的序列是一首歌曲，其中整數描述音符，我們必須找出最大可實現的多樣性。
問題類別
上述問題可以透過應用貪心問題解決技術來解決。貪心演算法技術是一種演算法型別，其中選擇當前最佳解決方案，而不是遍歷所有可能的解決方案。貪心演算法技術也用於解決最佳化問題，例如其更大的兄弟動態規劃。在動態規劃中，有必要遍歷所有可能的子問題以找出最佳解決方案，但它有一個缺點；它需要更多的時間和空間。因此，在各種情況下，使用貪心技術來找到問題的最佳解決方案。雖然它並非在所有情況下都能提供最佳解決方案，但如果設計得當，它可以比動態規劃問題更快地產生解決方案。貪心技術為最佳化問題提供區域性最優解。此技術的示例包括克魯斯卡爾和普里姆的最小生成樹 (MST) 演算法、霍夫曼樹編碼、迪傑斯特拉的單源最短路徑問題等。
https://tutorialspoint.tw/data_structures_algorithms/greedy_algorithms.htm
https://tutorialspoint.tw/data_structures_algorithms/dynamic_programming.htm
因此，如果我們問題的輸入類似於 A = [1, 2, 2, 2, 5, 6]，則輸出將為 5，因為我們可以將第二個、第五個和第六個元素增加以獲得序列 1, 3, 2, 2, 6, 7，它有 5 個不同的元素。
步驟
為了解決這個問題，我們將遵循以下步驟：
n := size of A Define one set s for initialize i := 0, when i < n, update (increase i by 1), do: x := A[i] if x is in s, then: (increase x by 1) insert x into s return size of s
示例
讓我們看看以下實現以獲得更好的理解：
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
int n = A.size();
set<int> s;
for (int i = 0; i < n; i++){
int x = A[i];
if (s.count(x))
x++;
s.insert(x);
}
return s.size();
}
int main(){
vector<int> A = { 1, 2, 2, 2, 5, 6 };
cout << solve(A) << endl;
}輸入
{ 1, 2, 2, 2, 5, 6 }輸出
5
130 次檢視
