[经典面试题][百度]数轴上从左到右有n各点a[0], a[1], ……,a[n -1],给定一根长度为L的绳子,求绳子最多能覆盖其中的几个点。

本文主要是介绍[经典面试题][百度]数轴上从左到右有n各点a[0], a[1], ……,a[n -1],给定一根长度为L的绳子,求绳子最多能覆盖其中的几个点。,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

数轴上从左到右有n各点a[0], a[1], ……,a[n -1],给定一根长度为L的绳子,求绳子最多能覆盖其中的几个点。

思路一

遍历所有区间跟绳子L比较。
i遍历区间起点,j遍历区间终点。
时间复杂度为O(n^2)

这里写图片描述

代码一

    /*-------------------------------------*   日期:2015-02-08*   作者:SJF0115*   题目: 绳子覆盖*   来源:百度2014*   博客:------------------------------------*/#include <iostream>#include <vector>#include <cstring>#include <algorithm>using namespace std;class Solution {public:// points 给定点 L 绳子长度int RopeCover(vector<int> points,int L) {int size = points.size();if(size <= 0){return 0;}//if// 所能覆盖的最多点数int max = 0;int start = 0,end = 0;// i起点 j终点 遍历所有区间;for(int i = 0;i < size-1;++i){for(int j = i+1;j < size;++j){if(points[j] - points[i] <= L && j - i + 1 > max){max = j - i + 1;start = i;end = j;}//if}}//forcout<<"起点->"<<start<<" 终点->"<<end<<endl;return max;}};int main(){Solution s;vector<int> points = {-1,0,3,9,11,25};int L = 15;int result = s.RopeCover(points,L);// 输出cout<<result<<endl;return 0;}

思路二

两个指针,start,end。
如果points[front]-points[rear]<=L,头start向前移动一步。
如果points[front]-points[rear]>L,尾巴end向前移动一步。
每个数最多遍历2遍,因此时间复杂度为O(n)。
对于这个算法,某网友给了一个形象的比喻:
就好像一条长度为L的蛇。头伸不过去的话,就把尾巴缩过来最多只需要走一次,就知道能覆盖几个点

这里写图片描述

代码二

    /*-------------------------------------*   日期:2015-02-08*   作者:SJF0115*   题目: 绳子覆盖*   来源:百度2014*   博客:------------------------------------*/#include <iostream>#include <vector>#include <cstring>#include <algorithm>using namespace std;class Solution {public:// points 给定点 L 绳子长度int RopeCover(vector<int> points,int L) {int size = points.size();if(size <= 0){return 0;}//if// 所能覆盖的最多点数int max = 0;int start = 1,end = 0;int maxS = 0,maxE = 0;while(end < start){if(points[start] - points[end] <= L){if(start - end + 1 > max){max = start - end + 1;maxS = end;maxE = start;}//if// 头向前移动一格++start;}//ifelse{// 尾巴向前移动一格++end;}}//whilecout<<"起点->"<<maxS<<" 终点->"<<maxE<<endl;return max;}};int main(){Solution s;vector<int> points = {-1,3,4,9,11,25};int L = 8;int result = s.RopeCover(points,L);// 输出cout<<result<<endl;return 0;}

如果本方法有什么问题,欢迎指正。如果有更好的方法,欢迎指导。

这篇关于[经典面试题][百度]数轴上从左到右有n各点a[0], a[1], ……,a[n -1],给定一根长度为L的绳子,求绳子最多能覆盖其中的几个点。的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/723104

相关文章

MySQL 获取字符串长度及注意事项

《MySQL获取字符串长度及注意事项》本文通过实例代码给大家介绍MySQL获取字符串长度及注意事项,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql 获取字符串长度详解 核心长度函数对比⚠️ 六大关键注意事项1. 字符编码决定字节长度2

全面解析MySQL索引长度限制问题与解决方案

《全面解析MySQL索引长度限制问题与解决方案》MySQL对索引长度设限是为了保持高效的数据检索性能,这个限制不是MySQL的缺陷,而是数据库设计中的权衡结果,下面我们就来看看如何解决这一问题吧... 目录引言:为什么会有索引键长度问题?一、问题根源深度解析mysql索引长度限制原理实际场景示例二、五大解决

Java实现按字节长度截取字符串

《Java实现按字节长度截取字符串》在Java中,由于字符串可能包含多字节字符,直接按字节长度截取可能会导致乱码或截取不准确的问题,下面我们就来看看几种按字节长度截取字符串的方法吧... 目录方法一:使用String的getBytes方法方法二:指定字符编码处理方法三:更精确的字符编码处理使用示例注意事项方

Git可视化管理工具(SourceTree)使用操作大全经典

《Git可视化管理工具(SourceTree)使用操作大全经典》本文详细介绍了SourceTree作为Git可视化管理工具的常用操作,包括连接远程仓库、添加SSH密钥、克隆仓库、设置默认项目目录、代码... 目录前言:连接Gitee or github,获取代码:在SourceTree中添加SSH密钥:Cl

Java覆盖第三方jar包中的某一个类的实现方法

《Java覆盖第三方jar包中的某一个类的实现方法》在我们日常的开发中,经常需要使用第三方的jar包,有时候我们会发现第三方的jar包中的某一个类有问题,或者我们需要定制化修改其中的逻辑,那么应该如何... 目录一、需求描述二、示例描述三、操作步骤四、验证结果五、实现原理一、需求描述需求描述如下:需要在

vue解决子组件样式覆盖问题scoped deep

《vue解决子组件样式覆盖问题scopeddeep》文章主要介绍了在Vue项目中处理全局样式和局部样式的方法,包括使用scoped属性和深度选择器(/deep/)来覆盖子组件的样式,作者建议所有组件... 目录前言scoped分析deep分析使用总结所有组件必须加scoped父组件覆盖子组件使用deep前言

Python绘制土地利用和土地覆盖类型图示例详解

《Python绘制土地利用和土地覆盖类型图示例详解》本文介绍了如何使用Python绘制土地利用和土地覆盖类型图,并提供了详细的代码示例,通过安装所需的库,准备地理数据,使用geopandas和matp... 目录一、所需库的安装二、数据准备三、绘制土地利用和土地覆盖类型图四、代码解释五、其他可视化形式1.

百度/小米/滴滴/京东,中台架构比较

小米中台建设实践 01 小米的三大中台建设:业务+数据+技术 业务中台--从业务说起 在中台建设中,需要规范化的服务接口、一致整合化的数据、容器化的技术组件以及弹性的基础设施。并结合业务情况,判定是否真的需要中台。 小米参考了业界优秀的案例包括移动中台、数据中台、业务中台、技术中台等,再结合其业务发展历程及业务现状,整理了中台架构的核心方法论,一是企业如何共享服务,二是如何为业务提供便利。

每天认识几个maven依赖(ActiveMQ+activemq-jaxb+activesoap+activespace+adarwin)

八、ActiveMQ 1、是什么? ActiveMQ 是一个开源的消息中间件(Message Broker),由 Apache 软件基金会开发和维护。它实现了 Java 消息服务(Java Message Service, JMS)规范,并支持多种消息传递协议,包括 AMQP、MQTT 和 OpenWire 等。 2、有什么用? 可靠性:ActiveMQ 提供了消息持久性和事务支持,确保消

uva 10061 How many zero's and how many digits ?(不同进制阶乘末尾几个0)+poj 1401

题意是求在base进制下的 n!的结果有几位数,末尾有几个0。 想起刚开始的时候做的一道10进制下的n阶乘末尾有几个零,以及之前有做过的一道n阶乘的位数。 当时都是在10进制下的。 10进制下的做法是: 1. n阶位数:直接 lg(n!)就是得数的位数。 2. n阶末尾0的个数:由于2 * 5 将会在得数中以0的形式存在,所以计算2或者计算5,由于因子中出现5必然出现2,所以直接一