力扣100题——杂题
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) {
@Override
protected 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题,撒花撒花