算法面试题总结

下载后可任意编辑算法面试题总结下载后可任意编辑1 算法面试题总结1.把二元查找树转变成排序的双向链表 题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创立任何新的结点，只调整指针的指向。 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;}2.设计包含 min 函数的栈。定义栈的数据结构，要求添加一个 min 函数，能够得到栈的最小元素。要求函数 min、push 以及 pop 的时间复杂度都是 O(1)。 3.求子数组的最大和题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为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]中最大值}4.在二元树中找出和为某一值的所有路径题目：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。例如 ...