首页 > 笔试面试题, 算法 数据结构 > 定长线段最多覆盖点的个数

定长线段最多覆盖点的个数

2013年1月5日 发表评论 阅读评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

来自之前百度一面的题目:给定一系列x轴的点坐标,例如 1,3,7,8,9,11这些坐标升序放在数组中,现在给一根绳子,长度为4,问绳子最多能覆盖的点数有多少,例如绳子放前面只能覆盖两个点,1,3,如果放后面能覆盖4个点。

题目不难,但也不是太容易想出来,两个指针前后跑的思路:两个指针往前走,前面的负责加,后面的负责减,前面的每次都移动,如果点间隔长度大于绳子长度,后面指针移动。

代码如下:

#include <iostream>
using namespace std;

#define ARRAYMAX 100

/* input:
 * pointNumber, segmentLength
 * the points
 * output:
 * the most number of cover points
 * input:
 * 6 4
 * 1 3 7 8 9 11
 * output:
 * 4
 */

/* 计算线段最多覆盖点数 */
int calculateNum(int * arr, int pointNum, int segLen)
{
	if(arr == NULL || pointNum <= 0 || segLen <= 0)	return 0;

	int frontPtr = 0, rearPtr = 1, coverMax = 1;
	while(rearPtr < pointNum)
	{
		while(arr[rearPtr] - arr[frontPtr] > segLen)
		{
			++frontPtr;
		}
		coverMax = (rearPtr-frontPtr+1) > coverMax ? (rearPtr-frontPtr+1) : coverMax;
		++rearPtr;
	}
	return coverMax;
}

void main()
{
	int pointArray[ARRAYMAX];
	int pointNum, segLen;
	scanf("%d %d", &pointNum, &segLen);
	for(int i = 0; i < pointNum; ++i)
	{
		scanf("%d",&pointArray[i]);
	}
	printf("%d\n",calculateNum(pointArray,pointNum,segLen));
}

(全文完)

  • 星云

    if(segLen == 1) return 1;
    似乎有问题,绳子长度为1时有可能覆盖两个点吧?当绳子长度为0时,才只能覆盖一个点。

    • Yx.Ac

      @星云 绳子长为0,覆盖点是0,不能是1;不过当segLen==1时,确实有可能覆盖两个点,所以将此语句去掉即可,只要segLen大于0,就进行计算,无论是覆盖1个点还是两个点,都没问题。谢谢指出错误,已更正!