總體感覺(jué)金山的筆試題難度還可以，既考查了基礎(chǔ)知識(shí)，又測(cè)試了考生的編程及算法能力。試題大概分為三部分，第一部分是一些簡(jiǎn)單的看程序填空，就是填寫(xiě)程序的運(yùn)行結(jié)果。這一部分只要仔細(xì)一點(diǎn)就沒(méi)什么問(wèn)題。第二部分是簡(jiǎn)答題，內(nèi)容包括TCP，UDP協(xié)議，C++拷貝構(gòu)造函數(shù)，快速排序算法，堆棧等基礎(chǔ)知識(shí)，這一部分問(wèn)題也不大。最后一部分是兩道編程題，由于時(shí)間很充裕(兩個(gè)小時(shí))如果能想出算法的話應(yīng)該很快就做完了。這里與大家分享一道編程題，主要考查算法。
題目1：有一個(gè)int型數(shù)組Num，里面存放著若干的正數(shù)和負(fù)數(shù)，請(qǐng)你設(shè)計(jì)一個(gè)算法，在數(shù)組中截取一段Num[start]--Num[end]，使得這一段的整數(shù)之和最大，并返回最大值max。
算法思想：start和end記錄最大段的起始和終止位置，首先讓start指向數(shù)組的第一個(gè)正數(shù)的下標(biāo)，end指向數(shù)組的倒數(shù)第一個(gè)正數(shù)的下標(biāo)，即略去數(shù)組首尾的負(fù)數(shù)。然后用兩個(gè)循環(huán)求出所有組合的最大值并返回，start記錄最大段的起始下標(biāo)，end記錄終止下標(biāo)。
以下是我用C語(yǔ)言實(shí)現(xiàn)的程序代碼，已經(jīng)在visual C++ 6.0上運(yùn)行通過(guò)了，想加入金山的可以過(guò)來(lái)圍觀一下，呵呵。
#include /在數(shù)組Num[]中截取一段Num[start]--Num[end]，使得這一段的元素之和最大，打印start和end并返回最大值max/ int findMaxPart(int Num[],int n) { int len=n;//數(shù)組的長(zhǎng)度 int start=0; int end=len-1; int sum=0; int max=0;//截取數(shù)組段的最大值 /略去數(shù)組首尾的負(fù)數(shù)/ while(Num[start]<0) start++; while(Num[end]<0) end--; max=Num[start]; for(int i=0;i { sum=0; for(int j=i;j { sum+=Num[j]; if(max { max=sum; start=i; end=j; } } } /打印start和end以及最大值max/ printf("start position is:%d/n",start); printf("end position is:%d/n",end); printf("The max value is:%d/n",max); return max;//返回max } void main() { int Num[]={2,-1,1,-20,4,9,-30,1,-1,2}; findMaxPart(Num,sizeof(Num)/sizeof(int)); } #include /在數(shù)組Num[]中截取一段Num[start]--Num[end]，使得這一段的元素之和最大，打印start和end并返回最大值max/ int findMaxPart(int Num[],int n) { int len=n;//數(shù)組的長(zhǎng)度 int start=0; int end=len-1; int sum=0; int max=0;//截取數(shù)組段的最大值 /略去數(shù)組首尾的負(fù)數(shù)/ while(Num[start]<0) start++; while(Num[end]<0) end--; max=Num[start]; for(int i=0;i { sum=0; for(int j=i;j { sum+=Num[j]; if(max { max=sum; start=i; end=j; } } } /打印start和end以及最大值max/ printf("start position is:%d/n",start); printf("end position is:%d/n",end); printf("The max value is:%d/n",max); return max;//返回max } void main() { int Num[]={2,-1,1,-20,4,9,-30,1,-1,2}; findMaxPart(Num,sizeof(Num)/sizeof(int)); }
問(wèn)題補(bǔ)充：這種算法的時(shí)間復(fù)雜度是O(n^2) ，效率太低了，在網(wǎng)友張立志同學(xué)的提示下，我用動(dòng)態(tài)規(guī)劃算法對(duì)程序做了優(yōu)化。時(shí)間復(fù)雜度是O(n)。代碼如下。
#include int main() { int num[]={5,-1,1,-10,5,-1,5,-20,1,-1,3}; int n=sizeof(num)/sizeof(int); int sum=0; int max=num[0];// record the value of max part int start=0;// the start position of the max part int end=0;// the end position of the max part int temp_start; for(int i=0;i { sum+=num[i]; // update max part if(max { max=sum; end=i; start=temp_start; } // find new max part if(sum<0) { sum=0; temp_start=i+1; } } printf("max=%d/n",max); printf("start=%d/n",start); printf("end=%d/n",end); return 0; } #include int main() { int num[]={5,-1,1,-10,5,-1,5,-20,1,-1,3}; int n=sizeof(num)/sizeof(int); int sum=0; int max=num[0];// record the value of max part int start=0;// the start position of the max part int end=0;// the end position of the max part int temp_start; for(int i=0;i { sum+=num[i]; // update max part if(max { max=sum; end=i; start=temp_start; } // find new max part if(sum<0) { sum=0; temp_start=i+1; } } printf("max=%d/n",max); printf("start=%d/n",start); printf("end=%d/n",end); return 0; }
閱讀了本文“金山(Kingsoft)服務(wù)器端開(kāi)發(fā)工程師筆試題”，本站思而學(xué)教育網(wǎng)（cnrencai）筆試頻道，還為你提供更多“筆試題目”相關(guān)文章閱讀
