优选算法第四讲:前缀和模块
优选算法第四讲:前缀和模块
- 1.[模板]前缀和
- 2.【模板】二维前缀和
- 3.寻找数组的中心下标
- 4.除自身以外数组的乘积
- 5.和为k的子数组
- 6.和可被k整除的子数组
- 7.连续数组
- 8.矩阵区域和
1.[模板]前缀和
链接: link
#include <iostream>
#include <vector>
using namespace std;int main() {int n = 0, q = 0;cin >> n >> q;vector<int> arr(n+1);//开辟一个n+1的数组for(int i = 1; i <= n; i++) cin >> arr[i];//创建一个前缀和数组。vector的构造会自己初始化vector<long long> dp(n+1);//更新前缀和数组for(int i = 1; i<=n; i++) dp[i] = dp[i-1] + arr[i];//直接使用前缀和数组进行返回即可int l = 0, r = 0;while(q--){cin >> l >> r;cout << dp[r] - dp[l-1] << endl;//直接输出结果即可}return 0;
}
2.【模板】二维前缀和
链接: link
3.寻找数组的中心下标
链接: link
class Solution {
public:int pivotIndex(vector<int>& nums) {int n = nums.size();vector<int> f(n), g(n);//1.分别求出前缀和、后缀和数组for(int i = 1; i<n; i++)f[i] = f[i-1] + nums[i-1];for(int i = n-2; i>=0; i--)g[i] = g[i+1] + nums[i+1];//2.使用前缀和、后缀和数组for(int i = 0; i<n; i++)if(f[i] == g[i]) return i;return -1;}
};
4.除自身以外数组的乘积
链接: link
class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> f(n), g(n);//1.先求出f和g数组f[0] = 1;//注意:细节问题一定要处理g[n-1] = 1;for(int i = 1; i<n; i++)f[i] = f[i-1] * nums[i-1];for(int i = n-2; i>=0; i--)g[i] = g[i+1] * nums[i+1];//2.使用两数组vector<int> ret(n);for(int i = 0; i<n; i++)ret[i] = f[i] * g[i];return ret;}
};
5.和为k的子数组
链接: link
class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int, int> hash;hash[0] = 1;int sum = 0, ret = 0;for(auto e : nums){sum += e;//计算当前位置的前缀和if(hash.count(sum - k)) ret += hash[sum-k];hash[sum]++;}return ret;}
};
6.和可被k整除的子数组
链接: link
class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int, int> hash;hash[0] = 1;//细节问题:如果nums的和可被k整除,那么也要将次数+1int sum = 0, ret = 0;for(auto e : nums){sum += e;int r = (sum%k + k) % k;//求余数的方法if(hash.count(r)) ret += hash[r];//如果sum%k = 前缀和%k,那么就可以被k整除hash[r]++;}return ret;}
};
7.连续数组
链接: link
class Solution {
public:int findMaxLength(vector<int>& nums) {unordered_map<int, int> hash;hash[0] = -1;int sum = 0, ret = 0;for(int i = 0; i<nums.size(); i++){sum += nums[i] == 0 ? -1 : 1;//我们不需要将数组的0改为1,只需要在加的这个部分加-1就行了if(hash.count(sum)) ret = max(ret, i-hash[sum]);else hash[sum] = i;//此时存储的应该是下标}return ret;}
};
8.矩阵区域和
链接: link
class Solution {
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {int m = 0, n = 0;m = mat.size();n = mat[0].size();//先计算出前缀和数组vector<vector<int>> dp(m+1, vector<int>(n+1));for(int i = 1; i<=m; i++)for(int j = 1; j<=n; j++)dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+mat[i-1][j-1];//前缀和数组的使用vector<vector<int>> ret(m, vector<int>(n));for(int i = 0; i<m; i++){for(int j = 0; j<n; j++){int x1 = 0, y1 = 0, x2 = 0, y2 = 0;x1 = max(0, i-k) + 1;y1 = max(0, j-k) + 1;x2 = min(m-1, i+k) + 1;y2 = min(n-1, j+k) + 1;ret[i][j] = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];}}return ret;}
};
相关文章:

优选算法第四讲:前缀和模块
优选算法第四讲:前缀和模块 1.[模板]前缀和2.【模板】二维前缀和3.寻找数组的中心下标4.除自身以外数组的乘积5.和为k的子数组6.和可被k整除的子数组7.连续数组8.矩阵区域和 1.[模板]前缀和 链接: link #include <iostream> #include <vector> using…...

ubuntu20.04 加固方案-设置限制su命令用户组
一、编辑/etc/pam.d/su配置文件 打开终端。 使用文本编辑器(如vim)编辑/etc/pam.d/su文件。 vim /etc/pam.d/su 二、添加配置参数 在打开的配置文件的中,添加以下参数: auth required pam_wheel.so 创建 wheel 组 并添加用户 …...
TDengine数据备份与恢复
TDengine数据备份与恢复 一、数据备份和恢复介绍二、基于 taosdump 进行数据备份恢复三、基于 taosExplorer 进行数据备份恢复3.1 taosExplorer 的安装与配置3.2 使用taosExplorer 进行数据备份 一、数据备份和恢复介绍 官网地址:TDengine - 数据备份和恢复 为了防止…...

2024最新的开源博客系统:vue3.x+SpringBoot 3.x 前后端分离
本文转载自:https://fangcaicoding.cn/article/54 大家好!我是方才,目前是8人后端研发团队的负责人,拥有6年后端经验&3年团队管理经验,截止目前面试过近200位候选人,主导过单表上10亿、累计上100亿数据…...
研究中的“异质性”、“异质性结果”是指?
“异质性”这个词在统计学和研究中指的是数据、现象或群体之间的差异,即不同个体、组别、区域或时间点的表现或特征并不相同。相对的概念是“同质性”,即所有个体或组别在某一方面表现相同或接近。 异质性(Heterogeneity)的含义 …...
Springboot整合AOP和redis
aop pom.xml <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-aop</artifactId> </dependency> 开启自动代理 注意:在完成了引入AOP依赖包后,一般来说并不需要去做其他…...

freetype学习总结
freetype学习总结 目录 freetype学习总结1. LCD显示字符问题引入2. freetype概念2.1 嵌入式设备使用FreeType的方法步骤2.2 嵌入式设备使用FreeType的注意事项 3. freetype官方C示例3.1 example1.c源码 4. 嵌入式设备上使用FreeType的简单示例4.1 简单示例代码4.2 代码分析 5. …...

上海亚商投顾:沪指缩量调整 华为概念股午后爆发
上海亚商投顾前言:无惧大盘涨跌,解密龙虎榜资金,跟踪一线游资和机构资金动向,识别短期热点和强势个股。 一.市场情绪 市场全天震荡调整,沪指、深成指午后跌超1%,创业板指一度跌逾2%,尾盘跌幅有…...

操作系统与进程【单身狗定制版】
大家好呀 我是浪前 今天给大家讲解的是操作系统与进程 祝愿所有点赞关注的人,身体健康,一夜暴富,升职加薪迎娶白富美!!! 点我领取迎娶白富美大礼包 前言: 我们今天我们来学习操作系统 当然啦,操作系统是一个很庞大的…...
监听el-table中 自定义封装的某个组件的值发现改变调用函数
监听el-table中 自定义封装的某个组件的值发现改变调用函数 当你在一个 el-table 中使用封装的自定义组件作为单元格内容时,监听这个组件的值变化并调用函数,可以通过以下步骤实现: 创建自定义组件:首先创建一个自定义的 Vue 组…...

frida安装
开始安装 frida https://github.com/frida/frida/releases 下载安装的时候查看自己手机是多少位的 adb shell getprop ro.product.cpu.abi # 按照自己的机型下载进行解压里面有个文件放入到手机中开始进入手机 然后按照下面的图执行命令 其中log 我只是看了下 不需要执行因为刚…...

链表详解(三)
目录 链表功能实现链表的查找SLNode* SLFind(SLNode* phead, SLNDataType x)代码 链表任意位置前插入void SLInsert(SLNode**pphead,SLNode* pos, SLNDataType x)代码 链表任意位置前删除void SLErase(SLNode**pphead,SLNode* pos)代码 链表任意位置后插…...

【RESP问题】RESP.app GUI for Redis 连接不上redis服务器
问题描述: 在使用RESP的时候出现地址和密码正确但是连接不上Redis服务器的情况,但是由于在之前我是修改过Redis的配置文件的,所以现在怀疑是防火墙的问题。 问题解决: 在[rootlocalhost ~]下输入以下命令打开防火墙 #放通6379/…...

【github 有趣项目】AMULE
官方网站github ‘All-platform’ P2P client based on eMule电骡社区文档 下载&安装 去官方网站下载(社区版一般版本较新),解压版解压打开即可。 点击“下一页”,输入名称,后边全都下一步即可 通过upnp设置端…...

【WRF数据准备】土地利用类型分类标准:USGS+MODIS IGBP 21
【WRF数据准备】土地利用类型分类标准:USGSMODIS IGBP 21 WRF常用土地类型分类MODIS IGBP 21USGSNLCD Landuse 选择土地利用分类标准替换城市土地类型后更改土地利用分类参考 WRF常用土地类型分类 WRF中土地利用类型最高分辨率是30s,且主要分为MODIS和U…...

KVM虚拟机迁移:无缝迁徙,重塑云上未来
作者简介:我是团团儿,是一名专注于云计算领域的专业创作者,感谢大家的关注 座右铭: 云端筑梦,数据为翼,探索无限可能,引领云计算新纪元 个人主页:团儿.-CSDN博客 目录 前言&#…...
CSS常见适配布局方式
在网页设计中,布局是确保内容按预期显示的关键部分。CSS 提供了多种布局方式,每种方式都有其特定的用途和优势。以下是您提到的五种布局方式的详细解释: 1. 流式布局(百分比布局) 概述: 流式布局…...
ArkUI常用布局:构建响应式和高效的用户界面
在HarmonyOS应用开发中,ArkUI作为用户界面开发框架,提供了多种布局方式来帮助开发者构建响应式和高效的用户界面。本文将详细介绍ArkUI中的常用布局方式,包括线性布局、层叠布局、弹性布局、相对布局、栅格布局、列表和轮播布局,并…...
论面向服务架构设计及其应用
一、引言 企业应用集成(Enterprise Application Integration,EAI)是企业实现信息系统协同工作的关键途径,尤其是在当前多系统、多平台并存的企业环境下,集成需求愈发显著。面向服务架构(Service-Oriented …...

HTML5 + CSS3 + JavaScript 编程语言学习教程
HTML5 CSS3 JavaScript 编程语言学习教程 欢迎来到这篇关于 HTML5、CSS3 和 JavaScript 的详细学习教程!无论你是初学者还是有一定基础的开发者,这篇文章都将帮助你深入理解这三种技术的核心概念、语法和应用。 目录 HTML5 1.1 HTML5 简介1.2 HTML5 …...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...

深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...
JavaScript 数据类型详解
JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型(Primitive) 和 对象类型(Object) 两大类,共 8 种(ES11): 一、原始类型(7种) 1. undefined 定…...
uniapp 字符包含的相关方法
在uniapp中,如果你想检查一个字符串是否包含另一个子字符串,你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的,但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...
MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用
文章目录 一、背景知识:什么是 B-Tree 和 BTree? B-Tree(平衡多路查找树) BTree(B-Tree 的变种) 二、结构对比:一张图看懂 三、为什么 MySQL InnoDB 选择 BTree? 1. 范围查询更快 2…...