当前位置：首页 > article >正文

力扣100题——杂题

article 2024/9/21 4:13:30

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)，因为需要遍历链表的所有元素。
内存消耗：由于 LinkedHashMap 还需要存储链表的额外指针，它比 HashMap 多消耗一些内存。每个节点需要两个额外的引用，一个指向前一个节点，一个指向后一个节点。

构造函数：

LinkedHashMap(int initialCapacity)：构造一个具有指定初始容量的 LinkedHashMap，链表的顺序按插入顺序维护。
LinkedHashMap(int initialCapacity, float loadFactor)：构造一个具有指定初始容量和负载因子的 LinkedHashMap，链表的顺序按插入顺序维护。
LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)：构造一个具有指定初始容量、负载因子和访问顺序的 LinkedHashMap。accessOrder 参数指定了链表的顺序是按插入顺序还是按访问顺序维护。