[经典面试题][百度]数轴上从左到右有n各点a[0], a[1], ……,a[n -1]，给定一根长度为L的绳子，求绳子最多能覆盖其中的几个点。
题目
数轴上从左到右有n各点a[0], a[1], ……,a[n -1]，给定一根长度为L的绳子，求绳子最多能覆盖其中的几个点。
思路一
遍历所有区间跟绳子L比较。
i遍历区间起点，j遍历区间终点。
时间复杂度为O(n^2)
代码一
<code class=" hljs cpp" style="box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; padding: 0.5em; color: rgb(0, 0, 0); border-top-left-radius: 0px; border-top-right-radius: 0px; border-bottom-right-radius: 0px; border-bottom-left-radius: 0px; display: block; background-color: transparent !important;"> <span class="hljs-comment" style="box-sizing: border-box; color: rgb(136, 136, 136);">/*-------------------------------------
* 日期：2015-02-08
* 作者：SJF0115
* 题目: 绳子覆盖
* 来源：百度2014
* 博客：
------------------------------------*/</span>
<span class="hljs-preprocessor" style="box-sizing: border-box; color: rgb(136, 0, 0);">#include <iostream></span>
<span class="hljs-preprocessor" style="box-sizing: border-box; color: rgb(136, 0, 0);">#include <vector></span>
<span class="hljs-preprocessor" style="box-sizing: border-box; color: rgb(136, 0, 0);">#include <cstring></span>
<span class="hljs-preprocessor" style="box-sizing: border-box; color: rgb(136, 0, 0);">#include <algorithm></span>
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">using</span> <span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">namespace</span> <span class="hljs-built_in" style="box-sizing: border-box; font-weight: bold;">std</span>;
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">class</span> Solution {
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">public</span>:
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(136, 136, 136);">// points 给定点 L 绳子长度</span>
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">int</span> RopeCover(<span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="box-sizing: border-box; font-weight: bold;">vector</span><<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">int</span>></span> points,<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">int</span> L) {
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">int</span> size = points.size();
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">if</span>(size <= <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">0</span>){
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">return</span> <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">0</span>;
}<span class="hljs-comment" style="box-sizing: border-box; color: rgb(136, 136, 136);">//if</span>
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(136, 136, 136);">// 所能覆盖的最多点数</span>
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">int</span> max = <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">0</span>;
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">int</span> start = <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">0</span>,end = <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">0</span>;
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(136, 136, 136);">// i起点 j终点 遍历所有区间;</span>
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">for</span>(<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">int</span> i = <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">0</span>;i < size-<span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">1</span>;++i){
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">for</span>(<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">int</span> j = i+<span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">1</span>;j < size;++j){
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">if</span>(points[j] - points[i] <= L && j - i + <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">1</span> > max){
max = j - i + <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">1</span>;
start = i;
end = j;
}<span class="hljs-comment" style="box-sizing: border-box; color: rgb(136, 136, 136);">//if</span>
}
}<span class="hljs-comment" style="box-sizing: border-box; color: rgb(136, 136, 136);">//for</span>
<span class="hljs-built_in" style="box-sizing: border-box; font-weight: bold;">cout</span><<<span class="hljs-string" style="box-sizing: border-box; color: rgb(136, 0, 0);">"起点->"</span><<start<<<span class="hljs-string" style="box-sizing: border-box; color: rgb(136, 0, 0);">" 终点->"</span><<end<<endl;
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">return</span> max;
}
};
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">int</span> main(){
Solution s;
<span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="box-sizing: border-box; font-weight: bold;">vector</span><<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">int</span>></span> points = {-<span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">1</span>,<span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">0</span>,<span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">3</span>,<span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">9</span>,<span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">11</span>,<span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">25</span>};
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">int</span> L = <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">15</span>;
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">int</span> result = s.RopeCover(points,L);
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(136, 136, 136);">// 输出</span>
<span class="hljs-built_in" style="box-sizing: border-box; font-weight: bold;">cout</span><<result<<endl;
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">return</span> <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">0</span>;
}
</code>
思路二
两个指针,start，end。
如果points[front]-points[rear]<=L，头start向前移动一步。
如果points[front]-points[rear]>L，尾巴end向前移动一步。
每个数最多遍历2遍，因此时间复杂度为O(n)。
对于这个算法，某网友给了一个形象的比喻：
就好像一条长度为L的蛇。头伸不过去的话，就把尾巴缩过来最多只需要走一次，就知道能覆盖几个点
代码二
<code class=" hljs cpp" style="box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; padding: 0.5em; color: rgb(0, 0, 0); border-top-left-radius: 0px; border-top-right-radius: 0px; border-bottom-right-radius: 0px; border-bottom-left-radius: 0px; display: block; background-color: transparent !important;"> <span class="hljs-comment" style="box-sizing: border-box; color: rgb(136, 136, 136);">/*-------------------------------------
* 日期：2015-02-08
* 作者：SJF0115
* 题目: 绳子覆盖
* 来源：百度2014
* 博客：
------------------------------------*/</span>
<span class="hljs-preprocessor" style="box-sizing: border-box; color: rgb(136, 0, 0);">#include <iostream></span>
<span class="hljs-preprocessor" style="box-sizing: border-box; color: rgb(136, 0, 0);">#include <vector></span>
<span class="hljs-preprocessor" style="box-sizing: border-box; color: rgb(136, 0, 0);">#include <cstring></span>
<span class="hljs-preprocessor" style="box-sizing: border-box; color: rgb(136, 0, 0);">#include <algorithm></span>
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">using</span> <span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">namespace</span> <span class="hljs-built_in" style="box-sizing: border-box; font-weight: bold;">std</span>;
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">class</span> Solution {
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">public</span>:
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(136, 136, 136);">// points 给定点 L 绳子长度</span>
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">int</span> RopeCover(<span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="box-sizing: border-box; font-weight: bold;">vector</span><<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">int</span>></span> points,<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">int</span> L) {
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">int</span> size = points.size();
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">if</span>(size <= <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">0</span>){
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">return</span> <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">0</span>;
}<span class="hljs-comment" style="box-sizing: border-box; color: rgb(136, 136, 136);">//if</span>
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(136, 136, 136);">// 所能覆盖的最多点数</span>
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">int</span> max = <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">0</span>;
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">int</span> start = <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">1</span>,end = <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">0</span>;
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">int</span> maxS = <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">0</span>,maxE = <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">0</span>;
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">while</span>(end < start){
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">if</span>(points[start] - points[end] <= L){
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">if</span>(start - end + <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">1</span> > max){
max = start - end + <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">1</span>;
maxS = end;
maxE = start;
}<span class="hljs-comment" style="box-sizing: border-box; color: rgb(136, 136, 136);">//if</span>
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(136, 136, 136);">// 头向前移动一格</span>
++start;
}<span class="hljs-comment" style="box-sizing: border-box; color: rgb(136, 136, 136);">//if</span>
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">else</span>{
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(136, 136, 136);">// 尾巴向前移动一格</span>
++end;
}
}<span class="hljs-comment" style="box-sizing: border-box; color: rgb(136, 136, 136);">//while</span>
<span class="hljs-built_in" style="box-sizing: border-box; font-weight: bold;">cout</span><<<span class="hljs-string" style="box-sizing: border-box; color: rgb(136, 0, 0);">"起点->"</span><<maxS<<<span class="hljs-string" style="box-sizing: border-box; color: rgb(136, 0, 0);">" 终点->"</span><<maxE<<endl;
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">return</span> max;
}
};
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">int</span> main(){
Solution s;
<span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="box-sizing: border-box; font-weight: bold;">vector</span><<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">int</span>></span> points = {-<span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">1</span>,<span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">3</span>,<span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">4</span>,<span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">9</span>,<span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">11</span>,<span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">25</span>};
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">int</span> L = <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">8</span>;
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">int</span> result = s.RopeCover(points,L);
<span class="hljs-comment" style="box-sizing: border-box; color: rgb(136, 136, 136);">// 输出</span>
<span class="hljs-built_in" style="box-sizing: border-box; font-weight: bold;">cout</span><<result<<endl;
<span class="hljs-keyword" style="box-sizing: border-box; font-weight: bold;">return</span> <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 136, 0);">0</span>;
}
</code>
如果本方法有什么问题，欢迎指正。如果有更好的方法，欢迎指导。