
luckydog
V1
2022/03/21阅读:42主题:默认主题
数据结构(146,155,208)
数据结构
LRU缓存(最近最少使用)
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存. int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1. void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字.
来源:力扣(LeetCode)
//哈希表+双向链表
class LRUCache {
class DLinkedNode{
int key;
int value;
DLinkedNode prev;
DLinkedNode next;
public DLinkedNode() {
}
public DLinkedNode(int key, int value) {
this.key = key;
this.value = value;
}
}
private Map<Integer, DLinkedNode> cache = new HashMap<>();
private int capacity;
private int size;
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
//初始化构造一个伪头部和尾部
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return -1;
}
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node == null) {
DLinkedNode newNode = new DLinkedNode(key, value);
cache.put(key, newNode);
addToHead(newNode);
++size;
if (size > capacity) {
DLinkedNode tail = removeTail();
cache.remove(tail.key);
--size;
}
}else {
node.value = value;
moveToHead(node);
}
}
//把一个节点移到头部
private void moveToHead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}
//将一个节点变成头节点
private void addToHead(DLinkedNode node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
//删除节点
private void removeNode(DLinkedNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
//删除尾结点
private DLinkedNode removeTail() {
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}
}
最小栈
//借用一个栈表示栈顶元素进栈之后栈的最小值
class MinStack {
Deque<Integer> xstack;
Deque<Integer> minStack;
public MinStack() {
xstack = new LinkedList<>();
minStack = new LinkedList<>();
minStack.push(Integer.MAX_VALUE);
}
public void push(int val) {
xstack.push(val);
minStack.push(Math.min(minStack.peek(), val));
}
public void pop() {
xstack.pop();
minStack.pop();
}
public int top() {
return xstack.peek();
}
public int getMin() {
return minStack.peek();
}
}
Trie 前缀树
class Trie {
private Trie[] children;
private boolean isEnd;
public Trie() {
children = new Trie[26];
isEnd = false;
}
public Trie searchPrefix(String prefix) {
Trie node = this;
for (int i = 0; i < prefix.length(); i++) {
int index = prefix.charAt(i) - 'a';
if (node.children[index] == null) {
return null;
}
node = node.children[index];
}
return node;
}
public void insert(String word) {
Trie node = this;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (node.children[index] == null) {
node.children[index] = new Trie();
}
node = node.children[index];
}
node.isEnd = true;
}
public boolean search(String word) {
Trie node = searchPrefix(word);
return node != null && node.isEnd;
}
public boolean startsWith(String prefix) {
return searchPrefix(prefix) != null;
}
}
作者介绍

luckydog
V1