API

发表于 更新于 分类于

算法

Arrays

填充

1
Arrays.fill(arr, begin, end, val); //左闭右开

数据结构

1. List

1.1 基本API

  • add(E e):尾部追加
  • add(int index, E e):在指定位置插入,后面的整体右移
  • get(int index):按下标读
  • set(int index, E e):覆盖写,长度不
  • remove(int index) / remove(Object o):一个删位置,一个删值
1
2
list.remove(1);                  // 删的是下标 1
list.remove(Integer.valueOf(1)); // 才是删元素 1
  • size():长度
  • isEmpty():是否为空

1.2 三种遍历方式

  • for 下标循环:
    可控、最安全,删除时要注意下标回退或倒序遍历。
  • 增强 for (for (E e : list)):
    只读视角,禁止结构性修改,否则直接 ConcurrentModificationException。
  • Iterator:
    唯一官方允许的“遍历中删除”方式,用 it.remove(),不是 list.remove()。
1
2
3
4
5
6
7
8
9
10
11
12
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
    if (it.next() == 3) { //必须先next再remove
        it.remove(); //remove()只能删“最近一次 `next()` 返回的元素”
    }
}

Iterator<Integer> it = list.iterator();
while(it.hasNext()){
	...
	Integer curr = it.next(); //会返回当前元素值
}

1.3 批量操作

  • addAll(Collection c):拼接
  • removeAll(Collection c):差集
  • retainAll(Collection c):交集
  • containsAll(Collection c):包含关系判断
    我认为 retainAll 特别适合表达“保留合法元素集合”这种语义,比手写循环更不容易出 bug。

1.4 查找相关

  • contains(Object o):是否存在
  • indexOf(Object o) / lastIndexOf(Object o):第一次 / 最后一次出现的位置
    注意一点:这些都是线性扫描,在 ArrayList 上是 O(n)。如果你在刷题里频繁查存在性,那大概率结构选错了,应该换 Set 或 Map。

1.5 具体实现类

1.5.1 ArrayList
初始化
1
2
3
new ArrayList<>();
new ArrayList<>(int initialCapacity);
new ArrayList<>(Collection<? extends E> c);//Arrays.asList(...)
1.5.2 LinkedList: 双向链表

实现了List<E>, Deque<E>, Queue<E>三个接口, 既能当 List 用,也能当队列、当双端队列用

初始化
1
2
3
4
5
6
7
//Integer
LinkedList<Integer> list = new LinkedList<>(Arrays.asList(1, 2, 3)); //注意只能是引用数据类型

//int类型
int[] a = {1, 2, 3};
LinkedList<Integer> list = new LinkedList<>();
for (int x : a) list.add(x);

作为双端队列:

1
2
3
4
5
6
7
8
9
10
addFirst(E e)
addLast(E e)
removeFirst()
removeLast()
getFirst()
getLast()

offer(E e)    // 入队（尾）
poll()        // 出队（头）
peek()        // 看头，不删

offer & poll 和add / remove 的区别不在逻辑,而在失败策略:

  • add / remove:失败抛异常
  • offer / poll:失败返回 false / null
    刷题里我建议你统一用 offer / poll / peek,更稳。

2. HashMap

computeIfAbsent()
1
2
3
4
5
6
7
8
9
10
11
default V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {  
    Objects.requireNonNull(mappingFunction);  
    V v;  
    V newValue;  
    if ((v = (V)this.get(key)) == null && (newValue = (V)mappingFunction.apply(key)) != null) {  
        this.put(key, newValue);  
        return newValue;  
    } else {  
        return v;  
    }  
}

3. PriorityQueue<>()

  • 初始化

    PriorityQueue pq = new PriorityQueue<>( (a,b)->a-b )

增加元素
pq.offer() 会加入null值的节点, 所以加入时要判断