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

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个压缩包&#xff0c;初始代码&#xff0c;实现前缀和&#xff0c;实现前缀积&#xff0c;实现前缀异或。都是在前者的基础上修改的。 本博文是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.语法和模板: 结论 当涉及到前端开发框架时&#xff0c…...

STM32 之 HAL 库串口 USART 丢数据及ORE卡死的解决方案

STM32 之 HAL 库串口 USART 丢数据及ORE卡死的解决方案_hal_uart_error_ore-CSDN博客...

递归最小二乘法RLS

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

Apache Doris (三十九):Doris数据导出 - MySQL dump导出

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

【Nginx32】Nginx学习:随机索引、真实IP处理与来源处理模块

Nginx学习&#xff1a;随机索引、真实IP处理与来源处理模块 完成了代理这个大模块的学习&#xff0c;我们继续其它 Nginx 中 HTTP 相关的模块学习。今天的内容都比较简单&#xff0c;不过最后的来源处理非常有用&#xff0c;可以帮我们解决外链问题。另外两个其实大家了解一下就…...

vue3后台管理框架之集成sass

我们目前在组件内部已经可以使用scss样式,因为在配置styleLint工具的时候,项目当中已经安装过sass sass-loader,因此我们再组件内可以使用scss语法!!!需要加上lang="scss" <style scoped lang="scss"></style> 接下来我们为项目添加一些…...

无需付费开会员,一个Python程序实现PDF转高清图片

今天需要将一个PDF导出为图片&#xff0c;但是一般的在线转换网站导出的图片清晰度都不高&#xff0c;分辨率只有1241*1754&#xff0c;这就导致输出的图片放大后字体是有点模糊的&#xff0c;所以就想到了使用Python中的PyPDF2库来处理PDF文件&#xff0c;以及Pillow库来处理图…...

为分布式系统设计数据库

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

Programming abstractions in C阅读笔记:p179-p180

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

在 VSCode 中使用 PlantUML

最近&#xff0c;因为工作需要绘制一些逻辑图&#xff0c;我自己现在使用的是 PlantUML 或者 mermaid&#xff0c;相比之下前者更加强大。不过它的环境也麻烦一些&#xff0c;mermaid 在一些软件上已经内置了。但是 PlantUML 一般需要自己本地安装或者使用远程服务器&#xff0…...

css3过渡属性属性名:transition

CSS3的过渡属性属性名是transition&#xff0c;它允许我们在状态改变时为元素添加过渡效果&#xff0c;例如在元素从一种样式变为另一种样式时添加平滑的过渡效果。 transition的语法如下&#xff1a; transition: property duration timing-function delay;其中&#xff0c;…...

关于数据链路层(初步)

以太网帧格式&#xff1a; 源地址和目的地址是指网卡的硬件地址&#xff08;也叫MAC地址&#xff09;&#xff0c;长度是48位&#xff0c;是在网卡出厂时固 化的&#xff1b; 帧协议类型字段有三种值&#xff0c;分别对应载荷的形式&#xff0c;有IP、ARP、RARP&#xff1b; …...

诊断DLL——CAPL_DLL集成安全访问算法

文章目录 前言一、CAPL DLL简介DLL生成C2338报错解决方案:二、添加27服务解锁算法三、CAPL调用dll前言 在实际诊断工程应用中,如UDS刷写——27服务,经常会遇到一些Seed2Key的算法问题,为了安全保密,这个算法的源码不便公开,我们可以将其打包成DLL,然后在CANoe诊断控制面…...

集合元素处理(传统方式和Stream方式)

1、集合元素处理&#xff08;传统方式&#xff09; 现在有两个ArrayList集合存储队伍当中的多个成员姓名&#xff0c;要求使用传统的for循环&#xff08;或增强for循环&#xff09;依次进行一下若干操作步骤&#xff1a; 第一个队伍只要 名字为 3 个字 的成员姓名&#xff1b;存…...

亲测好用,这3款免费高清录屏软件,效果惊人!

在当今社会上&#xff0c;录屏软件已经成为了人们日常生活中不可或缺的一部分。无论是在工作还是学习中&#xff0c;我们都需要使用录屏软件来录制屏幕上的内容。然而&#xff0c;许多录屏软件都是收费的&#xff0c;这对于那些想要尝试录屏软件但又不想花钱的人来说&#xff0…...

超声波清洗机洗眼镜真的可以洗干净吗?眼镜超声波清洗机推荐

截止2023年4月份近视眼的统计&#xff0c;我过近视人群高达3亿人&#xff0c;可想而知现在近视的群体是有多么庞大的。近视就免不了要戴眼镜&#xff0c;但是一副眼镜长时间的佩戴不清洗的话&#xff0c;镜片会不清晰&#xff0c;也有的朋友会眼镜脏了就去配一副新的&#xff0…...

centos7安装部署ElasticSearch

文章目录 ElasticSearch安装部署简介安装卸载 ElasticSearch安装部署 简介 全文搜索属于最常见的需求&#xff0c;开源的 Elasticsearch &#xff08;以下简称 es&#xff09;是目前全文搜索引擎的首选。 它可以快速地储存、搜索和分析海量数据。维基百科、Stack Overflow、G…...

websocket+node+vite(vue)实现一个简单的聊天

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

YApi和Swagger接口管理

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

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

stm32wle5 lpuart DMA数据不接收

配置波特率9600时&#xff0c;需要使用外部低速晶振...

leetcode73-矩阵置零

leetcode 73 思路 记录 0 元素的位置&#xff1a;遍历整个矩阵&#xff0c;找出所有值为 0 的元素&#xff0c;并将它们的坐标记录在数组zeroPosition中置零操作&#xff1a;遍历记录的所有 0 元素位置&#xff0c;将每个位置对应的行和列的所有元素置为 0 具体步骤 初始化…...