编程面试的10大算法概念汇总

《编程面试的10大算法概念汇总》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、编程面试的10大算法概念汇总以卜•是在编程而试中排名前10的算法相关的概念，我会通过一些简单的例子来阐述这些概念。由于完全掌握这些概念需要更多的努力，因此这份列表只是作为一个介绍。本文将从Java的角度看问题，包含下面的这些概念：1.字符串2.链表3.树4.图5.排序6.递归vs.迭代7.动态规划&位操作9.概率问题10.排列组合1.字符串如果IDE没有代码白动补全功能，所以你应该记住卜•面的这些方法。toCharArray()//获得字符串对应的char数组Arrays.sort()//数组排序Arrays.toString(char[Ja)//数组转成7符串charA

2、t(intx)//获得某个索引处的字符length()//字符串长度length//数组大小2.链表在Java屮,链表的实现非常简单，每个节点Node都有一个值val和指向卜•个节点的链接next。classNode{intval;Nodenext;Node(intx){val=x;next=null;)链农两个著名的应用是栈Stack和队列Queueo栈:classStack}Nodetop;publicNodepeek(){if(top!=null){returntop;}returnnull;publicNodepop(){if(top==null){returnn

3、ull;}else{Nodetemp=newNode(top.val);top=top.next;returntemp;}publicvoidpush(Nodcn){if(n!=null){n.next=top;top=n;))队列:classQueue{Nodefirst,last;publicvoidenqueue(Noden){if(first==null){first=n;last=first;}else{last.next=n;last=n;})publicNodedequeue(){if(first==null){returnnull;)else{Nodete

4、mp=newNode(first.val);first=first.next;returntemp;})}1.树这里的树通常是指二叉树，每个节点都包含一个左孩了节点和右孩了节点，像下面这样:classTreeNodejintvalue;TrccNodcleft;TreeNoderight;}下面是与树相关的一些概念:平衡vs.非平衡：平衡二叉树中，每个节点的左右子树的深度相差至多为1(1或0)。满二叉树(FullBinaryTree)：除叶子节点以为的每个节点都有两个孩子。完美二叉树(PerfectBinaryTree)：是具有下列性质的满二叉树：所有的叶子节点都有相同的

5、深度或处在同一层次，且每个父节点都必须有两个孩了。完全二叉树(CompleteBinaryTree)：二叉树屮，可能除了最后一个，每一层都被完全填满,且所有节点都必须尽可能想左靠。译者注：完美二叉树也隐约称为完全二义树。完美二义树的一个例子是一个人在给定深度的祖先图，因为每个人都一定有两个生父母。完全二叉树町以看成是可以有若干额外向左靠的叶子节点的完美二叉树。疑问：完美二叉树和满二叉树的区别？(参考：http://xlinux.nist.gov/dads/HTML7perfectBinaryTree.html)2.图图相关的问题主要集屮在深度优先搜索(depthfirst

6、search)和广度优先搜索(breathfirstsearch)o卜市是一个简单的图广度优先搜索的实现。1)定义GraphNodeclassGraphNode)intval;GraphNodenext;GraphNode[Jneighbors;booleanvisited;GraphNodc(intx){val=x;)GraphNode(intx,GraphNodef]n){val=x;neighbors=n;)publicStringtoString(){return"value:H+this.val;2)定义一个队列QueueclassQueue{GraphNode

7、first,last;publicvoidcnqucuc(GraphNodcn){if(first==null){first=n;last=first;}else{last.ncxt=n;last=n;publicGraphNodedcqucuc(){if(first==null){returnnull;}else{GraphNodetemp=newGraphNode(first.val,first.neighbors);first=first.ncxt;returntemp;3）川队列Queue实现广度优先搜索publicc