当前位置: 首页 > 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…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...