代码实现参见github/algorithm中各个类别下wz包中的代码。
1.数据结构中常犯错误
1.1 数组
- 1）空数组的写法——{}
private static final Object[] EMPTY_ELEMENTDATA = {};
- 2）入参检查
比如数组的索引有效性检查 - 3）引用类型数组删除时需要置为null，GC用
// clear to let GC do its work
elementData[--size] = null;
- 4）数组扩容时新容量各种情况的处理（容易遗漏情况）
private void ensureExplicitCapacity(int minCapacity) {
int oldCapacity = elementData.length;
if (minCapacity - oldCapacity > 0) {
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 忘记处理newCapacity比minCapacity小的情况
// 即使newCapacity溢出，newCapacity - minCapacity也仍大于0
if (newCapacity - minCapacity < 0) {
newCapacity = minCapacity;
}
// 忘记处理溢出的情况
if (newCapacity - MAX_CAPACITY > 0) {
if (newCapacity < 0) {
throw new OutOfMemoryError();
}
newCapacity = newCapacity > MAX_CAPACITY ? Integer.MAX_VALUE : MAX_CAPACITY;
}
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
1.2 泛型数组
- 5）set(int, E), add(E); remove(Object), contains(Object)
涉及到equals的，入参都是Object
doSomeReading(S<? extends Foo> foos) {
foos.contains(foo);
foos.contains(subFoo);
}
如果contains(E e)函数只能接受一个明确类型的参数。
但是在doSomeReading函数中，编译器无法确定到底是什么类型，它是Foo类型，还是SubFoo类型，还是SubSubFoo类型？
因此这里为了适应S<? extends Foo>，将contains的参数类型设置为Object，同理remove等的参数类型也为Object
- 6）删除的时候，注意前置条件：数组中还有元素
1.3 双链表
- 7）确保状态更新：add remove时会忘了更新size
- 8）循环语句，尤其是while，也不要忘了三要素
控制变量的初始化
循环条件
循环控制变量的更新
1.4 数组实现的栈
- 9）定义清楚各个状态变量的含义
/**
* 指向栈顶元素，push操作时是减少head
*/
private int head;
/**
* 指向栈底元素的下一个，（不考虑大小）因此栈中元素范围[head, tail)
*/
private int tail;
- 10）环形栈push注意事项
普通写法：
// 这里错写成head--导致不更新，忘记了+elements.length，导致负数报错
head = (--head + elements.length) % elements.length;
elements[head] = e;
高效写法，确保数组大小为2的幂次方
elements[head = (head - 1) & (elements.length - 1)] = e;
- 11）栈为空和栈满
（不考虑大小）因此栈中元素范围[head, tail)，因此栈空的条件是
public boolean isEmpty() {
return head == tail;
}
但要注意：push的时候，head == tail表示栈满，但此时会进行扩容，会重置head和tail
- 12）扩容
注意新容量溢出情况；
特别注意：不要忘了更新head tail
// 这里忘了更新head tail，导致出现错误
head = 0;
tail = rightNum;
1.5 双链表实现的栈
- 13）push
首先，建议先画图再写代码，注意更新时除了结点之间之间更新之外，不要忘了size
其次，注意特殊情况，栈为空情况 - 14）pop
注意将删除结点的element和next置为null，help GC
1.6 数组队列
编程时特别注意的事情：
a）分析清楚方法的前置和后置条件
前置条件：输入参数需要满足什么要求
后置条件：操作完要处于什么状态
b）注意对对象状态的更新，这里必须要注意更新head tail elements，若有size，也需注意size
c）对于集合类的操作，需要在删除元素时，将相应的slot置为null'
- 15）出队
首先，不要忘了检查队列是否为空（前置条件）
其次，对于集合类，删除时，不要忘了置为null，help GC
public E dequeue() {
// 忘了检测当队列为空时的错误
if (isEmpty()) {
throw new IllegalStateException("queue is empty!");
}
E value = (E)elements[head];
// 这里必须将elements[head]置为null，忘了
elements[head] = null;
head = (head + 1) & (elements.length - 1);
return value;
}
1.7 双链表队列
无
1.8 优先队列
- 16）注意清晰的定义
实现最大堆，这里特别注意索引是从1开始的；
另外，数组中1..size已经存储了元素，size本身也表示堆中存储元素的个数 - 17）siftUp siftDown
类似于插入排序，while循环内是queue[parent]，循环外也是；
在循环内涉及到right和left，也要进行索引是否超出范围的检查。
private void siftDown(int index, int e) {
int parent = index;
int left = index << 1;
int right = left + 1;
int half = size >> 1;
while (parent <= half) {
// 简化写法，合并左右对称写法
int child = left;
int c = queue[child];
// 这个地方少了对right索引的判断，right可能会超出范围！
if (right < size && queue[right] > queue[left]) {
c = queue[child = right];
}
if (queue[child] <= e) {
break;
}
queue[parent] = c;
parent = child;
left = parent << 1;
right = left + 1;
}
// 最后一个赋值要放在循环外，之前放在break里面，会导致e无法放到正确的位置！
queue[parent] = e;
}
1.9 索引优先队列
- 18）注意清晰的定义，结合多路归并排序来透彻理解
在堆数组中存储索引i，同时通过数组keys将索引i与key关联起来，保证堆性质的比较还是通过key来实现的（只不过需要通过i来获取对应的key，多了这一道取值的过程）
// 实际的堆数组，所有的堆操作都是在pq上进行，但是这里存储的是索引，比较的时候需要通过索引关联的key来进行比较
private int[] pq;
// 索引关联的key
private K[] keys;
// 索引在堆数组中的位置，这个与pq是相反的，引入这个数组的核心目的是能够通过索引快速找到存储在堆数组中的位置
private int[] qp;
- 19）对索引的范围的小心处理，在while循环内部少了检查
1.10 链表形式哈希表（非常经典）
- 20）putVal
对于while循环，要清楚各个变量的定义以及三个要素，并且不要忘了更新size。
如下，特别重要的是p与node的含义：
p——是(hash,key)的前驱结点，两种情况：在链表末尾和在链表中间
node——是(hash, key)结点本身，两种情况：在链表末尾（此时node为null）和在链表中间
private V putVal(int hash, K key, V value) {
// 数组table为空
Node<K,V> p;
int i;
if (table == null || table.length == 0) {
table = resize();
table[hash & (table.length - 1)] = newNode(hash, key, value, null);
} else if ((p = table[i = (hash & (table.length - 1))]) == null) {
// slot为空
table[i] = newNode(hash, key, value, null);
} else {
// 遍历链表，查看是否有key，如果有则更新value；否则放到链表尾部
Node<K,V> node;
if (p.hash == hash && ((p.key == key) || Objects.equals(key, p.key))) {
node = p;
} else {
node = p.next;
do{
// 到了链表末尾，同时是首先检测node是否为null
if (node == null) {
p.next = newNode(hash, key, value, null);
break;
}
// 这里需要node不为null
if (node.hash == hash && ((node.key == key) || Objects.equals(key, node.key))) {
break;
}
p = node;
node = node.next;
} while (p != null); // 此处之前写的是node != null，导致无法在链表末尾插入
}
if (node != null) {
afterNodeAccess(node);
return node.setValue(value);
}
}
// 不要忘了更新size，并判断是否扩容
size++;
if (size > threshold) {
resize();
}
afterNodeInsertion();
return null;
}
- 21）removeNode
前置条件：哈希表为空
特殊情况：删除的是链表首元素
后置条件：不要忘了更新size - 22）resize
数组扩容各种情况的考虑
将旧表数组移动到新表中时，需要将旧表对应位置置为null
1.11 开放寻址法哈希表
- 23）删除
关键在于删除，需要将该位置之后的数据重新插入 - 24）建议养成编程新习惯
首先列出方法的前置条件、后置条件以及各种情况；
其次根据这些条件写出程序大体轮廓
最后在深入各个细节进行处理
1.12 缓存LRU实现——LinkedHashMap
- 25）afterNodeAccess、linkNodeLast
e.next不要忘了置为null（画图，另一方面，对于链表情况，要注意检查一下结点的各个域是否更新正确）
不要忘了对特殊情况的处理
1.13 并查集（不相交集合）
- 26）注意对count的更新
- 27）find
对于递归方法，注意不要if和while搞混了
