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

【C++ 区间位运算】3209. 子数组按位与值为 K 的数目|2050

本文涉及知识点

位运算、状态压缩、枚举子集汇总

LeetCode3209. 子数组按位与值为 K 的数目

给你一个整数数组 nums 和一个整数 k ,请你返回 nums 中有多少个子数组
满足:子数组中所有元素按位 AND 的结果为 k 。
示例 1:
输入:nums = [1,1,1], k = 1
输出:6
解释:
所有子数组都只含有元素 1 。
示例 2:
输入:nums = [1,1,2], k = 1
输出:3
解释:
按位 AND 值为 1 的子数组包括:[1,1,2], [1,1,2], [1,1,2] 。
示例 3:
输入:nums = [1,2,3], k = 2
输出:2
解释:
按位 AND 值为 2 的子数组包括:[1,2,3], [1,2,3] 。
提示:
1 <= nums.length <= 105
0 <= nums[i], k <= 109

代码

核心代码

class CRangCal {
public:template<class _Pr, class T = int>static vector<vector<pair<T, int>>> RangCal(const vector<T>& nums, _Pr pr) {vector<vector<pair<int, int>>> vNumIndex(nums.size());for (int i = 0; i < nums.size(); i++) {if (i) {for (const auto& [preNum, preIndex] : vNumIndex[i - 1]) {auto iNew = pr(preNum, nums[i]);if (vNumIndex[i].empty() || (vNumIndex[i].back().first != iNew)) {vNumIndex[i].emplace_back(make_pair(iNew, preIndex));}else {vNumIndex[i].back().second = preIndex;}}}if (vNumIndex[i].empty() || (vNumIndex[i].back().first != nums[i])) {vNumIndex[i].emplace_back(make_pair(nums[i], i));}else {vNumIndex[i].back().second = i;}}return vNumIndex;}
};class Solution {public:long long countSubarrays(vector<int>& nums, int k) {auto res =	CRangCal::RangCal(nums, [&](int n1, int n2) {return n1 & n2; });long long ans = 0;int i = -1;for (const auto& v : res) {i++;for (int j = 0; j < v.size(); j++) {if (v[j].first == k) {		const int begin = (0 == j) ? -1 : v[j - 1].second;ans += (v[j].second-begin);}}}return ans;}};

单元测试

vector<int> nums;int k;TEST_METHOD(TestMethod11){nums = { 1, 1, 1 }, k = 1;auto res = Solution().countSubarrays(nums, k);AssertEx(6LL, res);}TEST_METHOD(TestMethod12){nums = { 1, 1, 2 }, k = 1;auto res = Solution().countSubarrays(nums, k);AssertEx(3LL, res);}TEST_METHOD(TestMethod13){nums = { 1, 2, 3 }, k = 2;auto res = Solution().countSubarrays(nums, k);AssertEx(2LL, 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++ 区间位运算】3209. 子数组按位与值为 K 的数目|2050

本文涉及知识点 位运算、状态压缩、枚举子集汇总 LeetCode3209. 子数组按位与值为 K 的数目 给你一个整数数组 nums 和一个整数 k &#xff0c;请你返回 nums 中有多少个子数组 满足&#xff1a;子数组中所有元素按位 AND 的结果为 k 。 示例 1&#xff1a; 输入&#xff1a…...

8 比例缩放(scale.rs)

scale.rs代码是几何变换库euclid中典型的数据结构和方法的例子&#xff0c;用于处理二维和三维空间中的缩放变换。 一、scale.rs文件源码 //! A type-checked scaling factor between units.use crate::num::One;use crate::approxord::{max, min}; use crate::{Box2D, Box3D…...

二分 机器人的跳跃问题

二段性:找到一个值&#xff0c;大于此值的时候都成立&#xff0c;小于的时候都不成立 更新的方式只有两种&#xff0c;左边的mid更新不需要1&#xff1b;右边的mid更新需要1 //对能量进行二分&#xff0c;确定能量的范围 //特判防止溢出int #include<bits/stdc.h> using…...

Hive:复杂数据类型之Map函数

Map函数 是Hive里面的一种复杂数据类型, 用于存储键值对集合。Map中的键和值可以是基础类型或复合类型&#xff0c;这使得Map在处理需要关联存储信息的数据时非常有用。 定义map时,需声明2个属性: key 和 value , map中是 key value 组成一个元素 key-value, key必须为原始类…...

R 字符串:深入理解与高效应用

R 字符串:深入理解与高效应用 引言 在R语言中,字符串是数据处理和编程中不可或缺的一部分。无论是数据清洗、数据转换还是数据分析,字符串的处理都是基础技能。本文将深入探讨R语言中的字符串概念,包括其基本操作、常见函数以及高效应用方法。 字符串基本概念 字符串定…...

设计模式Python版 桥接模式

文章目录 前言一、桥接模式二、桥接模式示例三、桥接模式与适配器模式的联用 前言 GOF设计模式分三大类&#xff1a; 创建型模式&#xff1a;关注对象的创建过程&#xff0c;包括单例模式、简单工厂模式、工厂方法模式、抽象工厂模式、原型模式和建造者模式。结构型模式&…...

记5(一元逻辑回归+线性分类器+多元逻辑回归

目录 1、一元逻辑回归2、线性可分&线性不可分3、Iris数据集实现多元逻辑回归4、绘制分类图5、鸢尾花分类图6、多分类问题&#xff1a;&#xff08;softmax回归&#xff09;6.1、编码&#xff1a;自然顺序码、独热编码、独冷编码6.2、二/多分类问题&#xff1a;6.3、softmax…...

【Python】第七弹---Python基础进阶:深入字典操作与文件处理技巧

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】【C详解】【Linux系统编程】【MySQL】【Python】 目录 1、字典 1.1、字典是什么 1.2、创建字典 1.3、查找 key 1.4、新增/修改元素 1.5、删除元素 1.6、遍历…...

Nginx 运维开发高频面试题详解

一、基础核心问题 原文链接&#xff1a;https://blog.csdn.net/weixin_51146329/article/details/142963853 1、什么是Nginx&#xff1f; Nginx 是一个高性能的 HTTP 和反向代理服务器&#xff0c;它以轻量级和高并发处理能力而闻名。Nginx 的反向代理功能允许它作为前端服务…...

下载OpenJDK

由于Oracle需要付费&#xff0c;并且之前我在寻找openJDK的时候&#xff0c;我不知道网址&#xff0c;并且也不知道在这个openjdk这个网址里点击哪个模块进行下载。最近我在看虚拟机相关的书籍的时候&#xff0c;找到了相关的网址。 注意&#xff1a;下面的下载都是基于可以科…...

Web3.js详解

Web1&Web2&Web3 以下是Web1、Web2和Web3的详细介绍&#xff0c;以及一个对比表格&#xff1a; Web1 定义&#xff1a;Web1指的是有着固定内容的非许可的开源网络。特点&#xff1a;在Web1时代&#xff0c;网站内容主要由网站管理员或创建者提供&#xff0c;用户只能…...

学习串行通信

本文来源&#xff1a; [8-1] 串口通信_哔哩哔哩_bilibili 智谱清言 ------------ 串口&#xff08;Serial Port&#xff09;&#xff1a; 串口是一种应用非常广泛的通讯接口&#xff0c;串口成本低&#xff0c;容易使用&#xff0c;通信线路简单&#xff0c;可实现两个设…...

【leetcode强化练习·二叉树】同时运用两种思维解题

本文参考labuladong算法笔记[【强化练习】同时运用两种思维解题 | labuladong 的算法笔记] 有的题目可以同时用「遍历」和「分解问题」两种思路来解&#xff0c;你可以利用这些题目训练自己的思维。 559. N 叉树的最大深度 | 力扣 | LeetCode | 给定一个 N 叉树&#xff0c;…...

Rank-analysis-1.2——一款基于LCU API的排位分析工具,大四学生独立开发

LOL Rank Record Analysis&#xff1a;一款基于LCU API的排位分析工具&#xff0c;大四学生独立开发&#xff01; 大家好&#xff01;我是河南科技学院的大四学生&#xff0c;今天给大家分享一个我自己开发的软件——LOL Rank Record Analysis。这是一个基于 Riot 提供的 LCU …...

什么是门控循环单元?

一、概念 门控循环单元&#xff08;Gated Recurrent Unit&#xff0c;GRU&#xff09;是一种改进的循环神经网络&#xff08;RNN&#xff09;&#xff0c;由Cho等人在2014年提出。GRU是LSTM的简化版本&#xff0c;通过减少门的数量和简化结构&#xff0c;保留了LSTM的长时间依赖…...

Google Chrome-便携增强版[解压即用]

Google Chrome-便携增强版 链接&#xff1a;https://pan.xunlei.com/s/VOI0OyrhUx3biEbFgJyLl-Z8A1?pwdf5qa# a 特点描述 √ 无升级、便携式、绿色免安装&#xff0c;即可以覆盖更新又能解压使用&#xff01; √ 此增强版&#xff0c;支持右键解压使用 √ 加入Chrome增强…...

智慧园区综合管理系统如何实现多个维度的高效管理与安全风险控制

内容概要 在当前快速发展的城市环境中&#xff0c;智慧园区综合管理系统正在成为各类园区管理的重要工具&#xff0c;无论是工业园、产业园、物流园&#xff0c;还是写字楼与公寓&#xff0c;都在积极寻求如何提升管理效率和保障安全。通过快鲸智慧园区管理系统&#xff0c;用…...

【PyTorch】7.自动微分模块:开启神经网络 “进化之门” 的魔法钥匙

目录 1. 梯度基本计算 2. 控制梯度计算 3. 梯度计算注意 4. 小节 个人主页&#xff1a;Icomi 专栏地址&#xff1a;PyTorch入门 在深度学习蓬勃发展的当下&#xff0c;PyTorch 是不可或缺的工具。它作为强大的深度学习框架&#xff0c;为构建和训练神经网络提供了高效且灵活…...

从0开始使用面对对象C语言搭建一个基于OLED的图形显示框架(协议层封装)

目录 协议层设计&#xff0c;以IIC为例子 关于软硬件IIC 设计的一些原则 完成协议层的抽象 刨析我们的原理 如何完成我们的抽象 插入几个C语言小技巧 完成软件IIC通信 开始我们的IIC通信 结束我们的IIC通信 发送一个字节 &#xff08;重要&#xff09;完成命令传递和…...

Mac M1 源码安装FFmpeg,开启enable-gpl 和 lib x264

1、第一步&#xff1a;下载并安装minicoda curl -O https://repo.anaconda.com/miniconda/Miniconda3-latest-MacOSX-arm64.shsh Miniconda3-latest-MacOSX-arm64.sh2、第二步&#xff1a;安装必要的依赖 conda install -c conda-forge gcc make nasm yasm3、第三步&#xff…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

Chrome 浏览器前端与客户端双向通信实战

Chrome 前端&#xff08;即页面 JS / Web UI&#xff09;与客户端&#xff08;C 后端&#xff09;的交互机制&#xff0c;是 Chromium 架构中非常核心的一环。下面我将按常见场景&#xff0c;从通道、流程、技术栈几个角度做一套完整的分析&#xff0c;特别适合你这种在分析和改…...

AI语音助手的Python实现

引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...