以下是在编程面试中排名前10的算法相关的概念,我会通过一些简单的例子来阐述这些概念。由于完全掌握这些概念需要更多的努力,因此这份列表只是作为一个介绍。本文将从Java的角度看问题,包含下面的这些概念:
如果IDE没有代码自动补全功能,所以你应该记住下面的这些方法。
在Java中,链表的实现非常简单,每个节点Node都有一个值val和指向下个节点的链接next。
链表两个著名的应用是栈Stack和队列Queue。
栈:
队列:
这里的树通常是指二叉树,每个节点都包含一个左孩子节点和右孩子节点,像下面这样:
下面是与树相关的一些概念:
译者注:完美二叉树也隐约称为完全二叉树。完美二叉树的一个例子是一个人在给定深度的祖先图,因为每个人都一定有两个生父母。完全二叉树可以看成是可以有若干额外向左靠的叶子节点的完美二叉树。疑问:完美二叉树和满二叉树的区别?(参考:http://xlinux.nist.gov/dads/HTML/perfectBinaryTree.html)
图相关的问题主要集中在深度优先搜索(depth first search)和广度优先搜索(breath first search)。
下面是一个简单的图广度优先搜索的实现。
1) 定义GraphNode
2) 定义一个队列Queue
3) 用队列Queue实现广度优先搜索
Output:
value: 2 value: 3 value: 5 Find value: 5
value: 4
下面是不同排序算法的时间复杂度,你可以去wiki看一下这些算法的基本思想。
另外,这里有一些实现/演示:: Counting sort、Mergesort、 Quicksort、 InsertionSort。
对程序员来说,递归应该是一个与生俱来的思想(a built-in thought),可以通过一个简单的例子来说明。
问题: 有n步台阶,一次只能上1步或2步,共有多少种走法。
步骤1:找到走完前n步台阶和前n-1步台阶之间的关系。
为了走完n步台阶,只有两种方法:从n-1步台阶爬1步走到或从n-2步台阶处爬2步走到。如果f(n)是爬到第n步台阶的方法数,那么f(n) = f(n-1) + f(n-2)。
步骤2: 确保开始条件是正确的。
f(0) = 0; f(1) = 1;
递归方法的时间复杂度是n的指数级,因为有很多冗余的计算,如下:
f(5) f(4) + f(3) f(3) + f(2) + f(2) + f(1) f(2) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1) f(1) + f(0) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)
直接的想法是将递归转换为迭代:
对这个例子而言,迭代花费的时间更少,你可能也想看看Recursion vs Iteration。
动态规划是解决下面这些性质类问题的技术:
爬台阶问题完全符合上面的四条性质,因此可以用动态规划法来解决。
位操作符:
获得给定数字n的第i位:(i从0计数并从右边开始)
例如,获得数字10的第2位:
i=1, n=10 1<<1= 10 1010&10=10 10 is not 0, so return true;
解决概率相关的问题通常需要很好的规划了解问题(formatting the problem),这里刚好有一个这类问题的简单例子:
一个房间里有50个人,那么至少有两个人生日相同的概率是多少?(忽略闰年的事实,也就是一年365天)
计算某些事情的概率很多时候都可以转换成先计算其相对面。在这个例子里,我们可以计算所有人生日都互不相同的概率,也就是:365/365 * 364/365 * 363/365 * … * (365-49)/365,这样至少两个人生日相同的概率就是1 – 这个值。
calculateProbability(50) = 0.97
组合和排列的区别在于次序是否关键。