下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
课后练习//生成滑动窗口的最大值数组//例如,k=3//4,3,5,4,3,3,6,7//[4,3,5],4,3,3,6,7//4,[3,5,4],3,3,6,7//4,3,[5,4,3],3,6,7//4,3,5,[4,3,3],6,7//4,3,5,4,[3,3,6],7//4,3,5,4,3,[3,6,7]//结果://5,5,5,4,6,7课后练习
public
static
int[]slideWindowMax(int[]a,int
k){
if(a==null||a.length<k||k<1)
return
null; Deque<Integer>deck=newArrayDeque<>(k);//预先知道队列的大小,选用ArrayQueue,否则LinkedList
//保证队头是滑动窗口中的最大值
for(int
i=0;i<k;i++){
while(!deck.isEmpty()&&a[i]>(a[deck.peekLast()])){
deck.pollLast(); }
deck.addLast(i); }
int[]result=new
int[a.length-k+1];
int
index=0;
result[index++]=a[deck.peekFirst()];
for(int
i=k;i<a.length;i++){
if(i-deck.peekFirst()>k-1)//超过了当前滑动窗口的最左边的位置
deck.pollFirst();
while(!deck.isEmpty()&&a[i]>(a[deck.peekLast()])){
deck.pollLast(); }
deck.addLast(i);
result[index++]=a[deck.peekFirst()]; }
return
result; }基本数据类型int,使用了比较运算符>比较大小课后练习
//适用于泛型
@SuppressWarnings("unchecked")
public
static<E>E[]slideWindowMax(E[]a,int
k){
if(a==null||a.length<k||k<1)
return
null; Deque<Integer>deck=newArrayDeque<>(k);
//保证队头是滑动窗口中的最大值
for(int
i=0;i<k;i++){ Comparable<?superE>tmp=(Comparable<?superE>)a[i];
while(!deck.isEmpty()&&tmp.compareTo(a[deck.peekLast()])>0){
deck.pollLast(); }
deck.addLast(i); } E[]result=(E[])Array.newInstance(a.getClass().getComponentType(),a.length-k+1);
int
index=0;
result[index++]=a[deck.peekFirst()];
for(int
i=k;i<a.length;i++){
if(i-deck.peekFirst()>k-1)
deck.pollFirst(); Comparable<?superE>tmp=(Comparable<?superE>)a[i];
while(!deck.isEmpty()&&tmp.compareTo(a[deck.peekLast()])>0){
deck.pollLast(); }
deck.addLast(i);
result[index++]=a[deck.peekFirst()]; }
return
result; }引用类型使用compareTo比较大小,要求该类型实现了Compable接口课后练习
//这种写法,去除了重复的代码,但for循环中多了1个if语句(执行时间会多一点),
@SuppressWarnings("unchecked")
public
static<E>E[]slideWindowMax1(E[]a,int
k){
if(a==null||a.length<k||k<1)
return
null; Deque<Integer>deck=newArrayDeque<>(k); E[]result=(E[])Array.newInstance(a.getClass().getComponentType(),a.length-k+1);
int
index=0;
for(int
i=0;i<a.length;i++){ Comparable<?superE>tmp=(Comparable<?superE>)a[i];
while(!deck.isEmpty()&&tmp.compareTo(a[deck.peekLast()])>0){
deck.pollLast(); }
deck.addLast(i);
if(i-deck.peekFirst()>k-1)//
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024光伏组件超薄平板玻璃
- 高中专业发展模拟试卷专业技能与全面能力
- 地理考察:世界各大洲的地理特点和资源分布
- 语法专项:名词的单复数形式和用法
- 谈谈你的理想职业是什么为什么你对它感兴趣
- 小学中国少数民族小测验
- 如何提高小学生的写作表达能力
- 体验剧场成为小小演员
- 月考检测(试题)-2024-2025学年五年级上册数学北师大版
- 初中地理湘教版八年级上册教案设计
- 客户关系维护费用管理制度(初稿)
- 四年级第一学期探究型课程教案
- 栏杆百叶的制作与安装施工方案
- 七年级政治上册第三课《角色与责任》课件 北师大版
- 研究性学习报告-分期付款
- 六年级阅读理解复习-复习-找中心句(课堂PPT)
- VTE健康宣传手册
- 广东城际铁路隧道高压旋喷桩钻芯法检测报告(附图)
- FRAMEWORK CONTRACT框架合同
- 检针机日常点检保养记录表
- 机械臂本科生毕业设计(论文)范文
评论
0/150
提交评论