此题是在翻勇幸的百度面经文章后看到的。题目描述如下:
给定一系列的X轴的点坐标,例如
1,3,7,8,9,11
,这些坐标升序放在数组中,现在给一根绳子,长度为4,问绳子最多能覆盖的点数是多少?
其实题目不难,是百度一面的题,最直接的方法,就是暴力来解决,首先从array[0]开始遍历数组,找出绳子能包含的点数,然后array[1],依次这样下去。还是更好的方法,用两个指针来处理,一个指针指前面,一个指后面,如果两个指针的差距小于4,前面的指针移动,如果大于或等于4,后面的移动。
int coverMaxPoints(int *array, int len, int seglen){
if(array == NULL || len <=0 || seglen < 0)
return -1;
int i = 0,j = 0;
int max = 0, current = 0, count = 1;
while(j < len - 1){
if(current + array[j+1] - array[j] <= seglen){
current += array[j+1] - array[j];
j++;
count++;
if(count > max)
max = count;
}else{
current -= array[i+1] - array[i];
i++;
count--;
}
}
return max;
}
随后对比了下勇幸的代码,发现自己的写得太不简练了,也没有很好的理解前后两个指针,还有变量命名有些欠缺,然后再重新写了一遍。
int coverMaxPointV2(int *array, int len, int seglen){
if(array == NULL || len <=0 || seglen <= 0)
return 0;
int front = 0, rear = 0, max = 1;
while(front < len){
while(front < len && array[front] - array[rear] <= seglen){
++front;
}
max = (front - rear) > max ? (front - rear) : max;
++rear;
}
return max;
}
这样简炼多了,直接可以用下标差表示点的个数了,不要判断两个数之差然后再来统计点的个数。
使用两个指针的好处是只需要遍历两遍就OK,两个指针分别走一遍,复杂度是O(N),如果如前面使用暴力解法,则复杂度最坏情况下是O(MN),如果存在很多相邻的数之间的差距大于1,则不需要比较M次,再最好的情况下复杂度也是O(N)。