【前缀和算法】--- 进阶题目赏析

 Welcome to 9ilk's Code World

       

(๑•́ ₃ •̀๑) 个人主页:        9ilk

(๑•́ ₃ •̀๑) 文章专栏:      算法Journey


本篇我们来赏析前缀和算法的进阶题目。


🏠 和可被K整除的子数组

📌 题目解析

和可被k整除的子数组

📌 算法原理

这道题与"和为K的子数组"其实是类似的,我们以i位置为结尾的子数组观察,如果能找到一段右边部分能被k整除,此时问题转化成在这段区间内找有多少个前缀和等于x使得sum[i] -x 能被k整除?

  • 同余定理
如果 (a - b) % n == 0 ,那么我们可以得到⼀个结论: a % n == b % n 。⽤⽂字叙述就是,如果两个数相减的差能被 n 整除,那么这两个数对 n 取模的结果相同。
因此我们只需要找是否有x对k的余数等于sum对k的余数即可。
  • 前缀和为负数的情况

以K=4为例子,求出某个前缀和为-1,-1%K应该为3,但有的编程语言-1%K = -1(不同编程语言对商的取整是不同的,有的向0取整,有的向负无穷取整).这里的-1应该要加上K,转正成3.这是因为-1和3分别模4结果看似不相等,但是3-(-1) = 4,4%4 == 0,所以前缀和-1和3其实是等价的,只是不同语言对%运算的处理不同。

---》修正:我们应该让正负统一,毕竟他们是等价的,即求余数(a%p + p)%p

问题转化为:在[ 0 , i - 1]区间内,找到有多少个前缀和的余数等于(sum%k+k)%k

我们哈希表此时存的不是前缀和,而是求前缀和的余数!

参考代码:

class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {int sum =  0;int n = nums.size();unordered_map<int,int> hash;int count = 0;hash[0] = 1;//sum[i]恰好就是能被整除for(int i = 0  ; i < n;i++){sum += nums[i];int leftnum =  (sum%k + k)%k;if(hash[leftnum]) count += hash[leftnum];hash[leftnum]++;}return count;}};

🏠 连续数组

📌 题目解析

连续数组

  • 数组中的数字不是0就是1。

📌 算法原理

本题也是能很好地转化,如果我们将所有的0转化为-1,此时问题转化为在数组中找最长的子数组,使子数组中所有元素为0(和为0的子数组)。

  • 由于涉及最长的子数组,哈希表里应该存的是某个位置的前缀和和这个位置的下标。
  • 使用完i位置之后,再将其丢进哈希表。
  • 长度求法:i - j.

  • 如果重复的<sum,i>,此时我们只需保留前面的那一对。(因为我们要最长的子数组,也就是要sum[i] - 0 = sum这个前缀和越短越好)
  • 默认前缀和为0的情况,此时表示sum正好为0,我们需要在这段区间的左边找等于0的子数组,显然是不存在的,因此设置hash[0] = -1即可。

参考代码:

class Solution 
{public:int findMaxLength(vector<int>& nums) {unordered_map<int, int> hash;hash[0] = -1; // 默认有⼀个前缀和为 0 的情况int sum = 0, ret = 0;for(int i = 0; i < nums.size(); i++){sum += nums[i] == 0 ? -1 : 1; // 计算当前位置的前缀和if(hash.count(sum)) ret = max(ret, i - hash[sum]);else hash[sum] = i;}return ret;}
};

🏠 矩阵区域和

📌 题目解析

矩阵的区域和

📌 算法原理

  • 由于i - k <= r <= i + k 和 j - k <= c <= j + k,所以r和c都分别有最大值和最小值,问题转化为求某块区域的面积,可以用到我们的二维前缀和,具体可跳转至前缀和模板
  • 由于i-k和i+k/j-k和j+k可能超出行数和列数,所以当超过时,我们应该取二维的边界。

参考代码:

class Solution {
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {//int n = mat.size();int m = mat[0].size();vector<vector<int>> dp(n + 1, vector<int>(m + 1));vector<vector<int>> answer(n, vector<int>(m));//获得二维前缀和数组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] + mat[i - 1][j - 1] - dp[i - 1][j - 1];}}//使用前缀和数组for (int i = 0; i < n; i++){for (int j = 0; j < m; j++) {  //确定下标int x1 = ((i - k) < 0) ? 0 : i - k;int x2 = (i + k >= n) ? n - 1 : i + k;int y1 = (j - k < 0) ? 0 : j - k;int y2 = (j + k >= m) ? m - 1 : j + k;answer[i][j] = dp[x2 + 1][y2 + 1] - dp[x2 + 1][y1] - dp[x1][y2 + 1] + dp[x1][y1];}}return answer;}
};

通过这几道题我们可以发现,在做前缀和题目我们当要求一段连续区间(比如子数组)可以想到用前缀和,此时需要进行适当的转化。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/413980.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

线性回归算法详解

目录 线性回归算法 线性回归方程 误差项分析 似然函数求解 线性回归求解 梯度下降算法 下山方向选择 梯度下降优化 梯度下降策略对比 学习率对结果的影响 代码实现 线性回归算法 线性回归是回归算法中最简单、实用的算法之一&#xff0c;在机器学习中很多知识点都是…

【网络】数据链路层协议——以太网,ARP协议

目录 1.局域网转发 2.MAC地址 2.1.什么是MAC地址 2.2.Mac地址的作用 2.3.MAC地址和IP地址的区别和联系 3.以太网协议 4.MTU&#xff0c;IP MTU&#xff0c;MSS 4.1.MTU 4.2. IP MTU 4.3. MSS 4.4. 区别及联系 5.局域网的数据碰撞 5.1.局域网内通信过程 5.2.数据碰…

宏集MIRO-L230工业路由器: 一站式全球联网解决方案

在日益互联的世界中&#xff0c;全球覆盖的稳定连接已成为业务成功的关键因素。宏集非常高兴地向您介绍我们的最新创新产品——MIRO-L230工业路由器&#xff0c;这是一款为现代企业量身定制的LTE路由器&#xff0c;为用户带来前所未有的稳定连接体验。 宏集MIRO-L230工业路由器…

墨兰:花语寓意、神秘传说与独特魅力全解析

在繁花似锦的植物世界中&#xff0c;墨兰宛如一位优雅的隐士&#xff0c;静静地散发着独特的魅力。它那婀娜的身姿和淡雅的芬芳&#xff0c;仿佛在诉说着一个个古老而神秘的故事。当我们凝视着墨兰&#xff0c;不禁会被它那独特的气质所吸引&#xff0c;想要探寻它背后隐藏的花…

电容的分类

电容作为电子产品中不可或缺的元件&#xff0c;其种类繁多&#xff0c;各具特色。以下是电容的主要分类、作用及优缺点概述&#xff1a; 一、电容的分类 电容的分类方式多样&#xff0c;常见的分类方式包括按结构、用途、电解质类型及制造材料等。 按结构分类&#xff1a; 固…

C++编程-递归算法1

目录 先言 关于递归算法 例题一 题目描述 算法分析 标准程序 代码分析 例题二 题目描述 算法分析 标准程序 例题三 题目描述 算法分析 标准程序 代码分析 例题四 题目描述 标准程序 代码分析 后言 先言 从今天开始&#xff0c;我们将新的算法——递归&…

大二必做项目贪吃蛇超详解之中篇游戏设计与分析

贪吃蛇系列文章 上篇win32 中篇设计与分析 文章目录 贪吃蛇系列文章1. 地图1. 1 <locale.h>本地化1. 2 类项1. 3 setlocale函数1. 4 宽字符的打印1. 5 地图坐标 2. 蛇身和食物3. 数据结构设计4. 游戏流程设计5. 核心逻辑实现分析5. 1 游戏主逻辑5. 2 GameStart5. 2. 1 S…

145. 利用 Redis Bitmap实践: 用户签到统计

文章目录 一、Redis Bitmap简介二、Bitmap 的主要应用三、Go使用Redis实现签到统计用户签到查询用户签到状态统计今年累计签到天数统计当月的签到情况 总结 在现代应用程序中&#xff0c;用户签到是一个常见的功能。我们通常使用 MySQL 数据库来存储用户的签到记录。然而&#…

Go入门:gin框架极速搭建图书管理系统

Go入门:gin框架极速搭建图书管理系统 前言 本项目适合 Golang 初学者,通过简单的项目实践来加深对 Golang 的基本语法和 Web 开发的理解。 项目源码请私信,欢迎前往博主博客torna.top免费查看。 项目结构 D:. ├─ go.mod ├─ go.sum │ ├─ cmd │ └─ main │ …

Docker 容器编排之 Docker Compose

目录 1 Docker Compose 概述 1.1 主要功能 1.2 工作原理 1.3 Docker Compose 中的管理层 2 Docker Compose 的常用命令参数 2.1 服务管理 2.1.1 docker-compose up &#xff1a; 2.1.2 docker-compose down &#xff1a; 2.1.3 docker-compose start &#xff1a; 2.1.4 docker…

OpenCV绘图函数(7)从一个椭圆定义中提取出多边形的顶点坐标函数ellipse2Poly()的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 近似一个椭圆弧为一个多边形线。 函数 ellipse2Poly 计算近似指定椭圆弧的多边形线的顶点。它被 ellipse 函数所使用。如果 arcStart 大于 arcEn…

景芯SoC A72实战反馈

先说结论&#xff1a; 内容非常全面&#xff0c;讲解到位&#xff0c;会有专门的工程师一对一答疑&#xff0c;整个项目跑下来提升非常大&#xff0c;绝对物超所值&#xff01; 一些细节&#xff1a; 本人微电子专业研一在读&#xff0c;有过两次简单的数字芯片流片经历&…

spring security 相关过滤器

Spring Security 提供了 30 多个过滤器。默认情况下Spring Boot 在对 SpringSecurity 进入自动化配置时&#xff0c;会创建一个名为 SpringSecurityFilerChain 的过滤器&#xff0c;并注入到Spring容器中&#xff0c;这个过滤器将负责所有的安全管理&#xff0c;包括用户认证、…

Windows系统中批量管理Windows服务器远程桌面工具——RDCMan

一、背景 在公司没有部署对应的堡垒机系统之前,做运维测试工作的人员,需要管理大量的服务器,每天需要对服务器进行必要的巡检、系统更新发布等内容,特别是有很多Windows服务器的时候,如果我们使用Windows自带的“远程桌面连接”只能一台台连接,比较繁琐。并且不能知道那台…

十二星座男女、穿越到古代会成为什麽角色 。

白羊座&#xff08; 大将军 &#xff09;&#xff1b; 金牛座&#xff08;财务大臣&#xff09;&#xff1b; 双子座&#xff08; 奸臣 &#xff09;&#xff1b; 巨蟹座&#xff08;御厨太医&#xff09;&#xff1b; 狮子座&#xff08;皇帝&#xff09;&#xff1b; …

虚幻5|按键触发学习

一&#xff0c;如图参考 1.下移 驱动阈值 越大按时间长才会触发&#xff0c;越小很快就可以触发 2.按下 当按下超出驱动阈值大小就会触发一次&#xff0c;这里的驱动阈值只能设置再0.1~1的大小 3.已松开 当按下的时候&#xff0c;先触发单次的started&#xff0c;如果按压…

精选算法编程题

一、有序数组的平方 给你一个按 非递减顺序 排序的整数数组 nums&#xff0c;返回 每个数字的平方 组成的新数组&#xff0c;要求也按 非递减顺序 排序。 示例 1&#xff1a; 输入&#xff1a;nums [-4,-1,0,3,10]输出&#xff1a;[0,1,9,16,100]解释&#xff1a;平方后&am…

中国各城市金融科技公司数目数据集(2009-2023年)

金融科技&#xff08;FinTech&#xff09;是金融与科技深度融合的产物&#xff0c;它利用大数据、云计算、人工智能、区块链等现代信息技术手段&#xff0c;对传统金融产品、业务、流程及服务模式进行革新&#xff0c;从而实现金融服务效率的提升、风险管理的优化以及客户体验的…

《深入浅出WPF》读书笔记.8路由事件

《深入浅出WPF》读书笔记.8路由事件 背景 路由事件是直接响应事件的变种。直接响应事件&#xff0c;事件触发者和事件响应者必须显示订阅。而路由事件的触发者和事件响应者之间的没有显示订阅&#xff0c;事件触发后&#xff0c;事件响应者安装事件监听器&#xff0c;当事件传…

我熟悉你的NLP焦虑,只因没有它

大家好&#xff0c;我是凡人。 最近凡人被一个NLP&#xff08;神经语言程序学[Neuro-Linguistic Programming]的英文缩写&#xff09;学习内容给震惊到了&#xff0c;熟悉NLP的同学都知道&#xff0c;NLP知识不仅庞大而且很有深度。 比如&#xff1a;机器信息就包含下图内容 肝…