1、程序员面试题精选100题(10)在排序数组中查找和为给定值的两个数字 题目：输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是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 sum, / the sumint& num1, / the first num
4、ber, 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;break;/ if the sum of two numbers is gre
5、ater 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-03-15 09:36:33 阅读3906 评论9 字号：大中小订阅 题目：输
6、入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。 例如输入： 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 nodeBSTreeNode *m_pRight; / right child of node
7、;分析：尽管我们可能一下子不能理解镜像是什么意思，但上面的例子给我们的直观感觉，就是交换结点的左右子树。我们试着在遍历例子中的二元查找树的同时来交换每个结点的左右子树。遍历时首先访问头结点8，我们交换它的左右子树得到： 8 / 10 6/ /9 11 5 7我们发现两个结点6和10的左右子树仍然是左结点的值小于右结点的值，我们再试着交换他们的左右子树，得到： 8 / 10 6/ /11 9 7 5刚好就是要求的输出。上面的分析印证了我们的直觉：在遍历二元查找树时每访问到一个结点，交换它的左右子树。这种思路用递归不难实现，将遍历二元查找树的代码稍作修改就可以了。参考代码如下：/ Mirror a
8、 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;pNode-m_pRight = pTemp;/ mirror left child sub
9、-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);while(stackTreeNode.size()BSTreeNode *pNode =
11、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(pNode-m_pLeft);/ push right child sub-tree into
12、 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。分析：这曾是微软的一道面试题。这道题实质上是要求遍历一棵二元树，只不过不是我们熟悉的前序、中序或者后序遍历。我们从树的根结点开始分析。自然先应该打印根结点8，同时为了下次能够打印8的两个子结点，我们应该在遍历到8时把子结点6和10保存到一个数据容器中。现在数据容器中就有两个元素6和10了。按照从左往右的要求，我们先取出6访问。打印6的同时要把6的两个子结点5和7放入数据容器中，此时数据容器中有三个元素10、5和7。接下来我们应该从数据容器中取出结点10访问了。注意10比5和7先放入容器，
