算法面试：精选微软经典的算法面试100题 [每周更新]
算法面试：精选微软经典的算法面试100题
--------------
个人认为，算法永远是王道。
特此，精选微软等公司经典的算法面试100题，以飨各位。
希望，能有更多的人，参与其讨论交流 中来。
不正之处，还望不吝赐教，指正。谢谢。
每公布一道面试题之后，若有人回复，我会无偿给各位积分。
最后，我将公布那题的解决思路和源码。每周不定期更新。
注：请确定你的思路和方案是你自己想道的，再回复。
网上找资料然后复制黏贴至此处，恕不搭理。!(我当然分辨得出是不是你自己个人的思路。)(*^__^*)
--July、2010年10月。
------------------------------
1.把二元查找树转变成排序的双向链表
题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
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
};
2.设计包含min函数的栈。
定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。
3.求子数组的最大和
题目：
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
4.在二元树中找出和为某一值的所有路径
题目：输入一个整数和一棵二元树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
例如 输入整数22和如下二元树
10
/ \
5 12
/ \
4 7
则打印出两条路径：10, 12和10, 5, 7。
二元树节点的数据结构定义为：
struct BinaryTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BinaryTreeNode *m_pLeft; // left child of node
BinaryTreeNode *m_pRight; // right child of node
};
5.查找最小的k个元素
题目：输入n个整数，输出其中最小的k个。
例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。
[解决办法]
第一题解题代码：
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
BSTreeNode* ConvertToList(BSTreeNode* root)
{
BSTreeNode* left, right;
left=right=NULL;
if (root->m_pLeft!=NULL)
{
left=ConvertToList(root->m_pLeft);
}
if (root->m_pRight!=NULL)
{
right=ConvertToList(root->m_pRight);
}
BSTreeNode* end=NULL;
if (left)
{
end=left;
while (end->m_pRight)
end=end->m_pRight;
}
if (end!=NULL)
{
end->m_pRight=root;
root->m_pLeft=end;
}
else
left==root;
if (right)
{
root->m_pRight=right;
right->m_pLeft=root;
}
return left;
}
不知正确否
[解决办法]
第10题
---------------------------------
翻转句子中单词的顺序。
题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。句子中单词以空格符隔开。
为简单起见，标点符号和普通字母一样处理。
例如输入“I am a student.”，则输出“student. a am I”。
思路：先将整个英文句子翻转，这样一来每个单词也都翻转了，在将每个单词翻转回去即可！[size=24px][/size]
[解决办法]
第一题
- C/C++ code
template<typename T>class BTree{public: struct Node { T _data; Node * _pParent; Node * _plChild; Node * _prChild; Node(T const &val,Node *p =NULL,Node *l =NULL,Node *r =NULL); }; template<typename OP> void InorderWalk_Desc(OP op); template<typename OP> static void InorderWalk_Desc(Node * pNode,OP op); Node * _pRoot;};template<typename T>template<typename OP>void BTree<T>::InorderWalk_Desc(OP op){ InorderWalk_Desc(_pRoot,op);}template<typename T>template<typename OP>static void BTree<T>::InorderWalk_Desc(Node * pNode,OP op){ if (pNode!=NULL) { InorderWalk_Desc(pNode->_prChild,op); op(pNode); InorderWalk_Desc(pNode->_plChild,op); }}struct Holder{ BTree<int>::Node * pLast; Holder():pLast(NULL){}};struct ConvertToList{ ConvertToList(Holder & h):holder(h){} void operator()(BTree<int>::Node* pNode) { pNode->_prChild = holder.pLast; if (holder.pLast!=NULL) { holder.pLast->_plChild = pNode; } holder.pLast = pNode; } Holder & holder;};int main(){ srand(time(NULL)); BTree<int> tree; for (int i =0;i<50;++i) { tree.Insert(rand()%1000); } tree.InorderWalk(tree.GetRoot(),Print()); cout<<endl; Holder holder; tree.InorderWalk_Desc((ConvertToList(holder))); while(holder.pLast!=NULL) { cout<<setw(8)<<holder.pLast->_data; holder.pLast=holder.pLast->_prChild; } return 0;};
[解决办法]