`
zhb8015
  • 浏览: 374210 次
  • 性别: Icon_minigender_1
  • 来自: 北京
博客专栏
Group-logo
Spring Roo杂谈
浏览量:0
社区版块
存档分类
最新评论

代码面试最常用的10大算法(转)

阅读更多
原文地址:
http://www.csdn.net/article/2014-04-10/2819237-Top-10-Algorithms-for-Coding-Interview

 

代码面试最常用的10大算法

 

摘要:面试也是一门学问,在面试之前做好充分的准备则是成功的必须条件,而程序员在代码面试时,常会遇到编写算法的相关问题,比如排序、二叉树遍历等等。

在程序员的职业生涯中,算法亦算是一门基础课程,尤其是在面试的时候,很多公司都会让程序员编写一些算法实例,例如快速排序、二叉树查找等等。

本文总结了程序员在代码面试中最常遇到的10大算法类型,想要真正了解这些算法的原理,还需程序员们花些功夫。

1.String/Array/Matrix

在Java中,String是一个包含char数组和其它字段、方法的类。如果没有IDE自动完成代码,下面这个方法大家应该记住: 

 

toCharArray() //get char array of a String
Arrays.sort()  //sort an array
Arrays.toString(char[] a) //convert to string
charAt(int x) //get a char at the specific index
length() //string length
length //array size 
substring(int beginIndex) 
substring(int beginIndex, int endIndex)
Integer.valueOf()//string to integer
String.valueOf()/integer to string
String/arrays很容易理解,但与它们有关的问题常常需要高级的算法去解决,例如动态编程、递归等。

下面列出一些需要高级算法才能解决的经典问题:

 

 

 

 

 

 

2.链表

在Java中实现链表是非常简单的,每个节点都有一个值,然后把它链接到下一个节点。 

 

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

比较流行的两个链表例子就是栈和队列。

栈(Stack) 

 

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;
		}
	}
}
队列(Queue)

 

 

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;
			return temp;
		}	
	}
}

值得一提的是,Java标准库中已经包含一个叫做Stack的类,链表也可以作为一个队列使用(add()和remove())。(链表实现队列接口)如果你在面试过程中,需要用到栈或队列解决问题时,你可以直接使用它们。

在实际中,需要用到链表的算法有:

 

 

 

 

 

 

 

3.树&堆

这里的树通常是指二叉树。

 

class TreeNode{
	int value;
	TreeNode left;
	TreeNode right;
} 
下面是一些与二叉树有关的概念:

 

 

  • 二叉树搜索:对于所有节点,顺序是:left children <= current node <= right children;
  • 平衡vs.非平衡:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树;
  • 满二叉树:除最后一层无任何子节点外,每一层上的所有结点都有两个子结点;
  • 完美二叉树(Perfect Binary Tree):一个满二叉树,所有叶子都在同一个深度或同一级,并且每个父节点都有两个子节点;
  • 完全二叉树:若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

 

堆(Heap)是一个基于树的数据结构,也可以称为优先队列( PriorityQueue),在队列中,调度程序反复提取队列中第一个作业并运行,因而实际情况中某些时间较短的任务将等待很长时间才能结束,或者某些不短小,但具有重要性的作业,同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。

下面列出一些基于二叉树和堆的算法:

 

 

4.Graph 

与Graph相关的问题主要集中在深度优先搜索和宽度优先搜索。深度优先搜索非常简单,你可以从根节点开始循环整个邻居节点。下面是一个非常简单的宽度优先搜索例子,核心是用队列去存储节点。

 

第一步,定义一个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; 
	}
}

第二步,定义一个队列

 

 

 

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;
		}	
	}
}
第三步,使用队列进行宽度优先搜索

 

 

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);
				}
			}
		}
	}
}
输出结果:

 

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

实际中,基于Graph需要经常用到的算法:

 

 

5.排序

不同排序算法的时间复杂度,大家可以到wiki上查看它们的基本思想。

 

BinSort、Radix Sort和CountSort使用了不同的假设,所有,它们不是一般的排序方法。 

下面是这些算法的具体实例,另外,你还可以阅读: Java开发者在实际操作中是如何排序的

 

 

6.递归和迭代

下面通过一个例子来说明什么是递归。

问题:

这里有n个台阶,每次能爬1或2节,请问有多少种爬法?

步骤1:查找n和n-1之间的关系

为了获得n,这里有两种方法:一个是从第一节台阶到n-1或者从2到n-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(2) + f(2) + 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;
}

 

在这个例子中,迭代花费的时间要少些。关于迭代和递归,你可以去 这里看看。

7.动态规划

动态规划主要用来解决如下技术问题:

 

  • 通过较小的子例来解决一个实例;
  • 对于一个较小的实例,可能需要许多个解决方案;
  • 把较小实例的解决方案存储在一个表中,一旦遇上,就很容易解决;
  • 附加空间用来节省时间。

 

上面所列的爬台阶问题完全符合这四个属性,因此,可以使用动态规划来解决: 

 

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.位操作

位操作符:

从一个给定的数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的第二位:

 

 

 

i=1, n=10
1<<1= 10
1010&10=10
10 is not 0, so return true;
典型的位算法:

 

 

 

9.概率

通常要解决概率相关问题,都需要很好地格式化问题,下面提供一个简单的例子: 

有50个人在一个房间,那么有两个人是同一天生日的可能性有多大?(忽略闰年,即一年有365天)

算法:

 

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.组合和排列

组合和排列的主要差别在于顺序是否重要。

例1:

1、2、3、4、5这5个数字,输出不同的顺序,其中4不可以排在第三位,3和5不能相邻,请问有多少种组合?

例2:

有5个香蕉、4个梨、3个苹果,假设每种水果都是一样的,请问有多少种不同的组合?

基于它们的一些常见算法

 

 

 

来自:ProgramCreek

分享到:
评论

相关推荐

    代码面试最常用的10大算法完整版

    代码面试最常用的10大算法的中文完整版(部分中文,部分英文)及英文原版。

    代码面试最常用的10大算法【英文版】

    转自原作者的网站:http://www.programcreek.com/2012/11/top-10-algorithms-for-coding-interview/ ...本文总结了程序员在代码面试中最常遇到的10大算法类型,想要真正了解这些算法的原理,还需程序员们花些功夫。

    代码面试最常用的10大算法

    在程序员的职业生涯中,算法亦算是一门基础课程,尤其是在面试的时候,很多公司都会让 程序员编写一些算法... 本文总结了程序员在代码面试中最常遇到的10个算法,想要真正了解这些算法的原理,还 需程序员们花些功夫。

    Java常用算法手册源代码

    3.1 常用算法思想概述 3.2 穷举算法思想 3.2.1 穷举算法基本思想 3.2.2 穷举算法实例 3.3 递推算法思想 3.3.1 递推算法基本思想 3.3.2 递推算法实例 3.4 递归算法思想 …… 第2篇 算法应用篇 第4章 排序算法 第5章 ...

    Java常用算法手册

    《Java常用算法手册》分三篇,共13章,分别介绍了算法基础、算法应用和算法面试题。首先介绍了算法概述,然后重点分析了数据结构和基本算法思想;接着,详细讲解了算法在排序、查找、数学计算、数论、历史趣题、游戏...

    C#常见面试算法代码

    常见c#面试算法代码,保证正确无误,欢迎下载!!!!

    常用算法Java代码

    基础数据结构,算法,大公司笔试真题,牛客算法题,lintcode,九章算法,《剑指Offer》,左程云《程序员代码面试指南》

    Java常用算法手册.zip

    本书旨在帮助Java语言初级程序员深入了解ava算法思想,提升其语言代码编程能力,还可以作为大中专院校学生学习数据结构和算法的参考书,也可为教师授课提供素材,同时还可以作为具有一定编程经验的程序员的参考用书。

    《剑指Offer》,《程序员代码面试指南》,Leetcode等算法题目集合

    《剑指Offer》,《程序员代码面试指南》,Leetcode等算法题目集合。基于.net core的控制台程序,C#实现,包含每道题目的完整描述,多种解法AC代码,以及解题思路,所有题目均可直接运行以查看输出结果。常用算法汇总...

    《Python数据结构与算法》教程及代码

    而数组是我们最常用的一种数据结构,支持根据下标快速访问。很多算法需要特定的数据结构来实现,所以经常把它们放到一块讲。 实际上,在真正的项目开发中,大部分时间都是 从数据库取数据 -&gt; 数据操作和结构化 -&gt; ...

    C语言常用算法源代码

    关于C语言的一些常用算法,许多公司面试时考过的。非常用用,也是学习C语言不可多得的资料。

    算法:《剑指提供》,《程序员代码面试指南》,Leetcode等算法衔接集合。基于.net core的控制台程序,C#实现,包含每道译文的完整描述,多种解法AC代码,以及解主题算法,所有回归正确直接运行以查看输出结果。常用算法汇总中每个算法同样有测试用例,可运行

    算法《剑指提供》,《程序员代码面试指南》,Leetcode等算法译集以及常用算法实现汇总本仓库是基于.net core的控制台程序,C#实现,包含每道译文的完整描述,多种解法AC代码,以及解题思路,所有转换直接运行以查看...

    妙趣横生的算法(C语言实现).zip

    全书分为2个部分共10章,内容涵盖了编程必备的基础知识(如数据结构、常用算法等),编程实例介绍,常见算法和数据结构面试题等。《妙趣横生的算法(C语言实现)》最大的特色在于实例丰富,题材新颖有趣,实用性强,...

    机器学习常用算法汇总

    本文为个人面试机器学习方面工作过程中,对机器学习中的常用算法做了一些汇总,个人认为非常全面,也希望对其他人有些帮助

    机器学习面试算法总结 手写

    在自己学习过程中,详细整理了数据挖掘领域常用的算法模型的数学推导,及其关键代码,可供面试前参阅

    必备的常用面试题汇总

    常见算法笔试或面试题 笔试面试专栏:字符串 数组 vc题集 十道海量数据处理面试题与十个方法大总结 google全程面试题 其他一些公司的面试题

    妙趣横生的算法

    全书分为2个部分共10章,内容涵盖了编程必备的基础知识(如数据结构、常用算法等),编程实例介绍,常见算法和数据结构面试题等。《妙趣横生的算法(C语言实现)》最大的特色在于实例丰富,题材新颖有趣,实用性强,...

    面试求职必会算法——树和堆

    1. 面试求职中常用的算法——树和堆; 2. 有关树和堆的ppt讲解以及相关数据代码

    C/C++常用算法手册(带详细目录)

    算法是一切程序设计的基础和灵魂,更是一位程序员编程水平高低的集中体现。...阐述到位:算法思想、算法实现和经典面试题合理搭配,相辅相成。实例完善:分析精准,注释精确,保证每段代码皆可通过编译执行。

Global site tag (gtag.js) - Google Analytics