【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 ,请你返回 nums 中有多少个子数组 满足:子数组中所有元素按位 AND 的结果为 k 。 示例 1: 输入:…...
8 比例缩放(scale.rs)
scale.rs代码是几何变换库euclid中典型的数据结构和方法的例子,用于处理二维和三维空间中的缩放变换。 一、scale.rs文件源码 //! A type-checked scaling factor between units.use crate::num::One;use crate::approxord::{max, min}; use crate::{Box2D, Box3D…...

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

Hive:复杂数据类型之Map函数
Map函数 是Hive里面的一种复杂数据类型, 用于存储键值对集合。Map中的键和值可以是基础类型或复合类型,这使得Map在处理需要关联存储信息的数据时非常有用。 定义map时,需声明2个属性: key 和 value , map中是 key value 组成一个元素 key-value, key必须为原始类…...
R 字符串:深入理解与高效应用
R 字符串:深入理解与高效应用 引言 在R语言中,字符串是数据处理和编程中不可或缺的一部分。无论是数据清洗、数据转换还是数据分析,字符串的处理都是基础技能。本文将深入探讨R语言中的字符串概念,包括其基本操作、常见函数以及高效应用方法。 字符串基本概念 字符串定…...

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

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

【Python】第七弹---Python基础进阶:深入字典操作与文件处理技巧
✨个人主页: 熬夜学编程的小林 💗系列专栏: 【C语言详解】 【数据结构详解】【C详解】【Linux系统编程】【MySQL】【Python】 目录 1、字典 1.1、字典是什么 1.2、创建字典 1.3、查找 key 1.4、新增/修改元素 1.5、删除元素 1.6、遍历…...
Nginx 运维开发高频面试题详解
一、基础核心问题 原文链接:https://blog.csdn.net/weixin_51146329/article/details/142963853 1、什么是Nginx? Nginx 是一个高性能的 HTTP 和反向代理服务器,它以轻量级和高并发处理能力而闻名。Nginx 的反向代理功能允许它作为前端服务…...

下载OpenJDK
由于Oracle需要付费,并且之前我在寻找openJDK的时候,我不知道网址,并且也不知道在这个openjdk这个网址里点击哪个模块进行下载。最近我在看虚拟机相关的书籍的时候,找到了相关的网址。 注意:下面的下载都是基于可以科…...
Web3.js详解
Web1&Web2&Web3 以下是Web1、Web2和Web3的详细介绍,以及一个对比表格: Web1 定义:Web1指的是有着固定内容的非许可的开源网络。特点:在Web1时代,网站内容主要由网站管理员或创建者提供,用户只能…...

学习串行通信
本文来源: [8-1] 串口通信_哔哩哔哩_bilibili 智谱清言 ------------ 串口(Serial Port): 串口是一种应用非常广泛的通讯接口,串口成本低,容易使用,通信线路简单,可实现两个设…...

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

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

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

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

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

【PyTorch】7.自动微分模块:开启神经网络 “进化之门” 的魔法钥匙
目录 1. 梯度基本计算 2. 控制梯度计算 3. 梯度计算注意 4. 小节 个人主页:Icomi 专栏地址:PyTorch入门 在深度学习蓬勃发展的当下,PyTorch 是不可或缺的工具。它作为强大的深度学习框架,为构建和训练神经网络提供了高效且灵活…...
从0开始使用面对对象C语言搭建一个基于OLED的图形显示框架(协议层封装)
目录 协议层设计,以IIC为例子 关于软硬件IIC 设计的一些原则 完成协议层的抽象 刨析我们的原理 如何完成我们的抽象 插入几个C语言小技巧 完成软件IIC通信 开始我们的IIC通信 结束我们的IIC通信 发送一个字节 (重要)完成命令传递和…...

Mac M1 源码安装FFmpeg,开启enable-gpl 和 lib x264
1、第一步:下载并安装minicoda curl -O https://repo.anaconda.com/miniconda/Miniconda3-latest-MacOSX-arm64.shsh Miniconda3-latest-MacOSX-arm64.sh2、第二步:安装必要的依赖 conda install -c conda-forge gcc make nasm yasm3、第三步ÿ…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...

2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...

图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

什么是Ansible Jinja2
理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具,可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板,允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板,并通…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

佰力博科技与您探讨热释电测量的几种方法
热释电的测量主要涉及热释电系数的测定,这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中,积分电荷法最为常用,其原理是通过测量在电容器上积累的热释电电荷,从而确定热释电系数…...

Sklearn 机器学习 缺失值处理 获取填充失值的统计值
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...