力扣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; // 查找前缀是否存在
}
};
相关文章:
力扣hot100-->前缀和/前缀书/LRU缓存
前缀和 1. 560. 和为 K 的子数组 中等 给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数 。 子数组是数组中元素的连续非空序列。 示例 1: 输入:nums [1,1,1], k 2 输出:2示例 2&#…...
Three.js CSS2D/CSS3D渲染器
在Three.js开发过程中,有时需要将 HTML 元素与 Three.js 渲染的 3D 场景相结合,这就需要用到 CSS2DRenderer 和 CSS3DRenderer。本文将详细介绍这两种渲染器的原理及其应用 一、CSS2DRenderer 渲染器 概述 CSS2DRenderer 渲染器用于在 3D 场景中渲染纯…...
mongodb文档字符串批量替换
【mongodb文档字符串批量替换脚本语句】 前言: 1、本方式对于数据量大的情况不适用,执行可能比较慢; 2、数据量大的情况,个人推荐代码层面解决,多线程替换更快: (1)写实体类的方式…...
前端安全和解决方案
提到这个我可能想到的就是不要暴露太多的账号密码信息。一些页面的请求和操作要加上权限。 然后下面就详细的介绍前端可能遇到的安全问题以及解决方法。 首先比较常见的前端的安全性问题就是跨站脚本攻击(XSS)。跨站请求伪造(csrfÿ…...
Tlias智能辅助学习系统-部门管理
包括查询、新增、删除、修改功能 控制层 package com.itheima.controller;import com.itheima.pojo.Dept; import com.itheima.pojo.Result; import com.itheima.service.DeptService; import lombok.extern.slf4j.Slf4j; import lombok.extern.slf4j.XSlf4j; import org.spr…...
React第十节组件之间传值之context
1、Context 使用creatContext() 和 useContext() Hook 实现多层级传值 概述: 在我们想要每个层级都需要某一属性,或者祖孙之间需要传值时,我们可以使用 props 一层一层的向下传递,或者我们使用更便捷的方案,用 creatC…...
flink中barrier不对齐的原因和影响
Barrier 不对齐(Barrier Misalignment)可能导致一些性能和一致性相关的问题,但 Flink 提供了机制来确保即使在不对齐的情况下,也可以保证数据的一致性。 1. 什么是 Barrier 不对齐? Barrier 不对齐是指在分布式数据流…...
软银集团孙正义再度加码OpenAI,近屿智能专注AI人才培养
11月28日凌晨,全球最大财经CNBC报道,软银集团创始人兼CEO孙正义再次向人工智能领域的领军企业OpenAI投资了15亿美元。软银对OpenAI的投资已不是首次。就在上个月,软银已在OpenAI的上一轮融资中注入了5亿美元的资金。但他一直寻求获得OpenAI更…...
麒麟系统x86安装达梦数据库
一、安装准备前工作 操作系统:银河麒麟V10,CPU: x86_64 架构 下载地址,麒麟官网:https://www.kylinos.cn/ 数据库:dm8_20220915_x86_kylin10_64 下载地址,达梦数据库官网:https://…...
Java中的“多态“详解
多态(Polymorphism)是面向对象编程(OOP)中的一个核心概念,它允许同一个接口或方法在不同对象上具有不同的实现方式。多态性使得程序在运行时可以根据对象的实际类型来决定调用哪个方法,从而提高代码的灵活性…...
buuctf-[SUCTF 2019]EasySQL 1解题记录
把你的旗帜给我,我会告诉你这面旗帜是对的。 堆叠注入查询数据库 1; show databases; 查询表名 1; show tables; 获取flag 1;set sql_modepipes_as_concat;select 1...
ASP.NET Core 入门
使用 .NET CLI 创建并运行 ASP.NET Core Web 应用。 文章目录 一、先决条件二、创建Web应用项目三、运行应用四、编辑Razor页面 一、先决条件 .NET 8.0 SDK 二、创建Web应用项目 打开命令行界面,然后输入以下命令: dotnet new webapp --output aspne…...
php反序列化1_常见php序列化的CTF考题
声明: 以下多内容来自暗月师傅我是通过他的教程来学习记录的,如有侵权联系删除。 一道反序列化的CTF题分享_ctf反序列化题目_Mr.95的博客-CSDN博客 一些其他大佬的wp参考:php_反序列化_1 | dayu’s blog (killdayu.com) 序列化一个对象将…...
题目 1013: [编程入门]Sn的公式求和
题目 1013: [编程入门]Sn的公式求和 [编程入门]Sn的公式求和 求Snaaaaaa…aa…aaa(有n个a)之值,其中a是一个数字,为2。 例如,n5时222222222222222,n由键盘输入。 #include<stdio.h> int A(int n)…...
算法——赎金信(leetcode383)
题目: 给你两个字符串:ransomNote 和 magazine ,判断 ransomNote 能不能由 magazine 里面的字符构成。 如果可以,返回 true ;否则返回 false 。 magazine 中的每个字符只能在 ransomNote 中使用一次。 示例 1&#…...
transformers训练(NLP)阅读理解(多项选择)
简介 在阅读理解任务中,有一种通过多项选择其中一个答案来训练机器的阅读理解。比如:给定一个或多个文档h,以及一个问题S和对应的多个答案候选,输出问题S的答案E,E是答案候选中的某一个选项。 这样的目的就是通过文档,…...
微软企业邮箱:安全可靠的企业级邮件服务!
微软企业邮箱的设置步骤?如何注册使用烽火域名邮箱? 微软企业邮箱作为一款专为企业设计的邮件服务,不仅提供了高效便捷的通信工具,更在安全性、可靠性和功能性方面树立了行业标杆。烽火将深入探讨微软企业邮箱的多重优势。 微软…...
什么是分布式锁
定义 分布式锁是控制分布式系统或集群中不同节点对共享资源访问的一种机制。在分布式环境下,多个节点(如多个服务器或多个进程)可能会同时访问诸如数据库中的某条记录、一个共享文件或者一个全局计数器等共享资源。分布式锁的目的是确保在同一…...
【含开题报告+文档+PPT+源码】基于SpringBoot的艺术培训学校管理系统的设计与实现
开题报告 艺术培训学校管理在现代教育行业中发挥着至关重要的作用,旨在为学员提供及时、专业且高效的课程服务,同时也激励培训机构不断提升教学质量与管理水平。然而,传统的艺术培训学校管理模式常面临一系列挑战,如课程报名程序…...
【网络安全 | 漏洞挖掘】绕过SAML认证获得管理员面板访问权限
未经许可,不得转载。 文章目录 什么是SAML认证?SAML是如何工作的?SAML响应结构漏洞结果什么是SAML认证? SAML(安全断言标记语言)用于单点登录(SSO)。它是一种功能,允许用户在多个服务之间切换时无需多次登录。例如,如果你已经登录了facebook.com,就不需要再次输入凭…...
相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...
LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...
代码规范和架构【立芯理论一】(2025.06.08)
1、代码规范的目标 代码简洁精炼、美观,可持续性好高效率高复用,可移植性好高内聚,低耦合没有冗余规范性,代码有规可循,可以看出自己当时的思考过程特殊排版,特殊语法,特殊指令,必须…...
R 语言科研绘图第 55 期 --- 网络图-聚类
在发表科研论文的过程中,科研绘图是必不可少的,一张好看的图形会是文章很大的加分项。 为了便于使用,本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中,获取方式: R 语言科研绘图模板 --- sciRplothttps://mp.…...
