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

力扣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 和链表的特性,提供了一个有序的映射。

特性:

  1. 保持插入顺序LinkedHashMap 使用双向链表维护了元素的插入顺序。当你迭代 LinkedHashMap 时,元素会按照它们的插入顺序返回。这使得 LinkedHashMap 在需要保持顺序的场景中非常有用,比如实现 LRU 缓存。

  2. 维护访问顺序LinkedHashMap 还可以配置为按访问顺序维护元素。这是通过在构造函数中将 accessOrder 参数设置为 true 实现的。这样一来,每次访问元素(无论是通过 get 还是 put 方法),该元素会被移动到链表的末尾,从而保持最新的访问顺序。

  3. 时间复杂度

    • 插入、删除和查找:时间复杂度为 O(1),因为 LinkedHashMap 使用了哈希表来存储键值对,同时链表维护顺序信息。
    • 迭代:时间复杂度为 O(n),因为需要遍历链表的所有元素。
  4. 内存消耗: 由于 LinkedHashMap 还需要存储链表的额外指针,它比 HashMap 多消耗一些内存。每个节点需要两个额外的引用,一个指向前一个节点,一个指向后一个节点。

构造函数:

  1. LinkedHashMap(int initialCapacity): 构造一个具有指定初始容量的 LinkedHashMap,链表的顺序按插入顺序维护。

  2. LinkedHashMap(int initialCapacity, float loadFactor): 构造一个具有指定初始容量和负载因子的 LinkedHashMap,链表的顺序按插入顺序维护。

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

常用方法:

  • 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题,撒花撒花


http://www.kler.cn/a/312745.html

相关文章:

  • 国标GB28181视频平台EasyCVR私有化部署视频平台对接监控录像机NVR时,录像机“资源不足”是什么原因?
  • LLMs:MindFormers的简介、安装和使用方法、案例应用
  • Lodash的常用方法整理
  • docker compose 多个 Dockerfile
  • git命令及原理
  • Fortran安装(vscode+gcc+Python)
  • Java集合(一)
  • C++ 文件操作
  • 十、数字人IP应用方案
  • chromedriver下载与安装方法
  • react之jsx基础(2)高频使用场景
  • DEPLOT: One-shot visual language reasoning by plot-to-table translation论文阅读
  • Android14请求动态申请存储权限
  • WGCAT工单系统 v1.2.1 支持导出PDF和分享创建工单功能
  • JAVA 根据开始和结束ip,计算中间的所有ip
  • 【MySQL】MySQL和Workbench版本兼容问题
  • 力扣每日一题 公交站间的距离
  • 远程访问NAS速度慢??那是因为你没用对。。。
  • 2024年9月北京docker安装+nvidia-docker
  • Clang插件演示-直接调用AI模型定义的变量完成模型推理
  • IP Source Guard技术原理与应用
  • 如何在GitHub上克隆仓库:HTTPS、SSH和GitHub CLI的区别
  • 【机器学习(五)】分类和回归任务-AdaBoost算法-Sentosa_DSML社区版
  • 【算法题】300. 最长递增子序列-力扣(LeetCode)
  • 【资料分析】刷题日记3
  • node前端开发基本设置