题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
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
};
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);
}
//把二叉树转化为双向链表
BSTreeNode* ConvertToDoubleList(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;
}
要求函数min、push 以及pop 的时间复杂度都是O(1)。
int data;
int min;
};
struct MinStack {
MinStackElement * data;
int size;
int top;
}
MinStack stack;
stack.size = maxSize;
stack.data = (MinStackElement*) malloc(sizeof(MinStackElement)*maxSize);
stack.top = 0;
return stack;
}
void MinStackFree(MinStack stack) {
free(stack.data);
}
void MinStackPush(MinStack stack, int d) {
if (stack.top == stack.size) error(“out of stack space.”);
MinStackElement* p = stack.data[stack.top];
p->data = d;
p->min = (stack.top==0?d : stack.data[top-1]);
if (p->min > d) p->min = d;
top ++;
}
int MinStackPop(MinStack stack) {
if (stack.top == 0) error(“stack is empty!”);
return stack.data[--stack.top].data;
}
int MinStackMin(MinStack stack) {
if (stack.top == 0) error(“stack is empty!”);
return stack.data[stack.top-1].min;
}
3、求子数组的最大和
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
参考编程之美
题目：输入一个整数和一棵二元树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
要求下排每个数都是先前上排那十个数在下排出现的次数。
上排的十个数如下：
【0，1，2，3，4，5，6，7，8，9】
举一个例子，
数值: 0,1,2,3,4,5,6,7,8,9
分配: 6,2,1,0,0,0,1,0,0,0
7、微软亚院之编程判断俩个链表是否相交
给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。
为了简化问题，我们假设俩个链表均不带环。
问题扩展：
1.如果链表可能有环列?
2.如果需要求出俩个链表相交的第一个节点列?
此贴选一些比较怪的题，，由于其中题目本身与算法关系不大，仅考考思维。特此并作一题。
这两个房间是分割开的，从一间里不能看到另一间的情况。
现在要求受训者分别进这两房间一次，然后判断出这三盏灯分别是由哪个开关控制的。
有什么办法呢？
块。
如果你只能将金条切割两次，你怎样分给这些工人?
ANSWER:
1+2+4;
3. 用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。
ANSWER:
Node * reverse(Node * head) {
if (head == NULL) return head;
if (head->next == NULL) return head;
Node * ph = reverse(head->next);
head->next->next = head;
head->next = NULL;
return ph;
}
Node * reverseNonrecurisve(Node * head) {
if (head == NULL) return head;
Node * p = head;
Node * previous = NULL;
while (p->next != NULL) {
p->next = previous;
previous = p;
p = p->next;
}
p->next = previous;
return p;
}
void reverse(char *str) {
reverseFixlen(str, strlen(str));
}
void reverseFixlen(char *str, int n) {
char* p = str+n-1;
while (str < p) {
char c = *str;
*str = *p; *p=c;
}
}
实现速度最快，移动最少。
判断整数序列是不是二元查找树的后序遍历结果
题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回true，否则返回false。
10、翻转句子中单词的顺序。
题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。
句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。
例如输入“I am a student.”，则输出“student. a am I”。
第11 题
求二叉树中节点的最大距离...
如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，
我们姑且定义"距离"为两节点之间边的个数。
写一个程序，
求一棵二叉树中相距最远的两个节点之间的距离。
struct NODE{ NODE *pLeft; NODE *pRight;}; struct RESULT{ int nMaxDistance; int nMaxDepth;}; RESULT GetMaximumDistance(NODE* root){ if (!root) { RESULT empty = { 0, -1 }; // trick: nMaxDepth is -1 and then caller will plus 1 to balance it as zero. return empty; } RESULT lhs = GetMaximumDistance(root->pLeft); RESULT rhs = GetMaximumDistance(root->pRight); RESULT result; result.nMaxDepth = max(lhs.nMaxDepth + 1, rhs.nMaxDepth + 1); result.nMaxDistance = max(max(lhs.nMaxDistance, rhs.nMaxDistance), lhs.nMaxDepth + rhs.nMaxDepth + 2); return result;}第12 题采用static成员变量。第13 题：两个指针。第14 题：void find2Number(int a[], int n, int dest) { sum = *f + *e; }第15 题：
void mirrorIteratively(Node * root) {第16 题：void printByLevel(Node root) {第17 题：
|
第18 题： 题目：n 个数字（0,1,…,n-1）形成一个圆圈，从数字0 开始， 每次从这个圆圈中删除第m 个数字（第一个为当前数字本身，第二个为当前数字的下一个数 字）。 当一个数字删除后，从被删除数字的下一个继续删除第m 个数字。 求出在这个圆圈中剩下的最后一个数字。
19、题目：定义Fibonacci 数列如下： / 0 n=0 f(n)= 1 n=1 \ f(n-1)+f(n-2) n=2 输入n，用最快的方法求该数列的第n 项。 第20 题： 题目：输入一个表示整数的字符串，把该字符串转换成整数并输出。 例如输入字符串"345"，则输出整数345。 第21 题 2010 年中兴面试题 编程求解： 输入两个整数n 和m，从数列1，2，3.......n 中随意取几个数, 使其和等于m ,要求将其中所有的可能组合列出来. void findCombination(int n, int m) { if (n>m) findCombination(m, m); int aux[n]; memset(aux, 0, n*sizeof(int)); helper(m, 0, aux); } void helper(int dest, int idx, int aux[], int n) { if (dest == 0) dump(aux, n); if (dest <= 0 || idx==n) return; helper(dest, idx+1, aux, n); aux[idx] = 1; helper(dest-idx-1, idx+1, aux, n); aux[idx] = 0; } void dump(int aux[], int n) { for (int i=0; i<n; i++) if (aux[i]) printf(“%3d”, i+1); printf(“\n”); } 第22 题： 有4 张红色的牌和4 张蓝色的牌，主持人先拿任意两张，再分别在A、B、C 三人额头上贴任意两张牌，A、B、C 三人都可以看见其余两人额头上的牌，看完后让他们猜自己额头上是什么颜色的牌，A 说不知道，B 说不知道，C 说不知道，然后A 说知道了。 思路：目的是推导出A的颜色，由于A先看B、C,则应先假定B、C的颜色然后推导A 分析：头上可能出现的牌为 bb、rr、rb（blue 、red） A：不知道 说明 B 、C中颜色相加没有等于4的牌 B：不知道 说明 A、C中颜色相加没有等于4的牌 C：不知道 说明 A、B中颜色相加没有等于4的牌
过程：1> B:rr(bb) C:rr(bb) A肯定知道，所以不符合要求 2> B:rr(bb) C:bb(rr) A不知道，由于B不知道，C不知道 所以A只能取 rb 3> B:rr C：rb C不知道->A不是rr A若是bb ->C根据A、B判断可以知道自己为rb，但C不知道，所以排除bb A=rb B:bb C：rb 同理可证A=rb B:rb C：rr 同理可证A=rb B:rb C：bb 同理可证A=rb 4> B:rb C：rb 如果A=rr B=rb C猜如果自己=bb 则B不可能不知道自己为rb 所以C可以猜到C=rb 如果A=bb B=rb 同理C可以猜到自己=rb 由于A排除了rr bb 所以只能取 A=rb 结论：不能同时存在rr和bb，A不能是rr和bb 第23 题： 用最简单，最快速的方法计算出下面这个圆形是否和正方形相交。 第24 题： 链表操作， （1）.单链表就地逆置， （2）合并链表 第25 题： |