Java 刷题常用知识

常用容器

List

接口：java.util.List<>

实现：

• java.util.ArrayList<> ：变长数组
• java.util.LinkedList<> ：双链表

函数：

• add()：在末尾添加一个元素
• clear()：清空
• size()：返回长度
• isEmpty()：是否为空
• get(i)：获取第i个元素
• set(i, val)：将第i个元素设置为val

栈

类：java.util.Stack<>

函数：

• push()：压入元素
• pop()：弹出栈顶元素，并返回栈顶元素
• peek()：返回栈顶元素
• size()：返回长度
• empty()：栈是否为空
• clear()：清空

队列

接口：java.util.Queue<>

实现：

• java.util.LinkedList<>：双链表
• java.util.PriorityQueue<>：优先队列
  • 默认是小根堆，大根堆写法：new PriorityQueue<>(Collections.reverseOrder())

函数：

• add()：在队尾添加元素
• remove()：删除并返回队头
• isEmpty()：是否为空
• size()：返回长度
• peek()：返回队头
• clear()：清空

Set

接口：java.util.Set<K>

实现：

• java.util.HashSet<K>：哈希表
• java.util.TreeSet<K>：平衡树

函数：

• add()：添加元素
• contains()：是否包含某个元素
• remove()：删除元素
• size()：返回元素数
• isEmpty()：是否为空
• clear()：清空

java.util.TreeSet多的函数：

• ceiling(key)：返回大于等于key的最小元素，不存在则返回null
• floor(key)：返回小于等于key的最大元素，不存在则返回null

Map

接口：java.util.Map<K, V>

实现：

• java.util.HashMap<K, V>：哈希表
• java.util.TreeMap<K, V>：平衡树

函数：

• put(key, value)：添加关键字和其对应的值
• get(key)：返回关键字对应的值
• containsKey(key)：是否包含关键字
• remove(key)：删除关键字
• size()：返回元素数
• isEmpty()：是否为空
• clear()：清空
• entrySet()：获取Map中的所有对象的集合
• Map.Entry<K, V>：Map中的对象类型
• getKey()：获取关键字
• getValue()：获取值

java.util.TreeMap<K, V>多的函数：

• ceilingEntry(key)：返回大于等于key的最小元素，不存在则返回null
• floorEntry(key)：返回小于等于key的最大元素，不存在则返回null

Pair

类：javafx.util.Pair<K, V>

例如：Pair<String, Integer> p = new Pair<>("a", 1)

函数：

• getKey()：获取关键字
• getValue() ：获取值

优先队列

接口：java.util.Queue<>

实现：java.util.PriorityQueue<>：优先队列

• 默认是小根堆，大根堆写法：new PriorityQueue<>(Collections.reverseOrder())

• 第二种定义方式

  // 定义大根堆
  PriorityQueue<Integer> queMin = new PriorityQueue<Integer>((a, b) -> (b - a));
  // 定义小根堆
  PriorityQueue<Integer> queMax = new PriorityQueue<Integer>((a, b) -> (a - b));

常用方法：

• add(e)：在队尾插入元素，并调整堆结构。
• offer(e)：在队尾插入元素，并调整堆结构。
• remove(e)：获取队头元素并删除，并调整堆结构。
• poll(e)：获取队头元素并删除，并调整堆结构。
• element()：返回队头元素，不删除
• peek()：返回队头元素，不删除
• isEmpty()：判断队列是否为空
• size()：获取队列中的元素个数
• clear()：清空队列
• contains(o)：判断队列中是否包含指定元素
• iterator()：迭代器

其他

给二维数组赋初值

int[][] arr = new int[100][100];
for(int[] a: arr) 
    Arrays.fill(a, Integer.MAX_VALUE);

对数组指定范围的元素进行排序

Arrays.sort(arr, start, end)：对数组中[start, end)元素进行排序

数组自定义排序

练习题目：把数组排成最小的数

int[][] arr = new int[10][2];
Arrays.sort(arr, new Comparator<int[]> {
	@Override
    publice int compare(int[] o1, int[] o2) {
        return (o1[0] + o2[1]) - (o2[0] + o2[1]);
    }
});

使用lambda表达式自定义排序规则

int[][] arr = new int[10][2];
Arrays.sort(arr, (o1, o2) -> {
    return (o1[0] + o1[1]) - (o2[0] + o2[1]);
});

ArrayList去重

通过LinkedHashSet进行去重，LinkedHashSet是有序不可重复的

List<Integer> list = new ArrayList<>(Arrays.asList(1,2,2,3,3,1,2));
Set<Integer> set = new LinkedHashSet<>(list); // 去重，排序

Java8新特性stream()的distinct()方法

List<Integer> list = new ArrayList<>(Arrays.asList(1,2,2,3,3,1,2));
List<Integer> newList = list.stream().distinct().collect(Collectors.toList());

使用contains()方法

List<Integer> list = new ArrayList<>(Arrays.asList(1,2,2,3,3,1,2));
List<Integer> newList = new ArrayList<>();
for(Integer x : list) {
    if(!newList.contains(x)) 
        newList.add(x);
}

利用HashSet()无序唯一的特性

List<Integer> list = new ArrayList<>(Arrays.asList(1,2,2,3,3,1,2));
List<Integer> newList = new ArrayList<>();
Set<Integer> set = new HashSet<>();

for(Integer x : list) {
    if(set.add(x)) 
        newList.add(x);
}

HashMap的7种遍历方式与性能分析

HashMap遍历从大的方向来说，可以分为四类：

1. 迭代器（Iterator）方式遍历
2. For Each方式遍历
3. Lambda表达式遍历（JDK 1.8+）
4. Streams API遍历（JDK 1.8+）

每种类型下又有不同的实现方式，因此具体的遍历方式又可以分为以下7种：

1. 使用迭代器（Iterator）EntrySet的方式进行遍历。
2. 使用迭代器（Iterator）KeySet的方式进行遍历。
3. 使用for each EntrySet的方式进行遍历。
4. 使用for each KeySet的方式进行遍历。
5. 使用Lambda表达式的方式进行遍历。
6. 使用Streams API单线程的方式进行遍历。
7. 使用Streams API多线程的方式进行遍历。

针对如下的HashMap进行7种方式遍历。

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

迭代器EntrySet

既安全又高效。首选。

Interator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
while(iterator.hasNext()) {
    Map.EntrySet<Integer, String> entry = iterator.next();
   	Integer key = entry.getKey();
    String value = entry.getValue();
}

迭代器keySet

Iterator<Integer> iterator = map.KeySet().iterator();
while(iterator.hasNext()) {
    Integer key = iterator.next();
  	String value = map.get(key);  // 有查询了一遍map，所以性能比EntrySet差
}

For Each EntrySet

for(Map.EntrySet<Integer, String> entry : map.entrySet()) {
    int key = entry.getKey();
    String value = entry.getValue();
}

For Each KeySet

for(Integer key : map.KeySet()) {
    String value = map.get(key);
}

Lambda

map.forEach((key, value) -> {
	System.out.println(key);
    System.out.println(value);
});

Streams API 单线程

map.entrySet().stream().forEach((entry) -> {
	Integer key = iterator.next();
  	String value = entry.getValue();
});

Streams API 多线程

map.entrySet().parallelStream().forEach((entry) -> {
    Integer key = iterator.next();
  	String value = entry.getValue();
});