文档章节

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

拉偶有所依
 拉偶有所依
发布于 2015/06/17 10:01
字数 2068
阅读 198
收藏 22
点赞 0
评论 0

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

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

1. 字符串

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

toCharArray() 
// 获得字符串对应的char数组
Arrays.sort()  
// 数组排序
Arrays.toString(char[] a)
// 数组转成字符串
charAt(int x)
// 获得某个索引处的字符
length()
// 字符串长度
length
// 数组大小

2. 链表

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

class Node {
   int val;
   Node next;

   Node(int x) {
       val = x;
       next = null;
   }
}

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

栈:

class Stack{
   Node top;

   public Node peek(){
       if(top != null){
           return top;
       }

       return null;
   }

   public Node pop(){
       if(top == null){
           return null;
       }else{
           Node temp = new Node(top.val);
           top = top.next;
           return temp;    
       }
   }

   public void push(Node n){
       if(n != null){
           n.next = top;
           top = n;
       }
   }
}

队列:

class Queue{
   Node first, last;

   public void enqueue(Node n){
       if(first == null){
           first = n;
           last = first;
       }else{
           last.next = n;
           last = n;
       }
   }

   public Node dequeue(){
       if(first == null){
           return null;
       }else{
           Node temp = new Node(first.val);
           first = first.next;
           if(last == temp) last = first;
           return temp;
       }    
   }
}

3. 树

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

class TreeNode{
   int value;
   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

class GraphNode{ 
   int val;
   GraphNode next;
   GraphNode[] neighbors;
   boolean visited;

   GraphNode(int x) {
       val = x;
   }

   GraphNode(int x, GraphNode[] n){
       val = x;
       neighbors = n;
   }

   public String toString(){
       return "value: "+ this.val;
   }
}

2) 定义一个队列Queue

class Queue{
   GraphNode first, last;

   public void enqueue(GraphNode n){
       if(first == null){
           first = n;
           last = first;
       }else{
           last.next = n;
           last = n;
       }
   }

   public GraphNode dequeue(){
       if(first == null){
           return null;
       }else{
           GraphNode temp = new GraphNode(first.val, first.neighbors);
           first = first.next;
           return temp;
       }  
   }
}

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

public class GraphTest {

   public static void main(String[] args) {
       GraphNode n1 = new GraphNode(1);
       GraphNode n2 = new GraphNode(2);
       GraphNode n3 = new GraphNode(3);
       GraphNode n4 = new GraphNode(4);
       GraphNode n5 = new GraphNode(5);

       n1.neighbors = new GraphNode[]{n2,n3,n5};
       n2.neighbors = new GraphNode[]{n1,n4};
       n3.neighbors = new GraphNode[]{n1,n4,n5};
       n4.neighbors = new GraphNode[]{n2,n3,n5};
       n5.neighbors = new GraphNode[]{n1,n3,n4};

       breathFirstSearch(n1, 5);
   }

   public static void breathFirstSearch(GraphNode root, int x){
       if(root.val == x)
           System.out.println("find in root");

       Queue queue = new Queue();
       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:

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 sortMergesort、 Quicksort、 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;

public static int f(int n){
   if(n <= 2) return n;
   int x = f(n-1) + f(n-2);
   return x;
}

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

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

public static int f(int n) {

   if (n <= 2){
       return n;
   }

   int first = 1, second = 2;
   int third = 0;

   for (int i = 3; i <= n; i++) {
       third = first + second;
       first = second;
       second = third;
   }

   return third;
}

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

7. 动态规划

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

  1. 一个问题可以通过更小子问题的解决方法来解决(译者注:即问题的最优解包含了其子问题的最优解,也就是最优子结构性质)。

  2. 有些子问题的解可能需要计算多次(译者注:也就是子问题重叠性质)。

  3. 子问题的解存储在一张表格里,这样每个子问题只用计算一次。

  4. 需要额外的空间以节省时间。

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

public static int[] A = new int[100];

public static int f3(int n) {
   if (n <= 2)
       A[n]= n;

   if(A[n] > 0)
       return A[n];
   else
       A[n] = f3(n-1) + f3(n-2);
//store results so only calculate once!
   return A[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计数并从右边开始)

public static boolean getBit(int num, int i){
   int result = num & (1<<i);

   if(result == 0){
       return false;
   }else{
       return true;
   }

例如,获得数字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 – 这个值。

public static double caculateProbability(int n){
   double x = 1;

   for(int i=0; i<n; i++){
       x *=  (365.0-i)/365.0;
   }

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

calculateProbability(50) = 0.97

10. 排列组合

组合和排列的区别在于次序是否关键。另外在安全方面,你是否有考虑过,如若没有,现在还来得及,编程源码的安全性问题,想要解决,完全可以借助专业的平台资源去实现,以便流出更多的时间去专心搞技术!


© 著作权归作者所有

共有 人打赏支持
拉偶有所依
粉丝 26
博文 81
码字总数 138944
作品 0
长沙
2017派卧底去阿里、京东、美团、滴滴带回来的面试题及答案

最近有很多朋友去目前主流的大型互联网公司面试(阿里巴巴、京东、美团、滴滴),面试回来之后会发给我一些面试题。有些朋友轻松过关,拿到offer,但是有一些是来询问我答案的。 我特意整理了...

youanyyou
2017/11/08
0
0
Android-Java面试

2016 年末,腾讯,百度,华为,搜狗和滴滴面试题汇总 2016 年未,腾讯,百度,华为,搜狗和滴滴面试题汇总 各大公司 Java 后端开发面试题总结 各大公司 Java 后端开发面试题总结 刚出炉的一线...

掘金官方
01/02
0
0
机器学习 人工智能 博文链接汇总

115 [入门问题] [TensorFlow] [深度学习] [好玩儿的算法应用实例] [聊天机器人] [神经网络] [机器学习] [机器学习算法应用实例] [自然语言处理] [数据科学] [Python] [Java] [机器学习--初...

aliceyangxi1987
2017/05/13
0
0
年末干货!Java技术栈2017年度精选干货总结

Java技术栈2017年总结 2017年即将收尾了 这一年,满满的都是干货 这一年,我们的更新不曾停歇 这一年,你装逼内功应已有所成 我是小猿,下面是本年度的分享知识图谱 看完是不是有点蒙逼了?没...

架构之路
2017/12/24
0
0
想去Google做AI?先看完这套面试指南(附面试题)

 作者 | 阿司匹林 出品 | 人工智能头条(公众号ID:AI_Thinker) 凭借强大的技术实力和良好的工作氛围,Google 对求职者一直有着强大吸引力。 虽然 Google 在几年前就已经退出了中国大陆...

dqcfkyqdxym3f8rb0
04/18
0
0
Java7任务并行执行神器:Fork&Join框架

Fork/Join是什么? Fork/Join框架是Java7提供的并行执行任务框架,思想是将大任务分解成小任务,然后小任务又可以继续分解,然后每个小任务分别计算出结果再合并起来,最后将汇总的结果作为大...

架构之路
2017/12/27
0
0
MoreWindows博客目录(微软最有价值专家,原创技术文章152篇)

为了方便大家查找和学习,现将本人博客中所有博客文章列出目录。 一. 白话经典算法 目前有17篇,分为七大排序和经典面试题讲解两大类 1. 《白话经典算法系列之一 冒泡排序的三种实现》 2. 《...

morewindows
2013/12/24
0
0
Linux运维基础原理汇总

01. 前言介绍 初始运维的小伙伴,有些技术概念原理还是需要掌握的。有些原理概念一旦理解透彻,首先, 对运维技术工作大有帮助;其次,在遇到一些技术交流会上,也可以装一装,不会显得没话说...

aiweiwei24
2017/07/04
0
0
2018年互联网技术岗(数据分析)暑期实习面试经验

此经验帖适合想找互联网相关工作的人,如数据分析、算法工程师、数据挖掘工程师等。或者是想进入BAT等互联网公司的人,我会介绍他们暑期实习招聘流程及笔面试经验等,暑期实习往往是有转正机...

你的社交帐号昵
05/22
0
0
微软面试、经典算法、编程艺术、红黑树4大系列总结

无私分享,造福天下 以下是本blog内的微软面试100题系列,经典算法研究系列,程序员编程艺术系列,红黑树系列4大经典原创系列作品与一些重要文章的集锦。 一、微软面试100题系列 横空出世,席...

长平狐
2013/01/06
262
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

32.filter表案例 nat表应用 (iptables)

10.15 iptables filter表案例 10.16/10.17/10.18 iptables nat表应用 10.15 iptables filter表案例: ~1. 写一个具体的iptables小案例,需求是把80端口、22端口、21 端口放行。但是,22端口我...

王鑫linux
今天
0
0
shell中的函数&shell中的数组&告警系统需求分析

20.16/20.17 shell中的函数 20.18 shell中的数组 20.19 告警系统需求分析

影夜Linux
今天
0
0
Linux网络基础、Linux防火墙

Linux网络基础 ip addr 命令 :查看网口信息 ifconfig命令:查看网口信息,要比ip addr更明了一些 centos 7默认没安装ifconfig命令,可以使用yum install -y net-tools命令来安装。 ifconfig...

李超小牛子
今天
1
0
[机器学习]回归--Decision Tree Regression

CART决策树又称分类回归树,当数据集的因变量为连续性数值时,该树算法就是一个回归树,可以用叶节点观察的均值作为预测值;当数据集的因变量为离散型数值时,该树算法就是一个分类树,可以很...

wangxuwei
昨天
1
0
Redis做分布式无锁CAS的问题

因为Redis本身是单线程的,具备原子性,所以可以用来做分布式无锁的操作,但会有一点小问题。 public interface OrderService { public String getOrderNo();} public class OrderRe...

算法之名
昨天
9
0
143. Reorder List - LeetCode

Question 143. Reorder List Solution 题目大意:给一个链表,将这个列表分成前后两部分,后半部分反转,再将这两分链表的节点交替连接成一个新的链表 思路 :先将链表分成前后两部分,将后部...

yysue
昨天
1
0
数据结构与算法1

第一个代码,描述一个被称为BankAccount的类,该类模拟了银行中的账户操作。程序建立了一个开户金额,显示金额,存款,取款并显示余额。 主要的知识点联系为类的含义,构造函数,公有和私有。...

沉迷于编程的小菜菜
昨天
1
0
从为什么别的队伍总比你的快说起

在机场候检排队的时候,大多数情况下,别的队伍都要比自己所在的队伍快,并常常懊悔当初怎么没去那个队。 其实,最快的队伍只能有一个,而排队之前并不知道那个队快。所以,如果有六个队伍你...

我是菜鸟我骄傲
昨天
1
0
分布式事务常见的解决方案

随着互联网的发展,越来越多的多服务相互之间的调用,这时候就产生了一个问题,在单项目情况下很容易实现的事务控制(通过数据库的acid控制),变得不那么容易。 这时候就产生了多种方案: ...

小海bug
昨天
3
0
python从零学——scrapy初体验

python从零学——scrapy初体验 近日因为一些事情,需要从网上爬取一些东西,故而想通过使用爬虫来顺便学习下强大的python。现将一些学习中遇到的问题记录下来,以便日后查询 1. 开发环境的准...

咾咔叽
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部