数组

数组的初始化

new int[]{-1,...}       
int size = nums.length;
int[] result = new int[size];//存放结果
Arrays.fill(result,-1);//默认全部初始化为-1

Arrays类

Java中的Arrays类提供了一系列静态方法来操作数组，包括排序、搜索、比较等功能

sort快排

Arrays.sort()方法使用的是经过优化的快速排序算法，平均时间复杂度为，最坏情况下是数组已经有序，时间复杂度为

int[] arr = new int[]{2, 6, 8, 7, 10};
Arrays.sort(arr);
System.out.println(Arrays.toString(arr)); // [2, 6, 7, 8, 10]

binarySearch二分查找（有序）

Arrays.binarySearch()方法使用的是二分查找算法。这个算法要求被搜索的数组必须是有序的，时间复杂度为

数组一定是排好序的，否则会出错

int[] arr = new int[]{2, 6, 8, 7, 10};
int index = Arrays.binarySearch(arr, 6);
System.out.println(index); // 1

如果找到要搜索的元素，则返回该元素的索引

如果找不到要搜索的元素，则返回一个负数值，表示该元素应该插入的位置的负数值减一

equals比较

Arrays.equals()方法用于比较两个数组是否相等，数组是地址传递，不能用==判断

boolean result = Arrays.equals(array1, array2);

如果两个数组在相同位置上的元素都相等，并且两个数组的长度也相等，则返回true，否则返回false
在最坏情况下，时间复杂度为，其中n是要比较的数组的长度。因为在比较两个数组时，需要逐个比较它们的元素

fill填充

Arrays.fill()方法用于将数组中的所有元素都设置为指定的值

Arrays.fill(array, value);

array是要填充的数组，value是要设置的值。调用该方法后，数组中的所有元素都会被设置为指定的value。时间复杂度为，其中n是数组的长度，需要遍历整个数组，并将每个元素设置为指定的值

copyOf复制

Arrays.copyOf()方法用于将一个数组复制到一个新的数组中，并可以指定新数组的长度

int[] newArray = Arrays.copyOf(originalArray, newLength);

originalArray：要复制的原始数组
newLength：新数组的长度
调用该方法后，将原始数组中的元素复制到一个新数组中，并返回这个新数组。如果新数组的长度大于原始数组的长度，则新数组的末尾会用默认值填充
时间复杂度取决于新数组的长度，即为

copyOfRange范围拷贝

Arrays.copyOfRange()方法用于将一个数组的指定范围内的元素复制到一个新的数组中

int[] newArray = Arrays.copyOfRange(originalArray, from, to);

originalArray：要复制的原始数组
from：要复制的起始索引（包含）
to：要复制的结束索引（不包含）
调用该方法后，将原始数组中从起始索引from（包含）到结束索引to（不包含）的元素复制到一个新数组中，并返回这个新数组
时间复杂度取决于要复制的元素数量，即为

toString输出

Arrays.toString()方法用于将数组转换为字符串形式，以便于打印或输出

String arrayString = Arrays.toString(array);

调用该方法后，数组中的元素会以逗号分隔的形式转换为一个字符串，并返回这个字符串

时间复杂度

asList转集合

Arrays.asList()方法用于将数组转换为List集合

List<T> list = Arrays.asList(array);

调用该方法后，数组中的元素会被转换为一个List集合，并返回这个List

时间复杂度为，n是数组的长度，需要遍历数组中的每个元素，并将其添加到List集合中

链表

Java中链表用LinkedList集合类来实现

LinkedList是双向链表实现的列表，适用于频繁插入和删除元素的场景
插入和删除元素的效率高，但随机访问元素效率较低（链表通病）
实现了List和Deque接口，支持队列和栈操作（可以当栈和队列使用）

添加元素

linkedList.add("A"); // 在链表末尾添加元素
linkedList.addFirst("B"); // 在链表开头添加元素
linkedList.addLast("C"); // 在链表末尾添加元素
linkedList.add(index, "D"); // 在指定位置添加元素

获取元素

String firstElement = linkedList.getFirst(); // 获取第一个元素
String lastElement = linkedList.getLast(); // 获取最后一个元素
String element = linkedList.get(index); // 获取指定位置的元素

删除元素

linkedList.removeFirst(); // 删除第一个元素
linkedList.removeLast(); // 删除最后一个元素
linkedList.remove(element); // 删除指定元素
linkedList.remove(index); // 删除指定位置的元素

其他常用操作

int size = linkedList.size(); // 获取链表大小
boolean isEmpty = linkedList.isEmpty(); // 判断链表是否为空
boolean contains = linkedList.contains("A"); // 判断链表是否包含指定元素
int index = linkedList.indexOf("B"); // 获取指定元素的索引

哈希表

哈希表都是用来快速判断一个元素是否出现集合里，数组也算一个哈希表

其他常用的有HashSet(集合)、ArrayList(动态数组)、HashMap(映射)

HashSet

HashSet是基于哈希表实现的Set集合，特点有元素唯一、无序、基于哈希表

常见的应用场景有：去重、快速查找、缓存数据

代码实现

// 用HashSet得导包
import java.util.HashSet;
// T是泛型，替换为想要保存的值类型 不能保存不同类型的值
HashSet<T> hashSet = new HashSet<>();

常用API

HashSet没有什么花哨的API，合适的场景选用可以大幅度提高效率

add(element)：向集合中添加元素
remove(element)：从集合中移除指定元素
contains(element)：判断集合中是否包含指定元素
size()：返回集合中元素的个数
isEmpty()：判断集合是否为空
clear()：清空集合中的所有元素
iterator()：返回集合的迭代器，可以用于遍历集合中的元素

HashMap

HashMap实现了Map接口，提供了键值对的存储和检索
应用场景有：

缓存：将数据以键值对的形式缓存起来，方便快速检索和访问
数据索引：可以根据键值对结构快速查找数据
数据映射：把不同类型的数据进行映射存储
常用API

put(key, value): 将指定的键值对存储到HashMap中
get(key): 返回与指定键关联的值
getOrDefault(key, defaultValue): 获取指定键对应的值 如果该键不存在则返回一个默认值
containsKey(key): 判断HashMap中是否包含指定的键
containsValue(value): 判断HashMap中是否包含指定的值
remove(key): 从HashMap中移除指定键及其关联的值
size(): 返回HashMap中键值对的个数
isEmpty(): 判断HashMap是否为空
clear(): 清空HashMap中的所有键值对
keySet(): 返回HashMap中所有键的集合
values(): 返回HashMap中所有值的集合
entrySet(): 返回HashMap中所有键值对的集合

ArrayList

ArrayList是Java中常用的动态数组实现，实现了List接口，可以根据需要动态增加或减少元素的大小

应用场景：

需要动态调整大小的数组
需要按索引访问元素
需要保持元素插入顺序：ArrayList会按照元素插入的顺序进行存储
常用API

add(element): 向ArrayList末尾添加元素
add(index, element): 在指定位置插入元素
get(index): 获取指定位置的元素
set(index, element): 替换指定位置的元素
remove(index): 移除指定位置的元素
remove(element): 移除指定元素
size(): 返回ArrayList中元素的个数
isEmpty(): 判断ArrayList是否为空
contains(element): 判断ArrayList是否包含指定元素
indexOf(element): 返回指定元素在ArrayList中第一次出现的位置
clear(): 清空ArrayList中的所有元素

字符串

字符串是最常用的类型之一了，Java中有不少字符串的处理方法和API

但是也有很多场景需要用到专门用来处理字符串的类StringBuilder

简单提一句StringBuilder和StringBuffer的区别，StringBuffer是线程安全的、StringBuilder是非线程安全的。不需要深入了解线程安全是什么，只需要知道在写算法题时使用StringBuilder速度更快，选它就对了！

字符串常用方法
在算法题中要尽量避免频繁切割字符串，字符串是不可变类型，每一次操作都会生成新的字符串，造成性能浪费

length(): 返回字符串的长度
charAt(int index): 返回指定位置的字符
indexOf(String str): 返回指定子字符串第一次出现的位置
lastIndexOf(String str): 返回指定子字符串最后一次出现的位置
substring(int beginIndex): 返回从指定位置开始到末尾的子字符串
substring(int beginIndex, int endIndex): 返回指定范围内的子字符串
toUpperCase(): 将字符串转换为大写
toLowerCase(): 将字符串转换为小写
equals(Object obj): 比较字符串内容是否相同
equalsIgnoreCase(String anotherString): 忽略大小写比较字符串内容是否相同
contains(CharSequence s): 判断字符串是否包含指定字符序列
replace(char oldChar, char newChar): 替换字符串中指定字符
replaceAll(String regex, String replacement): 使用给定的字符串替换此字符串所有匹配给定的正则表达式的子字符串
split(String regex): 根据给定正则表达式拆分字符串为字符串数组

StringBuilder
StringBuilder是专门用来操作字符串的类，通常在需要频繁进行字符串拼接或修改的情况下使用，不同于String类型的不可变，StringBuilder是可变的字符串，可以在原字符串基础上进行修改，避免频繁创建新的String对象，提高了性能

所以，当需要进行大量的字符串拼接、插入、删除等操作(尤其是在循环中)时可以考虑使用StringBuilder

常用API

append(String str): 在字符串末尾追加指定字符串
insert(int offset, String str): 在指定位置插入字符串
delete(int start, int end): 删除指定范围内的字符
deleteCharAt(int index): 删除指定位置的字符
replace(int start, int end, String str): 替换指定范围内的字符
substring(int start): 返回从指定位置开始到末尾的子字符串
substring(int start, int end): 返回指定范围内的子字符串
reverse(): 反转字符串
length(): 返回字符串的长度
charAt(int index): 返回指定位置的字符
indexOf(String str): 返回指定字符串第一次出现的位置
lastIndexOf(String str): 返回指定字符串最后一次出现的位置

栈

可以使用java.util.Stack类或者java.util.Deque接口的实现类java.util.ArrayDeque来实现栈

两者核心API上没有什么区别，java.util.Stack是线程安全的，因为它继承了Vector类

java.util.ArrayDeque不是线程安全的，还是一样写算法题无脑用ArrayDeque就行了

栈的相关API都很简单，要在合适的场景去使用

java.util.Stack类

push(E item): 将元素压入栈顶
pop(): 弹出栈顶元素
peek(): 查看栈顶元素但不移除
empty(): 判断栈是否为空
search(Object o): 查找元素在栈中的位置
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
int topElement = stack.pop();
int peekElement = stack.peek();
boolean isEmpty = stack.empty();
int index = stack.search(1);

java.util.ArrayDeque

ArrayDeque是一个双端队列，通过其丰富的API，可以实现栈

作为栈时，常用操作：

push(E e):  压栈，将元素压入栈顶，等效于addFirst(E e)
pop(): 弹栈，弹出栈顶元素并移除，等效于removeFirst()
peek(): 查看栈顶元素但不移除，等效于peekFirst()
isEmpty(): 判断栈是否为空

添加元素：

addFirst(E e): 在双端队列的开头添加元素
addLast(E e): 在双端队列的末尾添加元素
offerFirst(E e): 在双端队列的开头添加元素，如果成功返回true，否则返回false
offerLast(E e): 在双端队列的末尾添加元素，如果成功返回true，否则返回false
获取并移除元素： 

removeFirst(): 获取并移除双端队列的第一个元素
removeLast(): 获取并移除双端队列的最后一个元素
pollFirst(): 获取并移除双端队列的第一个元素，如果双端队列为空返回null
pollLast(): 获取并移除双端队列的最后一个元素，如果双端队列为空返回null
获取但不移除元素：

getFirst(): 获取但不移除双端队列的第一个元素
getLast(): 获取但不移除双端队列的最后一个元素
peekFirst(): 获取但不移除双端队列的第一个元素，如果双端队列为空返回null
peekLast(): 获取但不移除双端队列的最后一个元素，如果双端队列为空返回null

队列

队列可以通过使用java.util.Queue接口的实现类来实现

常用的队列实现类包括java.util.LinkedList和java.util.ArrayDeque

java.util.LinkedList是基于双向链表实现的，每个元素都包含对前一个和后一个元素的引用

java.util.ArrayDeque是基于数组实现的双端队列，可以在队列的两端进行高效的插入和删除操作

在大多数情况下，java.util.ArrayDeque的性能比java.util.LinkedList更好，因为数组结构的访问速度更快。
java.util.LinkedList在插入和删除元素时可能会更慢，因为需要调整链表中的指针

java.util.LinkedList

添加元素：

add(E e): 将元素添加到链表的末尾
addFirst(E e): 将元素添加到链表的开头
addLast(E e): 将元素添加到链表的末尾
offer(E e): 将元素添加到链表的末尾，如果成功返回true，否则返回false

获取并移除元素

remove(): 获取并移除链表的第一个元素
removeFirst(): 获取并移除链表的第一个元素
removeLast(): 获取并移除链表的最后一个元素
poll(): 获取并移除链表的第一个元素，如果链表为空返回null

获取但不移除元素：

getFirst(): 获取链表的第一个元素
getLast(): 获取链表的最后一个元素
peek(): 获取链表的第一个元素，如果链表为空返回null

其他常用方法：

size(): 返回链表中的元素个数
isEmpty(): 判断链表是否为空
clear(): 清空链表中的所有元素
iterator(): 返回链表的迭代器，可以用来遍历链表中的元素

java.util.ArrayDeque

添加元素：

add(E e): 将元素添加到队列的末尾，等效于offerLast(E e)
offer(E e): 将元素添加到队列的末尾，如果成功返回true，否则返回false
offerLast(E e): 将元素添加到队列的末尾，如果成功返回true，否则返回false

获取并移除元素：

remove(): 获取并移除队列的头部元素，等效于pollFirst()
poll(): 获取并移除队列的头部元素，如果队列为空返回null
pollFirst(): 获取并移除队列的头部元素，如果队列为空返回null

获取但不移除元素：

element(): 获取但不移除队列的头部元素，如果队列为空则抛出异常，等效于peekFirst()
peek(): 获取但不移除队列的头部元素，如果队列为空返回null
peekFirst(): 获取但不移除队列的头部元素，如果队列为空返回null

其他常用方法：

size(): 返回队列中的元素个数
isEmpty(): 判断队列是否为空
clear(): 清空队列中的所有元素