算法面试题总结.doc

. . -.
. 文档.
算法面试题总结

 题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创立任何新的结点，只调整指针的指向。
   10
  / \
  6  14
 / \ / \
4  8 12 16
 转换成双向链表
4=6=8=10=12=14=16。
解：首先我们定义的二元查找树 节点的数据构造如下：
 typedef struct tree
{
  int data; // value of node
  struct tree *left; // left child of node
  struct tree *right; // right child of node
}*ptree;
 
ptree f(ptree root,int sign)//sign==0返回链头，sign==1返回链尾
{ //main函数中调用f(root,0);
ptree p=root;
if(p->left) //如果左子树非空
{
p->left = f(p->left,1);//第4个参数为，说明f函数返回root左子树中根的链尾
p->left->right = p; //双链表中left记录前驱，right记录后继
}
if(p->right)
{
p->right=f(p->right,0);
p->right->left = p;
}
if(sign==0) while(p->left) p=p->left ;//顺着left找到双链表首元素
else while(p->right)p=p->right;//顺着right找到双链表尾元素
return p;
}
。
定义栈的数据构造，要求添加一个min函数，能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。
 
. . -.
. 文档.

题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。
解：设数组元素为a[1~n]，f(i)表示以a[i]为尾元素的最大子段和，那么有
f(1)=a[1], f(i)=max{f(i-1)+a[i], a[i]} (i>1)
动态规划求f(i), b[i]保存f(i)的值。
Int f(int i)
{ int j,max;
max=b[1]=a[1];
for(j=2;j<=I;j++)
{
b[i]=a[i-1]>0" a[i-1]+a[i] : a[i];
if(b[i]>max) max=b[i];
}
return max;//返回b[1]~b[i]中最大值
}

题目：输入一个整数和一棵二元树。
从树的根结点开场往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
例如 输入整数22和如下二元树
  10  
  / \   
 5  12   
 /   \   
4     7
那么打印出两条路径：10, 12和10, 5, 7。
解：首先我们定义的二元查找树 节点的数据构造如下：
 typedef struct tree
{
  int data; // value of node
  struct tree *left; // left child of node
  struct tree *right; //