力扣hot100-->前缀和/前缀书/LRU缓存

embedded/2024/11/30 4:35:27/

前缀和

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; // 查找前缀是否存在
    }
};
 


http://www.ppmy.cn/embedded/141652.html

相关文章

【UE5 C++课程系列笔记】04——创建可操控的Pawn

根据官方文档创建一个可以控制前后左右移动、旋转视角、缩放视角的Pawn 。 步骤 一、创建Pawn 1. 新建一个C类&#xff0c;继承Pawn类&#xff0c;这里命名为“PawnWithCamera” 2. 在头文件中申明弹簧臂、摄像机和静态网格体组件 3. 在源文件中引入组件所需库 在构造函数…

k8s1.30.0高可用集群部署

负载均衡 nginx负载均衡 两台nginx负载均衡 vim /etc/nginx/nginx.conf stream {upstream kube-apiserver {server 192.168.0.11:6443 max_fails3 fail_timeout30s;#server 192.168.0.12:6443 max_fails3 fail_timeout30s;#server 192.168.0.13:6443 max_fails3…

2024 java大厂面试复习总结(二)(持续更新)

10年java程序员&#xff0c;2024年正好35岁&#xff0c;2024年11月公司裁员&#xff0c;记录自己找工作时候复习的一些要点。 JVM 说一下 JVM 运行时数据区 程序计数器&#xff08;Program Counter Register&#xff09;&#xff1a;当前线程所执行的字节码的行号指示器&…

英语知识网站开发:Spring Boot框架应用

3系统分析 3.1可行性分析 通过对本英语知识应用网站实行的目的初步调查和分析&#xff0c;提出可行性方案并对其一一进行论证。我们在这里主要从技术可行性、经济可行性、操作可行性等方面进行分析。 3.1.1技术可行性 本英语知识应用网站采用SSM框架&#xff0c;JAVA作为开发语…

.cc扩展名是什么语言?主流编程语言扩展名?C语言必须用.c为扩展名吗?为什么看到Windows好多系统文件名的扩展名不超过3字符?

.cc扩展名是什么语言? .cc是C语言使用的扩展名&#xff0c;一种说法是它是c with class的简写&#xff0c;当然C语言使用的扩展名不止.cc和.cpp, 还包含.cxx, .c, .C等&#xff0c;这些在不同编译器系统采用的默认设定不同&#xff0c;需要区分使用。当然&#xff0c;编译器提…

RabbitMQ高级特性:TTL、死信队列与延迟队列

RabbitMQ高级特性&#xff1a;TTL、死信队列与延迟队列 RabbitMQ作为一款开源的消息代理软件&#xff0c;广泛应用于分布式系统中&#xff0c;用于实现消息的异步传递和系统的解耦。其强大的高级特性&#xff0c;包括TTL&#xff08;Time-To-Live&#xff09;、死信队列&#…

数据库学习记录03

DML【数据操作语言】 DQL是对数据的查操作&#xff0c;DML就是操作&#xff1a;增、删、改。数据库的基础操作就是&#xff1a;增删改查&#xff08;CRUD); 1.插入&#xff08;增&#xff09; #语法1 insert into 表名(字段名1,...) values(值1,...);#语法2 insert into 表名(…

本地化部署 私有化大语言模型

本地化部署 私有化大语言模型 本地化部署 私有化大语言模型Anaconda 环境搭建运行 代码概述环境配置安装依赖CUDA 环境配置 系统设计与实现文件处理与加载文档索引构建模型加载与推理文件上传与索引更新实时对话与文档检索Gradio 前端设计 主要功能完整代码功能说明运行示例文件…