各位见面爱好者,我们又加瓦了!哈哈~ 以下是我根据面试经验总结的一些常见的关于java基础的面试题目。做了一下总结,方便以后自己复习。 有需要的同学也可以收藏,后面我遇到新的面试题目会不断更新上去。 我尽量详细点回答,同学们千万不要死记硬背,要理解后用自己语言去总结概括,才能记得牢固。废话不多说,请看题吧~哈哈
JVM是java虚拟机,能够将 class 文件中的字节码指令进行识别并调用操作系统向上的 API 完成动作。 JRE是java运行时环境,它主要包含两个部分,jvm 的标准实现和 Java 的一些基本类库。它相对于 jvm 来说,多出来的是一部分的 Java 类库。换句话说,JRE包含JVM。 JDK是java开发工具包,它集成了 jre 和一些好用的小工具。例如:javac.exe,java.exe,jar.exe 等。JDK包含JRE。 所以总得来说,JDK>JRE>JVM。
有三大特征,继承,封装,多态。
因为java是编译成.class文件运行在JVM上的。针对不同的系统有不同的JVM实现,在不同的JVM实现上会映射到不同系统的 API 调用,从而实现代码的跨平台运行。
静态成员变量、静态代码块、实例成员变量,实例代码块,构造器,实例方法。
共同点: 1.都可以定义抽象方法,子类都要实现定义的抽象方法。 2.都不能被实例化,但是可以定义抽象类和接口类型的引用。 不同点: 1.接口没有构造器,抽象类可以定义构造器。 2.接口定义具体方法只能定义default修饰,抽象类可以直接定义具体方法。 3.接口的子类是实现接口,关键字是implements,抽象类的子类是继承,关键字是extends。 4.接口不能定义成员变量,只能定义常量。抽象类可以定义成员变量。
①修饰成员变量,用static修饰的成员变量就成为静态变量,静态变量只会存在一份,在类被加载时会初始化,且只会加载一次,通过类名访问。一般可以用static和final定义一些String类型,boolean类型,int类型的变量作为常量,可以减少资源的消耗。 ②static修饰方法,该方法就被定义为静态方法,静态方法是不能被方法重写的,通过类名调用。一般用static定义一些工具类的方法。 ③用static修饰代码块,该代码块就被定义为静态代码块,静态代码块在类初始化时被执行,且执行一次。一般用于初始化一些静态的成员变量的值。
JDK1.5前:byte、short、char、int JDK1.5:枚举 JDK1.7:String
特点: 1.枚举的构造器是私有的。 2.枚举不能被继承。 3.枚举是绝对的单例,即使是反序列化也无法创建多个实例。 使用场景: 当变量只能从一堆固定的值中取出一个时,那么就应该使用枚举。比如时间的单位,季度等等。
方法重载,一个类中允许同时存在一个以上的同名方法,主要体现在方法参数的类型和数量不同,方法名相同,与访问修饰符和返回值类型都是无关的。口诀是"一同两不同"。 方法重写一般在继承中,子类重写父类的方法,既然是重写一遍,那么方法名和参数部分一定是相同的。只是实现的功能不同。声明为 final 的方法不能被重写,声明为 static 的方法不能被重写,声明为 private 的方法不能被重写。
1.静态变量使用static修饰,实例变量不需要。 2.静态变量在类被加载时就会分配内存空间,就可以使用。实例变量需要实例对象才会分配内存空间,才可以被引用,是属于实例的。 3.静态变量是存在于静态区(全局区)的,实例变量位于堆内存中。
实例内部类、静态内部类、局部内部类、匿名内部类。
toString()、equals()、hashCode()。
toString()
默认输出对象的内存地址,一般不希望输出内存地址可以重写toString()方法。equals()
方法用于比较对象是否相等,默认比较是内存地址,所以要正确比较两个对象是否值相等,此方法必须被重写。hashCode()
方法用来返回其所在对象的物理地址(哈希码值),常会和equals()
方法同时重写,确保相等的两个对象拥有相等的hashCode。equals()
方法属于Object
对象的,所以比较基础数据类型是不能使用equals()
。必须使用==
。
在默认情况下,equals()
与==
是一样的,都是比较内存地址。所以在业务逻辑中,我们一般会重写equals()
方法。
1.equals()
相等的两个对象他们的hashCode()
肯定相等,也就是用equals()
对比是绝对可靠的。
2.hashCode()
相等的两个对象他们的equals()
不一定相等,也就是hashCode()
不是绝对可靠的。
在使用HashSet
或者HashMap
集合中,比较两个对象是否相等时,会先调用hashCode()
比较,如果hashCode()
相等,则会继续调用equals()
比较,equals()
也相等才会认为是同一个对象。如果hashCode()
返回不相等,则认为是不相等的对象。
所以一般我们会同时重写hashCode()
和equals()
方法。
&&
具有短路的功能,也就是如果&&
左边的条件为fasle
就不再执行后面的条件判断。
&
则会执行完左右两边的条件判断。
final
修饰类,表明这个类不可被其他类继承。
final
修饰成员变量,表示此变量为常量,只能在初始化时被赋值一次,赋值后不能修改。
final
修饰方法。把方法锁定,不能被子类重写,以防止子类对其进行更改。
finalize()
是Object
里定义的,也就是说每一个对象都有这么个方法。这个方法在gc启动,该对象被回收的时候被调用。一个对象的finalize()
方法只会被调用一次。
finally
作为异常处理的一部分,它只能用在try/catch
语句中,并且附带一个语句块。
Cloneable
接口是一个标记接口,实现了此接口,表示可以使用clone()
方法,没有实现此接口使用clone()
会抛出CloneNotSupportedException
异常。
浅克隆是指拷贝对象时仅仅拷贝对象本身(包括对象中的基本变量),而不拷贝对象包含的引用指向的对象。
深克隆不仅拷贝对象本身,而且拷贝对象包含的引用指向的所有对象。
序列化:把对象转换为字节序列的过程称为对象的序列化。 反序列化:把字节序列恢复为对象的过程称为对象的反序列化。
Serializable
接口是一个标记接口,一个类只有实现了Serializable
接口,它的对象才是可序列化的。否则序列化时会报NotSerializableException
异常。如果不显性声明serialVersionUID
,则会默认生成一个。为了serialVersionUID
的确定性,最好是显性声明。
String
被声明为final class
,是由定义final
的字符数组实现的,因为它的不可变性,所以拼接字符串时候会产生很多无用的中间对象,如果频繁的进行这样的操作对性能有所影响。StringBuffer
是由定义了临时数据transient
的字符数组实现的,提供append()
和add()
方法,可以将字符串添加到已有序列的末尾或指定位置,它的本质是一个线程安全的可修改的字符序列,所有修改数据的方法都加上synchronized
。性能相对StringBuilder
会差一点。StringBuilder
和StringBuffer
本质上没什么区别,区别是去掉了保证线程安全的synchronized
,减少了开销,性能有所提高。Java 泛型是 JDK1.5中引入的一个新特性, 泛型提供了编译时类型安全检测机制,该机制允许程序员在编译时检测到非法的类型。
上界用extends
关键字声明,表示参数化的类型可能是所指定的类型,或者是此类型的子类。
下界用super
进行声明,表示参数化的类型可能是所指定的类型,或者是此类型的父类型,直至Object。
Java反射机制是在运行状态中,对于任意一个类,都能够获得这个类的所有属性和方法,对于任意一个对象都能够调用它的任意一个属性和方法。这种在运行时动态的获取信息以及动态调用对象的方法的功能称为Java的反射机制。
Object
类中的getClass()
方法,想要用这种方法必须要明确具体的类并且创建该类的对象。.class
来获取对应的Class
对象。但是还是要明确到类,然后才能调用类中的静态成员。Class.forName()
方法完成,必须要指定类的全限定名,由于前两种方法都是在知道该类的情况下获取该类的字节码对象,因此不会有异常,但是Class.forName()
方法如果写错类的路径会报ClassNotFoundException
的异常。Throwable
类是Java
异常类型的顶层父类,Throwable
包含了Error
和Excetion
。Excetion
分为两种,一种是非运行时异常(又称为检查异常),另一种是运行时异常(RuntimeException)。
Error
是程序无法处理的, 比如OutOfMemoryError
、OutOfMemoryError
等等, 这些异常发生时, JVM
一般会终止线程。RuntimeException
),如 NullPointerException
、IndexOutOfBoundsException
等,是在程序运行的时候可能会发生的,所以程序可以捕捉,也可以不捕捉。这些错误一般是由程序的逻辑错误引起的,程序应该从逻辑角度去尽量避免。RuntimeException
以外的异常,是Exception
及其子类,这些异常从程序的角度来说是必须经过捕捉检查处理的,否则不能通过编译。如IOException
、SQLException
等。常用集合有Map、List、Set。
不是线程安全的。
使用Collections
类的synchronizedMap()
方法包装。
Map<String, Object> map = Collections.synchronizedMap(new HashMap<>());
使用java.util.concurrent
包下的ConcurrentHashMap
类也可以获得线程安全的Map。
ConcurrentHashMap concurrentHashMap = new ConcurrentHashMap();
使用Hashtable
类,也可以获得线程安全的Map
Map<String,Object> hashtable = new Hashtable<>();
Hashtable
继承自Dictionary
类,而HashMap
继承自AbstractMap
类。但二者都实现了Map接口。Hashtable
是线程安全的,HashMap
是线程不安全的。Hashtable
中,key和value都不允许出现null值。HashTable
在不指定容量的情况下的默认容量为11,而HashMap为16,Hashtable
不要求底层数组的容量一定要为2的整数次幂,而HashMap
则要求一定为2的整数次幂。Hashtable
扩容时,将容量变为原来的2倍加1,而HashMap
扩容时,将容量变为原来的2倍。HashMap
是采用链表法解决哈希冲突的。当put()
一个值到Map
时,会通过Key
拿到一个哈希值,通过哈希值获取数组下标,先查询是否存在该hash
值。若不存在,则直接以Entry
的方式存放在数组中。若存在,则再调用equals()
方法对比key
是否相同,若hashcode()
值和key
都相同,则替换value
,若hashcode()
值相同,key
不相同,则形成一个单链表,将hashcode()
值相同,key
不同的元素以Entry
的方式存放在链表中,这样就解决了哈希冲突。默认的数组初始大小是16。负载因子是0.75。 (为什么初始值是2的n次方,为什么负载因子取0.75,这两个问题可以网上找资料看看,这里就不详述了)
HashMap
是懒加载的,当调用put()
方法时,会先初始化Map
的大小,默认数组长度是16,负载因子是0.75,所以阈值是12。当HashMap
元素的个数超过阈值时,就会把数组的大小扩展到原来的2倍,然后重新计算每个元素在数组中的位置。
ArrayList
和LinkedList
。
ArrayList
基于数组+动态扩容实现的,LinkedList
基于双向链表实现。从储存结构上分析,LinkedList
更加占内存,因为每个节点除了存储数据外还要存储指向前节点的引用和指向后节点的引用。ArrayList
是基于数组下标访问,查询效率较高,但是由于数组的长度是固定的,所以当添加的元素到一定的阈值时会扩容数组,消耗性能,增删效率偏低。LinkedList
在查询时,需要从前到后依次遍历,所以查询效率不高,但是在增删时只需要更改节点的引用,开销较少,所以增删效率较高。使用List接口定义的sort()方法。
list.sort(Comparator.comparingInt(User::getAge));
使用Collections
的sort()
方法,排序的对象需要实现Comparable
接口,重写compareTo()
方法。
//实现Comparable接口
public class User implements Comparable<User> {
//重写compareTo方法
@Override
public int compareTo(User user) {
return Integer.compare(this.getAge(), user.getAge());
}
}
使用Collections
的sort()
方法
Collections.sort(list);
//如果不想实现Comparable接口,也可以使用这个方法
Collections.sort(list,Comparator.comparingInt(User::getAge));
使用Stream流操作的sort()
方法,传入一个Comparator
接口。
list.stream().sorted(Comparator.comparingInt(User::getAge)).collect(Collectors.toList());
栈是先进后出,队列是先进先出。
Stack
类是栈在java中的实现,继承Vector
类,底层是基于数组存储数据。
Queue
接口是队列在java中的代表,Queue
接口有几个常用的子类ArrayDeque
、LinkedList
。
IO包括:File
、OutputStream
、InputStream
、Writer
,Reader
。
NIO三大核心:selector
(选择器),channel
(通道),buffer
(缓冲区)
NIO与IO区别在于,IO面向流,NIO面向缓冲区。IO是阻塞,NIO是非阻塞。
使用SimpleDateFormat
类进行String
和Date
之间的转换。
使用Calendar
对象。如下所示:
//创建Calendar对象
Calendar calendar = Calendar.getInstance();
//设置年份,当前年份减去一年
calendar.set(Calendar.YEAR, calendar.get(Calendar.YEAR) - 1);
//以下是打印结果
Date time = calendar.getTime();
SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
System.out.println(sdf.format(time));//2019-06-08 23:43:14 正确
不一定。
参数类型为double
的构造方法的结果有一定的不可预知性,是有可能产生失真的。
BigDecimal bigDecimal = new BigDecimal(0.99);
System.out.println(bigDecimal);//结果如下
//0.9899999999999999911182158029987476766109466552734375
使用参数类型String
构造方法是完全可预知的,不会产生失真。所以在开发中推荐使用参数类型String
构造方法。
Thread
类创建线程类。Runnable
接口创建线程类。Callable
接口创建线程类。使用Callable
和FutureTask
接口,获取返回值。
public static void main(String[] args) throws Exception {
try {
//使用匿名内部类创建Callable
Callable callable = () -> "hello call";
FutureTask futureTask = new FutureTask(callable);
//执行线程
new Thread(futureTask).start();
if (!futureTask.isDone()) {
//获取返回值
System.out.println(futureTask.get());
}
} catch (Exception e) {
e.printStackTrace();
}
}
新建状态、就绪状态、运行状态、阻塞状态、死亡状态
synchronized、wait()、notify()
CountDownLatch
ReentrantLock
结合Condition
LockSupport
实现线程间的阻塞和唤醒以上几种方式的具体实现代码,可以网上找一下资料,这里不演示了。
相同点:
sleep()
方法和wait()
方法都用来改变线程的状态,能够让线程从运行状态,转变为休眠状态。不同点:
sleep()
方法是Thread
类中的静态方法,而wait()
方法是Object
类中的方法。sleep()
方法可以在任何地方调用,而wait()方法只能在同步代码块或同步方法中使用(即使用synchronized
关键字修饰的)。sleep()
方法不会释放对象锁。而wait()
方法则会释放对象锁。run()
方法完成后线程终止。stop()
方法强行终止(不推荐),可能会出现数据不同步,或者资源未释放等问题。interrupt()
方法中断线程。多个线程因竞争资源而造成的一种僵局(互相等待),若无外力作用,这些进程都将无法向前推进,这种现象称为死锁。
避免死锁的三种方式:
corePoolSize
线程池核心线程大小。在没有设置 allowCoreThreadTimeOut
为true
的情况下,核心线程会在线程池中一直存活,即使处于闲置状态。当向线程池提交一个任务时,若线程池已创建的线程数小于corePoolSize
,即便此时存在空闲线程,也会通过创建一个新线程来执行该任务,直到已创建的线程数大于或等于corePoolSize
。maximumPoolSize
线程池最大线程数量。线程池所允许的最大线程个数。当队列满了,且已创建的线程数小于maximumPoolSize
,则线程池会创建新的线程来执行任务。对于无界队列可以忽略此参数。keepAliveTime
线程存活保持时间。当线程池中线程数大于核心线程数时,线程的空闲时间如果超过线程存活时间,那么这个线程就会被销毁,直到线程池中的线程数小于等于核心线程数。unit
空间线程存活时间单位。workQueue
任务队列:用于传输和保存等待执行任务的阻塞队列。
①ArrayBlockingQueue
,基于数组的有界阻塞队列,按FIFO排序。
②LinkedBlockingQuene
,基于链表的无界阻塞队列(其实最大容量为Interger.MAX
),按照FIFO排序。当使用该队列时,maximumPoolSize
参数可以忽略。
③SynchronousQuene
,一个不缓存任务的阻塞队列,生产者放入一个任务必须等到消费者取出这个任务。
④PriorityBlockingQueue
,具有优先级的无界阻塞队列,优先级通过参数Comparator
实现。threadFactory
线程工厂,用于创建新线程。handler
线程饱和策略,当线程池和队列都满了,再加入线程会执行此策略。submit()
方法有三个重载方法。
<T> Future<T> submit(Callable<T> task);
<T> Future<T> submit(Runnable task, T result);
Future<?> submit(Runnable task);
execute()
方法只有一个
void execute(Runnable command);
execute()
没有返回值;而submit()
有返回值submit()
的返回值Future
调用get()
方法时,可以捕获处理异常。而execute()
没有返回值不能捕获异常。Executors.newCacheThreadPool()
:可缓存线程池,先查看池中有没有已建立的线程,如果有,就直接使用。如果没有,就建一个新的线程加入池中,缓存型池子通常用于执行一些生存期很短的异步型任务。
Executors.newFixedThreadPool()
:可重用固定个数的线程池,以共享的无界队列方式来运行这些线程。
Executors.newScheduledThreadPool(int n)
:定长线程池,支持定时及周期性任务执行。
Executors.newSingleThreadExecutor()
:单线程化的线程池,它只会用唯一的工作线程来执行任务,保证所有任务按照指定顺序(FIFO, LIFO, 优先级)执行。
当多个线程同时共享,同一个全局变量或者静态变量,做写的操作时,可能会发生数据冲突问题,也就是线程安全问题。
java的内存模型规定了所有的变量都存储在主内存中,每个线程拥有自己的工作内存,工作内存保存了该线程使用到的变量的主内存拷贝,线程对变量所有操作,读取,赋值,都必须在工作内存中进行,不能直接写主内存变量,线程间变量值的传递均需要主内存来完成。
volatile关键字有什么作用:
volatile
是Java提供的一种轻量级的同步机制,并不能保证原子性。
指令重排是指JVM
在编译Java代码的时候,或者CPU在执行JVM
字节码的时候,对现有的指令顺序进行重新排序。
指令重排的目的是为了在不改变程序执行结果的前提下,优化程序的运行效率。需要注意的是,这里所说的不改变执行结果,指的是不改变单线程下的程序执行结果。
this
)。synchronized(this){}
,被锁对象是类的实例。
②synchronized(XXX.Class)
,被锁对象是类对象。
③synchronized(new Object())
,被锁对象是实例对象object
。1.获取锁。2.上锁。3.释放锁。
注意点:释放锁最好放在finally{}
代码块中,保证能执行释放锁。
synchronized
是java内置关键字,在jvm
层面。Lock
是个java类。synchronized
无法判断是否获取锁的状态。Lock
可以判断是否获取到锁。synchronized
会自动释放锁。Lock
锁需要在finally{}
代码块中手工释放锁。synchronized
的锁可重入、不可中断、非公平。而Lock
锁可重入、可判断、可公平(两者皆可)。ConcurrentHashMap
、Vector
、Hashtable
、Stack
。还可以使用Collections包装方法
获得线程安全的集合。
CAS
是compare and swap
的缩写,意思是比较与交换。CAS
是乐观锁的一种实现。CAS操作包含三个操作数---内存位置的值(V)、预期原值(A)和新值(B)。如果内存位置的值与预期原值相匹配,那么处理器会自动将该位置更新为新值。否则,处理器不做任何操作。
CAS
有以下缺点:
CAS
机制所保证的只是一个变量的原子性操作,而不能保证整个代码块的原子性。比如需要保证3个变量共同进行原子性的更新,就不得不使用synchronized
了。这个类提供了线程局部变量也称为线程本地变量,它为变量在每个线程中创建了一个副本,通过这样的方式做到变量在线程间隔离且在方法间共享的场景。
ThreadLocal
存储的值不是线程共享的,而是属于线程的。内部会维护一个ThreadLocalMap
,key是当前线程的ThreadLocal
,value是存储的值。换句话说,每个线程都有自己的值,当然不会出现线程安全问题了。
源码如下:
public void set(T value) {
//获取当前线程
Thread t = Thread.currentThread();
//通过当前线程获取到ThreadLocalMap
ThreadLocalMap map = getMap(t);
if (map != null)
//key是this,value是需要存储的值
map.set(this, value);
else
//创建一个map
createMap(t, value);
}
Java内存模型(Java Memory Model,简称为JMM),是一种符合内存模型规范的,屏蔽了各种硬件和操作系统的访问差异的,保证了Java程序在各种平台下对内存的访问都能保证效果一致的机制及规范。
根据java虚拟机规范,JVM内存共分为虚拟机栈,堆,方法区,程序计数器,本地方法栈五个部分。
栈溢出原因就是方法执行时创建的栈帧超过了栈的深度。最有可能的就是方法递归调用产生这种结果。
OutOfMemoryError: Java heap space
。在创建新的对象时, 堆内存中的空间不足以存放新创建的对象时发生。产生原因:程序中出现了死循环,不断创建对象;程序占用内存太多,超过了JVM堆设置的最大值。OutOfMemoryError: unable to create new native thread
。产生原因:系统内存耗尽,无法为新线程分配内存;创建线程数超过了操作系统的限制。OutOfMemoryError: PermGen space
。永久代溢出,即方法区溢出了,一般出现于大量Class或者jsp页面,或者采用cglib等反射机制的情况,因为上述情况会产生大量的Class信息存储于方法区。OutOfMemoryError:GC overhead limit exceeded
。超过98%的时间都在用来做GC并且回收了不到2%的堆内存。连续多次的GC,都回收了不到2%的极端情况下才会抛出。标记-清除算法、复制算法、标记整理算法、分代收集算法。
会使用可达性分析算法进行判断,原理是从一系列被称为GC ROOT
的对象开始,向下搜索,搜索走过的路径称为引用链,当一个对象到GC ROOT
之间没有引用链,说明这个对象不可用,那么就会被GC回收。
强引用。一般new
出来的对象都是强引用。如果一个对象具有强引用,GC
绝不会回收它;当内存空间不足,JVM宁愿抛出OutOfMemoryError
错误。
//强引用
Object obj = new Object();
软引用。如果一个对象只具有软引用。如果内存空间足够,垃圾回收器就不会回收它,如果内存空间不足了,就会回收这些对象的内存。
//软引用
SoftReference<Object> softReference = new SoftReference<>(new Object());
弱引用。如果一个对象具有弱引用,在GC线程扫描内存区域的过程中,不管当前内存空间足够与否,都会回收内存。
//弱引用
WeakReference<Object> weakReference = new WeakReference<>(new Object());
虚引用。如果一个对象仅持有虚引用,在任何时候都可能被垃圾回收。
//虚引用
PhantomReference<Object> phantomReference = new PhantomReference<>(new Object(), new ReferenceQueue<>());
Java类加载器是Java运行时环境的一部分,负责动态加载Java类到JVM的内存空间中。
双亲委派机制是指当一个类加载器收到一个类加载请求时,该类加载器首先会把请求委派给父类加载器。每个类加载器都是如此,只有在父类加载器在自己的搜索范围内找不到指定类时,子类加载器才会尝试自己去加载。
加载、验证、准备、解析、初始化、使用、卸载。
有些资料会把(验证、准备、解析)归纳为连接,于是就变成:加载、连接、初始化、使用、卸载。
public class SingLeton {
//立即加载
private static SingLeton singLeton = new SingLeton();
//私有化构造器
private SingLeton(){}
//对外暴露获取实例的方法
public static SingLeton getSingLeton(){
return singLeton;
}
}
public class SingLeton {
//立即加载
private static SingLeton singLeton;
//私有化构造器
private SingLeton() {
}
//对外暴露获取实例的方法
public static SingLeton getSingLeton() {
if (singLeton == null) {
singLeton = new SingLeton();
}
return singLeton;
}
}
public class SingLeton {
//私有化构造器
private SingLeton() {}
//对外暴露获取实例的方法
public static SingLeton getSingLeton() {
return SingLetonHolder.SINGLETON;
}
//私有静态内部类
private static class SingLetonHolder {
private static final SingLeton SINGLETON = new SingLeton();
}
}
public enum SingLeton {
SINGLETON;
}
饿汉式实现、枚举、静态内部类都是线程安全的实现方式。 还可以使用双检锁的懒汉式方式实现:
public class SingLeton {
private static volatile SingLeton singLeton;
//私有化构造器
private SingLeton() {}
//对外暴露获取实例的方法
public static SingLeton getSingLeton() {
if (singLeton == null) {
synchronized (SingLeton.class) {
if (singLeton == null) {
singLeton = new SingLeton();
}
}
}
return singLeton;
}
}
(1)JDK动态代理
只能对实现了接口的类生成代理,而不能针对类。
(2)CGLIB
是针对类实现代理,主要是对指定的类生成一个子类,覆盖其中的方法。
因为是继承,所以该类或方法不能声明成final
。
使用场景:
java中经典的例子就是I/O流。具体分析过程可以参考我写的这篇文章:装饰者模式与IO流的应用。
插入排序、冒泡排序、归并排序、快速排序、堆排序、桶排序、基数排序等等。
平均的时间复杂度是O(n^2)
,最好的情况是O(n)
,最坏的情况是O(n^2)
。空间复杂度是O(1)
。
归并排序。最好和最坏的情况下,时间复杂度都是O(n*log n)
。
有两种方式,迭代法和递归法。时间复杂度是O(log n)
。
//递归法
public int binarySearch(int[] nums, int star, int mid, int end, int target) {
//递归终止条件,如果开始索引比末尾索引要大则证明找不到,返回-1
if (star > end) {
return -1;
}
//获取中间值
int midVal = nums[mid];
//如果等于目标值,就返回
if (midVal == target) {
return mid;
} else if (midVal > target) {
//如果不等于中间值,中间值大于目标值,就在左边的区间查找
return binarySearch(nums, star, (star + mid - 1) / 2, mid - 1, target);
} else {
//如果中间值小于目标值,在右边的区间查找
return binarySearch(nums, mid + 1, (mid + 1 + end) / 2, end, target);
}
}
//迭代法
public int binarySearch(int[] nums, int target) {
//左指针
int left = 0;
//右指针
int right = nums.length - 1;
//中间索引下标
int mid;
//只要左指针小于等于右指针就一直循环
while (left <= right) {
//获取中间索引下标,有些人喜欢写成 left+(right-left)/2;意思是一样的
mid = (left + right) / 2;
int midVal = nums[mid];
//判断中间值与目标值是否相等,相等则找到了,返回下标
if (midVal == target) {
return mid;
}
//如果中间值大于目标值,证明目标值在左边,把右指针移到中间索引前面
else if (midVal > target) {
right = mid - 1;
}
//如果中间值小于目标值,证明目标值在中间值右边,因为是升序排序的数组嘛,把左指针移到中间索引的后面
else {
left = mid + 1;
}
}
//如果左指针大于右指针了,跳出循环,证明找不到目标值,返回-1
return -1;
}
这是一个经典的斐波那契数列问题。力扣题库第70题。可以看看大佬们的题解。这是我的题解,使用了Map
作为缓存,减少一些不必要的递归,效率还不错。执行时间:1 ms。当然你去掉那个Map
也是完全没错的,只是运行时间会久一些,可能会超出leetcode
的时间限制,没法通过。
/**
* 题目描述:
* 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
* 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
*/
class Solution {
private Map<Integer, Integer> map = new HashMap<>();
public int climbStairs(int n) {
if (n == 1) {
map.put(n, 1);
return 1;
}
if (n == 2) {
map.put(n, 2);
return 2;
}
if (map.get(n) != null) {
return map.get(n);
} else {
int num = climbStairs(n - 1) + climbStairs(n - 2);
map.put(n, num);
return num;
}
}
}