【java基础】使用java写算法题的注意事项

特殊数据结构

1. 小根堆：PriorityQueue

PriorityQueue<Integer> heap=new PriorityQueue(); 
// 使用优先队列来实现小根堆，队首元素就是堆顶元素，是当前队列中最小的元素
// 实现大根堆的话需要重写compare

1. 有序的hash表：LinkedHashMap

在实现LRU时会要用到LinkedHashMap，它本身只能维护插入顺序（新插入的数据永远会保持在map的尾部），但是，如果在创建的时候将AccessOrder设置为true，此时LinkedHashMap会同时具备维护访问顺序的能力，使用get函数访问的键值对会自动地移动到map的尾部。简直就是实现LRU算法的最佳选择。

LinkedHashMap<Integer,Integer> cache
 this.cache=new LinkedHashMap<>(capacity,1,true);
 //将LinkedHashMap构造函数中的AccessOrder设置为true，会自动按照访问顺序更新map中的顺序