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

相关文章

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

Spring Boot 整合 SSE的高级实践(Server-Sent Events)

《SpringBoot整合SSE的高级实践(Server-SentEvents)》SSE(Server-SentEvents)是一种基于HTTP协议的单向通信机制,允许服务器向浏览器持续发送实... 目录1、简述2、Spring Boot 中的SSE实现2.1 添加依赖2.2 实现后端接口2.3 配置超时时

Spring Boot读取配置文件的五种方式小结

《SpringBoot读取配置文件的五种方式小结》SpringBoot提供了灵活多样的方式来读取配置文件,这篇文章为大家介绍了5种常见的读取方式,文中的示例代码简洁易懂,大家可以根据自己的需要进... 目录1. 配置文件位置与加载顺序2. 读取配置文件的方式汇总方式一:使用 @Value 注解读取配置方式二

一文详解Java异常处理你都了解哪些知识

《一文详解Java异常处理你都了解哪些知识》:本文主要介绍Java异常处理的相关资料,包括异常的分类、捕获和处理异常的语法、常见的异常类型以及自定义异常的实现,文中通过代码介绍的非常详细,需要的朋... 目录前言一、什么是异常二、异常的分类2.1 受检异常2.2 非受检异常三、异常处理的语法3.1 try-

Java中的@SneakyThrows注解用法详解

《Java中的@SneakyThrows注解用法详解》:本文主要介绍Java中的@SneakyThrows注解用法的相关资料,Lombok的@SneakyThrows注解简化了Java方法中的异常... 目录前言一、@SneakyThrows 简介1.1 什么是 Lombok?二、@SneakyThrows

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

Spring 请求之传递 JSON 数据的操作方法

《Spring请求之传递JSON数据的操作方法》JSON就是一种数据格式,有自己的格式和语法,使用文本表示一个对象或数组的信息,因此JSON本质是字符串,主要负责在不同的语言中数据传递和交换,这... 目录jsON 概念JSON 语法JSON 的语法JSON 的两种结构JSON 字符串和 Java 对象互转

SQL中redo log 刷⼊磁盘的常见方法

《SQL中redolog刷⼊磁盘的常见方法》本文主要介绍了SQL中redolog刷⼊磁盘的常见方法,将redolog刷入磁盘的方法确保了数据的持久性和一致性,下面就来具体介绍一下,感兴趣的可以了解... 目录Redo Log 刷入磁盘的方法Redo Log 刷入磁盘的过程代码示例(伪代码)在数据库系统中,r

JAVA保证HashMap线程安全的几种方式

《JAVA保证HashMap线程安全的几种方式》HashMap是线程不安全的,这意味着如果多个线程并发地访问和修改同一个HashMap实例,可能会导致数据不一致和其他线程安全问题,本文主要介绍了JAV... 目录1. 使用 Collections.synchronizedMap2. 使用 Concurren

Java Response返回值的最佳处理方案

《JavaResponse返回值的最佳处理方案》在开发Web应用程序时,我们经常需要通过HTTP请求从服务器获取响应数据,这些数据可以是JSON、XML、甚至是文件,本篇文章将详细解析Java中处理... 目录摘要概述核心问题:关键技术点:源码解析示例 1:使用HttpURLConnection获取Resp