我要招人

去企业版

首页 > 试题广场 >

数轴上从左到右有 n 个点 a[0],a[1],„„,a[n

[问答题]

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

推荐

test2014

满足a[j]-a[i] <= L && a[j+1]-a[i] > L这两个条件的j与i中间的所有点个数中的最大值，即j-i+1最大，方法很简单：直接从左到右扫描，两个指针i和j，i从位置0开始，j从位置1开始，如果a[j] - a[i] <= L则j++并记录中间经过的点个数，如果a[j] - a[i] > L则j--回退，覆盖点个数-1回到刚好满足条件的时候，将满足条件的最大值与所求最大值比较，然后i++,j++直到求出最大的点个数。

有两点需要注意：

（1）这里可能没有i和j使得a[j] - a[i]刚好等于L的，所以判断条件不能为a[j] - a[i] = L。

（2）可能存在不同的覆盖点但覆盖的长度相同，此时只选第一次覆盖的点。

// 求最大覆盖点  
#include <stdio.h> 
int maxCover(int a[], int n, int L){ 
    int count = 2, maxCount = 1, start; 
    int i = 0, j = 1; 
    while(i < n && j < n){ 
        while((j < n) && (a[j] - a[i] <= L))
        {
            j++;
            count++;
        } 
        // 退回到满足条件的j 
        j--;
        count--; 
        if(maxCount < count)
        {
            start = i;
            maxCount = count;
        }
        i++;
        j++;    
    }
    printf("covered point: "); 
    for(i = start; i < start + maxCount; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n"); return maxCount;
} 
int main()
{ 
    // test  
    int a[] = {1, 3, 7, 8, 10, 11, 12, 13, 15, 16, 17, 18, 21};
    printf("max count: %d\n\n", maxCover(a, 13, 8)); int b[] = {1,2,3,4,5,100,1000};
    printf("max count: %d\n", maxCover(b, 7, 8)); return 0;
}

编辑于 2015-01-28 17:03:46 回复(0)

牛客908435449号

public static int maxPoint(int[] arr,int L){
    if(arr == null || arr.length == 0) return 0;
    int res = 1;
    for(int i=0; i<arr.length; i++){
        int leftIndex = getLeft(arr,arr[i]-L,i);
        res = Math.max(res,i-leftIndex+1);
    }
    return res;
}

public static int getLeft(int[] arr,int value,int right){
    int left = 0;
    int mid = left + (right-left)>>1;
    int index = right;
    while(left<=right){
        if(arr[mid]>=value){
            index = mid;
            right = mid-1;
        }else{
            left = mid+1;
        }
        mid = left + (right-left)>>1;
    }
    return index;
}

发表于 2022-02-04 11:00:15 回复(0)

summer201812310132384

时间复杂度o(n)解法

int cover(vector<int> arr,int len)
{
    int begin = 0;
    int end = 0;
    int res = 0;
    while (begin< arr.size())
    {
        while (end + 1< arr.size() && arr[end +1] <= arr[begin] + len)
        {
            ++end;
        }
        res = max(res,end - begin + 1);
        ++begin;
    }
    return res;
}

编辑于 2020-07-11 13:37:17 回复(2)

YvonneZero

int getMax(int length,vector<int> a)
{
    int max=0;
    deque<int> dq;
    for(int i=0;i<a.size();++i)
    {
        while(!dq.empty() && a[i]-a[dq.front()]>length)
            dq.pop_front();
        dq.push_back(i);
        max=max>dq.size()?max:dq.size();
    }
    return max;
}

发表于 2020-02-16 11:27:52 回复(0)

林林同學

package java_example;
/**
 * 数轴上从左到右有 n 个点 a[0],a[1],„„,a[n-1],给定一根长度为 L 的绳子,求绳子最多能 覆盖其中的几个点。
 * @author lulinlin
 *
 */
public class MaxPoint {
    //方法一
    public static int maxPoint(int[]a,int l){

        int maxCount=0;

        for(int i=0;i<a.length-1;i++){
            int count=1;
            int j=i+1;
            while((j<a.length)&&(a[j]-a[i]<=l)){
                j++;
                count++;
                if(count>maxCount){
                    maxCount=count;
                }
            }
        }
        return maxCount;
    }
    //方法二
    public static int maxPoint1(int[]a,int l){

        int maxCount=0;
        int begin =0;
        int end=1;
        while(end<a.length){
            if(a[end]-a[begin]>l){    
                begin++;
            }
            else{
                if(end-begin>maxCount){
                    maxCount=end-begin+1;
                }
                end++;
            }
        }
        return maxCount;
    }

    public static void main(String[] args) {
        int[]a= new int[]{1,3,4,6};
        int l=5;
        //System.out.println(maxPoint(a,l));
        System.out.println(maxPoint1(a,l));
    }
}

编辑于 2018-08-10 22:29:18 回复(0)

Jessica

<pre class="prettyprint lang-cpp">#include<iostream> using namespace std; int cover(int arr[],int n,int L) { int maxCount=0; int count=1; int start=0; int i=1; while(i<n) { if(arr[i]-arr[start]<=L) { count++; ++i; } else { if(count>maxCount) maxCount=count; start++; count--; } } if(count>maxCount) maxCount=count; return maxCount; } int main() { int arr[]={1, 3, 7, 8, 10, 11, 12, 13, 15, 16, 17, 18, 21}; cout<<cover(arr,13,8)<<endl; }</pre>

发表于 2015-09-09 20:48:35 回复(0)

东到海

#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>

using namespace std;

const int N = 500;
const double L = 1000.0;
double a[N];
int flag = 0;

void rand_points()
{
srand(time(NULL));
for (int i = 0; i < N; ++i)
{
a[i] = (rand()%1000)/100.0;
}
std::sort(a,a+N);
}

int calc_max_count(int k)
{
int count = 0;
double sum = 0;
for (int i=k;i<N; ++i)
{
++count;
sum += a[i];
if (sum>L)
{
return count-1;
}
}
flag = 1;
return count;
}

int main()
{
rand_points();
vector<int> vi;
for (int i = 0; i < N; ++i)
{
if (flag == 1)
{
break;
}
vi.push_back(calc_max_count(i));
}
cout << *(std::max_element(vi.begin(), vi.end())) << endl;
return 0;
}

发表于 2015-03-30 20:48:25 回复(0)

牛客261727号

发表于 2014-11-29 14:42:46 回复(0)

jeffkoo

23123123

发表于 2014-11-05 13:59:22 回复(0)

刘玉婷

水电费

发表于 2014-11-04 15:03:44 回复(0)

温柔的牛奶

开始时我把题目理解错了，以为是求a中最大子序列和使其等于L，实际上是求满足a[j]-a[i] <= L && a[j+1]-a[i] > L这两个条件的j与i中间的所有点个数中的最大值，即j-i+1最大，这样题目就简单多了，方法也很简单：直接从左到右扫描，两个指针i和j，i从位置0开始，j从位置1开始，如果a[j] - a[i] <= L则j++并记录中间经过的点个数，如果a[j] - a[i] > L则j--回退，覆盖点个数-1回到刚好满足条件的时候，将满足条件的最大值与所求最大值比较，然后i++,j++直到求出最大的点个数。
有两点需要注意：
（1）这里可能没有i和j使得a[j] - a[i]刚好等于L的，所以判断条件不能为a[j] - a[i] = L。
（2）可能存在不同的覆盖点但覆盖的长度相同，此时只选第一次覆盖的点。

Source code：
HYPERLINK "http://www.cnblogs.com/lanxuezaipiao/p/javascript:void(0);" \o "复制代码" INCLUDEPICTURE \d "http:\\\\common.cnblogs.com\\images\\copycode.gif" \* MERGEFORMAT

// 求最大覆盖点
#include 
int maxCover(int a[], int n, int L)
{
    int count = 2, maxCount = 1, start;
    int i = 0, j = 1;
    while(i < n && j < n) { while((j < n) && (a[j] - a[i] <= L)) { j++; count++; } // 退回到满足条件的j j--; count--; if(maxCount < count) { start = i; maxCount = count; } i++; j++; } printf("covered point: "); for(i = start; i < start + maxCount; i++) { printf("%d ", a[i]); } printf("\n"); return maxCount; } int main() { // test int a[] = {1, 3, 7, 8, 10, 11, 12, 13, 15, 16, 17, 18, 21}; printf("max count: %d\n\n", maxCover(a, 13, 8)); int b[] = {1,2,3,4,5,100,1000}; printf("max count: %d\n", maxCover(b, 7, 8)); return 0; }

发表于 2014-10-25 00:26:03 回复(0)

提交观点

问题信息

模拟智力题百度

来自：百度2013研发工程师...

难度：

11条回答 47收藏 7277浏览

数轴上从左到右有 n 个点 a[0],a[1],„„,a[n

问题信息

热门推荐

相关试题