多易網(wǎng)絡(luò)2017 春招編程題

多益網(wǎng)絡(luò)2017春招兩個編程題原文地址:/KgdYsg/article/details/64494166題目1道對不對，畢竟不是在線oj不能查結(jié)果。題目描述，給n,m兩個數(shù)，n表示球隊的個數(shù)（從1到表示比賽場數(shù)，然后給ma贏了b，要求是輸出一種排列方式，使得不存在排在前面的隊輸過排在后面的隊。如果有（a,b）即a一定在b前面。我的想法是將這m場比賽視為m長度為n，默認排列順序為（1…n）然后進行m次檢驗，如果（a,b）在現(xiàn)有的排列中不滿足a在我試了下這個方法，發(fā)現(xiàn)排列的結(jié)果：12345比賽（2，3）滿12345比賽（2，4）滿12345比賽（1，2）滿12345比賽（1，5）滿15342比賽（5，2）調(diào)后面，以至于不滿足前面的規(guī)則。行test，檢查現(xiàn)在的結(jié)果是否滿足要求，如果不滿足，再進行一次sort，若干次排序后一定會得到一個結(jié)果滿足條件。代碼如下：#include<iostream>usingnamespacevoidsoft(intcount[],inta[][2],n){for(inti=0;i<{j,k,temp;for(j=0;j<n;{if(count[j]={break;}}for(k=0;k<n;{if(count[k]={break;}}if(j>k){temp=count[j];count[j]=count[k];count[k]=temp;}}}booltest(intcount[],{for(inti=0;i<{j,k;for(j=0;j<n;j{if(count[j]={break;}}for(k=0;k<{if(count[k]==a[i][1]){break;}}if(j>k){returnfalse;}}returntrue;}main(){cin>>n>>m;a[m][2];for(inti=0;i<m;{cin>>a[i][0]>>a[i][1];}count[n];for(inti=0;i<n;{count[i]=}while(!test(count,a,m,n)){soft(count,a,m,n);}for(inti=0;i<n;{cout<<count[i]<}return0;}可能還是會有些情況沒有評，所以沒辦法去驗證。題目2給一個數(shù)組a={8，3，5，2，7，4，6，1}，要求用O(n)的時間復(fù)雜度，O(1)的空間復(fù)雜度做。做法：申請一個數(shù)組（所有元素為aa中每一個元素的值做為count數(shù)組的下標(biāo)，并使該下標(biāo)對應(yīng)的數(shù)組元素的值自增。用空間換取時間的非典型排序方法。代碼如下：#include<iostream>usingnamespacevoidsort(intcount[],a[],len){for(inti=0;i<len;{count[a[i]]++;}for(inti=0,j=0;i<{if(count[i]0){a[j++]=count[i]--;}}}voidshow(inta[],len){for(inti=0;i<len;{cout<<a[i]<<"";}}usingnamespacemain(){count[65536]