【持续更新】java刷题常用数据结构、方法和思路

动态数组——ArrayList

ArrayList类是一个可以动态修改的数组，与普通数组的区别就是它是没有固定大小的限制，我们可以添加或删除元素；ArrayList 继承了 AbstractList ，并实现了 List 接口。

实例化方法：ArrayList<T> arr = new ArrayList<>();   其中T为泛型数据类型

ArrayList 是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。

函数方法：

add()：添加元素到ArrayList，如 arr.add("Weibo")就是在arr最后加上一个元素，叫"Weibo"。

remove()：删除ArrayList中的元素，如arr.remove(3)就是删除第四个元素。

set()：修改ArrayList中的元素，其中第一个参数为索引位置，第二个为要修改的值。

如arr.set(2, "Wiki")就是把第三个元素的值修改为"Wiki"。

get()：参数为索引，获取对应位置的值。

LinkedList（栈，队列，容器）

LinkedList既可以看作一个顺序容器，又可以看作一个队列（Queue），同时又可以看作一个栈（stack），它的底层通过双向链表实现，双向链表的每个节点用内部类Node表示，通过first和last引用分别指向链表的第一个和最后一个元素。

栈(Stack)

废弃栈的实例化方法：Stack<T> stack = new Stack<>();

现在栈的实例化方法：Deque<T> stack = new LinkedList<Integer>();

或者直接用LinkedList<T> stack

函数方法

peek()：查看堆栈顶部的对象，但不从堆栈中移除它，和pop()区分（查看且删除）。

isEmpty()：判断栈是否为空。

push()：把项压入堆栈顶部，对应的删除是pop()。

队列(Queue)

Queue 作为先进先出队列，只能从头部取元素、插入元素到尾部。Java 同样定义了双向队列 Deque，可以同时在头部、尾部插入和取出元素。

实例化方法： LinkedList<T> queue = new LinkedList<>();

或者  Queue<T> queue = new LinkedList<>();

函数方法

压入元素(添加)：add()、offer()
相同：未超出容量，从队尾压入元素，返回压入的那个元素。
区别：在超出容量时，add()方法会对抛出异常，offer()返回false。

弹出元素(删除)：remove()、poll()
相同：容量大于0的时候，删除并返回队头被删除的那个元素。
区别：在容量为0的时候，remove()会抛出异常，poll()返回false。

获取队头元素(不删除)：element()、peek()
相同：容量大于0的时候，都返回队头元素。但是不删除。
区别：容量为0的时候，element()会抛出异常，peek()返回null。

addFirst()/addLast()：插入元素到队列头部/尾部，失败则抛出异常。

removeFirst()/removeLast()：取出并移除头部元素/尾部元素，空队列抛出异常。

peekFirst()/peekLast()：取出但不移除头部元素/尾部元素，空队列返回null。

size()：获取队列长度。

优先队列（堆，PriorityQueue）

添加到 PriorityQueue 队列里面的元素都经过了排序处理，默认按照自然顺序，也可以通过 Comparator 接口进行自定义排序。它采用树形结构来描述元素的存储，具体说是通过完全二叉树实现一个小顶堆，在物理存储方面，PriorityQueue 底层通过数组来实现元素的存储。

由于 PriorityQueue 的底层是基于堆实现的，因此在数据量比较大时，使用 PriorityQueue 可以获得较好的时间复杂度。

优先队列默认的是最小堆（优先弹出最小值）

实例化方法：

最小堆（默认）：PriorityQueue<T> queue = new PriorityQueue<>();

最大堆：PriorityQueue<T> queue = new PriorityQueue<>(int capacity, (num1, num2) -> num2-num1);

方法：peek、poll、add、isEmpty、size…（类似队列）

集合（Map、List、Set）

HashMap 是 Java 中非常常用的数据结构之一，用于存储键值对。在 HashMap 中，每个键都映射到一个唯一的值，可以通过键来快速访问对应的值，算法时间复杂度可以达到 O(1)。

哈希表(HashMap)

实例化：HashMap<T1, T2> map = new HashMap<>();

方法：containsKey、containsValue、get、getOrDefault、isEmpty、put、remove、replace、size…

哈希集(HashSet)

List接口

有序表TreeMap

底层基于红黑树实现，是一棵平衡二叉搜索树，它的键是有序排列的

实例化：TreeMap<T1, T2> treeMap = new TreeMap<>();可以传入Comparator实现自定义排序，否则自动按键的默认方法排序

方法：firstKey、lastKey、containsKey、get、getOrDefault、isEmpty、put、remove…

TreeSet类似

类型转化

char与String互相转换

String s = String.valueOf(‘c’); //效率最高的方法

String s = String.valueOf(new char[]{‘a’,‘c’}); //将一个char数组转换成String

char[] sArr = s.toCharArray();

String转int

int i=Integer.parseInt(s);
int i=Integer.valueOf(s).intValue();

int转String

String s = String.valueOf(i);
String s = Integer.toString(i);
String s = “” + i;

StringBuilder构建String

被synchronize修饰的StringBuffer是线程安全的，但刷题为了效率一般都用StringBuilder

实例化：StringBuilder sb = new StringBuilder();

构建String: sb.toString

方法：append、toString、insert、delete…