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

【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算法&#xff1a;滑动窗口及双指针总结 LeetCode1248. 统计「优美子数组」 给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字&#xff0c;我们就认为这个子数组是「优美子数组」。 请返回这个数组中 「优美子数组」 的数…...

C语言导航 4.1语法基础

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

使用 Python 和 Py2Neo 构建 Neo4j 管理脚本

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

Centos 7 安装wget

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

定时器的小应用

第一个项目 第一步&#xff0c;RCC开启时钟&#xff0c;这个基本上每个代码都是第一步&#xff0c;不用多想&#xff0c;在这里打开时钟后&#xff0c;定时器的基准时钟和整个外设的工作时钟就都会同时打开了 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重启网卡&#xff1a;systemctl restart network.service ping不通域名…...

数据结构与算法分析模拟试题及答案5

模拟试题&#xff08;五&#xff09; 一、单项选择题&#xff08;每小题 2 分&#xff0c;共20分&#xff09; &#xff08;1&#xff09;队列的特点是&#xff08;   &#xff09;。 A&#xff09;先进后出 B&#xff09;先进先出 C&#xff09;任意位置进出 D&#xff0…...

.NET 9.0 中 System.Text.Json 的全面使用指南

以下是一些 System.Text.Json 在 .NET 9.0 中的使用方式&#xff0c;包括序列化、反序列化、配置选项等&#xff0c;并附上输出结果。 基本序列化和反序列化 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库&#xff0c;可以轻松地从网页中提取数据。但是&#xff0c;当网页返回的编码格式与Python默认的编码格式不一致时&#xff0c…...

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的聊天机器人构建的文章。 这篇论文在待读列表很长时间了&#xff0c;一直没有读&#xff0c;看题目以为FACTS是总结的一些事实经验&#xff0c;阅读过才发现FAC…...

【配置后的基本使用】CMake基础知识

&#x1f308; 个人主页&#xff1a;十二月的猫-CSDN博客 &#x1f525; 系列专栏&#xff1a; &#x1f3c0;各种软件安装与配置_十二月的猫的博客-CSDN博客 &#x1f4aa;&#x1f3fb; 十二月的寒冬阻挡不了春天的脚步&#xff0c;十二点的黑夜遮蔽不住黎明的曙光 目录 1.…...

ollama+springboot ai+vue+elementUI整合

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

【项目开发】理解SSL延迟:为何HTTPS比HTTP慢?

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

2.STM32之通信接口《精讲》之USART通信

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

Bootstrap和jQuery开发案例

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

Qt 之 qwt和QCustomplot对比

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

【STM32】MPU6050简介

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

Oracle 单机及 RAC 环境 归档模式及路径修改

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

抽象java入门1.5.3.1——类的进阶

前言&#xff1a;在研究神技代码Hello word的时候&#xff0c;发现了一个重大公式bug&#xff0c;在代码溯源中&#xff0c;我发现了一个奇怪的东西&#xff0c;就是OUT不是类中类&#xff08;不是常规类的写法&#xff09; 内容总结&#xff1a; 代码运行的顺序复习 正片开始…...

python——模块 迭代器 正则

一、python模块 先创建一个 .py 文件&#xff0c;这个文件就称之为 一个模块 Module。 使用模块的优点&#xff1a; 模块化编程&#xff0c;多文件编程 1.2 模块的使用 1.2.1 import语句 想要B.py文件中&#xff0c;使用A.py文件&#xff0c;只需要在B.py文件中使用关键字…...

QT仿QQ聊天项目,第三节,实现聊天界面

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

Linux-何为CentOS

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

C++中的 std::optional

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

猫狗识别之BUG汇总

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

【论文复现】自动化细胞核分割与特征分析

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

排序算法 -快速排序

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

K8S 查看pod节点的磁盘和内存使用情况

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

华为HCIP——MSTP/RSTP与STP的兼容性

一、MSTP/RSTP与STP的兼容性的原理&#xff1a; 1.BPDU版本号识别&#xff1a;运行MSTP/RSTP协议的交换机会根据收到的BPDU&#xff08;Bridge Protocol Data Unit&#xff0c;桥协议数据单元&#xff09;版本号信息自动判断与之相连的交换机的运行模式。如果收到的是STP BPDU…...

AI 大模型如何重塑软件开发流程:现状与未来展望

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