[python 刷题] 1248 Count Number of Nice Subarrays
[python 刷题] 1248 Count Number of Nice Subarrays
题目如下:
Given an array of integers
numsand an integerk. A continuous subarray is called nice if there arekodd numbers on it.Return the number of nice sub-arrays.
这道题和 1343 Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold 挺像的
双指针
先声明,我的写法不是最有效的,其他的双指针/滑动窗口的解法会更加的高效,不过我感觉对我来说这么写是最好理解的
首先题目要求必须要有 k 个奇数,以题目中 Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2 为例,它的 base case 是这样的:

同时,因为两边都是偶数,因此指针是可以向两边延长的,演唱后也都是满足题目需求,即,子数组中有 k 个奇数
首先用两个指针指向 l l l 和 r r r,使用 c o u n t e r counter counter 计算 [ l , l + 1 , . . . , r ] [l, l + 1, ..., r] [l,l+1,...,r] 中的奇数。每次移动 r r r 的时候,更新 c o u n t e r counter counter,这时候会出现两个需要照顾的条件:
-
c o u n t e r > k counter > k counter>k
这个时候就需要不断移动 l l l,一直到 c o u n t e r = = k counter == k counter==k
-
c o u n t e r = = k counter == k counter==k
依旧以上面的案例来说,因为左侧指针没有动过,实际上应该是这样的情况:

这时候新建一个 t e m p temp temp 指针代替右侧指针,并且将 d i f f diff diff 保存下来:

这里的 d i f f diff diff 代表着不同的组合,即 l l l 移动一格时所会产生的不同组合,在移动左侧指针时,每次添加 d i f f diff diff 即可
代码如下:
class Solution:def numberOfSubarrays(self, nums: List[int], k: int) -> int:n = len(nums)res, count = 0, 0l, r = 0, 0while r < n:if nums[r] % 2:count += 1while count > k:if nums[l] % 2:count -= 1l += 1if count == k:res += 1t = r + 1while t < n and not nums[t] % 2:res += 1t += 1diff = t - rr = t - 1while l < r and not nums[l] % 2:res += diffl += 1r += 1return res
prefix sum
使用 prefix sum 就比较简单了,这里是将所有出现奇数的次数全都保存下来到一个变量中,同时,会形成一个 {odd_num: even_num_freq + 1} 的对应关系,这样可以保存不同的组合
如 Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2,它的键值对的关系为 {0: 4, 1: 3, 2: 4},其中保存的对应关系为:
0: [default_value, 2,2,2]
1: [1,2,2]
2: [1,2,2,2]
这样,通过 count[odd_count - k] 就能够获取对应的变化,也就是上一个解法中的 d i f f diff diff,代码如下:
class Solution:def numberOfSubarrays(self, nums: List[int], k: int) -> int:n = len(nums)# 这里使用数组而非字典,不过其原理是一样的# 使用 n + 1 是因为 0 为没有出现 odd 的情况# 而当数组中所有的成员都是 odd 时,count 的长度就为 n + 1count = [0] * (n + 1)# 这个是 base case# 空数组也是一个合法的 subarraycount[0] = 1odd_count = 0res = 0for num in nums:if num % 2 == 1:odd_count += 1if odd_count >= k:res += count[odd_count - k]count[odd_count] += 1return res
相关文章:
[python 刷题] 1248 Count Number of Nice Subarrays
[python 刷题] 1248 Count Number of Nice Subarrays 题目如下: Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it. Return the number of nice sub-arrays. 这道题和 1343 Number of S…...
堆叠注入 [GYCTF2020]Blacklist1
打开题目 判断注入点 输入1,页面回显 输入1 页面报错 输入 1 # 页面正常,说明是单引号的字符型注入 我们输入1; show databases; # 说明有6个数据库 1; show tables; # 说明有三个表 我们直接查看FlagHere的表结构 1;desc FlagHere;# 发…...
算法:Java构建二叉树并递归实现二叉树的前序、中序、后序遍历
先自定义一下二叉树的类: // Definition for a binary tree node. public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val val;this.left…...
既然有了字节流,为什么还要有字符流?
字符流和字节流之间的区别主要在于它们处理数据的方式和用途: 字节流:字节流以字节为单位进行数据的读取和写入,适用于处理二进制数据,如图像、音频和视频文件。字节流是处理底层数据的理想选择,它不会对数据进行编码…...
3+单细胞+代谢+WGCNA+机器学习
今天给同学们分享一篇生信文章“Identification of new co-diagnostic genes for sepsis and metabolic syndrome using single-cell data analysis and machine learning algorithms”,这篇文章发表Front Genet.期刊上,影响因子为3.7。 结果解读&#x…...
音乐推荐与管理系统Python+Django网页界面+协同过滤推荐算法
一、介绍 音乐推荐与管理系统。本系统采用Python作为主要开发语言,前端使用HTML、CSS、BootStrap等技术搭建界面平台,后端使用Django框架处理请求,并基于Ajax等技术实现前端与后端的数据通信。在音乐个性推荐功能模块中采用通过Python编写协…...
(论文阅读15/100)You Only Look Once: Unified, Real-Time Object Detection
文献阅读笔记 简介 题目 You Only Look Once: Unified, Real-Time Object Detection 作者 Joseph Redmon, Santosh Divvala, Ross Girshick, Ali Farhadi 原文链接 https://arxiv.org/pdf/1506.02640.pdf 《You Only Look Once: Unified, Real-Time Object Detection》…...
init进程启动过程
首语 init进程是Android系统中用户空间的第一个进程,进程号为1,是Android系统启动的一个关键步骤,作为第一个进程,它的主要工作是创建Zygote和启动属性服务等。init进程是由多个源文件共同组成的,源码目录在system/co…...
全网最详细的【shell脚本的入门】
🏅我是默,一个在CSDN分享笔记的博主。📚📚 🌟在这里,我要推荐给大家我的专栏《Linux》。🎯🎯 🚀无论你是编程小白,还是有一定基础的程序员,这…...
CH10_简化条件逻辑
分解条件表达式(Decompose Conditional) if (!aDate.isBefore(plan.summerStart) && !aDate.isAfter(plan.summerEnd))charge quantity * plan.summerRate; elsecharge quantity * plan.regularRate plan.regularServiceCharge;if (summer())…...
nn.LayerNorm解释
这个是层归一化。我们输入一个参数,这个参数就必须与最后一个维度对应。但是我们也可以输入多个维度,但是必须从后向前对应。 import torch import torch.nn as nna torch.rand((100,5)) c nn.LayerNorm([5]) print(c(a).shape)a torch.rand((100,5,…...
Springboot搭建微服务案例之Eureka注册中心
一、父工程依赖管理 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apache.org…...
【MySQL】用户管理权限控制
文章目录 前言一. 用户管理1. 创建用户2. 删除用户3. 修改用户密码 二. 权限控制1. 用户授权2. 查看权限3. 回收权限 结束语 前言 MySQL的数据其实也以文件形式保存,而登录信息同样保存在文件中 MySQL的数据在Linux下默认路径是/var/lib/mysql 登录MySQL同样也可以…...
若依框架前后端分离版服务器部署,前端nginx的配置
server {listen 80;server_name 120.46.177.184;index index.php index.html index.htm default.php default.htm default.html;root /www/wwwroot/qilaike-vue/dist;#SSL-START SSL相关配置,请勿删除或修改下一行带注释的404规则#error_page 404/404.html;#SSL-END…...
基于单片机的滚筒洗衣机智能控制系统设计
收藏和点赞,您的关注是我创作的动力 文章目录 概要 一、系统整体设计方案2.1控制系统的功能2.2设计的主要内容 二、硬件设计3.1 控制系统整体框图3.2 电源电路 三 软件设计主程序设计仿真设计 四、 结论 概要 因此我们需要一个完善的智能系统来设计一个全自动滚筒洗…...
简述多模态学习中,对齐、融合和表示
在多模态学习中,对齐、融合和表示是三个核心概念,它们相互关联,共同支持多模态数据的处理和分析。 对齐(Alignment) 对齐是多模态学习中的一个关键步骤,它涉及到如何在不同的数据模态之间发现和建立对应关…...
Kotlin 进阶函数式编程技巧
Kotlin 进阶函数式编程技巧 Kotlin 简介 软件开发环境不断变化,要求开发人员不仅适应,更要进化。Kotlin 以其简洁的语法和强大的功能迅速成为许多人进化过程中的信赖伙伴。虽然 Kotlin 的初始吸引力可能是它的简洁语法和与 Java 的互操作性,…...
操作系统——内存映射文件(王道视频p57)
1.总体概述: 2.传统文件访问方式: 我认为,这种方式最大的劣势在于,如果要对整个文件的不同部分进行多次操作的话,这样确实开销可能会大一些,而且程序员还要指定对应的“分块”载入到内存中 3.内存映射文件…...
王道p18 07.将两个有序顺序表合并为一个新的有序顺序表,并由函数返回结果顺序表。(c语言代码实现)
视频讲解在这:👇 p18 第7题 c语言代码实现王道数据结构课后代码题_哔哩哔哩_bilibili 本题代码如下 int merge(struct sqlist* A, struct sqlist* B, struct sqlist* C) {if (A->length B->length > C->length)//大于顺序表的最大长度r…...
2024最新mac电脑清理垃圾的软件有哪些?
mac电脑是许多人喜爱的电子产品,它拥有优美的设计、流畅的操作系统和强大的性能。但是,随着使用时间的增长,mac电脑也会积累一些不必要的垃圾文件,这些文件会占用宝贵的存储空间,影响电脑的运行速度和稳定性。因此&…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
数据库分批入库
今天在工作中,遇到一个问题,就是分批查询的时候,由于批次过大导致出现了一些问题,一下是问题描述和解决方案: 示例: // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...
代理篇12|深入理解 Vite中的Proxy接口代理配置
在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...
SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...
MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)
macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 🍺 最新版brew安装慢到怀疑人生?别怕,教你轻松起飞! 最近Homebrew更新至最新版,每次执行 brew 命令时都会自动从官方地址 https://formulae.…...
