程序员面试题精选2585.docx

《程序员面试题精选2585.docx》由会员分享，可在线阅读，更多相关《程序员面试题精选2585.docx（16页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、程序员面试题精选100题(10)在排序数组中查找和为给定值的两个数字数组20007-033-14 15:225:011阅读46663评论论15字号：大大中小订阅题目：输入入一个已经经按升序排排序过的数数组和一个个数字，在在数组中查查找两个数数，使得它它们的和正正好是输入入的那个数数字。要求求时间复杂杂度是O(n)。如如果有多对对数字的和和等于输入入的数字，输输出任意一一对即可。例如输入数数组1、2、4、7、11、15和数字字15。由于于4+111=15，因因此输出44和11。分析：如果果我们不考考虑时间复复杂度，最最简单想法法的莫过去去先在数组组中固定一一个数字，再再依次判断断数组中剩剩下的n

2、-1个数字字与它的和和是不是等等于输入的的数字。可可惜这种思思路需要的的时间复杂杂度是O(n2)。我们假设现现在随便在在数组中找找到两个数数。如果它它们的和等等于输入的的数字，那那太好了，我我们找到了了要找的两两个数字；如果小于于输入的数数字呢？我我们希望两两个数字的的和再大一一点。由于于数组已经经排好序了了，我们是是不是可以以把较小的的数字的往往后面移动动一个数字字？因为排排在后面的的数字要大大一些，那那么两个数数字的和也也要大一些些，就有可可能等于输输入的数字字了；同样样，当两个个数字的和和大于输入入的数字的的时候，我我们把较大大的数字往往前移动，因因为排在数数组前面的的数字要小小一些，它

3、它们的和就就有可能等等于输入的的数字了。我们把前面面的思路整整理一下：最初我们们找到数组组的第一个个数字和最最后一个数数字。当两两个数字的的和大于输输入的数字字时，把较较大的数字字往前移动动；当两个个数字的和和小于数字字时，把较较小的数字字往后移动动；当相等等时，打完完收工。这这样扫描的的顺序是从从数组的两两端向数组组的中间扫扫描。问题是这样样的思路是是不是正确确的呢？这这需要严格格的数学证证明。感兴兴趣的读者者可以自行行证明一下下。参考代码：/ Finnd twwo nuumberrs wiith aa summ in a soortedd arrray/ Outtput: turre is

4、s fouund ssuch two numbbers, othherwiise ffalsee/bbool FinddTwoNNumbeersWiithSuum(int ddata, / a soortedd arrrayunnsignnedinnt leengthh, / thhe leengthh of the sortted aarrayy int ssum, / the sumiint& num11, / the firsst nuumberr, ouutputtint& num22 / the secoond nnumbeer, ooutpuut)bool founnd = fal

5、sse;if(leengthh beehindd)longg lonng cuurSumm = ddataaheaad + dattabeehindd;/ iif thhe suum off twoo nummberss is equaal too thee inpput/ we havee fouund tthemiif(cuurSumm = sum)num11 = ddatabehiind;num22 = ddataaheaad;founnd = truee;breaak;/ iif thhe suum off twoo nummberss is greaater thann thee i

6、npput/ deccreasse thhe grreateer nuumberrelseeif(cuurSumm ssum)aheaad -;/ iif thhe suum off twoo nummberss is lesss thaan thhe innput/ inncreaase tthe lless numbberellsebehiind +;retuurn ffoundd;扩展：如果果输入的数数组是没有有排序的，但但知道里面面数字的范范围，其他他条件不变变，如何在在O(n)时间里找找到这两个个数字程序员面试试题精选1100题(11)求二元查查找树的镜镜像树 20007-033-1

7、5 09:336:333 阅读33906 评论9 字号号：大中小小订阅题目：输入入一颗二元元查找树，将将该树转换换为它的镜镜像，即在在转换后的的二元查找找树中，左左子树的结结点都大于于右子树的的结点。用用递归和循循环两种方方法完成树树的镜像转转换。例如输入： 8 / 66 100/ /5 77 9 11输出： 8 / 10 6/ /111 9 7 5定义二元查查找树的结结点为：strucct BSSTreeeNodee / a noode iin thhe biinaryy seaarch treee (BSST)int m_nVValuee; / vallue oof noodeBSTrre

8、eNoode *m_ppLeftt; / leeft cchildd of nodeeBSTrreeNoode *m_ppRighht; / riight chilld off nodde;分析：尽管管我们可能能一下子不不能理解镜镜像是什么么意思，但但上面的例例子给我们们的直观感感觉，就是是交换结点点的左右子子树。我们们试着在遍遍历例子中中的二元查查找树的同同时来交换换每个结点点的左右子子树。遍历历时首先访访问头结点点8，我们交交换它的左左右子树得得到： 8 / 10 66/ /99 111 5 7我们发现两两个结点66和10的左右右子树仍然然是左结点点的值小于于右结点的的值，我们们再试着交交

9、换他们的的左右子树树，得到： 8 / 10 6/ /111 9 7 5刚好就是要要求的输出出。上面的分析析印证了我我们的直觉觉：在遍历历二元查找找树时每访访问到一个个结点，交交换它的左左右子树。这这种思路用用递归不难难实现，将将遍历二元元查找树的的代码稍作作修改就可可以了。参参考代码如如下：/ Mirrror a BSST (sswap the leftt rigght cchildd of eachh nodde) rrecurrsiveely/ thee heaad off BSTT in inittial calll/vvoid MirrrorReecurssivelly(BSSTree

10、eNodee *pNNode)if(!ppNodee)retuurn;/ sswap the righht annd leeft cchildd subb-treeeBSTrreeNoode *pTemmp = pNodde-mm_pLeeft;pNodde-mm_pLeeft = pNoode-m_pRRightt;pNodde-mm_pRiight = pTTemp;/ mmirroor leeft cchildd subb-treee iff nott nulllif(pNNode-m_ppLeftt)MirrrorReecurssivelly(pNNode-m_ppLeftt); /

11、mmirroor riight chilld suub-trree iif noot nuulliff(pNoode-m_pRRightt)MirrrorReecurssivelly(pNNode-m_ppRighht); 由于递归的的本质是编编译器生成成了一个函函数调用的的栈，因此此用循环来来完成同样样任务时最最简单的办办法就是用用一个辅助助栈来模拟拟递归。首首先我们把把树的头结结点放入栈栈中。在循循环中，只只要栈不为为空，弹出出栈的栈顶顶结点，交交换它的左左右子树。如如果它有左左子树，把把它的左子子树压入栈栈中；如果果它有右子子树，把它它的右子树树压入栈中中。这样在在下次循环环中就能交交换

12、它儿子子结点的左左右子树了了。参考代代码如下：/ Mirrror a BSST (sswap the leftt rigght cchildd of eachh nodde) IIteraativeely/ Inpput: pTreeeHeaad: tthe hhead of BBST/voiid MiirrorrIterrativvely(BSTrreeNoode *pTreeeHeaad)if(!ppTreeeHeadd)retuurn;std:staacksstackkTreeeNodee;stacckTreeeNodde.puush(ppTreeeHeadd);whhile(stacc

13、kTreeeNodde.siize()BSTrreeNoode *pNodde = stacckTreeeNodde.toop();stacckTreeeNodde.poop();/ sswap the righht annd leeft cchildd subb-treeeBSTrreeNoode *pTemmp = pNodde-mm_pLeeft;pNodde-mm_pLeeft = pNoode-m_pRRightt;pNodde-mm_pRiight = pTTemp;/ ppush leftt chiild ssub-ttree intoo staack iif noot nuul

14、liff(pNoode-m_pLLeft)stacckTreeeNodde.puush(ppNodee-m_pLefft);/ ppush righht chhild sub-treee intto sttack if nnot nnulliif(pNNode-m_ppRighht)stacckTreeeNodde.puush(ppNodee-m_pRigght);程序员面试试题精选1100题(12)从上往下下遍历二元元树队列 20007-003-199 21:17:003 阅读读37988 评论55 字字号：大中中小订阅阅题目：输输入一颗二二元树，从从上往下按按层打印树树的每个结结点，同一一

15、层中按照照从左往右右的顺序打打印。例如输入 8 / 6 100 / / 5 77 99 111输出8 6 10 5 7 9 111。分析：这曾曾是微软的的一道面试试题。这道道题实质上上是要求遍遍历一棵二二元树，只只不过不是是我们熟悉悉的前序、中中序或者后后序遍历。我们从树的的根结点开开始分析。自自然先应该该打印根结结点8，同时为为了下次能能够打印88的两个子子结点，我我们应该在在遍历到88时把子结结点6和10保存到到一个数据据容器中。现现在数据容容器中就有有两个元素素6和10了。按按照从左往往右的要求求，我们先先取出6访问。打打印6的同时要要把6的两个子子结点5和7放入数据据容器中，此此时数据

16、容容器中有三三个元素110、5和7。接下来来我们应该该从数据容容器中取出出结点100访问了。注注意10比5和7先放入容容器，此时时又比5和7先取出，就就是我们通通常说的先先入先出。因因此不难看看出这个数数据容器的的类型应该该是个队列列。既然已经确确定数据容容器是一个个队列，现现在的问题题变成怎么么实现队列列了。实际际上我们无无需自己动动手实现一一个，因为为STL已经经为我们实实现了一个个很好的ddequee（两端都都可以进出出的队列），我我们只需要要拿过来用用就可以了了。我们知道树树是图的一一种特殊退退化形式。同同时如果对对图的深度度优先遍历历和广度优优先遍历有有比较深刻刻的理解，将将不难看出

17、出这种遍历历方式实际际上是一种种广度优先先遍历。因因此这道题题的本质是是在二元树树上实现广广度优先遍遍历。参考代码：#incllude#iincluudeusinngnammespaace sstd;sstrucct BTTreeNNode / aa nodde inn thee binnary treeeint mm_nVaalue; / valuue off noddeBTreeeNodde *m_pLLeft; / lefft chhild of nnodeBTreeeNodde *m_pRRightt; / rigght cchildd of nodee;/ PPrintt a bbi

18、narry trree ffrom top leveel too botttom leveel/ Inpuut: ppTreeeRoott - tthe rroot of bbinarry trree/voiid PrrintFFromTTopTooBotttom(BBTreeeNodee *pTTreeRRoot)if(!ppTreeeRoott)retuurn;/ gget aa emppty qqueueedequue ddequeeTreeeNodee;/ iinserrt thhe rooot aat thhe taail oof quueuedequueTreeeNodde.puu

19、sh_bback(pTreeeRooot);whille(deequeTTreeNNode.sizee()/ gget aa nodde frrom tthe hhead of qqueueeBTreeeNodde *ppNodee = ddequeeTreeeNodee.froont();dequueTreeeNodde.poop_frront();/ pprintt thee noddecoutt mm_nVaalue m_pLLeft)dequueTreeeNodde.puush_bback(pNodde-mm_pLeeft);/ pprintt itss rigght cchildd

20、subb-treee iff it hasiif(pNNode-m_ppRighht)dequueTreeeNodde.puush_bback(pNodde-mm_pRiight);程序员面试试题精选1100题(13)第一个只只出现一次次的字符字符串 22007-03-221 211:17:22 阅阅读54665 评论论30 字号：大中小订阅题目：在一一个字符串串中找到第第一个只出出现一次的的字符。如如输入abbaccddeff，则则输出b。分析：这道道题是20006年googgle的一一道笔试题题。看到这道题题时，最直直观的想法法是从头开开始扫描这这个字符串串中的每个个字符。当当访问到某某字

21、符时拿拿这个字符符和后面的的每个字符符相比较，如如果在后面面没有发现现重复的字字符，则该该字符就是是只出现一一次的字符符。如果字字符串有nn个字符，每每个字符可可能与后面面的O(nn)个字符符相比较，因因此这种思思路时间复复杂度是OO(n2)。我们试试着去找一一个更快的的方法。由于题目与与字符出现现的次数相相关，我们们是不是可可以统计每每个字符在在该字符串串中出现的的次数？要要达到这个个目的，我我们需要一一个数据容容器来存放放每个字符符的出现次次数。在这这个数据容容器中可以以根据字符符来查找它它出现的次次数，也就就是说这个个容器的作作用是把一一个字符映映射成一个个数字。在在常用的数数据容器中中

22、，哈希表表正是这个个用途。哈希表是一一种比较复复杂的数据据结构。由由于比较复复杂，STTL中没有有实现哈希希表，因此此需要我们们自己实现现一个。但但由于本题题的特殊性性，我们只只需要一个个非常简单单的哈希表表就能满足足要求。由由于字符（char）是一个长度为8的数据类型，因此总共有可能256 种可能。于是我们创建一个长度为256的数组，每个字母根据其ASCII码值作为数组的下标对应数组的对应项，而数组中存储的是每个字符对应的次数。这样我们就创建了一个大小为256，以字符ASCII码为键值的哈希表。我们第一遍遍扫描这个个数组时，每每碰到一个个字符，在在哈希表中中找到对应应的项并把把出现的次次数增

23、加一一次。这样样在进行第第二次扫描描时，就能能直接从哈哈希表中得得到每个字字符出现的的次数了。参考代码如如下：/ Finnd thhe fiirst charr whiich aappeaars oonly oncee in a sttringg/ IInputt: pSStrinng - the striing/ Outtput: thee firrst nnot rrepeaatingg chaar iff thee strring has, othherwiise 00/cchar FirsstNottRepeeatinngChaar(chhar* pStrring)/ iinvalli

24、d iinputtif(!ppStriing)retuurn 00;/ gget aa hassh taable, andd iniitiallize itcconsttinttaableSSize =2566;unssigneedintthashhTablletaableSSize;forr(unsiigneddintii = 00; i 0k+22 - 1n-1 - n-kk-20 - n-k-1k-1 - nn-2把映射定义义为p，则p(xx)= (x-k-1)%nn，即如果果映射前的的数字是xx，则映射射后的数字字是(x-k-1)%n。对对应的逆映映射是p-1(x)=(x+k+1)%n

25、。由于映射之之后的序列列和最初的的序列有同同样的形式式，都是从从0开始的连连续序列，因因此仍然可可以用函数数f来表示，记记为f(nn-1,mm)。根据据我们的映映射规则，映映射之前的的序列最后后剩下的数数字f(n-1,m)= p-1 ff(n-11,m)=f(n-1,m)+kk+1%n。把k=mm%n-11代入得到到f(n,m)=ff(n-1,m)=f(n-1,m)+mm%n。经过上面复复杂的分析析，我们终终于找到一一个递归的的公式。要要得到n个数字的的序列的最最后剩下的的数字，只只需要得到到n-1个数数字的序列列的最后剩剩下的数字字，并可以以依此类推推。当n=1时，也也就是序列列中开始只只有

26、一个数数字0，那么很很显然最后后剩下的数数字就是00。我们把把这种关系系表示为： 0 nn=1f(n,m)= f(n-1,m)+m%n n1尽管得到这这个公式的的分析过程程非常复杂杂，但它用用递归或者者循环都很很容易实现现。最重要要的是，这这是一种时时间复杂度度为O(nn)，空间间复杂度为为O(1)的方法，因因此无论在在时间上还还是空间上上都优于前前面的思路路。思路一的参参考代码：/ n iinteggers (0, 1, . nn - 11) foorm aa cirrcle. Remmove the mth fromm / the circcle aat evvery timee. Fii

27、nd tthe llast numbber rremaiiningg / Inpuut: nn - tthe nnumbeer off inttegerrs inn thee cirrcle inittiallly/ mm - rremovve thhe mtth nuumberr at everry tiime/ Outtput: thee lasst nuumberr remmainiing wwhen the inpuut iss vallid,/ ottherwwise -1/intt LasstRemmainiing_SSoluttion11(unssigneedintt n, un

28、siigneddint mm)/ iinvallid iinputtif(n 1 | mm 11)retuurn -1;unsiigneddint ii = 00;/ iinitiiate a liist wwith n inntegeers (0, 11, . n - 1)listt inntegeers;for(ii = 00; i n; + i)inteegerss.pussh_baack(ii);listt:iiteraator curiintegger = inttegerrs.beegin();whille(inntegeers.ssize() 1)/ ffind the mth

29、inteeger. Notte thhat sstd:listt is not a ciirclee/ sso wee shoould handdle iit maanualllyfoor(int ii = 11; i m; + i)curiintegger +;if(cuurinttegerr = inteegerss.endd()curiintegger = inttegerrs.beegin();/ rremovve thhe mtth inntegeer. NNote thatt stdd:liist iis noot a circcle/ so we sshoulld haandle

30、e it manuuallyylistt:iiteraator nexttinteeger = + currinteeger;if(neextinntegeer = inttegerrs.ennd()nexttinteeger = inntegeers.bbeginn();- ccurinntegeer;inteegerss.eraase(ccurinntegeer);curiintegger = nexxtinttegerr;retuurn *(currinteeger);思路二的参参考代码：/ n iinteggers (0, 1, . nn - 11) foorm aa cirrcle.

31、 Remmove the mth fromm / the circcle aat evvery timee. Fiind tthe llast numbber rremaiiningg / Inpuut: nn - tthe nnumbeer off inttegerrs inn thee cirrcle inittiallly/ mm - rremovve thhe mtth nuumberr at everry tiime/ Outtput: thee lasst nuumberr remmainiing wwhen the inpuut iss vallid,/ ottherwwise

32、-1/intt LasstRemmainiing_SSoluttion22(intt n, unsiigneddint mm)/ iinvallid iinputtif(n = 00 | m 0)retuurn -1;/ iif thhere are onlyy onee inttegerr in the circcle iinitiiallyy,/ of ccoursse thhe laast rremaiiningg onee is 0intt lasstinttegerr = 00;/ ffind the lastt remmainiing oone iin thhe ciirclee witth n inteegerssfor (int ii = 22; i = nn; i +)lasttinteeger = (llastiintegger + m) % i;retuurn llastiintegger;如果对两种种思路的时时间复杂度度感兴趣的的读者可以以把n和m的值设的的稍微大一一点，比如如十万这个个数量级的的数字，运运行的时候候就能明显显感觉出这这两种思路路写出来的的代码时间间效率大不不一样。