[微软面试100题]3140

第三十六题：比赛排名

void match(int w[][8],int *order,int *result,int n){
    memcpy(result,order,n*sizeof(int));
    int round=n;
    while(round>0){
        for(int i=0,j=0;i<round;i+=2,++j){
                if(w[result[i]][result[i+1]]==result[i])swap(i,j,result);
                else swap(i+1,j,result);
        }
    round/=2;
    }
}

第三十八题：有大量的url，去除重复的

1、如果可以全部放入内存，则时候hash table即可

2、如果不能，则根据hash值分为k个bin存硬盘，每个bin可以放入内存中。然后再对每个bin用hash table。

 

第四十题：首尾相连的珠子，找出包含所有颜色的最短子串

用一个长度可变的窗口扫描珠子，如果找到全部颜色且长度比之前找到的更短则更新最优值。

int check(int* color,int thiscolor){//看这颜色有没有
    if(color[thiscolor]!=0)return 1;
    else return 0;
}
int all(int* color,int m){//查看是不是所有颜色都有
    for(int i=0;i<m;++i){
        if(color[i]==0){
            return 0;
        }
    }
    return 1;
}
 
int main()
{
    int a[]={0,1,0,1,2,1,3,1,2,2,3,0};//2,3,1,2,3,2,1,1,3,0,1
    int color[4]={0,0,0,0};
    int m=4;
    int len=sizeof(a)/sizeof(int);
    int b[len];
    for(int i=0;i<2;++i){//首尾相连其实复制数组连起来就可以当做不相连来做
        for(int j=0;j<len;++j)b[i*len+j]=a[j];
    }
    int *begin=b,*end=b;
    int beststart=0,bestlen=2*len;
    while(end!=b+2*len){
        int be=*begin,en=*end;
        color[*end]++;
        while(color[*begin]>1){
            color[*begin]--;
            begin++;
        }
        if(all(color,m) && end-begin+1<bestlen){
            bestlen=end-begin+1;
            beststart=begin-b;
        }
        end++;
    }
    cout<<beststart<<" "<<bestlen<<endl;
}