程序员面试题精选.doc

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 sumintif(length

4、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 greater than the input/ decrease the greater numberelse if(curSum sum)ahead -;/ i

5、f 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 BST (swap the left right child of each node) recursively/ the head of BST

8、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-tree if not nullif(pNode-m_pLeft)MirrorRecursively(pNode-m_pLeft); / mirro

9、r right child sub-tree if not nullif(pNode-m_pRight)MirrorRecursively(pNode-m_pRight); 由于递归的本质是编译器生成了一个函数调用的栈，因此用循环来完成同样任务时最简单的办法就是用一个辅助栈来模拟递归。首先我们把树的头结点放入栈中。在循环中，只要栈不为空，弹出栈的栈顶结点，交换它的左右子树。如果它有左子树，把它的左子树压入栈中；如果它有右子树，把它的右子树压入栈中。这样在下次循环中就能交换它儿子结点的左右子树了。参考代码如下：/ Mirror a BST (swap the left right child o

10、f 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 = stackTreeNode.top();stackTreeNode.pop();/ swap the right and left child sub

11、-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 stack if not nullif(pNode-m_pRight)stackTreeNode.push(pNode-m_pRight);程序员面

12、试题精选 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 保存到一个数据容器中。现在数据容器中就有两个元

13、素 6 和 10 了。按照从左往右的要求，我们先取出 6 访问。打印 6 的同时要把 6 的两个子结点 5 和 7 放入数据容器中，此时数据容器中有三个元素 10、5 和 7。接下来我们应该从数据容器中取出结点 10 访问了。注意 10 比 5和 7 先放入容器，此时又比 5 和 7 先取出，就是我们通常说的先入先出。因此不难看出这个数据容器的类型应该是个队列。既然已经确定数据容器是一个队列，现在的问题变成怎么实现队列了。实际上我们无需自己动手实现一个，因为 STL 已经为我们实现了一个很好的 deque（两端都可以进出的队列），我们只需要拿过来用就可以了。我们知道树是图的一种特殊退化形式。同

14、时如果对图的深度优先遍历和广度优先遍历有比较深刻的理解，将不难看出这种遍历方式实际上是一种广度优先遍历。因此这道题的本质是在二元树上实现广度优先遍历。参考代码：#include #include using namespace std;struct BTreeNode / a node in the binary treeint m_nValue; / value of nodeBTreeNode *m_pLeft; / left child of nodeBTreeNode *m_pRight; / right child of node;/ Print a binary tree from

15、 top level to bottom level/ Input: pTreeRoot - the root of binary tree/void PrintFromTopToBottom(BTreeNode *pTreeRoot)if(!pTreeRoot)return;/ get a empty queuedeque dequeTreeNode;/ insert the root at the tail of queuedequeTreeNode.push_back(pTreeRoot);while(dequeTreeNode.size()/ get a node from the h

16、ead of queueBTreeNode *pNode = dequeTreeNode.front();dequeTreeNode.pop_front();/ print the nodecout m_nValue m_pLeft)dequeTreeNode.push_back(pNode-m_pLeft);/ print its right child sub-tree if it hasif(pNode-m_pRight)dequeTreeNode.push_back(pNode-m_pRight);程序员面试题精选 100 题(13)第一个只出现一次的字符字符串 2007-03-21

17、21:17:22 阅读 5465 评论 30 字号：大中小 订阅 题目：在一个字符串中找到第一个只出现一次的字符。如输入 abaccdeff，则输出 b。 分析：这道题是 2006 年 google 的一道笔试题。看到这道题时，最直观的想法是从头开始扫描这个字符串中的每个字符。当访问到某字符时拿这个字符和后面的每个字符相比较，如果在后面没有发现重复的字符，则该字符就是只出现一次的字符。如果字符串有 n 个字符，每个字符可能与后面的 O(n)个字符相比较，因此这种思路时间复杂度是 O(n2)。我们试着去找一个更快的方法。由于题目与字符出现的次数相关，我们是不是可以统计每个字符在该字符串中出现的次

18、数？要达到这个目的，我们需要一个数据容器来存放每个字符的出现次数。在这个数据容器中可以根据字符来查找它出现的次数，也就是说这个容器的作用是把一个字符映射成一个数字。在常用的数据容器中，哈希表正是这个用途。哈希表是一种比较复杂的数据结构。由于比较复杂，STL 中没有实现哈希表，因此需要我们自己实现一个。但由于本题的特殊性，我们只需要一个非常简单的哈希表就能满足要求。由于字符（char）是一个长度为8 的数据类型，因此总共有可能 256 种可能。于是我们创建一个长度为 256 的数组，每个字母根据其ASCII 码值作为数组的下标对应数组的对应项，而数组中存储的是每个字符对应的次数。这样我们就创建了

19、一个大小为 256，以字符 ASCII 码为键值的哈希表。我们第一遍扫描这个数组时，每碰到一个字符，在哈希表中找到对应的项并把出现的次数增加一次。这样在进行第二次扫描时，就能直接从哈希表中得到每个字符出现的次数了。参考代码如下：/ Find the first char which appears only once in a string/ Input: pString - the string/ Output: the first not repeating char if the string has, otherwise 0/char FirstNotRepeatingChar(cha

20、r* pString)/ invalid inputif(!pString)return 0;/ get a hash table, and initialize it const int tableSize =256;unsignedint hashTabletableSize;for(unsignedint i = 0; i 0k+2 - 1n-1 - n-k-20 - n-k-1k-1 - n-2把映射定义为 p，则 p(x)= (x-k-1)%n，即如果映射前的数字是 x，则映射后的数字是(x-k-1)%n 。对应的逆映射是 p-1(x)=(x+k+1)%n。由于映射之后的序列和最初的

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

22、f(n-1,m)+m%n n1尽管得到这个公式的分析过程非常复杂，但它用递归或者循环都很容易实现。最重要的是，这是一种时间复杂度为 O(n)，空间复杂度为 O(1)的方法，因此无论在时间上还是空间上都优于前面的思路。思路一的参考代码：/ n integers (0, 1, . n - 1) form a circle. Remove the mth from / the circle at every time. Find the last number remaining / Input: n - the number of integers in the circle initially/

23、 m - remove the mth number at every time/ Output: the last number remaining when the input is valid,/ otherwise -1/int LastRemaining_Solution1(unsigned int n, unsigned int m)/ invalid inputif(n integers;for(i = 0; i :iterator curinteger = integers.begin();while(integers.size() 1)/ find the mth integ

24、er. Note that std:list is not a circle/ so we should handle it manuallyfor(int i = 1; i :iterator nextinteger = + curinteger;if(nextinteger = integers.end()nextinteger = integers.begin();- curinteger;integers.erase(curinteger);curinteger = nextinteger;return *(curinteger);思路二的参考代码：/ n integers (0, 1

25、, . n - 1) form a circle. Remove the mth from / the circle at every time. Find the last number remaining / Input: n - the number of integers in the circle initially/ m - remove the mth number at every time/ Output: the last number remaining when the input is valid,/ otherwise -1/int LastRemaining_So

26、lution2(int n, unsigned int m)/ invalid inputif(n = 0 | m 0)return -1;/ if there are only one integer in the circle initially,/ of course the last remaining one is 0int lastinteger = 0;/ find the last remaining one in the circle with n integersfor (int i = 2; i = n; i +) lastinteger = (lastinteger + m) % i;return lastinteger;如果对两种思路的时间复杂度感兴趣的读者可以把 n 和 m 的值设的稍微大一点，比如十万这个数量级的数字，运行的时候就能明显感觉出这两种思路写出来的代码时间效率大不一样。