程序员面试100题(编辑修改稿)

程序员面试100题(编辑修改稿)内容摘要：

输入 1， 2， 3， 4， 5， 6， 7 和 8 这 8 个数字，则最小的 4 个数字为 1， 2， 3 和 4。 分析：这道题最简单的思路莫过于把输入的 n 个整数排序，这样排在最前面的 k 个数就是最小的 k 个数。 只是这种思路的时间复杂度为 O(nlogn)。 我们试着寻找更快的解决思路。 我们可以开辟一个长度为 k 的数组。 每次从输入的 n 个整数中读入一个数。 如果数组中已经插入的元素少于 k 个，则将读入的整数直接放到数组中。 否则长度为 k 的数组已经满了，不能再往数组里插入元素，只能替换了。 如果读入的这个整数比数组中已有 k个整数的最大值要小，则用读入的这个整数替换这 个最大值；如果读入的整数比数组中已有 k 个整数的最大值还要大，则读入的这个整数不可能是最小的 k 个整数之一，抛弃这个整数。 这种思路相当于只要排序 k 个整数，因此时间复杂可以降到 O(n+nlogk)。 通常情况下 k 要远小于 n，所以这种办法要优于前面的思路。 这是我能够想出来的最快的解决方案。 不过从给面试官留下更好印象的角度出发，我们可以 11 进一步把代码写得更漂亮一些。 从上面的分析，当长度为 k 的数组已经满了之后，如果需要替换，每次替换的都是数组中的最大值。 在常用的数据结构中，能够在 O(1)时间里得到最大值的数据结构为最大堆。 因此我们可以用堆（ heap）来代替数组。 另外，自己重头开始写一个最大堆需要一定量的代码。 我们现在不需要重新去发明车轮，因为前人早就发明出来了。 同样， STL中的 set 和 multiset 为我们做了很好的堆的实现，我们可以拿过来用。 既偷了懒，又给面试官留下熟悉 STL 的好印象，何乐而不为之。 参考代码： include set include vector include iostream using namespace std。 typedef multisetint, greaterint IntHeap。 /////////////////////////////////////////////////////////////////////// // find k least numbers in a vector /////////////////////////////////////////////////////////////////////// void FindKLeastNumbers ( const vectorintamp。 data, // a vector of data IntHeapamp。 leastNumbers, // k least numbers, output unsigned int k ) { ()。 if(k == 0 || () k) return。 vectorint::const_iterator iter = ()。 for(。 iter != ()。 ++ iter) { // if less than k numbers was inserted into leastNumbers if((()) k) (*iter)。 // leastNumbers contains k numbers and it39。 s full now else { // first number in leastNumbers is the greatest one 12 IntHeap::iterator iterFirst = ()。 // if is less than the previous greatest number if(*iter *(())) { // replace the previous greatest number (iterFirst)。 (*iter)。 } } } } (06)判断整数序列是不是二元查找树的后序遍历结果 题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。 如果是返回true，否则返回 false。 例如输入 1 8，由于这一整数序列是如下树的后序遍历结果： 8 / \ 6 10 / \ / \ 5 7 9 11 因此返回 true。 如果输入 5，没有哪棵树的后序遍历的结果是这个序列，因此返回 false。 分析：这是一道 trilogy 的笔试题，主要考查对二元查找树的理解。 在后续遍历得到的序列中，最后一个元素为树的根结点。 从头开始扫描这个序列，比根结点小的元素都应该位于序列的左半部分；从第一个大于跟结点开始到跟结点前面的一个元素为止，所有元素都应该大于跟结点，因为这部分元素对应的是树的右子树。 根据这样的划分，把序列划分为左右两部分，我们递归地确认序列的左、右两部分是不是都是二元查找树。 参考代码： using namespace std。 /////////////////////////////////////////////////////////////////////// // Verify whether a squence of integers are the post order traversal // of a binary search tree (BST) // Input: squence the squence of integers // length the length of squence // Return: return ture if the squence is traversal result of a BST, 13 // otherwise, return false /////////////////////////////////////////////////////////////////////// bool verifySquenceOfBST(int squence[], int length) { if(squence == NULL || length = 0) return false。 // root of a BST is at the end of post order traversal squence int root = squence[length 1]。 // the nodes in left subtree are less than the root int i = 0。 for(。 i length 1。 ++ i) { if(squence[i] root) break。 } // the nodes in the right subtree are greater than the root int j = i。 for(。 j length 1。 ++ j) { if(squence[j] root) return false。 } // verify whether the left subtree is a BST bool left = true。 if(i 0) left = verifySquenceOfBST(squence, i)。 // verify whether the right subtree is a BST bool right = true。 if(i length 1) right = verifySquenceOfBST(squence + i, length i 1)。 return (left amp。 amp。 right)。 } 14 (07)－翻转句子中单词的顺序 题目：输入一个英文句子，翻转句子中单词 的顺序，但单词内字符的顺序不变。 句子中单词以空格符隔开。 为简单起见，标点符号和普通字母一样处理。 例如输入“ I am a student.”，则输出“ student. a am I”。 分析：由于编写字符串相关代码能够反映程序员的编程能力和编程习惯，与字符串相关的问题一直是程序员笔试、面试题的热门题目。 本题也曾多次受到包括微软在内的大量公司的青睐。 由于本题需要翻转句子，我们先颠倒句子中的所有字符。 这时，不但翻转了句子中单词的顺序，而且单词内字符也被翻转了。 我们再颠倒每个单词内的字符。 由于单词内的字符被翻转两次，因此顺序仍然和输入时的顺序保持一致。 还是以上面的输入为例子。 翻转“ I am a student.”中所有字符得到“ .tneduts a ma I”，再翻转每个单词中字符的顺序得到“ students. a am I”，正是符合要求的输出。 参考代码： /////////////////////////////////////////////////////////////////////// // Reverse a string between two pointers // Input: pBegin the begin pointer in a string // pEnd the end pointer in a string /////////////////////////////////////////////////////////////////////// void Reverse(char *pBegin, char *pEnd) { if(pBegin == NULL || pEnd == NULL) return。 while(pBegin pEnd) { char temp = *pBegin。 *pBegin = *pEnd。 *pEnd = temp。 pBegin ++, pEnd。 } } /////////////////////////////////////////////////////////////////////// // Reverse the word order in a sentence, but maintain the character // order inside a word // Input: pData the sentence to be reversed ///////////////////////////////////////////////////////////////////// 15 // char* ReverseSentence(char *pData) { if(pData == NULL) return NULL。 char *pBegin = pData。 char *pEnd = pData。 while(*pEnd != 39。 \039。 ) pEnd ++。 pEnd。 // Reverse the whole sentence Reverse(pBegin, pEnd)。 // Reverse every word in the sentence pBegin = pEnd = pData。 while(*pBegin != 39。 \039。 ) { if(*pBegin == 39。 39。 ) { pBegin ++。 pEnd ++。 continue。 } // A word is between with pBegin and pEnd, reverse it else if(*pEnd == 39。 39。 || *pEnd == 39。 \039。 ) { Reverse(pBegin, pEnd)。 pBegin = ++pEnd。 } else { pEnd ++。 } } return pData。 } 16 (08)－求 1+2+...+n 题目：求 1+2+…+n ，要求不能使用乘除法、 for、 while、 if、 else、 switch、 case 等关键 字以及条件判断语句（ A?B:C）。 分析：这道题没有多少实际意义，因为在软件开发中不会有这么变态的限制。 但这道题却能有效地考查发散思维能力，而发散思维能力能反映出对编程相关技术理解的深刻程度。 通常求 1+2+…+n 除了。