(笔试题)最大覆盖点
最大 笔试 覆盖
2023-09-14 08:59:06 时间
题目:
坐标轴上从左到右依次的点为a[0]、a[1]、a[2]……a[n-1],设一根木棒的长度为L,求L最多能覆盖坐标轴的几个点?
思路:
这是一道简单的数组题,
方法也很简单:直接从左到右扫描,两个指针i和j,i从位置0开始,j从位置1开始,如果a[j] - a[i] <= L(采用<=,是因为可能某个区间不能刚好等于L),则j++,并记录中间经过的点个数,如果a[j] - a[i] > L,则j--回退,覆盖点个数-1,回到刚好满足条件的时候,将满足条件的最大值与所求最大值比较,然后i++,j++,直到求出最大的点个数(结果可能有多种情况,只取第一次满足的情况)。
代码:
#include<iostream> using namespace std; int maxCover(int a[],int n,int L){ int i=0,j=1; int count=1,maxCount=1,start; while(i<n && j<n){ while((j<n) && (a[j]-a[i]<=L)){ j++; count++; } j--; if(maxCount<count){ maxCount=count; start=i; } i++; j++; count--; } cout<<"Covered points: \n"; for(int i=start;i<start+maxCount;i++) cout<<a[i]<<" "; cout<<endl; return maxCount; } int main() { // test int len; int L=8; int a[] = { 1, 3, 6, 8, 9,10, 11, 12, 13, 15, 16, 17, 18 }; len=sizeof(a)/sizeof(a[0]); cout<<"max count: "<<maxCover(a,len,L)<<endl;; int b[] = { 1, 2, 3, 4, 5, 100, 1000 }; len=sizeof(b)/sizeof(b[0]); cout<<"max count: "<<maxCover(b,len,L)<<endl; return 0; }
运行结果:
相关文章
- 最大似然估计(MLE)入门教程
- TINYTEXT,TEXT,MEDIUMTEXT和LONGTEXT最大存储容量
- 队列达到最大长度代码实战
- IPv4地址已经完全耗尽,互联网还能正常运转,NAT是最大功臣!
- 最常用的四大Mac磁盘空间清理方法,这些内存占比是最大的
- 比特币市场持续失血 钱都去了哪儿?以太币或成最大赢家
- 世界最大冰山在南极洲形成
- 值【MYSQL中:查询精准获取时间最大值】(mysql时间最大)
- 募资650亿,A股近十年最大IPO要来了
- Redis抵达数据最大上限(redis数量上限)
- 为什么 Schnorr 签名被誉为比特币 Segwit 后的最大技术更新
- 值Oracle中查询最大值的方法(oracle 查询最大)
- 查询Redis最大连接数实现全面的性能优化(查询redis最大连接数)
- 如何优化Redis使其发挥最大性能(怎么优化redis)
- 网页中实现浏览器的最大,最小化和关闭按钮