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

算法专题四:前缀和

前缀和

  • 一.一维前缀和(模板):
    • 1.思路一:暴力解法
    • 2.思路二:前缀和思路
  • 二. 二维前缀和(模板):
    • 1.思路一:构造前缀和数组
  • 三.寻找数组的中心下标:
    • 1.思路一:前缀和
  • 四.除自身以外数组的乘积:
    • 1.思路一:暴力解法
    • 2.思路二:前缀积+后缀积
  • 五.和为K的子数组:
    • 1.思路一:前缀和+哈希
  • 六.前缀和可以被K整除的子数组:
    • 1.思路一:前缀和+哈希
  • 七.连续数组:
    • 1.思路一:
  • 八.矩阵区域和:
    • 1.思路一:二维前缀和模板+细节处理

一.一维前缀和(模板):

请添加图片描述
一维前缀和

1.思路一:暴力解法

1.输入数组长度n和查询次数q。
2.使用一个一维数组保存数据。
3.使用一个循环获取q次需要查询范围的数据。
4.遍历r-l+1次进行一个范围求和然后输出。
5.时间复杂度:O(n^2)
6.通过不了所有的测试用例。

2.思路二:前缀和思路

1.输入数组长度n和查询次数q。
2.使用一个一维数组保存数据。
3.构建一个前缀和的一个数组。
在这里插入图片描述
4.使用一个循环获取q次需要查询范围的数据。
5.时间复杂度:O(n^2)
6.通过不了所有的测试用例。

#include <iostream>
#include <vector>
using namespace std;int main()
{//1.输入数组长度和查询次数: int n =0,q=0;cin>>n>>q;//2.输入数组数据:vector<int> arr(n+1);for(int i=1;i<=n;i++) cin>>arr[i];//3.前缀和数组:vector<long long> bp(n+1);for(int i=1;i<=n;i++) bp[i] = bp[i-1] + arr[i];//4.计算和:int i=0,r=0;while(q!=0){cin>>i>>r;cout<<(bp[r] - bp[i-1])<<endl;q--;}
}

二. 二维前缀和(模板):

请添加图片描述
二维前缀和

1.思路一:构造前缀和数组

在这里插入图片描述

#include <iostream>
#include <vector>
using namespace std;int main()
{//1.n行m列的一个二维数组:int n = 0, m = 0, q = 0;cin >> n >> m >> q;//2.数组输入数据:vector<vector<int>> vv((n + 1),vector<int>(m+1));for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++)cin >> vv[i][j];}//3.创造二维的求和dp数组vector<vector<long long>> dp((n + 1), vector<long long>(m + 1));for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){dp[i][j] = ((dp[i][j - 1] + dp[i - 1][j]) - dp[i-1][j-1]) + vv[i][j];}}//4.数据查询:while (q != 0){int x1 = 0, y1 = 0, x2 = 0, y2 = 0;cin >> x1 >> y1 >> x2 >> y2;cout << (dp[x2][y2] - (dp[x1 - 1][y2] + dp[x2][y1-1]) + dp[x1-1][y1-1]) << endl;q--;}}

三.寻找数组的中心下标:

在这里插入图片描述

寻找数组的中心下标

1.思路一:前缀和

在这里插入图片描述

class Solution {
public:int pivotIndex(vector<int>& nums) {//1.构建前缀和数组:int n = nums.size();vector<int> dp(n+1);//2.前缀和数组值遍历:for(int i = 1 ; i<=n;i++) dp[i] = dp[i-1] + nums[i-1];//3.进行中心下标的寻找:int mid = -1;for(int i=1 ; i <= n ; i++){if((dp[i-1] - dp[0]) == (dp[n] - dp[i])){mid = i-1;break;}}//4.没有中心下标的情况:return (mid == -1? -1:mid);}
};

四.除自身以外数组的乘积:

在这里插入图片描述

除自身以外数组的乘积

1.思路一:暴力解法

在这里插入图片描述

2.思路二:前缀积+后缀积

在这里插入图片描述

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {//1.前缀积+后缀积int n = nums.size();vector<int> left(n + 1, 1);vector<int> right(n + 1, 1);//2.遍历确定前缀积+后缀积的值:for (int i = 1; i <= n; i++) left[i] = left[i - 1] * nums[i - 1];for (int i = n - 1; i >= 0; i--) right[i] = right[i + 1] * nums[i];// 1  1  2  6  24// 24 24 12 4  1// 0  1  2  3  4//0   1   2  3//24  12  8  6vector<int> ret(n);//3.遍历ret数组并且赋值for (int i = 0; i < n; i++){ret[i] = left[i] * right[i+1];}return ret;}
};

五.和为K的子数组:

在这里插入图片描述

和为K的子数组

1.思路一:前缀和+哈希

在这里插入图片描述

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 n : nums){sum+=n;if(hash.count(sum-k)) ret+=hash[sum-k];hash[sum]++;}return ret;}
};

六.前缀和可以被K整除的子数组:

在这里插入图片描述

前缀和可以被K整除的子数组

1.思路一:前缀和+哈希

在这里插入图片描述

class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int,int> hash;hash[0] = 1;//1.开始遍历+判断int sum = 0 , ret = 0;for(auto a : nums){sum+=a;int n = (sum%k + k) % k;if(hash.count(n)) ret+=hash[n];hash[n]++;}return ret;}
};

七.连续数组:

请添加图片描述

连续数组

1.思路一:

在这里插入图片描述

在这里插入图片描述

class Solution {
public:int findMaxLength(vector<int>& nums) {vector<int> nums_1(nums);for(auto& n:nums_1){if(n==0) n = -1;}//2.hash+前缀和的思路unordered_map<int,int> hash;//1.前缀和为0的下标处理:hash[0] = -1;int sum = 0,ret = 0;for(int i=0;i<nums.size();i++){sum+=nums_1[i];if(hash.count(sum)) ret = max(ret , i - hash[sum]);else hash[sum] = i;}return ret;}
};

八.矩阵区域和:

请添加图片描述

矩阵区域和

1.思路一:二维前缀和模板+细节处理

在这里插入图片描述

class Solution {
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {int m = mat.size();int n = mat[0].size();//1.创建(m+1) * (n+1) 大小的二维数组vector<vector<int>> dp(m+1 , vector<int>(n+1));//2.dp数组赋值: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];}}//3.使用dp数组并且考虑i-k 和 j-k的越界问题:vector<vector<int>> ret(m,vector<int>(n));for(int i=0 ; i<m ; i++){for(int j=0 ; j<n ; j++){int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;int 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;}
};

相关文章:

算法专题四:前缀和

前缀和 一.一维前缀和(模板)&#xff1a;1.思路一&#xff1a;暴力解法2.思路二&#xff1a;前缀和思路 二. 二维前缀和(模板)&#xff1a;1.思路一&#xff1a;构造前缀和数组 三.寻找数组的中心下标&#xff1a;1.思路一&#xff1a;前缀和 四.除自身以外数组的乘积&#xff…...

STM32学习笔记十五:WS2812制作像素游戏屏-飞行射击游戏(5)探索动画之帧动画

本章又是个重要的章节——动画。 动画&#xff0c;本质上时一系列静态的画面连续播放&#xff0c;欺骗人眼产生动画效果。这个原理自打十九世纪电影诞生开始&#xff0c;就从来没变过。 我们的游戏中也需要一些动画效果&#xff0c;比如&#xff0c;被击中时的受伤效果&#…...

期末复习(程序设计)

根据字符出现频率排序 【问题描述】 给定一个字符串 s &#xff0c;根据字符出现的 频率 对其进行降序排序。一个字符出现的频率是它出现在字符串中的次数。 返回已排序的字符串。 频率相同的的字符按ascii值降序排序。 s不包含空格、制表符、换行符等特殊字符。 【输入格…...

html-css-js移动端导航栏底部固定+i18n国际化全局

需求&#xff1a;要做一个移动端的仿照小程序的导航栏页面操作&#xff0c;但是这边加上了i18n国家化&#xff0c;由于页面切换的时候会导致国际化失效&#xff0c;所以写了这篇文章 1.效果 切换页面的时候中英文也会跟着改变&#xff0c;不会导致切换后回到默认的语言 2.实现…...

Ubuntu Linux 入门指南:面向初学者

目录 1. Ubuntu Linux 简介 Ubuntu 的由来 Ubuntu 与其他 Linux 发行版的比较 Debian&#xff1a; Fedora&#xff1a; openSUSE&#xff1a; Arch Linux&#xff1a; Linux Mint&#xff1a; 第二部分&#xff1a;安装 Ubuntu 1. 准备安装 系统需求 创建 Ubuntu 启…...

常见算法面试题目

前言 总结一些常见的算法题目&#xff0c;每一个题目写一行思路&#xff0c;方便大家复习。具体题目的来源是下面的网站。 剑指offer 剑指offe2 leetcode200题 leetcode 100题 leetcode150题 leetcode 75题 文章目录 前言二叉树非递归遍历牛客JZ31 栈的压入、弹出序列 (…...

PiflowX组件-JDBCWrite

JDBCWrite组件 组件说明 使用JDBC驱动向任意类型的关系型数据库写入数据。 计算引擎 flink 有界性 Sink: Batch Sink: Streaming Append & Upsert Mode 组件分组 Jdbc 端口 Inport&#xff1a;默认端口 outport&#xff1a;默认端口 组件属性 名称展示名称默…...

算法导论复习题目

这题需要考虑什么呢&#xff1f; 一换元&#xff0c;二要使用主方法猜出结果&#xff0c;三是证明的时候添加一个低阶项来消除 LC检索 C&#xff08;x&#xff09;是从上帝视角来看的成本 对C(x)的一个估计&#xff1a; 由两个部分组成&#xff0c;就相当于由以往的经验对未来…...

HTTPS协议详解

目录 前言 一、HTTPS协议 1、加密是什么 2、为什么要加密 二、常见加密方式 1、对称加密 2、非对称加密 三、数据摘要与数据指纹 1、数据摘要 2、数据指纹 四、HTTPS加密策略探究 1、只使用对称加密 2、只使用非对称加密 3、双方都使用非对称加密 4、对称加密非…...

菜鸟学习vue3笔记-vue3 router回顾

1、路由router pnpm i vue-router2、创建使用环境 1.src下创建 router文件夹、里面创建index.ts文件 //创建一个路由暴露出去//1.引入createRouter import { createRouter, createWebHistory } from "vue-router";// import Home from ../components/Home.vue//…...

Mybatis枚举类型处理和类型处理器

专栏精选 引入Mybatis Mybatis的快速入门 Mybatis的增删改查扩展功能说明 mapper映射的参数和结果 Mybatis复杂类型的结果映射 Mybatis基于注解的结果映射 Mybatis枚举类型处理和类型处理器 再谈动态SQL Mybatis配置入门 Mybatis行为配置之Ⅰ—缓存 Mybatis行为配置…...

2023 NCTF writeup

CRYPTO Sign 直接给了fx,gx&#xff0c;等于私钥给了&#xff0c;直接套代码&#xff0c;具体可以参考&#xff1a; https://0xffff.one/d/1424 fx [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0…...

golang的大杀器协程goroutine

在Golang中&#xff0c;协程&#xff08;Goroutine&#xff09;是轻量级的执行单元&#xff0c;用于实现并发编程。它是Golang语言的重要组成部分&#xff0c;提供了简洁、高效的方式来处理并发任务。 特点&#xff1a; 1&#xff09;轻量级&#xff1a;Go语言的协程是轻量级…...

[Angular] 笔记 9:list/detail 页面以及@Output

1. Output input 好比重力&#xff0c;向下传递数据&#xff0c;list 传给 detail&#xff0c;smart 组件传给 dumb 组件&#xff0c;父组件传给子组件。input 顾名思义&#xff0c;输入数据给组件。 output 与之相反&#xff0c;好比火箭&#xff0c;向上传递数据或事件。ou…...

Linux学习笔记(一)

如果有自己的物理服务器请先查看这篇文章 文章目录 网卡配置Linux基础指令ls:列出目录内容cd(mkdir.rmkdir): 切换文件夹(创建,删除操作)cp:复制文件或目录mv:文件/文件夹移动cat:查看文件vi:文件查看编辑man:查看命令手册more: 查看文件内容less : 查看文件内容 ps: 显示当前进…...

Python 爬虫 教程

python爬虫框架&#xff1a;Scrapyd&#xff0c;Feapder&#xff0c;Gerapy 参考文章&#xff1a; python爬虫工程师&#xff0c;如何从零开始部署ScrapydFeapderGerapy&#xff1f; - 知乎 神器&#xff01;五分钟完成大型爬虫项目 - 知乎 爬虫框架-feapder - 知乎 scrap…...

uniapp原生插件 - android原生插件打包流程 ( 避坑指南一)

【彩带- 避坑知识点】: 当时开发中安卓插件打包成功后&#xff0c;uniapp引用插件aar&#xff0c;用云打包 &#xff0c;总是提示不包含插件。原因是因为module的androidManifest.xml文件没有注册activity。 这一步 很重要&#xff0c;一定要注册。 --------------------------…...

搭建maven私服

maven maven简介 什么是maven&#xff1f; Maven这个单词来自于意第绪语&#xff08;犹太语&#xff09;&#xff0c;意为知识的积累。 Maven项目对象模型(POM)&#xff0c;可以通过一小段描述信息来管理项目的构建&#xff0c;报告和文档的项目管理工具软件。 Maven 除了以…...

EST-100身份证社保卡签批屏按捺终端PC版web版本http协议接口文档,支持web网页开发对接使用

<!DOCTYPE html><html lang"zh-CN"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width,initial-scale1.0"><title>演示DEMO</title><script type"text/…...

基于SpringBoot的毕业论文管理系统

文章目录 项目介绍主要功能截图:部分代码展示设计总结项目获取方式🍅 作者主页:超级无敌暴龙战士塔塔开 🍅 简介:Java领域优质创作者🏆、 简历模板、学习资料、面试题库【关注我,都给你】 🍅文末获取源码联系🍅 项目介绍 基于SpringBoot的毕业论文管理系统,java…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...