算法题：设计LRU缓存
package EveryDay.Simulation;
import org.w3c.dom.NodeList;
import java.util.HashMap;
import java.util.List;
public class LRU {
public static void main(String[] args) {
}
static void solution(){
}
static class Node{
Node pre ;
Node next ;
int value;
int key;
Node(int value){
this.value = value;
}
Node(int key , int value){
this.key = key;
this.value = value;
}
}
static class MyList{
Node head = null;
Node tail = null;
//编写三个方法分别是
//添加尾节点
void add(Node node){
if(node == null) return;
if(head == null){//链表为空
head = node;
tail = node;
}else{
tail.next = node;
node.pre = tail;
tail = node;
}
}
//删去头节点
Node poll(){
if(head == null)return null;
if(head == tail)return head;
Node tmp = head;
head = head.next;
head.pre = null;
tmp.next = null;
return tmp;
}
//更新某个节点（要移动到末尾）
void moveToTail(Node node){
if(node == tail)return;
if(node == head){
head = head.next;
head.pre = null;
}else{
node.pre.next = node.next;
node.next.pre = node.pre;
}
node.pre = tail;
node.next = null;
tail.next = node;
tail = node;
}
}
static class MyCache{
HashMap<Integer , Node> map = new HashMap<>();
MyList list = new MyList();
int capacity;
MyCache(int cap){
this.capacity = cap;
}
//新增操作 更新操作
void set(int key , int value){
if(map.containsKey(key)){
//更新
map.get(key).value = value;
list.moveToTail(map.get(key));
}else{
//新增
Node node = new Node(key, value);
map.put(key , node);
list.add(node);
if(map.size() > capacity){
//新增时缓存满了
map.remove(list.poll());
}
}
}
//读取操作
Integer get(int key){
if(map.containsKey(key)){
Node tmp = map.get(key);
list.moveToTail(tmp);
return tmp.value;
}
return null;
}
}
}
算法题：最小的k个数（topk问题）
参考k神的代码，思想是使用快排，这是最优解：因为题中仅仅只说找出就行，那么tmp左边肯定是小于的数，若tmp的下标就是k那么说明tmp右边的k个数就是最小的k个数，Arrays.copyof就行。
https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/ohwddh/
算法题：寻找第k大
算法题：连续子数组的最大和
算法题：最长无重复子串
算法题：每k个节点反转链表
算法题：删除链表倒数第n个节点
算法题：岛屿数量
算法题：N皇后问题
参考题解：
https://leetcode-cn.com/problems/n-queens/solution/gen-ju-di-46-ti-quan-pai-lie-de-hui-su-suan-fa-si-/
了解n皇后的解题思想即可，面试出现频率不高。
n皇后的经典在于使用回溯进行剪枝，最终找到答案，其实上这是一个树的深度遍历
