编程面试的10大算法概念汇总(http://blog.jobbole.com/52144/)

以下是在编程面试中排名前10的算法相关的概念,我会通过一些简单的例子来阐述这些概念。由于完全掌握这些概念需要更多的努力,因此这份列表只是作为一个介绍。本文将从Java的角度看问题,包含下面的这些概念:

1. 字符串
2. 链表
3. 树
4. 图
5. 排序
6. 递归 vs. 迭代
7. 动态规划
8. 位操作
9. 概率问题
10. 排列组合

1. 字符串

如果IDE没有代码自动补全功能,所以你应该记住下面的这些方法。


1

2

3

4

5

6

toCharArray()// 获得字符串对应的char数组

Arrays.sort() // 数组排序

Arrays.toString(char[] a)// 数组转成字符串

charAt(intx)
// 获得某个索引处的字符

length()
// 字符串长度

length
// 数组大小

2. 链表

在Java中,链表的实现非常简单,每个节点Node都有一个值val和指向下个节点的链接next。


1

2

3

4

5

6

7

8

9

classNode {

    intval;

    Node next;

  

    Node(intx)
{

        val = x;

        next =null;

    }

}

链表两个著名的应用是栈Stack和队列Queue。

栈:


1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

classStack{

    Node top; 

  

    publicNode peek(){

        if(top !=null){

            returntop;

        }

  

        returnnull;

    }

  

    publicNode pop(){

        if(top ==null){

            returnnull;

        }else{

            Node temp =newNode(top.val);

            top = top.next;

            returntemp;    

        }

    }

  

    publicvoidpush(Node
n){

        if(n !=null){

            n.next = top;

            top = n;

        }

    }

}

队列:


1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

classQueue{

    Node first, last;

  

    publicvoidenqueue(Node
n){

        if(first ==null){

            first = n;

            last = first;

        }else{

            last.next = n;

            last = n;

        }

    }

  

    publicNode dequeue(){

        if(first ==null){

            returnnull;

        }else{

            Node temp =newNode(first.val);

            first = first.next;

            returntemp;

        }   

    }

}

3. 树

这里的树通常是指二叉树,每个节点都包含一个左孩子节点和右孩子节点,像下面这样:


1

2

3

4

5

classTreeNode{

    intvalue;

    TreeNode left;

    TreeNode right;

}

下面是与树相关的一些概念:

  1. 平衡 vs. 非平衡:平衡二叉树中,每个节点的左右子树的深度相差至多为1(1或0)。
  2. 满二叉树(Full Binary Tree):除叶子节点以为的每个节点都有两个孩子。
  3. 完美二叉树(Perfect Binary Tree):是具有下列性质的满二叉树:所有的叶子节点都有相同的深度或处在同一层次,且每个父节点都必须有两个孩子。
  4. 完全二叉树(Complete Binary Tree):二叉树中,可能除了最后一个,每一层都被完全填满,且所有节点都必须尽可能想左靠。

译者注:完美二叉树也隐约称为完全二叉树。完美二叉树的一个例子是一个人在给定深度的祖先图,因为每个人都一定有两个生父母。完全二叉树可以看成是可以有若干额外向左靠的叶子节点的完美二叉树。疑问:完美二叉树和满二叉树的区别?(参考:http://xlinux.nist.gov/dads/HTML/perfectBinaryTree.html

4. 图

图相关的问题主要集中在深度优先搜索(depth first search)和广度优先搜索(breath first search)。

下面是一个简单的图广度优先搜索的实现。

1) 定义GraphNode


1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

classGraphNode{ 

    intval;

    GraphNode next;

    GraphNode[] neighbors;

    boolean visited;

  

    GraphNode(intx)
{

        val = x;

    }

  

    GraphNode(intx,
GraphNode[] n){

        val = x;

        neighbors = n;

    }

  

    publicStringtoString(){

        return"value:
"
+this.val; 

    }

}

2) 定义一个队列Queue


1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

classQueue{

    GraphNode first, last;

  

    publicvoidenqueue(GraphNode
n){

        if(first ==null){

            first = n;

            last = first;

        }else{

            last.next = n;

            last = n;

        }

    }

  

    publicGraphNode dequeue(){

        if(first ==null){

            returnnull;

        }else{

            GraphNode temp =newGraphNode(first.val,
first.neighbors);

            first = first.next;

            returntemp;

        }   

    }

}

3) 用队列Queue实现广度优先搜索


1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

publicclassGraphTest
{

  

    publicstaticvoidmain(String[]
args) {

        GraphNode n1 =newGraphNode(1); 

        GraphNode n2 =newGraphNode(2); 

        GraphNode n3 =newGraphNode(3); 

        GraphNode n4 =newGraphNode(4); 

        GraphNode n5 =newGraphNode(5); 

  

        n1.neighbors =newGraphNode[]{n2,n3,n5};

        n2.neighbors =newGraphNode[]{n1,n4};

        n3.neighbors =newGraphNode[]{n1,n4,n5};

        n4.neighbors =newGraphNode[]{n2,n3,n5};

        n5.neighbors =newGraphNode[]{n1,n3,n4};

  

        breathFirstSearch(n1,5);

    }

  

    publicstaticvoidbreathFirstSearch(GraphNode
root,
intx){

        if(root.val == x)

            System.out.println("find in root");

  

        Queue queue =newQueue();

        root.visited =true;

        queue.enqueue(root);

  

        while(queue.first !=null){

            GraphNode c = (GraphNode) queue.dequeue();

            for(GraphNode n: c.neighbors){

  

                if(!n.visited){

                    System.out.print(n +" ");

                    n.visited =true;

                    if(n.val == x)

                        System.out.println("Find "+n);

                    queue.enqueue(n);

                }

            }

        }

    }

}

Output:


1

2

value: 2 value: 3 value: 5 Find value: 5

value: 4


5. 排序

下面是不同排序算法的时间复杂度,你可以去wiki看一下这些算法的基本思想。

Algorithm Average Time Worst Time Space
冒泡排序 n^2 n^2 1
选择排序 n^2 n^2 1
Counting Sort n+k n+k n+k
Insertion sort n^2 n^2  
Quick sort n log(n) n^2  
Merge sort n log(n) n log(n) depends

另外,这里有一些实现/演示:: Counting sortMergesortQuicksort
InsertionSort

6. 递归 vs. 迭代

对程序员来说,递归应该是一个与生俱来的思想(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;


1

2

3

4

5

publicstaticintf(intn){

    if(n <=2)returnn;

    intx = f(n-1)
+ f(n-
2);

    returnx;

}

递归方法的时间复杂度是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)

直接的想法是将递归转换为迭代:


1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

publicstaticintf(intn)
{

  

    if(n <=
2){

        returnn;

    }

  

    intfirst =
1, second =2;

    intthird =
0;

  

    for(inti
=
3; i <= n; i++) {

        third = first + second;

        first = second;

        second = third;

    }

  

    returnthird;

}

对这个例子而言,迭代花费的时间更少,你可能也想看看Recursion vs Iteration

 

7. 动态规划

动态规划是解决下面这些性质类问题的技术:

  1. 一个问题可以通过更小子问题的解决方法来解决(译者注:即问题的最优解包含了其子问题的最优解,也就是最优子结构性质)。
  2. 有些子问题的解可能需要计算多次(译者注:也就是子问题重叠性质)。
  3. 子问题的解存储在一张表格里,这样每个子问题只用计算一次。
  4. 需要额外的空间以节省时间。

爬台阶问题完全符合上面的四条性质,因此可以用动态规划法来解决。


1

2

3

4

5

6

7

8

9

10

11

12

publicstaticint[]
A =
newint[100];

  

publicstaticintf3(intn)
{

    if(n <=
2)

        A[n]= n;

  

    if(A[n] >0)

        returnA[n];

    else

        A[n] = f3(n-1) +
f3(n-
2);//store results so only calculate once!

    returnA[n];

}

8. 位操作

位操作符:

OR (|) AND (&) XOR (^) Left Shift (<<) Right Shift (>>) Not (~)
1|0=1 1&0=0 1^0=1 0010<<2=1000 1100>>2=0011 ~1=0

获得给定数字n的第i位:(i从0计数并从右边开始)


1

2

3

4

5

6

7

8

publicstaticboolean
getBit(
intnum,
inti){

    intresult = num & (1<<i);

  

    if(result ==0){

        returnfalse;

    }else{

        returntrue;

    }

例如,获得数字10的第2位:

i=1, n=10
1<<1= 10
1010&10=10
10 is not 0, so return true;

9. 概率问题

解决概率相关的问题通常需要很好的规划了解问题(formatting the problem),这里刚好有一个这类问题的简单例子:

一个房间里有50个人,那么至少有两个人生日相同的概率是多少?(忽略闰年的事实,也就是一年365天)

计算某些事情的概率很多时候都可以转换成先计算其相对面。在这个例子里,我们可以计算所有人生日都互不相同的概率,也就是:365/365 * 364/365 * 363/365 * … * (365-49)/365,这样至少两个人生日相同的概率就是1 – 这个值。


1

2

3

4

5

6

7

8

9

publicstaticdouble
caculateProbability(
intn){

    double x =1

  

    for(inti=0;
i<n; i++){

        x *=  (365.0-i)/365.0;

    }

  

    double pro = Math.round((1-x)
*
100);

    returnpro/100;

calculateProbability(50) = 0.97

10. 排列组合

组合和排列的区别在于次序是否关键。

如果你有任何问题请在下面评论。

参考/推荐资料:
1. Binary tree
2. Introduction to Dynamic Programming
3. UTSA Dynamic Programming slides
4. Birthday paradox
5. Cracking the Coding Interview: 150 Programming Interview Questions and Solutions, Gayle Laakmann McDowell

 

时间: 2013-12-02

编程面试的10大算法概念汇总(http://blog.jobbole.com/52144/)的相关文章

细数二十世纪最伟大的10大算法

导读:作者July总结了一篇关于计算方法的文章<细数二十世纪最伟大的10大算法>,此文只是本人对算法比较感兴趣,所以也做翻译,学习研究下.以下是文章内容: 发明十大算法的其中几位算法大师 一.1946 蒙特卡洛方法 [1946: John von Neumann, Stan Ulam, and Nick Metropolis, all at the Los Alamos Scientific Laboratory, cook up the Metropolis algorithm, also

Java主宰全球的10大算法

在开放性论坛Reddit.com上有篇帖子介绍了算法对我们现在生活的重要性,以及哪些算法对现代文明所做贡献最大.如果对算法有所了解,读这篇文章时你可能会问"作者知道算法为何物吗?",或是"Facebook的'信息流'(News Feed)算是一种算法吗?",如果"信息流"是算法,那就可以把所有事物都归结为一种算法.才疏学浅,结合那篇帖子,接下来我试着解释一下算法是什么,又是哪10个算法正在主导我们的世界. 什么是算法? 简而言之,任何定义明确的计

使用电脑有哪些坏习惯 电脑使用的10大坏习惯汇总

  你是否经常在电脑上多个程序同时运行?边玩游戏边吃零食?电脑长期使用也不清理?习惯性的大力敲击电脑键盘?这些不恰当的操作都会长期损害您的电脑!下面,我们就一起来看看那些使用电脑的坏习惯! 一.多程序同时运行 许多人喜欢玩电脑时,游戏多开,或者边玩游戏,边聊天,看邮件,浏览网页,听音乐等等.这些很容易造成电脑高负荷运行,对电脑硬件造成不可恢复的损伤,甚至直接烧坏我们的电脑. 二.在键盘上吃零食,喝饮料 这个习惯恐怕是很普遍了,我身边很多人都是这样的,特别是入迷者更是把电脑台当成饭桌来使用.我想你

机器学习十大算法都是何方神圣?看完你就懂了

雷锋网(公众号:雷锋网)按:机器学习与人工智能变得越来越热.大数据原本在工业界中就已经炙手可热,而基于大数据的机器学习则更加流行,因为其通过对数据的计算,可以实现数据预测.为公司提供决策依据.跟我们生活息息相关的最常见机器学习算法包括电影推荐算法.图书推荐算法.这些算法都是基于你的电影观看记录或图书购买记录来给你做推荐的. James Le 在 KDnuggets 上发布了一篇文章,介绍了他是如何入门机器学习的.此外,他在其中摸索出十大常用的机器学习算法,并逐一进行介绍.雷锋网编译如下,未经许可

KDnuggets调查|数据科学家最常用的10种算法

最新的KDnuggets调查统计了数据科学家们实际工作中最常使用的算法,在大多数学术和产业界,都有惊人发现哦! 根据Gregory Piatetsky, KDnuggets,最新的调查问题是:在最近的12个月中,你在实际数据科学相关应用中用到了那些模型/算法? 于是就有了以下基于844份答卷的结果. ◆ ◆ ◆ 排名前十的算法和它们在投票者中所占比例 图1:数据科学家最常用的10大算法,所有算法见文末表格   每个受访者平均用到了8.1种算法,这相比于 2011 的相似调查显示的结果有了巨大的增

数据科学家最常用的10种算法

最新的KDnuggets调查统计了数据科学家们实际工作中最常使用的算法,在大多数学术和产业界,都有惊人发现哦! 根据Gregory Piatetsky, KDnuggets,最新的调查问题是:在最近的12个月中,你在实际数据科学相关应用中用到了那些模型/算法? 于是就有了以下基于844份答卷的结果. ◆ ◆ ◆ 排名前十的算法和它们在投票者中所占比例 图1:数据科学家最常用的10大算法,所有算法见文末表格 每个受访者平均用到了8.1种算法,这相比于 2011 的相似调查显示的结果有了巨大的增长.

你必须知道的10大编程格言

我读了Kevin Pang 的一篇可能非常老但非常好的有趣文章:每个程序员都该知道的10大编程格言. Kevin给了我们10条按他的观点的每个程序员必须知道的编程格言. 可以看出,这都是不错的格言,而下面是我自己最喜欢的编程格言. 保持简单直白(Keep It Simple Stupid) 不要自我复制(Don't Repeat Yourself) 能干的人解决问题.智慧的人绕开问题(A clever person solves a problem. A wise person avoids i

白板与编程面试:为什么不在电脑上编程更有帮助

在技术评估中的检查方法 白板编程可以检查出两方面的技能: 从一开始就可以写简洁的代码,以及 知其代码之所以然. 这两大技能对于一个出色的软件开发人员是至关重要的.通过进行白板编程,这两种技能都能被准确地检验出来. 从一开始就写简洁的代码. 不管我们是否喜欢,现代软件工程主要在于知道足够的模式,并在正确的规则中使用正确的模式. 几天甚至几周后的工作的结果,通常只是修改几百行的代码. 表面上看,原来的开发人员在写代码时需要多少协助并不重要.他们可能在写代码之前,在脑子里就已经想好所有细节了.或者也有

编程面试中的十个常见错误

身为程序员,你肯定知道和其他技术工作面试比起来,编程工作的面试流程略有不同. 这篇文章会就你在编程面试中应当避免的10个问题展开讨论. 1.从未在纸上或白板上写过代码 这是求职者最容易犯的大错之一.绝大多数编程面试都会安排在纸上或白板上.而与电脑上大量的编码练习相比,绝大多数求职者极少在纸上或白板上进行编码练习. 用惯了IDE(或是文本编辑器)的求职者会在如何保持纸间良好代码规范这第一步上磕磕碰碰.众所周知,编码规范是编程面试的必要条件.而且,在纸上 写代码的时候,没有编译器帮你指出明显的编译时