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

【LeetCode每日一题】前缀和的例题1248. 统计「优美子数组」974. 和可被 K 整除的子数组

leetcode 724. 寻找数组的中心索引

题目描述

给定一个整数类型的数组 nums,请编写一个能够返回数组 “中心索引” 的方法。

我们是这样定义数组 中心索引 的:数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。

如果数组不存在中心索引,那么我们应该返回 -1。如果数组有多个中心索引,那么我们应该返回最靠近左边的那一个。

/*** @param {number[]} nums* @return {number}*/
var pivotIndex = function(nums) {let sum = nums.reduce((a, b) => a + b, 0);let leftSum = 0;for(let i = 0; i < nums.length; i++){if(leftSum === sum - leftSum-nums[i]){return i;}leftSum+=nums[i];}return -1
};

560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数

子数组是数组中元素的连续非空序列。

思路:
用map存放前缀和出现的位置,用一个count 维护出现的次数。

/*** @param {number[]} nums* @param {number} k* @return {number}*/
var subarraySum = function(nums, k) {let res = 0;let map = new Map();map.set(0, 1);let prefixSum = 0;for(let i = 0; i < nums.length; i++){prefixSum += nums[i];if(map.has(prefixSum - k)){res += map.get(prefixSum - k);}if(map.has(prefixSum)){map.set(prefixSum, map.get(prefixSum) + 1);}else{map.set(prefixSum, 1);}}return res;
};

930. 和相同的二元子数组

给你一个二元数组 nums ,nums[i] 不是 0 就是 1,和一个整数 goal ,请你统计并返回有多少个和为 goal非空 子数组。

子数组 是数组的一段连续部分。

示例 1:

输入:nums = [1,0,1,0,1], goal = 2
输出:4
解释:
有 4 个满足题目要求的子数组:[1,0,1]、[1,0,1,0]、[0,1,0,1]、[1,0,1]

示例 2:

输入:nums = [0,0,0,0,0], goal = 0
输出:15
/*** @param {number[]} nums* @param {number} goal* @return {number}*/
var numSubarraysWithSum = function(nums, goal) {let map = new Map();map.set(0, 1);let res = 0;let prefixSum = 0;for(let i = 0; i < nums.length; i++){prefixSum += nums[i];if(map.has(prefixSum - goal)){res += map.get(prefixSum - goal);}if(map.has(prefixSum)){map.set(prefixSum, map.get(prefixSum) + 1);}else{map.set(prefixSum, 1);}}return res;
};

leetcode1248. 统计「优美子数组」

给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字,我们就认为这个子数组是「优美子数组」。

请返回这个数组中 「优美子数组」 的数目。

思路:简化数组 + 930. 和相同的二元子数组

var numberOfSubarrays = function(nums, k) {// 简化数组nums = nums.map(item=>item%2===0?0:1)let res = 0;let map = new Map();map.set(0, 1);let prefixSum = 0;for(let i = 0; i < nums.length; i++){prefixSum += nums[i];if(map.has(prefixSum - k)){res += map.get(prefixSum - k);}if(map.has(prefixSum)){map.set(prefixSum, map.get(prefixSum) + 1);}else{map.set(prefixSum, 1);}}return res;
};

974. 和可被 K 整除的子数组

给定一个整数数组 nums 和一个整数 k ,返回其中元素之和可被 k 整除的(连续、非空) 子数组 的数目。

思路:

x - y 能够被 k 整除,

⇒ (x - y)% k = 0

⇒ x % k - y % k = 0

⇒ x % k = y % k

用map存储presum % k 的结果,如果有相同的 ,则说明 x - y 能够被 k 整除

/*** @param {number[]} nums* @param {number} k* @return {number}*/
var subarraysDivByK = function(nums, k) {let res = 0;let map = new Map();map.set(0, 1);let prefixSum = 0 ;for(let i = 0; i < nums.length; i++){prefixSum += nums[i];let key = (prefixSum % k + k) % k; //如果是负数,需要 + k 修正,如果+k 后大于k,需要%k。if(map.has(key)){res += map.get(key);map.set(key, map.get(key) + 1);}else{map.set(key, 1);}}return res;
};

523. 连续的子数组和

给你一个整数数组 nums 和一个整数 k ,编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组:

  • 子数组大小 至少为 2 ,且
  • 子数组元素总和为 k 的倍数。

如果存在,返回 true ;否则,返回 false

如果存在一个整数 n ,令整数 x 符合 x = n * k ,则称 xk 的一个倍数。0 始终视为 k 的一个倍数。

思路:

map :key 存放preSum,value存放第一次出现的索引。只要最长的大于等于2 ,即为存在。

/*** @param {number[]} nums* @param {number} k* @return {boolean}*/
var checkSubarraySum = function(nums, k) {let map = new Map();map.set(0, -1);let prefixSum = 0;for(let i = 0; i < nums.length; i++){prefixSum += nums[i];let key = (prefixSum % k+k)%k;if(map.has(key)){if(i - map.get(key) >= 2){return true;}}else{map.set(key, i);}}return false;
};

相关文章:

【LeetCode每日一题】前缀和的例题1248. 统计「优美子数组」974. 和可被 K 整除的子数组

leetcode 724. 寻找数组的中心索引 题目描述 给定一个整数类型的数组 nums&#xff0c;请编写一个能够返回数组 “中心索引” 的方法。 我们是这样定义数组 中心索引 的&#xff1a;数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。 如果数组不存在中心索引&…...

备战蓝桥杯---数学基础3

本专题主要围绕同余来讲&#xff1a; 下面介绍一下基本概念与定理&#xff1a; 下面给出解这方程的一个例子&#xff1a; 下面是用代码实现扩展欧几里得算法&#xff1a; #include<bits/stdc.h> using namespace std; int gcd(int a,int b,int &x,int &y){if(b…...

[算法学习] 逆元与欧拉降幂

费马小定理 两个条件&#xff1a; p为质数a与p互质 逆元 如果要求 x^-1 mod p &#xff0c;用快速幂求 qmi(x,p-2) 就好 欧拉函数 思路&#xff1a;找到因数 i&#xff0c;phi / i * (i-1)&#xff0c;除干净&#xff0c;判断最后的n 欧拉降幂 欧拉定理 应用示例 m! 是一个…...

【Chrono Engine学习总结】4-vehicle-4.1-vehicle的基本概念

由于Chrono的官方教程在一些细节方面解释的并不清楚&#xff0c;自己做了一些尝试&#xff0c;做学习总结。 1、基本介绍 Vehicle Overview Vehicle Mannel Vehicle的官方demo 1.1 Vehicle的构型 一个车辆由许多子系统构成&#xff1a;悬挂、转向、轮子/履带、刹车/油门、动…...

腾讯云4核8G服务器多少钱?2024精准报价

腾讯云4核8G服务器S5和轻量应用服务器优惠价格表&#xff0c;轻量应用服务器和CVM云服务器均有活动&#xff0c;云服务器CVM标准型S5实例4核8G配置价格15个月1437.3元&#xff0c;5年6490.44元&#xff0c;标准型SA2服务器1444.8元一年&#xff0c;轻量应用服务器4核8G12M带宽一…...

汽车出租管理系统

文章目录 汽车出租管理系统一、系统演示二、项目介绍三、系统部分功能截图四、部分代码展示五、底部获取项目源码&#xff08;9.9&#xffe5;带走&#xff09; 汽车出租管理系统 一、系统演示 汽车租赁系统 二、项目介绍 语言&#xff1a;java 框架&#xff1a;SpringBoot、…...

使用SM4国密加密算法对Spring Boot项目数据库连接信息以及yaml文件配置属性进行加密配置(读取时自动解密)

一、前言 在业务系统开发过程中,我们必不可少的会使用数据库,在应用开发过程中,数据库连接信息往往都是以明文的方式配置到yaml配置文件中的,这样有密码泄露的风险,那么有没有什么方式可以避免呢?方案当然是有的,就是对数据库密码配置的时候进行加密,然后读取的时候再…...

【LeetCode每日一题】二维前缀和基本概念与案例

二维前缀和 根据某个块块 的 左上角坐标&#xff0c;和右下角坐标 求出 块块的累加和。 304. 二维区域和检索 - 矩阵不可变 /*** param {number[][]} matrix*/ var NumMatrix function(matrix) {let row matrix.length;let col matrix[0].length;// 初始化一个二维数组&am…...

计算机网络——网络安全

计算机网络——网络安全 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家&#xff0c; [跳转到网站](https://www.captainbed.cn/qianqiu) 小程一言专栏链接: [link](http://t.csdnimg.cn/ZUTXU) 网络安全何…...

SQl 注入 - 利用报错函数updatexml及extracevalue

环境准备:构建完善的安全渗透测试环境:推荐工具、资源和下载链接_渗透测试靶机下载-CSDN博客 一、updatexml() 函数 1. 使用前提: 在 MySQL 高版本中(大于5.1版本)添加了对 XML 文档进行查询和修改的函数,包括 updatexml() 和 extractvalue()。 2. 显示错误处理: 在…...

ChatGPT高效提问—prompt实践(生成VBA)

ChatGPT高效提问—prompt实践(生成VBA) 2. 生成VBA函数操作Excel ​ 当前Excel表格数据无背景颜色,区分不明显。假如我们想美化数据展示效果,把标题行设置为浅蓝色,其余奇数行设置为橙色,该怎么操作呢?这次我们基于ChatGPT写一个prompt来创建VBA函数。 ​ 输入prompt…...

Ps:直接从图层生成文件(图像资源)

通过Ps菜单&#xff1a;文件/导出/将图层导出到文件 Layers to Files命令&#xff0c;我们可以快速地将当前文档中的每个图层导出为同一类型、相同大小和选项的独立文件。 Photoshop 还提供了一个功能&#xff0c;可以基于文档中的图层或图层组的名称&#xff0c;自动生成指定大…...

springboot-接入ai机器人 汇总

鱼聪明 Java SDKGitHub - liyupi/yucongming-java-sdk: 鱼聪明 AI 的 Java SDK&#xff0c;几行代码使用 AI 助手能力&#xff01;...

蓝桥杯嵌入式第9届真题(完成) STM32G431

蓝桥杯嵌入式第9届真题(完成) STM32G431 题目 分析和代码 main.h /* USER CODE BEGIN Header */ /********************************************************************************* file : main.h* brief : Header for main.c file.* …...

电商小程序03登录页面开发

目录 1 创建应用2 创建页面3 首页功能搭建4 登录页搭建5 设置叠加效果总结 小程序开发在经过需求分析和数据源设计之后&#xff0c;就可以进入到页面开发的阶段了。首先我们需要开发登录的功能。 登录功能要求用户输入用户名和密码&#xff0c;勾选同意用户协议和隐私协议&…...

聊聊PowerJob的CleanService

序 本文主要研究一下PowerJob的CleanService CleanService Slf4j Service public class CleanService {private final DFsService dFsService;private final InstanceInfoRepository instanceInfoRepository;private final WorkflowInstanceInfoRepository workflowInstance…...

Qt QML学习(一):Qt Quick 与 QML 简介

参考引用 QML和Qt Quick快速入门全面认识 Qt Widgets、QML、Qt Quick 1. Qt Widgets、QML、Qt Quick 区别 1.1 QML 和 Qt Quick 是什么关系&#xff1f; 1.1.1 从概念上区分 QML 是一种用户界面规范和标记语言&#xff0c;它允许开发人员创建高性能、流畅的动画和具有视觉吸引…...

Kylin系统下Qt的各种中文问题解决思路

一、编译生成的程序运行,中文乱码 这个比较简单。 Windows下基本就是编码格式设置。ini中文问题,见QSettings读取ini中文key方法。 其他Linux版本没玩过,不清楚。Kylin系统下基本就是缺中文的字库。找个好的中文字库,放到目录下即可,系统目录/usr/lib/fonts,qt的安装目…...

C 练习实例69-约瑟夫环

题目&#xff1a;有n个人围成一圈&#xff0c;顺序排号。从第一个人开始报数&#xff08;从1到3报数&#xff09;&#xff0c;凡报到3的人退出圈子&#xff0c;问最后留下的是原来第几号的那位。 代码&#xff1a; #include <stdio.h> int main() {int n8;int table[n]…...

【Qt Design】界面介绍

文章目录 前言Widget Box&#xff08;工具箱&#xff09;对象查看器Qt Design属性编译器sizePolicy内容 信号/槽编辑器资源浏览器ui文件编辑完窗口后查看代码在Pycharm中添加QtDesign 前言 Widget Box&#xff08;工具箱&#xff09; 提供很多控件 对象查看器 对象查看区域…...

Python:操作 Excel 折叠

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

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

ubuntu系统文件误删(/lib/x86_64-linux-gnu/libc.so.6)修复方案 [成功解决]

报错信息&#xff1a;libc.so.6: cannot open shared object file: No such file or directory&#xff1a; #ls, ln, sudo...命令都不能用 error while loading shared libraries: libc.so.6: cannot open shared object file: No such file or directory重启后报错信息&…...

自然语言处理——文本分类

文本分类 传统机器学习方法文本表示向量空间模型 特征选择文档频率互信息信息增益&#xff08;IG&#xff09; 分类器设计贝叶斯理论&#xff1a;线性判别函数 文本分类性能评估P-R曲线ROC曲线 将文本文档或句子分类为预定义的类或类别&#xff0c; 有单标签多类别文本分类和多…...

面试高频问题

文章目录 &#x1f680; 消息队列核心技术揭秘&#xff1a;从入门到秒杀面试官1️⃣ Kafka为何能"吞云吐雾"&#xff1f;性能背后的秘密1.1 顺序写入与零拷贝&#xff1a;性能的双引擎1.2 分区并行&#xff1a;数据的"八车道高速公路"1.3 页缓存与批量处理…...

高防服务器价格高原因分析

高防服务器的价格较高&#xff0c;主要是由于其特殊的防御机制、硬件配置、运营维护等多方面的综合成本。以下从技术、资源和服务三个维度详细解析高防服务器昂贵的原因&#xff1a; 一、硬件与技术投入 大带宽需求 DDoS攻击通过占用大量带宽资源瘫痪目标服务器&#xff0c;因此…...

规则与人性的天平——由高考迟到事件引发的思考

当那位身着校服的考生在考场关闭1分钟后狂奔而至&#xff0c;他涨红的脸上写满绝望。铁门内秒针划过的弧度&#xff0c;成为改变人生的残酷抛物线。家长声嘶力竭的哀求与考务人员机械的"这是规定"&#xff0c;构成当代中国教育最尖锐的隐喻。 一、刚性规则的必要性 …...