java代码面试常见的算法-mark

2024-06-06 11:58

本文主要是介绍java代码面试常见的算法-mark,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

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

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

1.String/Array/Matrix

在Java中,String是一个包含char数组和其它字段、方法的类。如果没有IDE自动完成代码,下面这个方法大家应该记住:
Java code
?
1
2
3
4
5
6
7
8
9
10
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中实现链表是非常简单的,每个节点都有一个值,然后把它链接到下一个节点。
Java code
?
1
2
3
4
5
6
7
8
9
class  Node {
     int  val;
     Node next;
  
     Node( int  x) {
         val = x;
         next =  null ;
     }
}


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

栈(Stack) 

Java code
?
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
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)

Java code
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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.树&堆

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

Java code
?
1
2
3
4
5
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
Java code
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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; 
     }
}


第二步,定义一个队列

Java code
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
         }   
     }
}


第三步,使用队列进行宽度优先搜索

Java code
?
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
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


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; 

Java code
?
1
2
3
4
5
public  static  int  f( int  n){
     if (n <=  2 return  n;
     int  x = f(n- 1 ) + f(n- 2 );
     return  x;
}


递归方法的时间复杂度指数为n,这里会有很多冗余计算。

Java code
?
1
2
3
4
f( 5 )
f( 4 ) + f( 3 )
f( 3 ) + f( 2 ) + f( 2 ) + f( 1 )
f( 2 ) + f( 1 ) + f( 2 ) + f( 2 ) + f( 1 )


该递归可以很简单地转换为迭代。 

Java code
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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.动态规划

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

通过较小的子例来解决一个实例;
对于一个较小的实例,可能需要许多个解决方案;
把较小实例的解决方案存储在一个表中,一旦遇上,就很容易解决;
附加空间用来节省时间。
上面所列的爬台阶问题完全符合这四个属性,因此,可以使用动态规划来解决: 
Java code
?
1
2
3
4
5
6
7
8
9
10
11
12
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开始,然后向右开始)
Java code
?
1
2
3
4
5
6
7
8
9
public  static  boolean  getBit( int  num,  int  i){
     int  result = num & ( 1 <<i);
  
     if (result ==  0 ){
         return  false ;
     } else {
         return  true ;
     }
}


例如,获取10的第二位:
Java code
?
1
2
3
4
i= 1 , n= 10
1 << 1 10
1010 & 10 = 10
10  is not  0 , so  return  true ;


9.概率

通常要解决概率相关问题,都需要很好地格式化问题,下面提供一个简单的例子: 
有50个人在一个房间,那么有两个人是同一天生日的可能性有多大?(忽略闰年,即一年有365天)

算法:
Java code
?
1
2
3
4
5
6
7
8
9
10
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个苹果,假设每种水果都是一样的,请问有多少种不同的组合?

来自:   http://bbs.csdn.net/topics/390768965

这篇关于java代码面试常见的算法-mark的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1036049

相关文章

Java中StopWatch的使用示例详解

《Java中StopWatch的使用示例详解》stopWatch是org.springframework.util包下的一个工具类,使用它可直观的输出代码执行耗时,以及执行时间百分比,这篇文章主要介绍... 目录stopWatch 是org.springframework.util 包下的一个工具类,使用它

Java进行文件格式校验的方案详解

《Java进行文件格式校验的方案详解》这篇文章主要为大家详细介绍了Java中进行文件格式校验的相关方案,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、背景异常现象原因排查用户的无心之过二、解决方案Magandroidic Number判断主流检测库对比Tika的使用区分zip

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

springboot security使用jwt认证方式

《springbootsecurity使用jwt认证方式》:本文主要介绍springbootsecurity使用jwt认证方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录前言代码示例依赖定义mapper定义用户信息的实体beansecurity相关的类提供登录接口测试提供一

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

基于SpringBoot实现文件秒传功能

《基于SpringBoot实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.

Java利用JSONPath操作JSON数据的技术指南

《Java利用JSONPath操作JSON数据的技术指南》JSONPath是一种强大的工具,用于查询和操作JSON数据,类似于SQL的语法,它为处理复杂的JSON数据结构提供了简单且高效... 目录1、简述2、什么是 jsONPath?3、Java 示例3.1 基本查询3.2 过滤查询3.3 递归搜索3.4

Tomcat版本与Java版本的关系及说明

《Tomcat版本与Java版本的关系及说明》:本文主要介绍Tomcat版本与Java版本的关系及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Tomcat版本与Java版本的关系Tomcat历史版本对应的Java版本Tomcat支持哪些版本的pythonJ