【C++滑动窗口】1248. 统计「优美子数组」|1623
本文涉及的基础知识点
C++算法:滑动窗口及双指针总结
LeetCode1248. 统计「优美子数组」
给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字,我们就认为这个子数组是「优美子数组」。
请返回这个数组中 「优美子数组」 的数目。
示例 1:
输入:nums = [1,1,2,1,1], k = 3
输出:2
解释:包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
示例 2:
输入:nums = [2,4,6], k = 1
输出:0
解释:数列中不包含任何奇数,所以不存在优美子数组。
示例 3:
输入:nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出:16
提示:
1 <= nums.length <= 50000
1 <= nums[i] <= 105
1 <= k <= nums.length
滑动窗口
nums[i…j1]包括k个奇数的数字,且j1最小。
nums[i…j2]包括k+1个奇数的数字,且j2最小。
枚举i,ans += j2-j1。此方法称为三指针。
为了简化代码,可以用两个滑动窗口。
一,N-j1,以i开头,包括k个及以上奇数的数目。
二,N-j2,以i开头,包括k+1个及以上奇数的数目。
代码
核心代码
class Solution {public:int numberOfSubarrays(vector<int>& nums, int k) {const int N = nums.size();auto Do = [&](int len) {int cnt = 0;long long res = 0;for (int i = 0, j = 0; i < N; i++) {while ((j < N) && (cnt < len )) {cnt += bool(nums[j] & 1); j++;}if (cnt >= len){res += N - j+1;}cnt -= bool(nums[i] & 1);}return res;};return Do(k) - Do(k + 1);}};
单元测试
vector<int> nums; int k;TEST_METHOD(TestMethod11){nums = { 1,1,2,1,1 },k=3;auto res = Solution().numberOfSubarrays(nums, k);AssertEx(2, res);}TEST_METHOD(TestMethod12){nums = { 2,4,6 }, k = 1;auto res = Solution().numberOfSubarrays(nums, k);AssertEx(0, res);}TEST_METHOD(TestMethod13){nums = { 2,2,2,1,2,2,1,2,2,2 }, k = 2;auto res = Solution().numberOfSubarrays(nums, k);AssertEx(16, res);}
扩展阅读
我想对大家说的话 |
---|
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。 |
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作 |
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注 |
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。
相关文章:

【C++滑动窗口】1248. 统计「优美子数组」|1623
本文涉及的基础知识点 C算法:滑动窗口及双指针总结 LeetCode1248. 统计「优美子数组」 给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字,我们就认为这个子数组是「优美子数组」。 请返回这个数组中 「优美子数组」 的数…...

C语言导航 4.1语法基础
第四章 顺序结构程序设计 第一节 语法基础 语句概念 语句详解 程序详解 4.1.1语句概念 说明:构成高级语言源程序的基本单位。 特征:在C语言中语句以分号作为结束标志。 分类: (1)简单语句:空语句、…...

使用 Python 和 Py2Neo 构建 Neo4j 管理脚本
Neo4j 是一个强大的图数据库,适合处理复杂的关系型数据。借助 Python 的 py2neo 库,我们可以快速实现对 Neo4j 数据库的管理和操作。本文介绍一个功能丰富的 Python 脚本,帮助用户轻松管理 Neo4j 数据库,包含启动/停止服务、清空数…...

Centos 7 安装wget
Centos 7 安装wget 最小化安装Centos 7 的话需要上传wget rpm包之后再路径下安装一下。rpm包下载地址(http://mirrors.163.com/centos/7/os/x86_64/Packages/) 1、使用X-ftp 或者WinSCP等可以连接上传的软件都可以首先连接服务器,这里我用的…...

定时器的小应用
第一个项目 第一步,RCC开启时钟,这个基本上每个代码都是第一步,不用多想,在这里打开时钟后,定时器的基准时钟和整个外设的工作时钟就都会同时打开了 RCC_APB1PeriphClockCmd(RCC_APB1Periph_TIM2, ENABLE);第二步&…...

linux企业中常用NFS、ftp服务
1.静态ip配置 修改ip地址为静态vim /etc/sysconfig/network-scripts/ifcfg-enxxx BOOTPROTO"static" IPADDR192.168.73.10 GATEWAY192.168.73.2 # 该配置与虚拟机网关一致 NETMASK255.255.255.0重启网卡:systemctl restart network.service ping不通域名…...

数据结构与算法分析模拟试题及答案5
模拟试题(五) 一、单项选择题(每小题 2 分,共20分) (1)队列的特点是( )。 A)先进后出 B)先进先出 C)任意位置进出 D࿰…...

.NET 9.0 中 System.Text.Json 的全面使用指南
以下是一些 System.Text.Json 在 .NET 9.0 中的使用方式,包括序列化、反序列化、配置选项等,并附上输出结果。 基本序列化和反序列化 using System; using System.Text.Json; public class Program {public class Person{public string Name { get; se…...

Python自动检测requests所获得html文档的编码
使用chardet库自动检测requests所获得html文档的编码 使用requests和BeautifulSoup库获取某个页面带来的乱码问题 使用requests配合BeautifulSoup库,可以轻松地从网页中提取数据。但是,当网页返回的编码格式与Python默认的编码格式不一致时,…...

11.12机器学习_特征工程
四 特征工程 1 特征工程概念 特征工程:就是对特征进行相关的处理 一般使用pandas来进行数据清洗和数据处理、使用sklearn来进行特征工程 特征工程是将任意数据(如文本或图像)转换为可用于机器学习的数字特征,比如:字典特征提取(特征离散化)、文本特征提取、图像特征提取。 …...

RAG经验论文《FACTS About Building Retrieval Augmented Generation-based Chatbots》笔记
《FACTS About Building Retrieval Augmented Generation-based Chatbots》是2024年7月英伟达的团队发表的基于RAG的聊天机器人构建的文章。 这篇论文在待读列表很长时间了,一直没有读,看题目以为FACTS是总结的一些事实经验,阅读过才发现FAC…...

【配置后的基本使用】CMake基础知识
🌈 个人主页:十二月的猫-CSDN博客 🔥 系列专栏: 🏀各种软件安装与配置_十二月的猫的博客-CSDN博客 💪🏻 十二月的寒冬阻挡不了春天的脚步,十二点的黑夜遮蔽不住黎明的曙光 目录 1.…...

ollama+springboot ai+vue+elementUI整合
1. 下载安装ollama (1) 官网下载地址:https://github.com/ollama/ollama 这里以window版本为主,下载链接为:https://ollama.com/download/OllamaSetup.exe。 安装完毕后,桌面小图标有一个小图标,表示已安装成功&…...

【项目开发】理解SSL延迟:为何HTTPS比HTTP慢?
未经许可,不得转载。 文章目录 前言HTTP与HTTPS的耗时差异TCP握手HTTPS的额外步骤:SSL握手使用curl测量SSL延迟性能与安全的权衡前言 在互联网发展的早期阶段,Netscape公司设计了SSL(Secure Sockets Layer)协议,为网络通信提供加密和安全性。有人曾提出一个大胆的设想:…...

2.STM32之通信接口《精讲》之USART通信
有关通信详解进我主页观看其他文章!【免费】SPIIICUARTRS232/485-详细版_UART、IIC、SPI资源-CSDN文库 通过以上可以看出。根据电频标准,可以分为TTL电平,RS232电平,RS485电平,这些本质上都属于串口通信。有区别的仅是…...

Bootstrap和jQuery开发案例
目录 1. Bootstrap和jQuery简介及优势2. Bootstrap布局与组件示例:创建一个响应式的表单界面 3. jQuery核心操作与事件处理示例:使用jQuery为表单添加交互 4. Python后端实现及案例代码案例 1:用户登录系统Flask后端代码前端代码 5. 设计模式…...

Qt 之 qwt和QCustomplot对比
QWT(Qt Widgets for Technical Applications)和 QCustomPlot 都是用于在 Qt 应用程序中绘制图形和图表的第三方库。它们各有优缺点,适用于不同的场景。 以下是 QWT 和 QCustomPlot 的对比分析: 1. 功能丰富度 QWT 功能丰富&a…...

【STM32】MPU6050简介
文章目录 MPU6050简介MPU6050关键块带有16位ADC和信号调理的三轴MEMS陀螺仪具有16位ADC和信号调理的三轴MEMS加速度计I2C串行通信接口 MPU6050对应的数据手册:MPU6050 陀螺仪加速度计 链接: https://pan.baidu.com/s/13nwEhGvsfxx0euR2hMHsyw?pwdv2i6 提取码: v2i6…...

Oracle 单机及 RAC 环境 归档模式及路径修改
Oracle 数据库的使用过程中经常会根据需求的不同而调整归档模式,也经常会修改归档文件存放路径。 下面分别演示单机及 RAC 环境下修改归档模式及路径的操作步骤。 一、单机环境 1.查询当前归档模式及路径 SQL> archive log list Database log mode …...

抽象java入门1.5.3.1——类的进阶
前言:在研究神技代码Hello word的时候,发现了一个重大公式bug,在代码溯源中,我发现了一个奇怪的东西,就是OUT不是类中类(不是常规类的写法) 内容总结: 代码运行的顺序复习 正片开始…...

python——模块 迭代器 正则
一、python模块 先创建一个 .py 文件,这个文件就称之为 一个模块 Module。 使用模块的优点: 模块化编程,多文件编程 1.2 模块的使用 1.2.1 import语句 想要B.py文件中,使用A.py文件,只需要在B.py文件中使用关键字…...

QT仿QQ聊天项目,第三节,实现聊天界面
一,界面控件示意图 界面主要由按钮QPushButton,标签QLabel,列表QListWidget 要注意的是QListWidget既是实现好友列表的控件,也是实现聊天气泡的控件 二,控件样式 QPushButton#btn_name {border:none;}QPushButton#btn_close {border:1px;bac…...

Linux-何为CentOS
今年公司做的 POC 项目中,越来越多地听到客户开始或已经将系统迁移到麒麟、统信、openEuler,但还是有很多客户在用CentOS 7,或者和CentOS 7兼容的其他Linux。今天把CentOS 7相关概念统一整理下供后续参考使用 何为CentOS CentOS — Communit…...

C++中的 std::optional
std::optional<T>是 C17 中的一个标准库组件,optional <T>对象默认是空的,也就是处于无效状态,给它赋值后因为里面有了元素,就变成了有效状态。 1.引入背景 c函数常用返回值表示函数是否执行成功。如返回nullptr表示…...

猫狗识别之BUG汇总
一、github登不上去问题 下载watt toolkit 下载地址:https://steampp.net/ 可以下载后加速,访问github 二、猫狗总体参考核心 B哥的博客 https://github.com/bubbliiiing/classification-keras?tabreadme-ov-file 三、CSDN很多会员才能阅读问题 根据…...

【论文复现】自动化细胞核分割与特征分析
📝个人主页🌹:Eternity._ 🌹🌹期待您的关注 🌹🌹 ❀自动化细胞核分割与特征分析 引言1. 效果展示2. HoverNet概述3. HoverNet原理分析整体网络框架实例分割原理 4. HoverNet评估结果5. 复现过程…...

排序算法 -快速排序
文章目录 1. 快速排序(Quick Sort)1.1、 简介1.2、 快速排序的步骤 2. Hoare 版本2.1、 基本思路1. 分区(Partition)2. 基准选择(Pivot Selection)3. 递归排序(Recursive Sorting) 2…...

K8S 查看pod节点的磁盘和内存使用情况
查看某个节点的磁盘使用率: kubectl exec -it pod名称 -n 命名空间 – df -h 查询所有节点的已使用内存: kubectl top pods --all-namespaces | grep itsm 查询某个节点的总内存, kubectl describe pod itsr-domain-59f4ff5854-hzb68 --nam…...

华为HCIP——MSTP/RSTP与STP的兼容性
一、MSTP/RSTP与STP的兼容性的原理: 1.BPDU版本号识别:运行MSTP/RSTP协议的交换机会根据收到的BPDU(Bridge Protocol Data Unit,桥协议数据单元)版本号信息自动判断与之相连的交换机的运行模式。如果收到的是STP BPDU…...

AI 大模型如何重塑软件开发流程:现状与未来展望
随着人工智能技术的飞速发展,AI 大模型的出现正在深刻改变软件开发行业的传统模式。从代码生成到智能测试,AI 已渗透到软件开发的各个环节,为开发者提供了前所未有的效率提升,同时也带来了全新的挑战与思考。在本文中,…...