力扣hot100--＞前缀和/前缀树/LRU缓存

前缀和

1. 560. 和为 K 的子数组

中等

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

提示：

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();  // 获取输入数组的大小
        unordered_map<int,int> unMap;  // 哈希表，用来存储前缀和的频次
        unMap[0] = 1;  // 初始化哈希表，表示前缀和为0出现1次（这对从索引0开始的子数组非常重要）

        vector<int> pre(n+1);  // 存储前缀和的数组（pre[i] 表示 nums[0] 到 nums[i-1] 的和）
        int result{};  // 用于存储满足条件的子数组个数
        
        for(int i = 0; i < n; ++i) {
            pre[i+1] = pre[i] + nums[i];  // 更新当前的前缀和
            
            // 判断当前前缀和减去 k 是否存在于哈希表中
            if(unMap.find(pre[i+1] - k) != unMap.end()) {
                // 如果存在，说明从之前某个位置到当前的位置的子数组和为 k
                result += unMap[pre[i+1] - k];  // 将该频次累加到结果中
            }

            // 更新当前前缀和的频次
            unMap[pre[i+1]]++;
        }

        return result;  // 返回满足条件的子数组个数
    }
};
 

解释:

per[i+1] 表示从 nums[0] 到 nums[i] 的累加和。

子数组 nums[0..i] 的和可以通过公式计算： sum(nums[0..i])=per[i+1]−per[0]

前缀树

1. 208. 实现 Trie (前缀树)

中等

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

• Trie() 初始化前缀树对象。
• void insert(String word) 向前缀树中插入字符串 word 。
• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

// 字典树（Trie）的实现
class Trie {
private:
    // 子节点数组，存储当前节点的所有子节点（26个字母）
    vector<Trie*> children;

    // 标记当前节点是否是某个单词的结束
    bool isEnd;

    // 辅助函数：查找指定前缀的最后一个节点
    Trie* searchPrefix(string prefix) {
        Trie* node = this; // 从当前节点（根节点）开始查找
        for (char ch : prefix) { // 遍历前缀字符串的每个字符
            ch -= 'a'; // 将字符转换为索引值（'a' 对应索引 0，'z' 对应索引 25）
            if (node->children[ch] == nullptr) { // 如果对应的子节点不存在
                return nullptr; // 前缀不存在，返回空指针
            }
            node = node->children[ch]; // 移动到子节点
        }
        return node; // 返回前缀的最后一个节点
    }

public:
    // 构造函数：初始化根节点
    Trie() : children(26), isEnd(false) {}

    // 插入一个单词到字典树
    void insert(string word) {
        Trie* node = this; // 从根节点开始插入
        for (char ch : word) { // 遍历单词的每个字符
            ch -= 'a'; // 将字符转换为索引
            if (node->children[ch] == nullptr) { // 如果对应的子节点不存在
                node->children[ch] = new Trie(); // 创建一个新的子节点
            }
            node = node->children[ch]; // 移动到子节点
        }
        node->isEnd = true; // 标记该节点为单词的结束
    }

    // 搜索一个完整单词是否存在于字典树中
    bool search(string word) {
        Trie* node = this->searchPrefix(word); // 查找单词的最后一个节点
        return node != nullptr && node->isEnd; // 节点存在且是单词结尾
    }

    // 判断是否存在以指定前缀开头的字符串
    bool startsWith(string prefix) {
        return this->searchPrefix(prefix) != nullptr; // 查找前缀是否存在
    }
};
 

LRU缓存

3. 146. LRU 缓存

中等

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 105
• 最多调用 2 * 105 次 get 和 put

class LRUCache {
public:
    // 构造函数，初始化缓存容量
    LRUCache(int capacity) {
        size = capacity; // 设置缓存大小
    }
    
    // 获取操作：如果key存在，将其更新为最近使用的状态并返回值；如果不存在，返回-1
    int get(int key) {
        if(m.find(key) == m.end()){ // 如果key不在哈希表中
            return -1; // 返回-1表示未找到
        }
        // 将对应的节点移到链表头部，表示最近使用
        l.splice(l.begin(), l, m[key]);
        return m[key]->second; // 返回节点的值
    }
    
    // 插入操作：插入新键值对或更新现有键值对
    void put(int key, int value) {
        if(m.find(key) != m.end()){ // 如果key已存在
            // 更新节点为最近使用并更新值
            l.splice(l.begin(), l, m[key]);
            m[key]->second = value;
            return;
        }

        // 如果容量已满，删除最久未使用的元素
        if(size == l.size()){
            auto dKey = l.back().first; // 获取链表尾部的键（最久未使用的）
            l.pop_back(); // 删除链表尾部节点
            m.erase(dKey); // 从哈希表中移除对应的索引
        }

        // 插入新元素到链表头部
        l.push_front({key, value});
        m[key] = l.begin(); // 在哈希表中更新对应索引
    }

private:
    list<pair<int, int>> l; // 双向链表，用于维护最近最少使用（LRU）顺序
    unordered_map<int, list<pair<int, int>>::iterator> m; // 哈希表，用于快速查找节点位置
    int size{}; // 缓存容量
};

解释：

数据结构

1. 双向链表（list<pair<int, int>> l）：用于按访问顺序存储缓存项，链表头部存储最近使用的元素，尾部存储最久未使用的元素。

   • pair<int, int>：pair.first 是 key，pair.second 是 value。
   • l.push_front 将新的节点（或更新后的节点）移动到链表头部，表示最近使用。
   • l.pop_back 删除尾部元素，表示最久未使用的元素。

2. 哈希表（unordered_map<int, list<pair<int, int>>::iterator> m）：用于存储缓存项的 键 和链表中对应节点的 迭代器。

   • m[key] 指向链表中对应 key 的节点。
   • 使用哈希表可以 O(1) 时间复杂度查找和更新缓存项。

操作流程

1. put(key, value)：插入或更新缓存。
   • 如果 key 已经存在，则更新其 value 并将其移到链表头部，表示最近使用。
   • 如果 key 不存在，则检查缓存是否已满。如果已满，删除尾部的节点（最久未使用的元素），然后插入新节点到链表头部。
2. get(key)：获取缓存中的值。
   • 如果 key 存在，移动该节点到链表头部并返回其 value。
   • 如果 key 不存在，返回 -1。

其他

编写一个程序，解析给定的多个文件路径，并以树形结构打印出各个目录的层级关系。路径格式为Unix风格的路径，即各个目录由 / 分隔。根目录的子目录不需要前缀 -，其他目录按层级递归打印，子目录前面需要加上 - 并根据层级缩进。

示例输入：

 5
 /a/b/c
 /a/b/d
 /a/e
 /f/g

示例输出：

 a
   - b
     - c
     - d
   - e
 f
   - g

import java.util.*;

// 目录树构建与打印的类
public class PathParse {
    public static void main(String[] args) {
        // 创建扫描器用于读取输入
        Scanner sc = new Scanner(System.in);

        // 读取路径的数量
        int n = Integer.parseInt(sc.nextLine());

        // 用于存储路径的列表
        List<String> paths = new ArrayList<>(n);

        // 读取所有路径并存储到路径列表中
        for (int i = 0; i < n; i++)
            paths.add(sc.nextLine());

        // 根据路径列表构建目录树
        Node root = buildTree(paths);

        // 打印根目录的子节点及其子目录
        for (Node each : root.children.values()) {
            // 最高级目录前面没有 - ，需要特殊处理
            System.out.println(each.name);
            for (Node child : each.children.values()) {
                // 递归打印子目录及其子目录
                printTree(child, 2);
            }
        }

        // 关闭扫描器
        sc.close();
    }

    // 递归打印树的方法，使用空格进行缩进来表示目录层级
    private static void printTree(Node root, int blankCount) {
        StringBuilder sb = new StringBuilder();

        // 根据层级（blankCount）添加空格进行缩进
        for (int i = 0; i < blankCount; i++)
            sb.append(" ");
        
        // 打印当前节点的目录名，前面加上“- ”表示子目录
        sb.append("- ").append(root.name);
        System.out.println(sb.toString());

        // 递归打印所有子目录
        for (Node each : root.children.values()) {
            printTree(each, blankCount + 2);  // 每深入一层，缩进增加两个空格
        }
    }

    // 根据路径列表构建目录树
    private static Node buildTree(List<String> paths) {
        // 根节点为空字符串
        Node root = new Node("");
        
        // 遍历每一个路径，拆分并添加到树中
        for (String path : paths) {
            String[] strs = path.split("/");  // 将路径根据"/"进行分割
            add(root, strs);  // 将拆分后的目录添加到树中
        }
        
        return root;
    }

    // 根据拆分后的路径数组添加节点到树中
    private static void add(Node root, String[] strs) {
        Node parent = root;

        // 遍历路径数组中的每个目录
        for (String str : strs) {
            // 如果当前目录没有该子节点，则创建新的子节点
            if (!parent.children.containsKey(str)) {
                parent.children.put(str, new Node(str));
            }

            // 将当前节点更新为其子节点，继续深入
            parent = parent.children.get(str);
        }
    }
}

// 目录节点类，包含目录名称和子节点
class Node {
    String name;
    Map<String, Node> children;

    // 构造方法，初始化节点名称和子节点Map
    public Node(String name) {
        this.name = name;
        this.children = new HashMap<>();
    }
}