C++算法:前缀和基础
相关
源码测试用例下载
https://download.csdn.net/download/he_zhidan/88430716 包括4个压缩包,初始代码,实现前缀和,实现前缀积,实现前缀异或。都是在前者的基础上修改的。
本博文是CSDN学院课程的讲义
https://edu.csdn.net/course/detail/38771
前缀和(前缀积、前缀异或)应用的博文
C++前缀和算法:构造乘积矩阵
原理
长度为n的数组nums,共有n+1个以nums[0]开始的子数组。索引范围分别为[0,i),i取值区间[0,n]。preSum[i]记录子数组[0,i)的和。比如:nums = {1,2,3,4},则preSum = {0,1,3,6,10}。通过preSum,我们可以求任意nums的子数组和。子数组[i,j)等于子数组[0,j)减去[0,i),也就是子数组[i,j)的和等于preSum[j] – preSum[i]。如果i等于j,则preSum[i]-preSum[i],和为0,符合计算公式。如果i大于j,则非法,需要提前排除。
暴力法
时间复杂度O(n*n)。
核心代码
class CPreSum
{
public:
//左闭右开空间
long long SumO2(int left, int r)
{
long long llRet = 0;
for (; left < r; left++)
{
llRet += m_sums[left];
}
return llRet;
}
vector m_sums;
};
测试代码
template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
assert(v1[i] == v2[i]);
}
}
template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
void Test1()
{
CPreSum preSum;
preSum.m_sums = { 1,2,3,4 };
vector ans = { 0,1,3,6,10 };
auto res = preSum.SumO2(0, 4);
Assert(10LL, res);
res = preSum.SumO2(0, 3);
Assert(6LL, res);
res = preSum.SumO2(0, 2);
Assert(3LL, res);
res = preSum.SumO2(0, 1);
Assert(1LL, res);
res = preSum.SumO2(0, 0);
Assert(0LL, res);
res = preSum.SumO2(1, 4);
Assert(9LL, res);
res = preSum.SumO2(1, 3);
Assert(5LL, res);
}
void Test2()
{
srand(time(nullptr));
int n = rand() % 10 + 1;
CPreSum preSum;
for (int i = 0; i < n; i++)
{
preSum.m_sums.emplace_back(rand() % 10000);
}
preSum.Init();
for (int left = 0; left < n; left++)
{
for (int r = left; r <= n; r++)
{
long long res1 = preSum.SumO1(left, r);
long long res2 = preSum.SumO2(left, r);
assert(res1==res2);
}
}
}
int main()
{
Test1();
Test2();
}
前缀和
时间复杂度O(n),预处理O(n),每次查询O(1)。
代码
void Init()
{
m_vPreSum.emplace_back(0);
for (const auto& n : m_nums)
{
m_vPreSum.emplace_back(n + m_vPreSum.back());
}
}
long long SumO1(int left, int r)
{
return m_vPreSum[r] - m_vPreSum[left];
}
vector m_vPreSum;
前缀乘积
只需要修改三处m_vPreSum[0]=1,+变成*,-变成除。
修改后的代码
class CPreSum
{
public:
//左闭右开空间
long long SumO2(int left, int r)
{
long long llRet = 1;
for (; left < r; left++)
{
llRet *= m_nums[left];
}
return llRet;
}
void Init()
{
m_vPreSum.emplace_back(1);
for (const auto& n : m_nums)
{
m_vPreSum.emplace_back(n * m_vPreSum.back());
}
}
long long SumO1(int left, int r)
{
return m_vPreSum[r] / m_vPreSum[left];
}
vector m_vPreSum;
vector m_nums;
};
前缀异或
C语言异或的符合是,初始0,也就是m_vPreSum.emplace_back(0)。异或的逆运算是本身,所以乘除都换成。
其它
视频课程
要是你认为本篇难道较大,不好入手,推荐你先学习基础算法的课程,我已完成部分,余下部分持续更新中,就在CSDN学院。
https://edu.csdn.net/course/detail/38771
C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统:win7 开发环境: VS2019 C++17
相关下载
如果你想观其大略,建设下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
博主想队大家说的话 |
---|
墨家名称的来源:有所得以墨记之。 |
闻缺陷则喜的来由:早发现,早修改问题,成本更低 |
程序是龙,算法是睛 |
相关文章:

C++算法:前缀和基础
相关 源码测试用例下载 https://download.csdn.net/download/he_zhidan/88430716 包括4个压缩包,初始代码,实现前缀和,实现前缀积,实现前缀异或。都是在前者的基础上修改的。 本博文是CSDN学院课程的讲义 https://edu.csdn.net/c…...

vue和react的区别
目录 1. 数据绑定 Vue React 2. 组件化 Vue React 3. 学习曲线 4. 状态管理 Vue React 5. 社区和生态系统 3. 学习曲线 4. 状态管理 Vue React 5. 生态系统 6. 社区和支持 7. 性能 8. 生产环境性能 9.语法和模板: 结论 当涉及到前端开发框架时,…...
STM32 之 HAL 库串口 USART 丢数据及ORE卡死的解决方案
STM32 之 HAL 库串口 USART 丢数据及ORE卡死的解决方案_hal_uart_error_ore-CSDN博客...

递归最小二乘法RLS
参考:RLS递归最小二乘法(Recursive Least Squares)_hymwgk的博客-CSDN博客...

Apache Doris (三十九):Doris数据导出 - MySQL dump导出
🏡 个人主页:IT贫道_大数据OLAP体系技术栈,Apache Doris,Clickhouse 技术-CSDN博客 🚩 私聊博主:加入大数据技术讨论群聊,获取更多大数据资料。 🔔 博主个人B栈地址:豹哥教你大数据的个人空间-豹哥教你大数据个人主页-哔哩哔哩视频 目录...

【Nginx32】Nginx学习:随机索引、真实IP处理与来源处理模块
Nginx学习:随机索引、真实IP处理与来源处理模块 完成了代理这个大模块的学习,我们继续其它 Nginx 中 HTTP 相关的模块学习。今天的内容都比较简单,不过最后的来源处理非常有用,可以帮我们解决外链问题。另外两个其实大家了解一下就…...
vue3后台管理框架之集成sass
我们目前在组件内部已经可以使用scss样式,因为在配置styleLint工具的时候,项目当中已经安装过sass sass-loader,因此我们再组件内可以使用scss语法!!!需要加上lang="scss" <style scoped lang="scss"></style> 接下来我们为项目添加一些…...
无需付费开会员,一个Python程序实现PDF转高清图片
今天需要将一个PDF导出为图片,但是一般的在线转换网站导出的图片清晰度都不高,分辨率只有1241*1754,这就导致输出的图片放大后字体是有点模糊的,所以就想到了使用Python中的PyPDF2库来处理PDF文件,以及Pillow库来处理图…...

为分布式系统设计数据库
【squids.cn】 全网zui低价RDS,免费的迁移工具DBMotion、数据库备份工具DBTwin、SQL开发工具等 数据库设计是微服务和云原生解决方案的关键因素,因为基于微服务的架构导致了数据的分布式。数据管理不再在一个单一的过程中发生,而是可以通过多…...

Programming abstractions in C阅读笔记:p179-p180
《Programming Abstractions In C》学习第60天,p179-p180总结。 一、技术总结 1.palindrome(回文) (1)包含单个字符的字符串(如"a"),或者空字符串(如" ")也是回文。 (2)示例:“level”、“noon”。 2.predicate fun…...

在 VSCode 中使用 PlantUML
最近,因为工作需要绘制一些逻辑图,我自己现在使用的是 PlantUML 或者 mermaid,相比之下前者更加强大。不过它的环境也麻烦一些,mermaid 在一些软件上已经内置了。但是 PlantUML 一般需要自己本地安装或者使用远程服务器࿰…...
css3过渡属性属性名:transition
CSS3的过渡属性属性名是transition,它允许我们在状态改变时为元素添加过渡效果,例如在元素从一种样式变为另一种样式时添加平滑的过渡效果。 transition的语法如下: transition: property duration timing-function delay;其中,…...

关于数据链路层(初步)
以太网帧格式: 源地址和目的地址是指网卡的硬件地址(也叫MAC地址),长度是48位,是在网卡出厂时固 化的; 帧协议类型字段有三种值,分别对应载荷的形式,有IP、ARP、RARP; …...

诊断DLL——CAPL_DLL集成安全访问算法
文章目录 前言一、CAPL DLL简介DLL生成C2338报错解决方案:二、添加27服务解锁算法三、CAPL调用dll前言 在实际诊断工程应用中,如UDS刷写——27服务,经常会遇到一些Seed2Key的算法问题,为了安全保密,这个算法的源码不便公开,我们可以将其打包成DLL,然后在CANoe诊断控制面…...
集合元素处理(传统方式和Stream方式)
1、集合元素处理(传统方式) 现在有两个ArrayList集合存储队伍当中的多个成员姓名,要求使用传统的for循环(或增强for循环)依次进行一下若干操作步骤: 第一个队伍只要 名字为 3 个字 的成员姓名;存…...

亲测好用,这3款免费高清录屏软件,效果惊人!
在当今社会上,录屏软件已经成为了人们日常生活中不可或缺的一部分。无论是在工作还是学习中,我们都需要使用录屏软件来录制屏幕上的内容。然而,许多录屏软件都是收费的,这对于那些想要尝试录屏软件但又不想花钱的人来说࿰…...

超声波清洗机洗眼镜真的可以洗干净吗?眼镜超声波清洗机推荐
截止2023年4月份近视眼的统计,我过近视人群高达3亿人,可想而知现在近视的群体是有多么庞大的。近视就免不了要戴眼镜,但是一副眼镜长时间的佩戴不清洗的话,镜片会不清晰,也有的朋友会眼镜脏了就去配一副新的࿰…...
centos7安装部署ElasticSearch
文章目录 ElasticSearch安装部署简介安装卸载 ElasticSearch安装部署 简介 全文搜索属于最常见的需求,开源的 Elasticsearch (以下简称 es)是目前全文搜索引擎的首选。 它可以快速地储存、搜索和分析海量数据。维基百科、Stack Overflow、G…...

websocket+node+vite(vue)实现一个简单的聊天
1.前端逻辑 本项目基于之前搭建的vite环境:https://blog.csdn.net/beekim/article/details/128083106?spm1001.2014.3001.5501 新增一个登录页和聊天室页面 <template><div>登录页</div><div>用户名:<input type"text" pl…...

YApi和Swagger接口管理
这篇博客针对苍穹外卖而写 YApi 之前的官网:yapi.smart-xwork.cn 由于之前的网址访问不了,现在我用的是这个网址:YApi Pro-高效、易用、功能强大的可视化接口管理平台 登录之后如下 创建两个工作空间 用户端接口也是如法炮制 Swagger 使用…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...

select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...

C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...

听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》
这段 Python 代码是一个完整的 知识库数据库操作模块,用于对本地知识库系统中的知识库进行增删改查(CRUD)操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 📘 一、整体功能概述 该模块…...

【JVM面试篇】高频八股汇总——类加载和类加载器
目录 1. 讲一下类加载过程? 2. Java创建对象的过程? 3. 对象的生命周期? 4. 类加载器有哪些? 5. 双亲委派模型的作用(好处)? 6. 讲一下类的加载和双亲委派原则? 7. 双亲委派模…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill
视觉语言模型(Vision-Language Models, VLMs),为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展,机器人仍难以胜任复杂的长时程任务(如家具装配),主要受限于人…...

在 Spring Boot 中使用 JSP
jsp? 好多年没用了。重新整一下 还费了点时间,记录一下。 项目结构: pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...
MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释
以Module Federation 插件详为例,Webpack.config.js它可能的配置和含义如下: 前言 Module Federation 的Webpack.config.js核心配置包括: name filename(定义应用标识) remotes(引用远程模块࿰…...