微软等数据结构+算法面试100题全部答案集锦下

doublepower(doublebase,intexp){if(exp==1)returnbase;doublehalf=power(base,exp>>1);return(((exp&1)==1)base:1.0)halfhalf;}

Thetrickislikethis:takeuseoftheoldpSibling,makeitpointstothenewcreatedclonednode,whilemakethenewclonednode’spNextbackuptheoldpSibling.

ComplexNodeClone(ComplexNodepHead){if(pHead==NULL)returnNULL;preClone(pHead);inClone(pHead);returnpostClone(pHead);}

voidpreClone(ComplexNodepHead){ComplexNodep=newComplexNode();p->m_pNext=pHead->m_pSibling;pHead->m_pSibling=p;if(pHead->m_pNext!=NULL)preClone(pHead->m_pNext);}

voidinClone(ComplexNodepHead){ComplexNodepSib=pNew->m_pNext;if(pSib==NULL){pNew->m_pSibling=NULL;}else{pNew->m_pSibling=pSib->m_pSibling;}if(pHead->m_pNext!=NULL)inClone(pHead->m_pNext);}

ComplexNodepostClone(ComplexNodepHead){ComplexNodepNew=pHead->m_pSibling;ComplexNodepSib=pNew->m_pNext;if(pHead->m_pNext!=NULL){pNew->m_pNext=pHead->m_pNext->m_pSibling;pHead->m_pSibling=pSib;postClone(pHead->m_pNext);}else{pNew->pNext=NULL;pHead->m_pSibling=NULL;}returnpNew;}

NodemergeSort(Nodep,intlen){if(len==1){p->next=NULL;returnp;}Nodepmid=p;for(inti=0;inext;}Nodep1=mergeSort(p,len/2);Nodep2=mergeSort(pmid,len-len/2);returnmerge(p1,p2);}Nodemerge(Nodep1,Nodep2){Nodep=NULL,ph=NULL;while(p1!=NULL&&p2!=NULL){if(p1->datadata){if(ph==NULL){ph=p=p1;}else{p->next=p1;p1=p1->next;p=p->next;}}else{if(ph==NULL){ph=p=p2;}else{p->next=p2;p2=p2->next;p=p->next;}}}p->next=(p1==NULL)p2:p1;returnph;}

Similarly,assumeC(M,2)>=nandC(M-1,2)

Alsorecursivewayworks.PossibleoptimizationslikeSundayalgorithmorRabin-Karpalgorithmwilldo.

Node*array2Tree(int[]array){returnhelper(array,0,n-1);}

Nodehelper(int[]array,intstart,intend){if(start>end)returnNULL;intm=start+(end-start)/2;Noderoot=newNode(array[m]);root->left=helper(array,start,m-1);root->right=helper(array,m+1,end);returnroot;}

intpartitionStar(chara[]){intcount=0;inti=a.length-1,j=a.length-1;//iforthecursor,jforthefirstnon-charwhile(i>=0){if(a[i]!=‘’){swap(a,i--,j--);}else{i--;count++;}}returncount;}

Asub-quadraticsolutioncanbedonebyDP.

f(n)=f(n-1)+Index(n)Index(n),whichistodeterminehowmanynumbersissmallerthana[n]ina[0..n-1],canbedoneinlog(n)timeusingBSTwithsubtreesize.