字节跳动2018校招测试开发方向（第二批）

真题链接：https://www.nowcoder.com/test/8537269/summary

第一题：

#include"iostream"
#include"algorithm"
#include"stdio.h"
using namespace std;
const int MAXN=300005;
struct node
{
    int value;
    int index;
};
node users[MAXN];
int  n,q;

bool Cmp(const node &a,const node &b)
{
    if(a.value!=b.value)
        return a.value<b.value;
    return a.index<b.index;
}

int BinarySearch(int l,int r,int k)
{
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(users[mid].value==k)
            return mid;
        if(users[mid].value<k)
            l=mid+1;
        else
            r=mid-1;
    }
    return -1;
}

int CountKInRange(int l,int r,int k)
{
    int kIndex=BinarySearch(1,n,k);
    if(kIndex==-1)
        return 0;
    int result=0,tempIndex=kIndex;
    while(tempIndex>=1&&users[tempIndex].value==k)
    {
        if(users[tempIndex].index>=l&&users[tempIndex].index<=r)
            result++;
        tempIndex--;
    }
    tempIndex=kIndex+1;
    while(tempIndex<=n&&users[tempIndex].value==k)
    {
        if(users[tempIndex].index>=l&&users[tempIndex].index<=r)
            result++;
        tempIndex++;
    }
    return result;
}
int main()
{
    while(scanf("%d",&n)==1)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&users[i].value);
            users[i].index=i;
        }
        sort(users+1,users+1+n,Cmp);

//        for(int i=1;i<=n;i++)
 //           cout<<users[i].value<<' '<<users[i].index<<endl;
        cin>>q;
        int l,r,k;
        while(q--)
        {
            scanf("%d%d%d",&l,&r,&k);
            cout<<CountKInRange(l,r,k)<<endl;
        }
    }
    return 0;
}

 第二题：

#include"iostream"
#include"stdio.h"
#include"string.h"
#include"math.h"
using namespace std;

int color[55][10005];
int colorIndex[55];
int n,m,c;

int Min(int a,int b)
{
    return a<b?a:b;
}

int GetMinDistance(int i,int j)
{
    return Min(abs(i-j),n-abs(i-j));
}

int CountInvalidColoor()
{
    int result=0;
    for(int i=1;i<=c;i++)
    {
        for(int j=0;j<colorIndex[i];j++)
        {
            if(GetMinDistance(color[i][j],color[i][(j+1)%colorIndex[i]])<=(m-1))
            {
                result++;
                break;
            }
        }
    }
    return result;
}
int main()
{

    while(scanf("%d%d%d",&n,&m,&c)==3)
    {
        memset(colorIndex,0,sizeof(colorIndex));
        for(int i=0;i<n;i++)
        {
            int numI,iColor;
            scanf("%d",&numI);
            for(int j=0;j<numI;j++)
            {
                cin>>iColor;
                color[iColor][colorIndex[iColor]++]=i;
            }
        }
        /*
        for(int i=0;i<=c;i++)
        {
            for(int j=0;j<colorIndex[i];j++)
                cout<<color[i][j]<<' ';
            cout<<endl;
        }
        */
        cout<<CountInvalidColoor()<<endl;
    }
    return 0;
}

第三题：