594. 最长和谐子序列-快速排序
2023-09-14 09:06:54 时间
594. 最长和谐子序列-快速排序
和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。
现在,给你一个整数数组 nums ,请你在所有可能的子序列中找到最长的和谐子序列的长度。
数组的子序列是一个由数组派生出来的序列,它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。
示例 1:
输入:nums = [1,3,2,2,5,2,3,7]
输出:5
解释:最长的和谐子序列是 [3,2,2,2,3]
示例 2:
输入:nums = [1,2,3,4]
输出:2
示例 3:
输入:nums = [1,1,1,1]
输出:0
解题代码如下:
void quick(int *a,int low,int high){
if(low<high){
int l=low,h=high,p=a[low];
while(low<high){
while(low<high&&a[high]>=p){
high--;
}
a[low]=a[high];
while(low<high&&a[low]<=p){
low++;
}
a[high]=a[low];
}
a[low]=p;
quick(a,l,low-1);
quick(a,low+1,h);
}
}
int findLHS(int* nums, int numsSize){
quick(nums,0,numsSize-1);
int max=0;
for(int i=0;i<numsSize;){
int start=nums[i];
int index=i;
int next=-1;
for(;i<numsSize;){
if(nums[i]<=start+1){
i++;
}
else{
break;
}
if(i<numsSize){
if(nums[i]!=start&&next==-1){
next=i;
}
}
}
if(nums[i-1]!=start)
max=fmax(i-index,max);
if(next!=-1){
i=next;
}
}
return max;
}
相关文章
- 机器学习笔记 - 时间序列预测研究:法国香槟的月销量
- Grafana Panel 面板介绍和Time series(时间序列)
- QuantitativeFinance:量化金融之金融时间序列分析之ES/ETS/GARCH模型的简介、Box-Jenkins方法-AR/MA/ARMA/ARIMA模型的简介及其建模四大步骤之详细攻略
- 【关于时间序列的ML】项目 8 :使用 Facebook Prophet 模型预测股票价格
- 剑指 Offer II 095. 最长公共子序列-动态规划算法
- Leetcode 2099. 找到和最大的长度为 K 的子序列(已解决)
- 据序和中序序列或者也许为了一个二进制序列,恢复二进制和打印图像(c语言)
- C++基本序列式容器 list (二)
- 上升时间最长的序列
- 类似前缀和的 left min 和 right max,在求解买卖股票的最佳时机、递增的三元子序列比较有效
- 关于时间序列数据库的思考——(1)运用hash文件(例如:RRD,Whisper) (2)运用LSM树来备份(例如:LevelDB,RocksDB,Cassandra) (3)运用B-树排序和k/v存储(例如:BoltDB,LMDB)
- Keras之MLPR:利用MLPR算法(3to1【窗口法】+【Input(3)→(12+8)(relu)→O(mse)】)实现根据历史航空旅客数量数据集(时间序列数据)预测下月乘客数量问题
- 动态规划——最长公共子序列(闫氏DP)