Java 刷题集合类

快速查看

方法
String charAt toCharArray split substring indexOf lastIndexOf replace length
List add remove get size subList
Stack push pop peek isEmpty size
Queue offer poll peek isEmpty size
PriorityQueue offer poll peek isEmpty size
Set add remove contains isEmpty size first(TreeSet) last(TreeSet)
Map put get getOrDefault containsKey containsValue keySet values isEmpty size

静态数组 Static Array

性质:初始化后长度不能变了

初始化

一维

// Type[] names = new Type[capacity];
int[] a = new int[10];
String[] s = new String[3];

// Type[] names = new Type[]{Tpye ...a};
int[] a = new int[]{1, 2, 3, 4};    // int[] a = {1, 2, 3, 4};
char[] b = new char[]{'a', 'b'};    // char[] b = {'a', 'b'};
String[] s = new String[]{"hello", "world"};

// 创建
Set<String> set = new Set[105]; // 每一个指向一个null
for (int i = 0; i < 105; i++) jud[i] = new HashSet<>();  // 每个Set现在才被创建出来

二维

// 二维
int[][] c = new int[10][10];

instance属性

length

.length 记得是属性而不是方法 arr.length 没有()

技巧

Arrays.sort从小到大排序

Arrays.sort(int[] arr) Arrays.sort(int[] arr, int fromIndex, int toIndex) 数组类型只要实现了Comparable接口就行(基本数据类型int也可以)

Arrays.sort(int[] arr, int fromIndex, int toIndex, 比较器); //一定是需要泛型

Arrays.sort(arr, (o1, o2) -> o2 - o1); //数组全部 从大到小排序 跟Collections.sort()一样

Arrays.sort(arr, 0, 3, (o1, o2) -> o2 - o1); //从大到小排序,只排序[0, 3)

Arrays.fill填满一个数组

int[] a = new int[5];
Arrays.fill(a, 1);

Arrays.copyOf / arr.clone()复制一个数组(二维数组也可以)

int[] a = new int[5];
int[] newA = Array.copyOf(a, 5);
// or
int[][] a = {{1}, {1,2}, {1,2,3}, {1,2,3,4}, {1,2,3,4,5}}; // 不是5*5,第一维1 2 3 4 5
int[][] newa = a.clone(); // 不是5*5矩阵

动态数组 List & Dynamic Array

性质: 可以动态扩容的数组

初始化

常规 - ArrayList更常用

List<Integer> array = new ArrayList<>();    // 数组
List<Integer> list = new LinkedList<>();    // 链表

接受一个Stack、Set等容器为参数 - 以Set举例

// Set<Integer> a = new HashSet....
List<Integer> b = new ArrayList<>(a);

instance方法(List接口方法)

方法:get, size, add, remove, subList

get

.get(int index)    // 返回元素位置在index的元素e --- array O(1), list O(n)

size

.size()    // 返回数组长度 --- O(1)

add

.add(E e)    // 在尾部添加一个元素e --- O(1)
.add(int index, E e)    // 在index位置插一个元素e --- O(n)

remove

.remove(int index)    // 删除位于index的元素,并返回删除元素e --- 删除最后元素为O(1), 其余为O(n)
//删除最后元素 list.remove(list.size() - 1);

subList

.subList(int from, int to)    // 相当于返回原数组的一个片段,但不要对其进行改动,改动会影响原数组 --- O(1)
// List<Integer> list, 对原来的list和返回的list做的“非结构性修改”(non-structural changes),
//都会影响到彼此对方. 如果你在调用了sublist返回了子list之后,如果修改了原list的大小,那么之前产生的子list将会失效,变得不可使用

技巧

Collections.sort(list); 从小到大排序
Collections.sort(list, (o1, o2) -> o2 - o1); 从大到小排序, 第二个参数为一个比较器
``

栈 Stack

性质: 先进后出

初始化 (唯一初始化方式)

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

instance方法

方法:push, pop, peek, isEmpty, size

push

.push(E e);    // 入栈元素e, 返回值为元素e --- O(1)

pop

.pop();    // 出栈一个元素,返回出栈元素e --- O(1)

peek

.peek();    // 查看栈顶元素, 返回值为栈顶元素e --- O(1)

isEmpty

.isEmpty()    // 若栈空返回true, 否则返回false --- O(1)

size

.size()    // 返回栈中元素个数 --- O(1)

队列 Queue

性质:先进先出
通过实现实现队列接口的LinkedList<>();

初始化

使用LinkedList实现Queue接口初始化

Queue<Integer> q = new LinkedList<>();

把集合如Stack、Set、List等Collection作为参数

// Set<Integer> set = new HashSet<>();
Queue<Integer> q = new LinkedList<>(set);

instance方法 (Queue接口)

方法:offer, poll, peek, isEmpty, size

offer

.offer(E e);    // 队尾加入元素e。 若成功入队返回值true,否则返回false --- O(1)

poll

.poll();    // 出队首,返回出队元素e --- O(1)

peek

.peek();    // 查看队首元素, 返回值队首元素e --- O(1)

isEmpty

.isEmpty()    // 若队空返回true, 否则返回false --- O(1)

size

.size()    // 返回队中元素个数 --- O(1)

优先队列 PriorityQueue (Heap)

性质:底层是一颗数, 以小根堆为例。对于任意结点来说,该节点的值比其左右孩子的值都要小。 (就是最上面的结点最小)。 大根堆类似,最上面结点最大

初始化

小根堆

Queue<Integer> minH = new PriorityQueue<>();    // 小根堆,默认大小为11 相当于  new PriorityQueue<>(11)
Queue<Integer> minH = new PriorityQueue<>(100);  // 定义一个默认容量有100的小根堆。在当中增加元素会扩容,只是开始指定大小。不是size,是capacity

大根堆

Queue<Integer> maxH = new PriorityQueue<>((i1, i2) -> i2 - i1);    // 大根堆,默认大小为11 相当于  new PriorityQueue<>(11, (i1, i2) -> i2 - i1)
Queue<Integer> maxH = new PriorityQueue<>(100, (i1, i2) -> i2 - i1);    // 定义一个默认容量有100的大根堆。在当中增加元素会扩容,只是开始指定大小

instance方法 (Queue接口方法)

方法:offer, poll, peek, isEmpty, size

offer

.offer(E e);    // 在堆中加入元素e,并调整堆。若成功入堆返回值true,否则返回false --- O(logN)

poll

.poll();    // 弹出堆顶元素,并重新调整堆,返回出队元素e --- O(logN)

peek

.peek();    // 查看堆顶元素, 返回值堆顶元素e --- O(1)

isEmpty

.isEmpty()    // 若队空返回true, 否则返回false --- O(1)

size

.size()    // 返回队中元素个数 --- O(1)

技巧

从小到大(或从大到小弹出元素)

while (!pq.isEmpty()) {}

集合 Set - HashSet

性质:Set中没有重复元素,重复添加的元素抛弃

初始化

默认构造函数

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

把集合如Stack、Queue、List等Collection作为参数

// List<Integer> list = new ArrayList<>....;
// Set<Integer> set = new HashSet<>(list);

instance方法 (Set接口方法)

方法:add, remove, contains, isEmpty, size

add

.add(E e);    // 在集合中添加元素E e, 若成功添加则返回true,若集合中有元素e则返回false --- O(1)

remove

.remove(E e);    // 在集合中删除元素e,若删除成功返回true;若集合中没有元素e,返回false --- O(1)

contains

.contains(E e);    // 若存在元素e,则返回true,否则返回false --- O(1)

isEmpty

.isEmpty()    // 若集合为空返回true, 否则返回false --- O(1)

size

.size()    // 返回集合中中元素个数 --- O(1)

first (TreeSet)

.first()    // 返回集合里的最小值(若给了比较器从大到小则是返回最大值)

last (TreeSet)

.last()    // 返回集合里的最大值(若给了比较器从大到小则是返回最小值)

散列表 HashMap

性质:使用健值对的方式存储数据 <Key,Value>

初始化

<Key, Value> key和value是任何Collection或任何Object

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

instance方法 (Map接口方法)

方法:put, get, getOrDefault, containsKey, containsValue, keySet, values, isEmpty, size

put

.put(K key, V value);    // 在Map中加入键值对<key, value>。返回value值。如果Map中有key,则replace旧的value --- O(1)

get

.get(K key);    // 返回Map中key对应的value。若Map中没有该key,则返回null --- O(1)

getOrDefault

.getOrDefault(K key, V defaultValue);    // 返回Map中key对应的value。若Map中没有该key,则返回defaultValue --- O(1)

// For example:
// Map<Character, Integer> map = new HashMap<>();
// if (...)    // 如果发现k,则k在Map中的值加1。没一开始没有k,则从0开始加1。(相当于给了key在Map中的一个初试值)
    map.put('k', map.getOrDefault('k', 0) + 1);

containsKey

.containsKey(Key key);    // 在Map中若存在key,则返回true,否则返回false --- O(1)

.get(x) == null // 可以代替改用法

containsValue

.containsValue(V value);    // 在Map中若存在value,则返回true,否则返回false --- O(1)

keySet

.keySet();    // 返回一个Set,这个Set中包含Map中所有的Key --- O(1)

// For example:
// We want to get all keys in Map
// Map<Character, Integer> map = new HashMap<>();
for (Character key : map.keySet()) {
    // Operate with each key
}

values

.values();    // 返回一个Collection<v>,里面全是对应的每一个value --- O(1)

// For example:
// We want to get all values in Map
// Map<Character, Integer> map = new HashMap<>();
for (Integer value : map.values()) {
    // Operate with each values
}

isEmpty

.isEmpty()    // 若Map为空返回true, 否则返回false --- O(1)

size

.size()    // 返回Map中中键值对<K, V>的个数 --- O(1)

字符串

String

性质:不可变量(相当于只读final修饰)
每个位置元素是个char

初始化

字符串复制初始化
String s = "abc";
基于另外一个字符串
// s = "abc"
String s2 = new String(s);
基于char[]
// s = "abc";
// char[] c = s.toCharArray();
String s3 = new String(c);

// 可以偏移
// public String(char value[], int offset, int count)
String s4 = new String(c, 1, 2);    // [offset, offset + count) [)

// 把char[] 变成字符串
char[] ch = {'a', 'b', 'c'};
String.valueOf(ch);

类方法

String.valueOf( 一个参数Object/基本数据类型 ) 返回传入参数obj的toString(),若为空返回字符串"null"。 若为基本类型调用其 包装类的toString方法(Integer.toString(i)

instance方法

方法: charAt, length, substring, equals, indexOf, lastIndexOf, replace, toCharArray, trim, split, toLowerCase, toUpperCase

charAt
.charAt(int index);    // 返回index位置的char --- O(1)
length
.length();    // 返回字符串长度 --- O(1)
substring
.substring(int beginIndex, int endIndex);    // 返回字符片段[beginIndex, endIndex) --- O(n)

.substring(int beginIndex);    // 返回字符片段[beginIndex, end_of_String) 就是从beginIndex开始后面的 ---- O(n)
indexOf 是(暴力查找字符串,不是KMP)
.indexOf(String str)    // 返回str第一个出现的位置(int),没找到则返回-1。 --- O(m * n) m为原串长度, n为str长度
// (假如要找一个字符char c,str可以表示成String.valueOf(c),然后作为参数传进去.

s.indexOf(String str, int fromIndex);    // 同上,但从fromIndex开始找 --- O(m * n)
lastIndexOf
.lastIndexOf(String str);    // 返回str最后出现的位置(int),没找到则返回-1。 --- O(m * n) m为原串长度, n为str长度
// (假如要找一个字符char c,str可以表示成String.valueOf(c),然后作为参数传进去.

.lastIndexOf(String str, int fromIndex);    // 同上,
//但从fromIndex开始从后往前找 [0 <- fromIndex] --- O(m * n)
replace 只能换char
.replace(char oldChar, char newChar);    // 返回一个新字符串String,其oldChar全部变成newChar --- O(n)
toCharArray
.toCharArray();    // 返回char[] 数组。 把String编程字符数组 --- O(n)
trim 去除前后空格
.trim();    // 返回去除前后空格的新字符串 --- O(n)
split 以什么分开
.split(String regex);    // 返回 String[],以regex(正则表达式)分隔好的字符换数组。 ---- O(n)

// For example
// 从非"/"算起 若"/a/c" -> 会变成"" "a" "c"
String[] date = str.split("/");     // date[0]:1995 date[1]:12 date[2]:18 --- O(n)
toLowerCase, toUpperCase 转换大小写
s = s.toLowerCase();    // 返回一个新的字符串全部转成小写 --- O(n)
s = s.toUpperCase();    // 返回一个新的字符串全部转成大写 --- O(n)

技巧

通过+连接其他字符串, 但是是两个组成一个新的字符串,有开销。最好用StringBuilder

StringBuilder

初始化

StringBuilder sb = new StringBuilder();

instance方法

方法: append, charAt, length, setCharAt, insert, deleteCharAt, delete, reverse, toString

charAt
.charAt(int index);    // 返回index位置的char --- O(1)
length
.length();    // 返回缓冲字符串长度 --- O(1)
setCharAt
.setCharAt(int index, char ch);    // 设置index位置的char为ch --- O(1)
insert
.insert(int offset, String str);    // 在offer位置的插入字符串str--- O(m + n)
deleteCharAt
.deleteCharAt(int index);    // 删除index位置的char --- O(n)

.deleteCharAt(sb.length() - 1);    // 删除最后一个char --- O(1)
delete
.delete(int start, int end);    // 删除[start, end)位置的char --- O(n)
reverse
.reverse();    // 反转缓存字符串 --- O(n)
toString
.toString();    // 返回一个与构建起或缓冲器内容相同的字符串 --- O(n)