LRU缓存
题目
146. LRU 缓存 - 力扣（LeetCode）
思路
-
LinkedHashMap是一个适合实现 LRU 缓存的容器，因为它能够保持插入顺序，并允许我们在 O(1) 时间复杂度内访问和更新元素。 -
需要在
put操作中检查容量，并在必要时移除最久未使用的元素。
代码
class LRUCache {private int capacity;private Map<Integer, Integer> map;public LRUCache(int capacity) {this.capacity = capacity;map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {@Overrideprotected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {return size() > capacity;}};}public int get(int key) {return map.getOrDefault(key, -1);}public void put(int key, int value) {map.put(key, value);}
}
前缀树
题目
208. 实现 Trie (前缀树) - 力扣（LeetCode）
思路
-
每个节点代表一个字符，节点中存储指向子节点的指针和一个标志位（表示当前节点是否是一个完整单词的结尾）。
-
根据单词中的每个字符，逐个添加节点。如果某个字符已经存在于当前路径中，则沿着现有路径继续；如果字符不存在，则创建新的节点。
-
从根节点开始，逐个检查单词中的每个字符。如果每个字符都可以在路径中找到，且到达单词的结尾标志为真，则该单词存在。
代码
class Trie {private final TrieNode root;public Trie() {root = new TrieNode();}public void insert(String word) {TrieNode node = root;for (char c : word.toCharArray()) {node = node.children.computeIfAbsent(c, k -> new TrieNode());}node.isWord = true;}public boolean search(String word) {TrieNode node = getNode(word);return node!=null&&node.isWord;}public boolean startsWith(String prefix) {return getNode(prefix)!=null;}private TrieNode getNode(String prefix) {TrieNode node = root;for (char c : prefix.toCharArray()) {node = node.children.get(c);if (node == null) {return null;}}return node;}}class TrieNode{Map<Character, TrieNode> children;boolean isWord;public TrieNode() {isWord = false;this.children = new HashMap<Character, TrieNode>();}}寻找重复数
题目
287. 寻找重复数 - 力扣（LeetCode）
思路
快慢指针，将问题转化为一个链表环检测问题。
代码
public int findDuplicate(int[] nums) {int slow = nums[0];int fast = nums[0];do {slow = nums[slow];fast = nums[nums[fast]];} while (slow != fast);fast = nums[0];while (slow != fast) {slow = nums[slow];fast = nums[fast];}return slow;}
LinkedHashMap简介
LinkedHashMap 是 Java 中一个实现了 Map 接口的类，它结合了 HashMap 和链表的特性，提供了一个有序的映射。
特性：
-
保持插入顺序：
LinkedHashMap使用双向链表维护了元素的插入顺序。当你迭代LinkedHashMap时，元素会按照它们的插入顺序返回。这使得LinkedHashMap在需要保持顺序的场景中非常有用，比如实现 LRU 缓存。 -
维护访问顺序：
LinkedHashMap还可以配置为按访问顺序维护元素。这是通过在构造函数中将accessOrder参数设置为true实现的。这样一来，每次访问元素（无论是通过get还是put方法），该元素会被移动到链表的末尾，从而保持最新的访问顺序。 -
时间复杂度：
- 插入、删除和查找：时间复杂度为 O(1)，因为
LinkedHashMap使用了哈希表来存储键值对，同时链表维护顺序信息。 - 迭代：时间复杂度为 O(n)，因为需要遍历链表的所有元素。
- 插入、删除和查找：时间复杂度为 O(1)，因为
-
内存消耗： 由于
LinkedHashMap还需要存储链表的额外指针，它比HashMap多消耗一些内存。每个节点需要两个额外的引用，一个指向前一个节点，一个指向后一个节点。
构造函数：
-
LinkedHashMap(int initialCapacity)： 构造一个具有指定初始容量的LinkedHashMap，链表的顺序按插入顺序维护。 -
LinkedHashMap(int initialCapacity, float loadFactor)： 构造一个具有指定初始容量和负载因子的LinkedHashMap，链表的顺序按插入顺序维护。 -
LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)： 构造一个具有指定初始容量、负载因子和访问顺序的LinkedHashMap。accessOrder参数指定了链表的顺序是按插入顺序还是按访问顺序维护。
常用方法：
put(K key, V value)：插入键值对到LinkedHashMap。如果键已经存在，则更新其值。get(Object key)：根据键获取值，如果键不存在，则返回null。remove(Object key)：根据键删除对应的键值对。containsKey(Object key)：检查LinkedHashMap中是否存在指定的键。containsValue(Object value)：检查LinkedHashMap中是否存在指定的值。keySet()：返回LinkedHashMap中所有键的集合，按插入顺序。values()：返回LinkedHashMap中所有值的集合，按插入顺序。entrySet()：返回LinkedHashMap中所有键值对的集合，按插入顺序。
总结
至此，也赶在中秋节放假之前完成了力扣100题，撒花撒花