Java 常用数据结构

Java 数据结构类

Java 字符串反转，使用 StringBuilder。

常用包

import java.util.Scanner;
import java.util.Map;
import java.util.Collection;
import java.lang.Math;

输入输出

scan.hasNext() : 是否还有下一个有效字符串
scan.hasNextXXX() : 是否还有下一个 xxx
scan.hasNextLine() : 是否还有一行
scan.next() ：获取下一个字符串，没获取前忽略空白字符，获取后遇到空白字符就停止。
scan.nextXXX() : Int、Short 等，获取下一个 int、short 等。
scan.nextLine() ：获取下一行，以 Enter 为结束符。

import java.util.Scanner;
Scanner input = new Scanner(System.in);
String s1 = input.next();
 
int len = input.nextInt();
int arr[] = new int[len];
int idx = 0;
while(input.hasNext())
	arr[idx++] = input.nextInt();
 
try(BufferedReader in=new BufferedReader(new InputStreamReader(new FileInputStream("地址")))){
	while((line=in.readLine())!=null){
		System.out.println(line);
	}
}
catch(Exception ex){
	ex.printStackTrace();
}
 
try(BufferedReader bw=new BufferedWriter(new OutputStreamWriter(new FileOutputStream("地址")))){
	bw.write("test"+" ");
	bw.newLine();
}
catch(Exception ex){
	ex.printStackTrace();
}

String 类

获取
int length() : 返回此字符串的长度, 也就是字符串中的包含的字符数。
char charAt(int index) : 返回指定索引处的 char 值
int indexOf(int ch): 返回的是 ch 在字符串中第一次出现的索引位置
int indexOf(int ch,int fromIndex) : 从 formIndex 指定位置开始，获取 ch 在字符串中出现的索引位置
int indexOf(String str) : 返回的是 str 在字符串中第一次出现的索引位置
int indexOf(String str, int fromIndex) ：从 fromIndex 指定位置开始，获取 str 在字符串中出现的位置
int lastIndexOf(...) ：从 fromIndex 指定位置开始反向索引，获取 str 在字符串中最后出现的位置

判断 > boolean contains(str) : 字符串中是否包含某一个子字符串
boolean isEmpty() : 字符串中是否有内容。原理就是判断字符串长度是否为 0
boolean startsWith(String prefix) ：字符串是否是以指定前缀开头
boolean startsWith(String prefix, int toffset) ：字符串是否是以指定前缀开头
boolean endsWith(String suffix) ：字符串是否是以指定后缀结尾
boolean endsWith(String suffix, int toffset) ：字符串是否是以指定后缀结尾
boolean equals(str) ：判断字符串内容是否相同。复写了 Object 类中的 equals 方法，只判断字符串内容是否相同
boolean equalsIgnoreCase(str) ：忽略大小写，判断内容是否相同
boolean matches(str) ：忽略大小写，判断内容是否相同

转换 > char[] toCharArray() ：将字符串转成字符数组
byte[] getBytes() ：将字符串转成字节数组
String(byte[]) ：将字节数组转成字符串
String(byte[],offset,count) : 将字节数组中的一部分转成字符串
static String valueOf(int) ：将基本数据类型 int 转成字符串
static String valueOf(double) ：将基本数据类型转成字符串

替换和合并 > String replace(char oldchar,char newchar) : 如果要替换的字符不存在，返回的还是原串
String replaceAll(String regex, String replacement) : 正则表达替换全部
String replaceFirst(String regex, String replacement) : 正则表达替换第一个
String concat(String str) ：将指定字符串参数连接到此字符串的结尾，均不能为 null
subString() 、 concat() 和 replace() 等等操作生成新的 String 对象，然后更改变量的引用。

子串 > String substring(begin) ：返回一个新的字符串，它是此字符串的一个子字符串。从指定位置开始到结尾。如果角标不存在，会出现字符串角标越界异常。
String substring(begin,end): 返回一个新字符串，它是此字符串的一个子字符串。

切割 > String[] split(String regex) ：根据匹配给定的正则表达式来拆分此字符串
String[] split(String regex, int limit) : 根据匹配给定的正则表达式来拆分此字符串

转换大小写、去除空格和比较 > String toUpperCase() ：将字符串全部转成大写
String toLowerCase() ：将字符串全部转成小写
String trim() ：删除字符串的头尾空白符
String replace(' ', '') ：消除字符串所有空格
int compareTo(str) ：对两个字符串进行字典顺序的比较。比较基于字符串中各个字符的 Unicode 值。
int compareToIgnoreCase(str) ：对两个字符串进行字典顺序的比较。比较基于字符串中各个字符的 Unicode 值。

String (Java SE 11 & JDK 11 )

StringBuilder 类

StringBuilder sb = new StringBuilder();

增删 > StringBuilder append(boolean|char|char[]|int|long|float|double|String|StringBuffer) ：将 xx 字符串表示形式追加到序列中。
StringBuilder insert(int offset, boolean|char|char[]|int|long|float|double|String) : 将 xx 字符串表示形式插入此序列中。
StringBuilder insert(int offset, char[] str, int offset, int len) : 将 str 数组参数的子数组的字符串表示形式插入此序列中。
StringBuilder delete(int start, int end) : 删除此序列的子字符串中的字符。
StringBuilder deleteCharAt(int index) ：按此顺序删除指定位置的 char 。

改 > void setCharAt(int index, char ch) : 指定索引处的字符设置为 ch 。
StringBuilder replace(int start, int end, String str) : 使用指定的 String 的字符替换此序列的子字符串中的字符。

索引
char charAt(int index) : 返回指定索引处的 char 值
int indexOf(String str) : 返回的是 str 在字符串中第一次出现的索引位置
int indexOf(String str, int fromIndex) ：从 fromIndex 指定位置开始，获取 str 在字符串中出现的位置
int lastIndexOf(String str) : 返回指定子字符串最后一次出现的字符串中的索引。
int lastIndexOf(String str, int fromIndex) ：返回指定子字符串最后一次出现的字符串中的索引，从指定索引开始向后搜索。

子串 > String substring(int start) ：返回一个新的 String ，其中包含此字符序列中当前包含的字符的子序列。
String substring(int start, int end) ：返回一个新的 String ，其中包含当前包含在此序列中的字符的子序列。

其他 > int length() : 返回长度（字符数）。
int compareTo(sb) ：对两个字符串进行字典顺序的比较。比较基于字符串中各个字符的 Unicode 值。
StringBuilder reverse() : 致此字符序列被序列的反向替换。
String toString() : 返回此序列中数据的字符串表示形式。

StringBuilder (Java SE 11 & JDK 11 )

Integer 类

int intValue() > String toString() > static int parseInt(str) > static String toString(int i) > static Integer valueOf(str) > static Integer valueOf(int)

Integer (Java SE 11 & JDK 11 )

ArrayList 类

List<Integer> list = new ArrayList<>();

增删 > void add(int index, E element) ：将指定元素插入此列表中的指定位置。
boolean add(E e) ：将指定的元素追加到此列表的末尾。
boolean addAll(int index, Collection<? extends E> c) ：从指定位置开始，将指定集合中的所有元素插入此列表。
boolean addAll(Collection<? extends E> c) ：将指定集合中的所有元素按指定集合的 Iterator 返回的顺序附加到此列表的末尾。
E remove(int index) ：删除此列表中指定位置的元素。
boolean remove(Object o) ：从该列表中删除指定元素的第一个匹配项（如果存在）。
boolean removeAll(Collection<?> c) ：从此列表中删除指定集合中包含的所有元素。
boolean retainAll(Collection<?> c) ：仅保留此列表中包含在指定集合中的元素。
boolean removeIf(Predicate<E> filter) ：删除所有满足特定条件的数组元素。
void removeRange(int fromIndex, int toIndex) : 用于删除指定索引之间存在的元素。
void clear() ：从此列表中删除所有元素。

改 > E set(int index, E element) ：用指定的元素替换此列表中指定位置的元素。
void setCharAt(int index, char ch) : 指定索引处的字符设置为 ch 。

索引 > boolean contains(Object o) ：如果此列表包含指定的元素，则返回 true 。
boolean containsAll(Collection c) : 是否包含指定集合中的所有元素.
E get(int index) ：返回此列表中指定位置的元素。
int indexOf(Object o) ：返回此列表中第一次出现的指定元素的索引，如果此列表不包含该元素，则返回-1。
int lastIndexOf(Object o) ：返回此列表中指定元素最后一次出现的索引，如果此列表不包含该元素，则返回-1。

子串 > List<E> subList(int fromIndex, int toIndex) ：返回指定的 fromIndex （包含）和 toIndex （不包括）之间的此列表部分的视图。

其他 > int size() ：返回此列表中的元素数。
boolean isEmpty() ：如果此列表不包含任何元素，则返回 true 。
void sort(Comparator c) ：根据指定的顺序对动态数组中的元素进行排序。
String toString() : 将 Arraylist 对象转换为字符串。
void forEach(Consumer<? super E> action) ：对 Iterable 每个元素执行给定操作，直到处理 Iterable 所有元素或操作引发异常。
Iterator<E> iterator() ：以适当的顺序返回此列表中元素的迭代器。
Object[] toArray() ：没有参数，返回 Object 数组。
<T> T[] toArray(T[] a) ：有参数，则拷贝到数组后，返回该数组。

部分示例

list.removeIf(e -> e.contains("Tao"));
list.forEach((e) -> {  e = e * 10;  });
list.sort(Comparator.naturalOrder()); // 元素进行升序排列
String[] arr = new String[sites.size()];
list.toArray(arr);

ArrayList (Java SE 11 & JDK 11 )

LinkedList 类

LinkedList 继承了 AbstractSequentialList 类。
LinkedList 实现了 Queue 接口，可作为队列使用。
LinkedList 实现了 List 接口，可进行列表的相关操作。
LinkedList 实现了 Deque 接口，可作为双端队列使用。
LinkedList 实现了 Cloneable 接口，可实现克隆。
LinkedList 实现了 java.io.Serializable 接口，即可支持序列化，能通过序列化去传输。

List<Integer> list = new LinkedList<>();

在 ArrayList 函数的基础上补充：

增加 > boolean add(E e) : 尾部插入元素，Queue 接口。
void addFirst(E e) ：头部插入元素。
void addLast(E e) ：尾部插入元素。
boolean offer(E e) ：尾部插入元素，Queue 接口。
boolean offerFirst(E e) ：头部插入元素。
boolean offerLast(E e) ：尾部插入元素。

删除
E poll() ：去掉头部元素，Queue 接口。
E remove() ：去掉头部元素，Queue 接口。
E removeFirst() ：去掉头部元素。
E removeLast() ：去掉尾部元素。

索引
E element() : 获得头部元素，Queue 接口。
E getFirst() : 获得头部元素。
E getLast() : 获得尾部元素。
E peek() : 获得头部元素，Queue 接口。
E peekFirst() : 获得头部元素。
E peekLast() : 获得尾部元素。

迭代器
Iterator descendingIterator() : 返回倒序迭代器。
ListIterator listIterator(int index) : 返回从指定位置开始到末尾的迭代器。

LinkedList (Java SE 11 & JDK 11 )

HashSet 类

Set<Integer> set = new HashSet<>();

add, addAll,
remove, removeAll, removeIf, retainAll > contains, containsAll > size, isEmpty，clear
toArray, toString， forEach

HashMap 类

Map<Integer, Integer> map = new HashMap<>();

增删改 > V put(K key, V value) ：将指定的值与此映射中的指定键相关联。
putIfAbsent(K key, V value) ：如果不存在，则关联此映射。
void putAll(Map<? extends K,? extends V> m) ：将指定映射中的所有映射复制到此映射。
V remove(Object key) ：从此映射中删除指定键的映射（如果存在）。
boolean remove(Object key, Object value) > void clear() ：从此映射中删除所有映射。

查 > V get(Object key) ：返回指定键映射到的值，如果此映射不包含键的映射，则返回 null 。
V getOrDefault(Object key, V defaultValue) ：返回 key 相映射的的 value，如果给定的 key 在映射关系中找不到，则返回指定的默认值。
boolean containsKey(Object key) ：如果此映射包含指定键的映射，则返回 true 。
boolean containsValue(Object value) ：如果此映射将一个或多个键映射到指定值，则返回 true 。

其他 > boolean isEmpty() ：如果此映射不包含键 - 值映射，则返回 true 。
int size() ：返回此映射中键 - 值映射的数量。
Set<Map.Entry<K,V>> entrySet() ：返回此映射中包含的映射的 Set 视图。
Set<K> keySet() ：返回此映射中包含的键的 Set 视图。
Collection<V> values() ：返回此映射中包含的值的 Collection 视图。
String toString() ：将 Map 转换为键值对形式的字符串
forEach(BiConsumer<K, V> action) ：对 HashMap 中的每个映射执行指定的操作。

prices.forEach((key, value) -> {
         value = value - value * 10/100;
});

HashMap (Java SE 11 & JDK 11 )

Stack 类

Stack<String> stack = new Stack<>();

empty, pop, push, peek, size

Stack (Java SE 11 & JDK 11 )

PriorityQueue 类

PriorityQueue<int[]> queue = new PriorityQueue<>();
PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[0]==b[0]? a[1]-b[1] : a[0] - b[0]); //注意不要相减越 int 界限

add, offer 增加元素，前者超出大小限制报错，后者返回 false
remove, removeAll, removeIf, retainAll, poll 删除元素，前者为空报错，后者返回 null
element, peek 查看队首，前者为空报错，后者返回 null
contains, containsAll > isEmpty, size, forEach, toArray

PriorityQueue (Java SE 11 & JDK 11 )

BitSet 类

Java Bitset 类 | 菜鸟教程

Java 工具类

Arrays 类

Arrays.sort();

以 int 数组为例

三个类似 Object 函数 > static String toString(int[] a) : 返回指定数组内容的字符串表示形式。
static int hashCode(int[] a) : 根据指定数组的内容返回哈希码。
*static int equals(int[] a, int[] a2) ：如果两个指定的数组彼此相等，则返回 true 。

排序 > *static void sort(int[] a) : 将指定的数组按升序排序。
*static <T> void sort(T[] a, Comparator<? super T> c) ：根据指定比较器引发的顺序对指定的对象数组进行排序。

其他常用 > static <T> List<T> asList(T... a) ：返回由指定数组支持的固定大小的列表。
static int[] copyOf(int[] original, int newLength) ：使用 xxx 复制指定的数组，截断或填充，以使副本具有指定的长度。
static int[] copyOfRange(int[] original, int from, int to) ：将指定数组的指定范围复制到新数组中。
*static int binarySearch(int[] a, int key) ：使用二进制搜索算法在指定的字节数组中搜索指定的值。
*static void fill(int[] a, int val) : 将指定 val 分配给指定字节数组的每个元素。
*static int compare(int[] a, int[] b) ：字典顺序比较两个阵列。
*static <T> int compare(T[] a, T[] b, Comparator<? super T> cmp) ：使用指定的比较器按字典顺序比较两个 Object 阵列。
*static int mismatch(int[] a, int[] b) ：查找并返回两个数组之间第一个不匹配的索引，否则如果未找到不匹配则返回-1。

补充
大部分函数（在前面用 * 标出）同时有对应的范围操作函数，只需要在数组后增加两个参数 int fromIndex, int toIndex，如下述：
static void sort(int[] a, int fromIndex, int toIndex) : 按升序对数组的指定范围进行排序。
static <T> void sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c) ：根据指定比较器引发的顺序对指定对象数进行排序。

Arrays (Java SE 11 & JDK 11 )

Collections 类

max, min, sort, fill, reverse

Collections (Java SE 11 & JDK 11 )

Collections 工具类常用方法:

排序
查找, 替换操作
同步控制(不推荐，需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合)

void reverse(List list)//反转
void shuffle(List list)//随机排序
void sort(List list)//按自然排序的升序排序
void sort(List list, Comparator c)//定制排序，由Comparator控制排序逻辑
void swap(List list, int i , int j)//交换两个索引位置的元素
void rotate(List list, int distance)//旋转。当distance为正数时，将list后distance个元素整体移到前面。当distance为负数时，将 list的前distance个元素整体移到后面
 
int binarySearch(List list, Object key)//对List进行二分查找，返回索引，注意List必须是有序的
int max(Collection coll)//根据元素的自然顺序，返回最大的元素。 类比int min(Collection coll)
int max(Collection coll, Comparator c)//根据定制排序，返回最大元素，排序规则由Comparatator类控制。类比int min(Collection coll, Comparator c)
void fill(List list, Object obj)//用指定的元素代替指定list中的所有元素
int frequency(Collection c, Object o)//统计元素出现次数
int indexOfSubList(List list, List target)//统计target在list中第一次出现的索引，找不到则返回-1，类比int lastIndexOfSubList(List source, list target)
boolean replaceAll(List list, Object oldVal, Object newVal)//用新元素替换旧元素

Collections 提供了多个 synchronizedXxx() 方法·，该方法可以将指定集合包装成线程同步的集合，从而解决多线程并发访问集合时的线程安全问题。

我们知道 HashSet，TreeSet，ArrayList, LinkedList, HashMap, TreeMap 都是线程不安全的。Collections 提供了多个静态方法可以把他们包装成线程同步的集合。

最好不要用下面这些方法，效率非常低，需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合。

方法如下：

synchronizedCollection(Collection<T>  c) //返回指定 collection 支持的同步（线程安全的）collection。
synchronizedList(List<T> list)//返回指定列表支持的同步（线程安全的）List。
synchronizedMap(Map<K,V> m) //返回由指定映射支持的同步（线程安全的）Map。
synchronizedSet(Set<T> s) //返回指定 set 支持的同步（线程安全的）set。

函数用法补充

二分查找

def lower_bound(nums: list, target: int) -> int:
    '''
    return the target lower bound index in nums
    '''
    first, last = 0, len(nums)
    while first < last:
        mid = first + (last - first) // 2
        # 注意此处是小于号
        if nums[mid] < target:
            first = mid + 1
        else:
            last = mid
    return first

def upper_bound(nums: list, target: int) -> int:
    '''
    return the first idx in nums when nums[idx] > target
    '''
    first, last = 0, len(nums)
    while first < last:
        mid = first + (last - first) // 2
        # 注意直接把 < 改成 <=
        if nums[mid] <= target:
            first = mid + 1
        else:
            last = mid
    return first

最长递增子序列

public int findIndexAndReplace(List<Integer> arr, int num){
	int left = 0, right = arr.size()-1;
	if(num > arr.get(right)){
		arr.add(num);
		return right+1;
	}else{
		while(left < right){
			int mid = (left+right)/2;
			if(arr.get(mid) < num){
				left = mid+1;
			}else{
				right = mid;
			}
		}
		arr.set(right, num);
		return right;
	}
}

split 函数

Java String 的 split(String regex) 和 split(String regex, int limit) 方法.

. 、 $ 、 | 和 * 等转义字符，必须得加 \\。
多个分隔符，可以用 | 作为连字符。
Limit 默认为 0。Limit 大于 0，最多分成 limit 份； limit 等于 0，尽可能分割，并且省略字符串前后的空字符串；limit 小于 0，尽可能分割，不省略字符串前后的字符串。

练习题：
468. 验证 IP 地址

`Arrays.asList` 函数

引用数据类型使用

String[] myArray = { "Apple", "Banana", "Orange" }；
List<String> myList = Arrays.asList(myArray);

List<String> myList = Arrays.asList("Apple", "Orange");

基本数据类型使用
直接将基本数据类型数组放入到里面，会产生一个一个包含一个元素的列表。该元素就是 int 数组。

  int[] myArray = { 1, 2, 3 };
  List myList = Arrays.asList(myArray);

方案一：使用包装类数组来实现该功能。

Integer[] myArray = { 1, 2, 3 };
List myList = Arrays.asList(myArray);

方案二：Java 8 新引入的 API

List myList = Arrays.stream(intArray).boxed().collect(Collectors.toList());

生成的列表是固定大小的

String[] myArray = { "Apple", "Banana", "Orange" };
List<String> myList = Arrays.asList(myArray);
// myList.add("Guava"); 报错

可以修改大小的列表

  String[] myArray = { "Apple", "Banana", "Orange" };
  List<String> myList = new ArrayList<String>(Arrays.asList(myArray));
  myList.add("Guava");

常用语法段

// 创建列表并添加数据
map.putIfAbsent(arr[i], new ArrayList<Integer>());
map.get(arr[i]).add(i);

Java 函数用法补充

使用 Arrays.sort() 和 Lambda 表达式增加排序比较时，需要注意数组元素是否超过表示范围，如 Interger.MAX_VALUE - Interger.MIN_VALUE。

String.valueOf(nums[i])

Integer.bitCount(int i) 统计二进制中所有 1 的个数。

new Random().nextInt(i) [0,i) 的随机数

列表使用 isEmpty() 方法判空，O(1)的；size 是 On 的。
Collectors.toMap(Person::getName, Person::getPhoneNumber)
不要在 foreach 循环里进行元素的 remove/add 操作。

String [] s= new String[]{
    "dog", "lazy", "a", "over", "jumps", "fox", "brown", "quick", "A"
};
List<String> list = Arrays.asList(s);
Collections.reverse(list);
//没有指定类型的话会报错
s=list.toArray(new String[0]);

Arrays.asList()

ACM 模式

import java.util.*;
import java.io.BufferedInputStream;
 
public class Main{
    public static void main(String []args){
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext()){
            String str = scan.nextLine();
            String strs[] = str.split(" ");
            int n = 0;
            for(String s: strs){
                n += Integer.parseInt(s);
            }
            System.out.println(n);
        }
    }
}

热频考题 ⭐

编辑距离问题、快速排序和其中的 partition 算法、堆排序和建堆算法、大数加法和乘法、二叉树层级遍历的各种变形版本
二叉树、前缀和、字典树高频
单调栈
加速搜索的数据结构：树 (二叉搜索树，平衡树，红黑树等)，哈希表 (解决 hash 冲突的方法，如何构造、插入、删除)
排序算法 (原理，复杂度和稳定性)
Top K 问题 (以及很大数据量的情况)
链表反转：递归和非递归写法，必须一次写对
二叉树前中后序遍历：递归和非递归写法，可以想想为什么后序的非递归遍历要复杂一些
归并排序/快速排序/堆排序：自己写一个跑出来，然后背下来吧，我几乎每次面试前都要写一遍
链表的归并排序/快速排序
一些经典的回溯/全排列/搜索题目
字符串相关的动态规划，例如回文串
LRU 实现
C++智能指针 shared_ptr 的实现
栈和队列的模拟

书籍

《剑指 offer》必看的⭐
《背包问题九讲》

🪴 Obsidian Publish

探索

Java 常用数据结构

Java 数据结构类

常用包

输入输出

String 类

StringBuilder 类

Integer 类

ArrayList 类

LinkedList 类

HashSet 类

HashMap 类

Stack 类

PriorityQueue 类

BitSet 类

Java 工具类

Arrays 类

Collections 类

函数用法补充

二分查找

最长递增子序列

split 函数

`Arrays.asList` 函数

常用语法段

Java 函数用法补充

ACM 模式

热频考题 ⭐

书籍

目录

反向链接

🪴 Obsidian Publish

探索

Java 常用数据结构

Java 数据结构类

常用包

输入输出

String 类

StringBuilder 类

Integer 类

ArrayList 类

LinkedList 类

HashSet 类

HashMap 类

Stack 类

PriorityQueue 类

BitSet 类

Java 工具类

Arrays 类

Collections 类

函数用法补充

二分查找

最长递增子序列

split 函数

Arrays.asList 函数

常用语法段

Java 函数用法补充

ACM 模式

热频考题 ⭐

书籍

目录

反向链接

`Arrays.asList` 函数