程序员面试题精选100题完整版(3)

很全面,很经典的程序员面试题精选100题,包括网络编程,socket编程,c++/c编程程序员面试题,linux/windows网络编程面试必备。

这是我能够想出来的最快的解决方案。不过从给面试官留下更好印象的角度出发，我们可以进一步把代码写得更漂亮一些。从上面的分析，当长度为k的数组已经满了之后，如果需要替换，每次替换的都是数组中的最大值。在常用的数据结构中，能够在O(1)时间里得到最大值的数据结构为最大堆。因此我们可以用堆（heap）来代替数组。

另外，自己重头开始写一个最大堆需要一定量的代码。我们现在不需要重新去发明车轮，因为前人早就发明出来了。同样，STL中的set和multiset为我们做了很好的堆的实现，我们可以拿过来用。既偷了懒，又给面试官留下熟悉STL的好印象，何乐而不为之？ 参考代码：

#include <set>

#include <vector>

#include <iostream>

using namespace std;

typedef multiset<int, greater<int> > IntHeap;

///////////////////////////////////////////////////////////////////////

// find k least numbers in a vector

///////////////////////////////////////////////////////////////////////

void FindKLeastNumbers

(

)

{

// leastNumbers contains k numbers and it's full now else { // first number in leastNumbers is the greatest one vector<int>::const_iterator iter = data.begin(); for(; iter != data.end(); ++ iter) { // if less than k numbers was inserted into leastNumbers if((leastNumbers.size()) < k) leastNumbers.insert(*iter); if(k == 0 || data.size() < k) return; leastNumbers.clear(); const vector<int>& data, // a vector of data IntHeap& leastNumbers, // k least numbers, output unsigned int k

很全面,很经典的程序员面试题精选100题,包括网络编程,socket编程,c++/c编程程序员面试题,linux/windows网络编程面试必备。

} } } // if is less than the previous greatest number if(*iter < *(leastNumbers.begin())) { } // replace the previous greatest number leastNumbers.erase(iterFirst); leastNumbers.insert(*iter);

(06)判断整数序列是不是二元查找树的后序遍历结果

题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。

例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果： 8

/ \

6 10

/ \ / \

5 7 9 11

因此返回true。

如果输入7、4、6、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, // otherwise, return false

/////////////////////////////////////////////////////////////////////

很全面,很经典的程序员面试题精选100题,包括网络编程,socket编程,c++/c编程程序员面试题,linux/windows网络编程面试必备。

bool verifySquenceOfBST(int squence[], int length)

{

} return (left && right); // verify whether the right sub-tree is a BST bool right = true; if(i < length - 1) right = verifySquenceOfBST(squence + i, length - i - 1); // verify whether the left sub-tree is a BST bool left = true; if(i > 0) left = verifySquenceOfBST(squence, i); // the nodes in the right sub-tree are greater than the root int j = i; for(; j < length - 1; ++ j) { } if(squence[j] < root) return false; // the nodes in left sub-tree are less than the root int i = 0; for(; i < length - 1; ++ i) { } if(squence[i] > root) break; // root of a BST is at the end of post order traversal squence int root = squence[length - 1]; if(squence == NULL || length <= 0) return false;

(07)－翻转句子中单词的顺序

题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。

例如输入“I am a student.”，则输出“student. a am I”。

分析：由于编写字符串相关代码能够反映程序员的编程能力和编程习惯，与字符串相关的问

很全面,很经典的程序员面试题精选100题,包括网络编程,socket编程,c++/c编程程序员面试题,linux/windows网络编程面试必备。

题一直是程序员笔试、面试题的热门题目。本题也曾多次受到包括微软在内的大量公司的青睐。

由于本题需要翻转句子，我们先颠倒句子中的所有字符。这时，不但翻转了句子中单词的顺序，而且单词内字符也被翻转了。我们再颠倒每个单词内的字符。由于单词内的字符被翻转两次，因此顺序仍然和输入时的顺序保持一致。

还是以上面的输入为例子。翻转“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)

{

}

///////////////////////////////////////////////////////////////////////

// Reverse the word order in a sentence, but maintain the character // order inside a word

// Input: pData - the sentence to be reversed

///////////////////////////////////////////////////////////////////////

char* ReverseSentence(char *pData)

{

char *pB …… 此处隐藏：4314字，全部文档内容请下载后查看。喜欢就下载吧 ……