2022年程序员面试题精选.doc
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《2022年程序员面试题精选.doc》由会员分享,可在线阅读,更多相关《2022年程序员面试题精选.doc(10页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、程序员面试题精选100题(10)在排序数组中查找和为给定值的两个数字数组 2007-03-14 15:25:01 阅读4663 评论15 字号:大中小订阅 标题:输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。假如有多对数字的和等于输入的数字,输出任意一对即可。例如输入数组1、2、4、7、11、15和数字15。由于4+11=15,因而输出4和11。分析:假如我们不考虑时间复杂度,最简单办法的莫过去先在数组中固定一个数字,再依次推断数组中剩下的n-1个数字与它的和是不是等于输入的数字。惋惜这种思路需要的时间复杂度是O(n2
2、)。我们假设如今随意在数组中找到两个数。假如它们的和等于输入的数字,那太好了,我们找到了要找的两个数字;假如小于输入的数字呢?我们希望两个数字的和再大一点。由于数组已经排好序了,我们是不是能够把较小的数字的往后面挪动一个数字?由于排在后面的数字要大一些,那么两个数字的和也要大一些,就有可能等于输入的数字了;同样,当两个数字的和大于输入的数字的时候,我们把较大的数字往前挪动,由于排在数组前面的数字要小一些,它们的和就有可能等于输入的数字了。我们把前面的思路整理一下:最初我们找到数组的第一个数字和最后一个数字。当两个数字的和大于输入的数字时,把较大的数字往前挪动;当两个数字的和小于数字时,把较小的
3、数字往后挪动;当相等时,打完收工。如此的顺序是从数组的两端向数组的中间。咨询题是如此的思路是不是正确的呢?这需要严格的数学证明。感兴趣的读者能够自行证明一下。参考代码:/ Find two numbers with a sum in a sorted array/ Output: ture is found such two numbers, otherwise false/bool FindTwoNumbersWithSum(int data, / a sorted arrayunsigned int length, / the length of the sorted array int
4、sum, / the sumint num1, / the first number, outputint num2 / the second number, output)bool found = false;if(length behind)long long curSum = dataahead + databehind;/ if the sum of two numbers is equal to the input/ we have found themif(curSum = sum)num1 = databehind;num2 = dataahead;found = true;br
5、eak;/ if the sum of two numbers is greater than the input/ decrease the greater numberelse if(curSum sum)ahead -;/ if the sum of two numbers is less than the input/ increase the less numberelsebehind +;return found;扩展:假如输入的数组是没有排序的,但明白里面数字的范围,其他条件不变,如何在O(n)时间里找到这两个数字程序员面试题精选100题(11)求二元查找树的镜像树 2007-0
6、3-15 09:36:33 阅读3906 评论9 字号:大中小订阅 标题:输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。 例如输入: 8 / 6 10/ /5 7 9 11输出: 8 / 10 6/ /11 9 7 5定义二元查找树的结点为:struct BSTreeNode / a node in the binary search tree (BST)int m_nValue; / value of nodeBSTreeNode *m_pLeft; / left child of nodeBSTre
7、eNode *m_pRight; / right child of node;分析:尽管我们可能一下子不能理解镜像是什么意思,但上面的例子给我们的直观感受,确实是交换结点的左右子树。我们试着在遍历例子中的二元查找树的同时来交换每个结点的左右子树。遍历时首先访咨询头结点8,我们交换它的左右子树得到: 8 / 10 6/ /9 11 5 7我们发觉两个结点6和10的左右子树仍然是左结点的值小于右结点的值,我们再试着交换他们的左右子树,得到: 8 / 10 6/ /11 9 7 5刚好确实是要求的输出。上面的分析印证了我们的直觉:在遍历二元查找树时每访咨询到一个结点,交换它的左右子树。这种思路用递归
8、不难实现,将遍历二元查找树的代码稍作修正就能够了。参考代码如下:/ Mirror a BST (swap the left right child of each node) recursively/ the head of BST in initial call/void MirrorRecursively(BSTreeNode *pNode)if(!pNode)return;/ swap the right and left child sub-treeBSTreeNode *pTemp = pNode-m_pLeft;pNode-m_pLeft = pNode-m_pRight;pNod
9、e-m_pRight = pTemp;/ mirror left child sub-tree if not nullif(pNode-m_pLeft)MirrorRecursively(pNode-m_pLeft); / mirror right child sub-tree if not nullif(pNode-m_pRight)MirrorRecursively(pNode-m_pRight); 由于递归的本质是编译器生成了一个函数调用的栈,因而用循环来完成同样任务时最简单的方法确实是用一个辅助栈来模仿递归。首先我们把树的头结点放入栈中。在循环中,只要栈不为空,弹出栈的栈顶结点,交换它
10、的左右子树。假如它有左子树,把它的左子树压入栈中;假如它有右子树,把它的右子树压入栈中。如此在下次循环中就能交换它儿子结点的左右子树了。参考代码如下:/ Mirror a BST (swap the left right child of each node) Iteratively/ Input: pTreeHead: the head of BST/void MirrorIteratively(BSTreeNode *pTreeHead)if(!pTreeHead)return;std:stackstackTreeNode;stackTreeNode.push(pTreeHead);whi
11、le(stackTreeNode.size()BSTreeNode *pNode = stackTreeNode.top();stackTreeNode.pop();/ swap the right and left child sub-treeBSTreeNode *pTemp = pNode-m_pLeft;pNode-m_pLeft = pNode-m_pRight;pNode-m_pRight = pTemp;/ push left child sub-tree into stack if not nullif(pNode-m_pLeft)stackTreeNode.push(pNod
12、e-m_pLeft);/ push right child sub-tree into stack if not nullif(pNode-m_pRight)stackTreeNode.push(pNode-m_pRight);程序员面试题精选100题(12)从上往下遍历二元树队列 2007-03-19 21:17:03 阅读3798 评论5 字号:大中小订阅 标题:输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。 例如输入 8 / 6 10 / / 5 7 9 11输出8 6 10 5 7 9 11。分析:这曾是微软的一道面试题。这道题本质上是要求遍历一棵二元树
13、,只不过不是我们熟悉的前序、中序或者后序遍历。我们从树的根结点开场分析。自然先应该打印根结点8,同时为了下次能够打印8的两个子结点,我们应该在遍历到8时把子结点6和10保存到一个数据容器中。如今数据容器中就有两个元素6和10了。按照从左往右的要求,我们先取出6访咨询。打印6的同时要把6的两个子结点5和7放入数据容器中,如今数据容器中有三个元素10、5和7。接下来我们应该从数据容器中取出结点10访咨询了。留意10比5和7先放入容器,如今又比5和7先取出,确实是我们通常说的先入先出。因而不难看出这个数据容器的类型应该是个队列。既然已经确定数据容器是一个队列,如今的咨询题变成如何实现队列了。实际上我
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022 程序员 试题 精选
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内