算法面试题及答案

算法面试题及答案【篇一：数据结构与算法面试题80道】前已整理公布的前80题，现在，一次性分享出来。此也算是前80题第一次集体亮相。此些题，已有上万人，看到或见识到，若私自据为己有，必定为有知之人识破，付出代价。所以，作者声明:向你的厚道致敬。谢谢。----------------------------------------------------------------------------------------------------------------1.把二元查找树转变成排序的双向链表题目:输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。10/\614/\/\481216转换成双向链表4=6=8=10=12=14=16。首先我们定义的二元查找树节点的数据结构如下:structbstreenode{intm_nvalue;//valueofnodebstreenode*m_pleft;//leftchildofnodebstreenode*m_pright;//rightchildofnode};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。4.在二元树中找出和为某一的所有路径题目:输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。例如输入整数22和如下二元树10/\512/\47则打印出两条路径:10,12和10,5,7。二元树节点的数据结构定义为:structbinarytreenode//anodeinthebinarytree{intm_nvalue;//valueofnodebinarytreenode*m_pleft;//leftchildofnodebinarytreenode*m_pright;//rightchildofnode};5.查找最小的k个元素题目:输入n个整数，输出其中最小的k个。例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。第6题腾讯面试题:给你10分钟时间，根据上排给出十个数，在其下排填出对应的十个数要求下排每个数都是先前上排那十个数在下排出现的次数。上排的十个数如下:【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,00在下排出现了6次，1在下排出现了2次，2在下排出现了1次，3在下排出现了0次....以此类推..第7题微软亚院之编程判断俩个链表是否相交为了简化问题，我们假设俩个链表均不带环。问题扩展:1.如果链表可能有环列?2.如果需要求出俩个链表相交的第一个节点列?第8题此贴选一些比较怪的题，，由于其中题目本身与算法关系不大，仅考考思维。特此并作一题。1.有两个房间，一间房里有三盏灯，另一间房有控制着三盏灯的三个开关，这两个房间是分割开的，从一间里不能看到另一间的情况。现在要求受训者分别进这两房间一次，然后判断出这三盏灯分别是由哪个开关控制的。有什么办法呢?2.你让一些人为你工作了七天，你要用一根金条作为报酬。金条被分成七小块，每天给出一块。如果你只能将金条切割两次，你怎样分给这些工人?3.★用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。★用一种算法在一个循环的链接表里插入一个节点，但不得穿越链接表。★用一种算法整理一个数组。你为什么选择这种方法?★用一种算法使通用字符串相匹配。★颠倒一个字符串。优化速度。优化空间。★颠倒一个句子中的词的顺序，比如将“我叫克丽丝”转换为“克丽丝叫我”，实现速度最快，移动最少。★找到一个子字符串。优化速度。优化空间。★比较两个字符串，用o(n)时间和恒量空间。★假设你有一个用1001个整数组成的数组，这些整数是任意排列的，但是你知道所有的整数都在1到1000(包括1000)之间。此外，除一个数字出现两次外，其他所有数字只出现一次。假设你只能对这个数组做一次处理，用一种算法找出重复的那个数字。如果你在运算中使用了辅助的存储方式，那么你能找到不用这种方式的算法吗?★不用乘法或加法增加8倍。现在用同样的方法增加7倍。第9题判断整数序列是不是二元查找树的后序遍历结果题目:输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果:8/\610/\/\57911因此返回true。如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。第10题翻转句子中单词的顺序。题目:输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。句子中单词以空符隔开。为简单起见，标点符号和普通字母一样处理。例如输入“iamastudent.”，则输出“student.aami”。第11题求二叉树中节点的最大距离...如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义距离为两节点之间边的个数。写一个程序，求一棵二叉树中相距最远的两个节点之间的距离。第12题题目:求1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句(a?b:c)。【篇二：java经典算法42例(包含企业常用面试题及答案欢迎下载)】欢迎大家加入java讨论群！java帝国：165715601【程序1】题目：古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第四个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？1.程序分析：兔子的规律为数列1,1,2,3,5,8,13,21....publicclassexp2{publicstaticvoidmain(stringargs[]){inti=0;for(i=1;i=20;i++)system.out.println(f(i));}publicstaticintf(intx){if(x==1||x==2)return1;elsereturnf(x-1)+f(x-2);}}或publicclassexp2{publicstaticvoidmain(stringargs[]){inti=0;mathmymath=newmath();for(i=1;i=20;i++)system.out.println(mymath.f(i));}}classmath{publicintf(intx){if(x==1||x==2)return1;elsereturnf(x-1)+f(x-2);}}【程序2】题目：判断101-200之间有多少个素数，并输出所有素数。1.程序分析：判断素数的方法：用一个数分别去除2到sqrt(这个数)，如果能被整除，则表明此数不是素数，反之是素数。publicclassexp2{publicstaticvoidmain(stringargs[]){inti=0;mathmymath=newmath();for(i=2;i=200;i++)if(mymath.iszhishu(i)==true)system.out.println(i);}}classmath{publicintf(intx){if(x==1||x==2)return1;elsereturnf(x-1)+f(x-2);}publicbooleaniszhishu(intx){}}for(inti=2;i=x/2;i++)if(x%2==0)returnfalse;returntrue;【程序3】题目：打印出所有的水仙花数，所谓水仙花数是指一个三位数，其各位数字立方和等于该数本身。例如：153是一个水仙花数，因为153=1的三次方＋5的三次方＋3的三次方。1.程序分析：利用for循环控制100-999个数，每个数分解出个位，十位，百位。publicclassexp2{publicstaticvoidmain(stringargs[]){inti=0;mathmymath=newmath();for(i=100;i=999;i++)if(mymath.shuixianhua(i)==true)system.out.println(i);}}classmath{publicintf(intx){if(x==1||x==2)return1;elsereturnf(x-1)+f(x-2);}publicbooleaniszhishu(intx){for(inti=2;i=x/2;i++)if(x%2==0)returnfalse;returntrue;}publicbooleanshuixianhua(intx){inti=0,j=0,k=0;i=x/100;j=(x%100)/10;k=x%10;if(x==i*i*i+j*j*j+k*k*k)returntrue;elsereturnfalse;}}【程序4】题目：将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。程序分析：对n进行分解质因数，应先找到一个最小的质数k，然后按下述步骤完成：(1)如果这个质数恰等于n，则说明分解质因数的过程已经结束，打印出即可。(2)如果nk，但n能被k整除，则应打印出k的值，并用n除以k的商,作为新的正整数你,重复执行第一步。(3)如果n不能被k整除，则用k+1作为k的值,重复执行第一步。publicclassexp2{publicexp2(){}publicvoidfengjie(intn){for(inti=2;i=n/2;i++){if(n%i==0){system.out.print(i+*);fengjie(n/i);}}system.out.print(n);system.exit(0);///不能少这句，否则结果会出错}publicstaticvoidmain(string[]args){stringstr=;exp2c=newexp2();str=javax.swing.joptionpane.showinputdialog(请输入n的值（输入exit退出）：);intn;n=0;try{n=integer.parseint(str);}catch(numberformatexceptione){e.printstacktrace();}system.out.print(n+分解质因数：+n+=);c.fengjie(n);}}【程序5】题目：利用条件运算符的嵌套来完成此题：学习成绩=90分的同学用a表示，60-89分之间的用b表示，60分以下的用c表示。1.程序分析：(ab)?a:b这是条件运算符的基本例子。importjavax.swing.*;publicclassex5{publicstaticvoidmain(string[]args){stringstr=;str=joptionpane.showinputdialog(请输入n的值（输入exit退出）：);intn;n=0;try{n=integer.parseint(str);}catch(numberformatexceptione){e.printstacktrace();}str=(n90?a:(n60?b:c));system.out.println(str);}}【程序6】题目：输入两个正整数m和n，求其最大公约数和最小公倍数。1.程