数据结构
网络
关系型数据库管理系统
操作系统
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.com/data_structures_algorithms/greedy_algorithms.htm
https://tutorialspoint.com/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 次查看
