# Java的OJ编程模板

Java 1.5发行版本中增加了泛型(Generic)。
- 参考自：《Effietive Java》P97
⚡️OJ中Java常用数据结构

<font style="background:yellow">

# 目录

[TOC]

# ⭐️Java在OJ的万能模板

import java.util.*;	//Scanner等，还有各种泛型数据结构
import java.lang.*;	//字符串
import java.math.*;	//大整型+大浮点型

1
2
3

# ✅模块1.思考对比

# 🤔int和Integer有什么区别？

int是我们常说的整形数字，是Java的8个原始数据类型之一。Java语言虽然号称一切都是对象，但原始数据类型是例外。
Integer是int对应的包装类，它有一个int类型的字段存储数据，并且提供了基本操作，比如数学运算、int和字符串之间转换等。在Java 5中，引入了自动装箱和自动拆箱功能（boxing/unboxing），Java可以根据上下文，自动进行转换，极大地简化了相关编程。关于Integer的值缓存，这涉及Java 5中另一个改进。构建Integer对象的传统方式是直接调用构造器(constructor)，直接new一个对象。但是根据实践，我们发现大部分数据操作都是集中在有限的、较小的数值范围，因而，在Java 5中新增了静态工厂方法valueOf，在调用它的时候会利用一个缓存机制，带来了明显的性能改进。按照Javadoc，这个值默认缓存是-128到127之间。

# 🤔String、StringBuffer、StringBuilder有什么区别？

String是Java语言非常基础和重要的类，提供了构造和管理字符串的各种基本逻辑。它是典型的Immutable类，被声明成为final class，所有属性也都是final的。也由于它的不可变性，类似拼接、裁剪字符串等动作，都会产生新的String对象。由于字符串操作的普遍性，所以相关操作的效率往往对应用性能有明显影响。
StringBufer是为解决上面提到拼接产生太多中间对象的问题而提供的一个类。StringBufer本质是一个线程安全的可修改字符序列，它保证了线程安全，也随之带来了额外的性能开销，所以除非有线程安全的需要，不然还是推荐使用它的后继者，也就是StringBuilder。
StringBuilder是Java 1.5中新增的，在能力上和StringBufer没有本质区别，但是它去掉了线程安全的部分，有效减小了开销，是绝大部分情况下进行字符串拼接的首选

# 🤔【集合提醒】对比`ArrayList`和`LinkedList`和【淘汰】`Vector`

这三者都是实现集合框架中的List，也就是所谓的有序集合，因此具体功能也比较近似，比如都提供按照位置进行定位、添加或者删除的操作，都提供迭代器以遍历其内容等。但因为具体的设计区别，在行为、性能、线程安全等方面，表现又有很大不同
Vector是Java早期提供的线程安全的动态数组，如果不需要线程安全，并不建议选择，毕竟同步是有额外开销的。Vector内部是使用对象数组来保存数据，可以根据需要自动的增加容量，当数组已满时，会创建新的数组，并拷贝原有数组数据。『扩容逻辑：Vector在扩容时会提高1倍』
ArrayList是应用更加广泛的动态数组实现，它本身不是线程安全的，所以性能要好很多。与Vector近似，ArrayList也是可以根据需要调整容量，不过两者的调整逻辑有所区别，『扩容逻辑：ArrayList则是增加50%』ArrayList列表底层是用『数组』实现的
LinkedList顾名思义是Java提供的双向链表，所以它不需要像上面两种那样调整容量，它也不是线程安全的。LinkedList底层是用『双链表』实现的。

Vector已经被淘汰了。

# 🤔【集合体系】对比`HashMap`、`TreeMap`和【淘汰】的`Hashtable`

java中HashMap和Hashtable的区别 (opens new window)
Hashtable、HashMap、TreeMap都是最常见的一些Map实现，是以键值对的形式存储和操作数据的容器类型。
Hashtable是早期Java类库提供的一个哈希表实现，本身是同步的，不支持null键和值，由于同步导致的性能开销，所以已经很少被推荐使用
- 1.历史原因:Hashtable是基于陈旧的Dictionary类的，HashMap是Java + 1.2引进的Map接口的一个实现
HashMap是应用更加广泛的哈希表实现，行为上大致上与HashTable一致，主要区别在于HashMap不是同步的，支持null键和值等。通常情况下，HashMap进行put或者get操作，可以达到常数时间的性能，所以它是绝大部分利用键值对存取场景的首选。
TreeMap则是基于红黑树的一种提供顺序访问的Map，和HashMap不同，它的get、put、remove之类操作都是O（log(n)）的时间复杂度，具体顺序可以由指定的Comparator来决定，或者根据键的自然顺序来判断。

# 🌱模块2.API记忆

# ✅01.字符串`StringBuilder`和`String`

# String基本操作

String str="HACV";

//注意，Java的字符串处理起来比C++麻烦，因为它不支持用[]直接访问其中的字符，而且不能直接修改
//需要转换为char[] 类型后才能修改
//获取str[2];
char c=str.charAt(2);
//Java的字符串不能直接修改，要用toCharArray转化为『char[]』类型的数组后进行修改，然后转换回『String』类型
char[] demo=str.toCharArray();
demo[1]='a';

String strTemp=new String( demo );

System.out.println( strTemp );

1
2
3
4
5
6
7
8
9
10
11
12
13

# String的其他操作

//注意。一定要用equals方法判断字符串是否相同
//不要用==比较，否则可能出现不易察觉的bug
if( s1.euqals(s2) )
{
    //s1和s2相同
}
else
{
    //s1和s2不相同
}

//字符串可以用『加号』进行拼接
String s3=s1+"!!!";
System.out.println(s3);

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 第2种

虽然String支持用+进行拼接，但是效率并不高，不建议在for循环中使用
如果需要进行频繁的字符串拼接，推荐使用StringBuilder

StringBuilder sb=new StringBuilder();

for( char c='a'; c<'f'; c++ )
{
    sb.append(c);
}

//append方法支持拼接字符、字符串、数字等类型
sb.append('g').append("hhh").append(123);

String res=sb.toString();

System.out.println(res);

1
2
3
4
5
6
7
8
9
10
11
12
13

# ✅02.栈Stack

# 栈的基础

Stack<Integer> s=new Stack<>();

# 栈的常用函数

boolean isEmpty();		//判断Stack是否空
int size();				//返回Stack中元素个数
ElementType push( ElementType item );	 //把元素压入栈顶
ElementType peek();		//返回栈顶元素『和C++ STL不一样』
ElementType pop();		//删除并且返回栈顶元素『和C++ STL不一样』

1
2
3
4
5

# ✅03.队列Queue

# 队列的基础

注意：注意这个初始化

Queue<String> qq=new LinkedList<>();	//注意！『前面是Queue，后面是LinkedList』

# 队列的常用函数

boolean isEmpty();		//判断Queue是否空
int size();				//返回Queue中元素个数
ElementType peek();		//返回队头的元素『和C++ STL不一样』
ElementType poll();		//删除并返回队头的元素『和C++ STL不一样』
boolean offer( ElementType val );	//将元素val插入队尾

1
2
3
4
5

# ⭐️对比记忆

对比记忆1：

C++ STL中『push，压入』『pop，弹出』
Java的队列中『offer，插入队尾』『poll，删除并返回队头的元素』
Git中『push，提交去远程』『pull，从远程拉取到本地』

对比记忆2：

C++ STL中返回『栈顶』元素，用『top』
C++ STL中返回『队列头』元素，用『front』，返回队尾用『back』
Java中『栈顶』元素/『队列头』元素，全都用的『peek』

# ✅04.哈希表HashMap

HashMap『记忆方式，C++ STL中也常用map系列来做哈希』

HashMap<Integer, String> mp=new HashMap<>();//整数映射到字符串的哈希表
HashMap<Integer,int[]> mp=new HashMap<>();//字符串映射到数组的哈希表

1
2

常用函数

boolean containsKey( Object key );//判断哈希表中是否存在键『key』
val get( Objevt key );//获得键key对应的值val，如果key不存在，则返回null
val put( Key key, Val value );//键值对存入哈希表
val remove( Object key );//如果key存在，删除key并且返回对应的值
val getOrDefault( Object key, val defaultValue );//获得key的值，如果key不存在，则返回defaultValue

Set<K> keySet();//获得哈希表中的所有key

//如果key不存在，则将键值对key和value存入哈希表
//如果key存在，则什么都不做
val putIfAbsent( Key key, Val value );

1
2
3
4
5
6
7
8
9
10
11

# ✅05.哈希集合HashSet

HashSet

注意：注意这个初始化

Set<String> set=new HashSet<>();//新建一个存储String的哈希集合

常用函数

boolean add( ElementType e );//如果e不存在，则将e添加到哈希集合
boolean contains( Object O );//判断元素O是否存在于哈希集合中
boolean remove( Object o );//如果元素o存在，则删除元素o

1
2
3

# ✅06.动态数组ArrayList

类似C++的vector容器，ArrayList相当于把Java内置的数组类型做了包装

ArrayList<Integer> str=new ArrayList<>();//初始化一个存储int类型数据的动态数组
ArrayList<String>  str=new ArrayList<>();//初始化一个存储String类型数据的动态数组

1
2

常见函数

boolean isEmpty();//判断数组是否为空
int size();//返回数组中元素的格式
ElementType get( int index );//返回索引index的元素
boolean add( ElementType e );//在数组尾部添加元素e

1
2
3
4

# ✅07.双向链表LinkedList

LinkedList底层是双向链表实现的

LinkedList<Integer> str=new LinkedList<>();//初始化一个存储int类型数据的双链表
LinkedList<String>  str=new LinkedList<>();//初始化一个存储String类型数据的双链表

1
2

常用函数

boolean isEmpty();//判断链表是否为空
int size();//返回链表中元素的个数
boolean contains( Object o );//判断链表中是否存在元素o

boolean add( Element e );//在链表尾部添加元素e
void addFirst( Element e );//在链表头部添加元素e『注意』

Element removeFirst();//删除链表头结点中第1个元素
Element removeLast();//删除链表尾部最后1个元素

1
2
3
4
5
6
7
8
9

Tips：ArrayList和LinkedList都是List类型的子类，做OJ的时候注意

# ✅08.优先队列/大顶堆

PriorityQueue 是非线程安全的，所以 Java 提供了 PriorityBlockingQueue（实现 BlockingQueue接口）用于Java 多线程环境。

# 优先队列基础

import java.util.PriorityQueue;
import java.util.Queue;

Queue<String> q = new PriorityQueue<>(); //注意『前面是

1
2
3
4

import java.util.PriorityQueue;
import java.util.Queue;
public class Main {
    public static void main(String[] args) {
        Queue<String> q = new PriorityQueue<>();
        // 添加3个元素到队列:
        q.offer("apple");
        q.offer("pear");
        q.offer("banana");
        System.out.println(q.poll()); // apple
        System.out.println(q.poll()); // banana
        System.out.println(q.poll()); // pear
        System.out.println(q.poll()); // null,因为队列为空
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 9.双端队列

Queue是队列，只能一头进，另一头出。

如果把条件放松一下，允许两头都进，两头都出，这种队列叫双端队列（Double Ended Queue），学名Deque。

Java集合提供了**接口D**eque来实现一个双端队列，它的功能是：

既可以添加到队尾，也可以添加到队首；
既可以从队首获取，又可以从队尾获取。

	Queue	Deque
添加元素到队尾	add(E e) / offer(E e)	addLast(E e) / offerLast(E e)
取队首元素并删除	E remove() / E poll()	E removeFirst() / E pollFirst()
取队首元素但不删除	E element() / E peek()	E getFirst() / E peekFirst()
添加元素到队首	无	addFirst(E e) / offerFirst(E e)
取队尾元素并删除	无	E removeLast() / E pollLast()
取队尾元素但不删除	无	E getLast() / E peekLast()

对于添加元素到队尾的操作，Queue提供了add()/offer()方法，而Deque提供了addLast()/offerLast()方法。添加元素到队首、取队尾元素的操作在Queue中不存在，在Deque中由addFirst()/removeLast()等方法提供。

注意到Deque接口实际上扩展自Queue：

public interface Deque<E> extends Queue<E> {
    ...
}

1
2
3

因此，Queue提供的add()/offer()方法在Deque中也可以使用，但是，使用Deque，最好不要调用offer()，而是调用offerLast()：

import java.util.Deque;
import java.util.LinkedList;

Deque<String> deque = new LinkedList<>();

1
2
3
4

import java.util.Deque;
import java.util.LinkedList;
public class Main {
    public static void main(String[] args) {
        Deque<String> deque = new LinkedList<>();
        deque.offerLast("A"); // A
        deque.offerLast("B"); // A <- B
        deque.offerFirst("C"); // C <- A <- B
        System.out.println(deque.pollFirst()); // C, 剩下A <- B
        System.out.println(deque.pollLast()); // B, 剩下A
        System.out.println(deque.pollFirst()); // A
        System.out.println(deque.pollFirst()); // null
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

因此，使用Deque，推荐总是明确调用offerLast()/offerFirst()或者pollFirst()/pollLast()方法。

Deque是一个接口，它的实现类有ArrayDeque和LinkedList。

我们发现LinkedList真是一个全能选手，它即是List，又是Queue，还是Deque。但是我们在使用的时候，总是用特定的接口来引用它，这是因为持有接口说明代码的抽象层次更高，而且接口本身定义的方法代表了特定的用途。

// 不推荐的写法:
LinkedList<String> d1 = new LinkedList<>();
d1.offerLast("z");
// 推荐的写法：
Deque<String> d2 = new LinkedList<>();
d2.offerLast("z");

1
2
3
4
5
6

可见面向抽象编程的一个原则就是：尽量持有接口，而不是具体的实现类。

# 参考资料[记忆这个]

https://www.liaoxuefeng.com/wiki/1252599548343744/1265121225603904

# 🌱Java SE 常用类-目录

参考：CSDN，JavaSE常用类 (opens new window)

# 1.`java.lang`包

对象
包装类
数学
字符串
系统类
运行时异常
参考资料：CSDN的java.lang包 (opens new window)

# 3.`java.util`包

哈希表
可变数组
链表
日期
数组
TreeMap + TreeSet

查看：Java8的中文文档发现 (opens new window)

# Interfaces
Collection
Comparator
Deque
Enumeration
EventListener
Formattable
Iterator
List
ListIterator
Map
Map.Entry
NavigableMap
NavigableSet
Observer
PrimitiveIterator
PrimitiveIterator.OfDouble
PrimitiveIterator.OfInt
PrimitiveIterator.OfLong
Queue
RandomAccess
Set
SortedMap
SortedSet


# Classes
AbstractCollection
AbstractList
AbstractMap
AbstractMap.SimpleEntry
AbstractMap.SimpleImmutableEntry
AbstractQueue
AbstractSequentialList
AbstractSet
ArrayDeque
ArrayList
Arrays
Base64
Base64.Decoder
Base64.Encoder
BitSet
Calendar
Calendar.Builder
Collections
Currency
Date
Dictionary
DoubleSummaryStatistics
EnumMap
EnumSet
EventListenerProxy
EventObject
FormattableFlags
Formatter
GregorianCalendar
HashMap
HashSet
Hashtable
IdentityHashMap
IntSummaryStatistics
LinkedHashMap
LinkedHashSet
LinkedList
ListResourceBundle
Locale
Locale.Builder
Locale.LanguageRange
LongSummaryStatistics
Objects
Observable
Optional
OptionalDouble
OptionalInt
OptionalLong
PriorityQueue
Properties
PropertyPermission
PropertyResourceBundle
Random
Scanner
SplittableRandom
Stack
StringJoiner
StringTokenizer
Timer
TimerTask
TimeZone
TreeMap
TreeSet
Vector
WeakHashMap

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

java.util.regex包
- 正则表达式
java.text包
- 日期格式化

# ♻️参考资料

CyC2018，Java部分 (opens new window)
labuladong的算法小抄
java核心技术36讲，极客时间，杨晓峰
java的泛型、集合 (opens new window)，廖雪峰

# Java的OJ编程模板

# 目录

# ⭐️Java在OJ的万能模板

# ✅模块1.思考对比

# 🤔int和Integer有什么区别？

# 🤔String、StringBuffer、StringBuilder有什么区别？

# 🤔【集合提醒】对比ArrayList和LinkedList和【淘汰】Vector

# 🤔【集合体系】对比HashMap、TreeMap和【淘汰】的Hashtable

# 🌱模块2.API记忆

# ✅01.字符串StringBuilder和String

# String基本操作

# String的其他操作

# 第2种

# ✅02.栈Stack

# 栈的基础

# 栈的常用函数

# ✅03.队列Queue

# 队列的基础

# 队列的常用函数

# ⭐️对比记忆

# ✅04.哈希表HashMap

# ✅05.哈希集合HashSet

# ✅06.动态数组ArrayList

# ✅07.双向链表LinkedList

# ✅08.优先队列/大顶堆

# 优先队列基础

# 9.双端队列

# 参考资料[记忆这个]

# 🌱Java SE 常用类-目录

# 1.java.lang包

# 3.java.util包

# ♻️参考资料

# 🤔【集合提醒】对比`ArrayList`和`LinkedList`和【淘汰】`Vector`

# 🤔【集合体系】对比`HashMap`、`TreeMap`和【淘汰】的`Hashtable`

# ✅01.字符串`StringBuilder`和`String`

# 1.`java.lang`包

# 3.`java.util`包