http://www.cnblogs.com/mfryf/archive/2012/07/31/2616697.html
1.一个整数数列，元素取值可能是0~65535中的任意一个数，相同数值不会重复出现。0是例外，可以反复出现。
请设计一个算法，当你从该数列中随意选取5个数值，判断这5个数值是否连续相邻。
注意：
- 5个数值允许是乱序的。比如： 8 7 5 0 6
- 0可以通配任意数值。比如：8 7 5 0 6 中的0可以通配成9或者4
- 0可以多次出现。
- 复杂度如果是O(n2)则不得分。
思路：非0最大-非0最小+1 <=5 ==> 非0最大-非0最小 <=4
2.设计一个算法，找出二叉树上任意两个结点的最近共同父结点。
复杂度如果是O(n2)则不得分。
思路：如果每个节点包含父亲指针，把两个节点到根的路径都记录下来，两条路径的最后面的元素肯定相同，从两条路径的最后一个元素向前比较，直到第一次出现分叉为止，就可以找到最近节点。复杂度为O（n），路径最长可能是n。如果不包含父亲节点，那就先前序遍历二叉树，遍历的时候可以像哈夫曼树那样左右01编号，记录给定两节点的到达路径，最后比较两个0，1序列的前面位数，直到出现不相等为止，就找到最近父节点，复杂度也是O（n）
3.一棵排序二叉树，令 f=(最大值+最小值)/2，设计一个算法，找出距离f值最近、大于f值的结点。
复杂度如果是O(n2)则不得分。
思路：找出最大值，最小值，复杂度都是O（h），然后搜索f，可以找到f应该插入的位置，复杂度也是O（h），再找f的后继，复杂度也是O（h），h最大可能是n，所以总体最坏情况复杂度就是O（n）
4.一个整数数列，元素取值可能是1~N（N是一个较大的正整数）中的任意一个数，相同数值不会重复出现。设计一个算法，找出数列中符合条件的数对的个数，满足数对中两数的和等于N+1。
复杂度最好是O(n)，如果是O(n2)则不得分。
思路：先排序，复杂度O（nlgn），然后用两个指示器（front和back）分别指向第一个和最后一个元素，
如果A[front]+A[back]>N+1，则back–；
如果A[front]+A[back]=N+1，则计数器加1，back–，同时front++；
如果A[front]+A[back]重复上述步骤，O（n）时间找到所有数对，总体复杂度为O（nlgn）
5.输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
10
/ \
6 14
/ \ / \
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16。
首先我们定义的二元查找树 节点的数据结构如下：
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
思路一：当我们到达某一结点准备调整以该结点为根结点的子树时，先调整其左子树将左子树转换成一个排好序的左子链表，再调整其右子树转换右子链表。最近链接左子链表的最右结点（左子树的最大结点）、当前结点和右子链表的最左结点（右子树的最小结点）。从树的根结点开始递归调整所有结点。
思路一对应的代码：
BSTreeNode* ConvertNode(BSTreeNode* pNode, bool asRight){
if(!pNode)
return NULL;
BSTreeNode *pLeft = NULL;
BSTreeNode *pRight = NULL;
// Convert the left sub-tree
if(pNode->m_pLeft)
pLeft = ConvertNode(pNode->m_pLeft, false);
// Connect the greatest node in the left sub-tree to the current node
if(pLeft)
{
pLeft->m_pRight = pNode;
pNode->m_pLeft = pLeft;
}
// Convert the right sub-tree
if(pNode->m_pRight)
pRight = ConvertNode(pNode->m_pRight, true);
// Connect the least node in the right sub-tree to the current node
if(pRight){
pNode->m_pRight = pRight;
pRight->m_pLeft = pNode;
}
BSTreeNode *pTemp = pNode;
// If the current node is the right child of its parent,
// return the least node in the tree whose root is the current node
if(asRight){
while(pTemp->m_pLeft)
pTemp = pTemp->m_pLeft;
}
// If the current node is the left child of its parent,
// return the greatest node in the tree whose root is the current node
else{
while(pTemp->m_pRight)
pTemp = pTemp->m_pRight;
}
return pTemp;
}
BSTreeNode* Convert(BSTreeNode* pHeadOfTree)
{
// As we want to return the head of the sorted double-linked list,
// we set the second parameter to be true
return ConvertNode(pHeadOfTree, true);
}
思路二：
我们可以中序遍历整棵树。按照这个方式遍历树，比较小的结点先访问。如果我们每访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整当前结点的指针将其链接到链表的末尾。当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。
void ConvertNode(BSTreeNode* pNode, BSTreeNode*& pLastNodeInList){
if(pNode == NULL)
return;
BSTreeNode *pCurrent = pNode;
// Convert the left sub-tree
if (pCurrent->m_pLeft != NULL)
ConvertNode(pCurrent->m_pLeft, pLastNodeInList);
// Put the current node into the double-linked list
pCurrent->m_pLeft = pLastNodeInList;
if(pLastNodeInList != NULL)
pLastNodeInList->m_pRight = pCurrent;
pLastNodeInList = pCurrent;
// Convert the right sub-tree
if (pCurrent->m_pRight != NULL)
ConvertNode(pCurrent->m_pRight, pLastNodeInList);
}
///////////////////////////////////////////////////////////////////////
// Covert a binary search tree into a sorted double-linked list
// Input: pHeadOfTree - the head of tree
// Output: the head of sorted double-linked list
///////////////////////////////////////////////////////////////////////
BSTreeNode* Convert_Solution1(BSTreeNode* pHeadOfTree)
{
BSTreeNode *pLastNodeInList = NULL;
ConvertNode(pHeadOfTree, pLastNodeInList);
// Get the head of the double-linked list
BSTreeNode *pHeadOfList = pLastNodeInList;
while(pHeadOfList && pHeadOfList->m_pLeft)
pHeadOfList = pHeadOfList->m_pLeft;
return pHeadOfList;
}
6.设计包含min函数的栈。定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。
思路：这是google的一道面试题。
看到这道题目时，第一反应就是每次push一个新元素时，将栈里所有逆序元素排序。这样栈顶元素将是最小元素。但由于不能保证最后push进栈的元素最先出栈，这种思路设计的数据结构已经不是一个栈了。
在栈里添加一个成员变量存放最小元素（或最小元素的位置）。每次push一个新元素进栈的时候，如果该元素比当前的最小元素还要小，则更新最小元素。
乍一看这样思路挺好的。但仔细一想，该思路存在一个重要的问题：如果当前最小元素被pop出去，如何才能得到下一个最小元素？
因此仅仅只添加一个成员变量存放最小元素（或最小元素的位置）是不够的。我们需要一个辅助栈。每次push一个新元素的时候，同时将最小元素push到辅助栈中；
//或最小元素的位置。考虑到栈元素的类型可能是复杂的数据结构，用最小元素的位置将能减少空间消耗。
每次pop一个元素出栈的时候，同时pop辅助栈。
参考代码：
#include
#include
template class CStackWithMin
{
public:
CStackWithMin(void) {}
virtual ~CStackWithMin(void) {}
T& top(void);
const T& top(void) const;
void push(const T& value);
void pop(void);
const T& min(void) const;
private:
T>m_data;// theelements of stack
size_t>m_minIndex;// the indicesof minimum elements
};
// get the last element of mutable stack
template T& CStackWithMin::top()
{
return m_data.back();
}
// get the last element of non-mutable stack
template const T& CStackWithMin::top() const
{
return m_data.back();
}
// insert an elment at the end of stack
template void CStackWithMin::push(const T& value)
{
// append the data into the end of m_data
m_data.push_back(value);
// set the index of minimum elment in m_data at the end of m_minIndex
if(m_minIndex.size() == 0)
m_minIndex.push_back(0);
else
{
if(value < m_data[m_minIndex.back()])
m_minIndex.push_back(m_data.size() - 1);
else
m_minIndex.push_back(m_minIndex.back());
}
}
// erease the element at the end of stack
template void CStackWithMin::pop()
{
// pop m_data
m_data.pop_back();
// pop m_minIndex
m_minIndex.pop_back();
}
// get the minimum element of stack
template const T& CStackWithMin::min() const
{
assert(m_data.size() > 0);
assert(m_minIndex.size() > 0);
return m_data[m_minIndex.back()];
}
6.求子数组的最大和（更高效的思路见编程珠玑83页）
题目：输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。
如果不考虑时间复杂度，我们可以枚举出所有子数组并求出他们的和。
不过非常遗憾的是，由于长度为n的数组有O(n2)个子数组；
而且求一个长度为n的数组的和的时间复杂度为O(n)。因此这种思路的时间是O(n3)。
当我们加上一个正数时，和会增加；当我们加上一个负数时，和会减少。
如果当前得到的和是个负数，那么这个和在接下来的累加中应该抛弃并重新清零，
不然的话这个负数将会减少接下来的和。基于这样的思路，我们可以写出如下代码。
参考代码：
// Find the greatest sum of all sub-arrays
// Return value: if the input is valid, return true, otherwise return false
/////////////////////////////////////////////////////////////////////////////
bool FindGreatestSumOfSubArray(
int *pData, // an array
unsigned int nLength, // the length of array
int &nGreatestSum // the greatest sum of all sub-arrays
)
{
// if the input is invalid, return false
if((pData == NULL) || (nLength == 0))
return false;
int nCurSum = nGreatestSum = 0;
for(unsigned int i = 0; i < nLength; ++i)
{
nCurSum += pData[i];
// if the current sum is negative, discard it
if(nCurSum < 0)
nCurSum = 0;
// if a greater sum is found, update the greatest sum
if(nCurSum > nGreatestSum)
nGreatestSum = nCurSum;
}
// if all data are negative, find the greatest element in the array
if(nGreatestSum == 0)
{
nGreatestSum = pData[0];
for(unsigned int i = 1; i < nLength; ++i)
{
if(pData[i] > nGreatestSum)
nGreatestSum = pData[i];
}
}
return true;
}
7.题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。句子中单词以空格符隔开。
为简单起见，标点符号和普通字母一样处理。
例如输入“I am a student.”，则输出“student. a am I”。
思路1：先将整个英文句子翻转，这样一来每个单词也都翻转了，在将每个单词翻转回去即可！
思路2：参照autoreleasepool添加哨兵指针的方式，第一次遍历给每个单词开头安插一个哨兵（index），然后将哨兵入栈。遍历完成后从栈顶开始遍历每个哨兵并输出哨兵索引对应的单词。
网友评论