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

前缀异或优化

前言:这个题目其实就是考察前缀和,正常情况下开二维数组来记录,但是也可以优化成一位的位运算
我们顺便可以学习一下如何进行查询二进制串中1的个数


在这里插入图片描述

class Solution {
public:vector<bool> canMakePaliQueries(string s, vector<vector<int>> &queries) {int n = s.length(), q = queries.size();vector<array<int, 26>> sum(n + 1);for (int i = 0; i < n; i++) {sum[i + 1] = sum[i];sum[i + 1][s[i] - 'a']++;}vector<bool> ans(q);for (int i = 0; i < q; i++) {auto &query = queries[i];int left = query[0], right = query[1], k = query[2], m = 0;for (int j = 0; j < 26; j++)m += (sum[right + 1][j] - sum[left][j]) % 2; // 奇数+1,偶数+0if((right-left+1)&1) m--;ans[i] = m  <= k*2;}return ans;}
};

优化后的代码

class Solution {
public:vector<bool> canMakePaliQueries(string s, vector<vector<int>>& queries) {int n = s.size();vector<int> count(n + 1);for (int i = 0; i < n; i++) {count[i + 1] = count[i] ^ (1 << (s[i] - 'a'));}vector<bool> res;for (auto& query : queries) {int l = query[0], r = query[1], k = query[2];int bits = 0, x = count[r + 1] ^ count[l];while (x > 0) {x &= x - 1;bits++;}res.push_back(bits <= k * 2 + 1);}return res;}
};

在这里插入图片描述

相关文章:

前缀异或优化

前言&#xff1a;这个题目其实就是考察前缀和&#xff0c;正常情况下开二维数组来记录&#xff0c;但是也可以优化成一位的位运算 我们顺便可以学习一下如何进行查询二进制串中1的个数 class Solution { public:vector<bool> canMakePaliQueries(string s, vector<vec…...

AI学习指南深度学习篇-卷积神经网络中的正则化和优化

AI学习指南深度学习篇-卷积神经网络中的正则化和优化 在深度学习领域&#xff0c;卷积神经网络&#xff08;Convolutional Neural Networks&#xff0c;CNN&#xff09;是一类非常重要的模型&#xff0c;被广泛应用于图像识别、目标检测等任务中。然而&#xff0c;在训练CNN时…...

AutoGen Studio 本地源码构建

目录 一、环境配置 1.1 创建本地环境 1.2 下载 autogen 源码 1.3 安装依赖 2. 构建 3. 运行 本文主要介绍 AutoGen Studio 本地源码构建过程。 一、环境配置 1.1 创建本地环境 通过 conda 创建一个环境,Python 3.10+,Node.js 14.15.0+。 conda create -n autogen p…...

医疗陪诊系统源码详解:在线问诊APP开发的技术要点

如今&#xff0c;开发一款高效、可靠的在线问诊APP则成为了许多企业的目标。本篇文章&#xff0c;小编将详细解析医疗陪诊系统的源码&#xff0c;并探讨在线问诊APP开发的关键技术要点。 一、医疗陪诊系统的基本功能 在开始开发之前&#xff0c;首先需要明确医疗陪诊系统的基本…...

VSCode编译多个不同文件夹下的C++文件

实际上VSCode编译C文件就是通过向g传递参数实现的&#xff0c;因此即使是不同包下面的cpp文件或者.h文件都是可以通过修改g的编译参数实现&#xff0c;而在VSCode中&#xff0c;task.json文件其实就是在配置g的编译参数&#xff0c;因此我们可以通过修改task.json里面的参数&am…...

【安卓】连接真机和使用通知

文章目录 连接到真机使用通知通知的简单使用通知的详细信息 连接到真机 先用USB线将手机与电脑连接。 打开手机的设置&#xff0c;找到关于手机&#xff0c;点开之后&#xff0c;找到开发者选项界面。或者找到软件版本号&#xff0c;连续点击&#xff0c;系统会提示你点击几次能…...

CSS3下拉菜单实现

导航菜单&#xff1a; <nav class"multi_drop_menu"><!-- 一级开始 --><ul><li><a href"#">Power</a></li><li><a href"#">Money</a></li><li><a href"#"…...

Mysql8.3.0排序导致分页数据错乱

#业务场景 生产环境 仓库管理&#xff0c;能看到各个仓库的C库位 物料管理&#xff0c;编辑物料&#xff0c;弹框时选择库位时&#xff0c;7页数据&#xff0c;没有C库位&#xff0c;查询条件指定C&#xff0c;能查到数据 本地环境 数据还原到本地 弹框数据在2页与第3页看…...

漏洞复现-Cacti命令执行漏洞 (CVE-2022-46169)

1.漏洞描述 Cacti是一套基于PHP&#xff0c;MySQL&#xff0c;SNMP及RRDTool开发的网络流量监测图形分析工具&#xff0c;可为用户提供强大且可扩展的操作监控和故障管理框架。 该漏洞存在于remote_agent.php文件中&#xff0c;未经身份验证的恶意攻击者可以通过设置HTTP_变量…...

【Ajax使用说明】Ajax、Axios以及跨域

目录 一、原生Ajax 1.1 Ajax简介 1.2 XML简介 1.3 AJAX 的特点 1.3.1 AJAX的优点 1.3.2 AJAX 的缺点 1.4 AJAX 的使用 1.4.1AJAX的基本操作 1.4.2AJAX的传参 1.4.3 AJAX的post请求及设置请求体 1.4.4 AJAX响应json数据 1.4.5 AJAX请求超时与网络异常处理 1.4.5 AJ…...

IIS网站搬家工具WebDeploy(把网站迁移去另一台服务器)

如果不能克隆镜像&#xff0c;又想快速迁移&#xff0c;请保证新服务器和原服务器的文件目录结构一致&#xff0c;各种程序的安装路径一致&#xff0c;包括python的安装路径、mysql的秘密 防火墙设置等 网站迁移去另一台服务器&#xff0c;如果重新设置IIS&#xff0c;还是有…...

SQL Server 2022的游标

《SQL Server 2022从入门到精通&#xff08;视频教学超值版&#xff09;》图书介绍-CSDN博客 《SQL Server 2022从入门到精通&#xff08;视频教学超值版&#xff09;&#xff08;数据库技术丛书&#xff09;》(王英英)【摘要 书评 试读】- 京东图书 (jd.com) 游标是SQL Serv…...

「11月·香港」第三届人工智能、人机交互和机器人国际学术会议(AIHCIR 2024)

第三届人工智能、人机交互和机器人国际学术会议&#xff08;AIHCIR 2024&#xff09;组委会热忱地邀请您参与本届大会。本届大会旨在聚集领先的科学家、研究人员和学者&#xff0c;共同交流和分享在人工智能、人机交互和机器人各个方面的经验和研究成果&#xff0c;为研究人员、…...

【redis】springboot 用redis stream实现MQ消息队列 考虑异常ack重试场景

redis stream是redis5引入的特性&#xff0c;一定程度上借鉴了kafka等MQ的设计&#xff0c;部署的redis版本必须 > 5 本文主要讲的是思路&#xff0c;结合简单的源码分析&#xff08;放心&#xff0c;无需深入大量源码&#xff09;&#xff1b;讲述在redis stream文档缺乏&a…...

初识IDEA

一、IDEA简介 IDEA 全称 IntelliJ IDEA&#xff0c;是 JAVA编程语言开发的集成环境。IntelliJ 在业界被公认为最好的 java开发⼯具 之⼀&#xff0c;尤其在智能代码助⼿、代码⾃动提示、重构、J2EE⽀持、Ant、JUnit、CVS整合、代码审 查⽅⾯。 JetBrains官⽹ : JetBrains: Esse…...

zigbee笔记:十、ZStack(2.3.0-1.4.0)的OSAL使用分析

zigbee笔记&#xff1a;九中&#xff0c;我们已经学会了利用模板&#xff0c;定制自己的个性开发工程&#xff0c;本文为协议栈&#xff08;ZStack-CC2530-2.3.0-1.4.0&#xff09;代码使用分析笔记&#xff0c;来进一步掌握协议栈的使用。 一、协议栈使用知识点 1、协调器、路…...

SpringBoot响应式编程(1)Reactor核心

一、概述 1.1介绍 Reactor 是一个用于JVM的完全非阻塞的响应式编程框架&#xff0c;Webflux 底层使用的也是该框架&#xff0c;其通过流的方式实现了异步相应&#xff0c;具备高效的需求管理&#xff08;即对 “背压&#xff08;backpressure&#xff09;”的控制&#xff09…...

Java后端处理前端字符串与 JSON 数据:安全拼接与转义技巧

在现代 Web 开发中&#xff0c;前后端数据交互是家常便饭。我们经常需要处理前端传递的字符串和 JSON 数据&#xff0c;并在后端进行加工处理后发送到其他服务。本文将以 Spring Boot 为例&#xff0c;探讨如何安全地拼接字符串和 JSON 数据&#xff0c;并介绍如何避免 JSON 特…...

一文搞懂bfs,dfs和高级图算法

你以为BFS&#xff08;广度优先搜索&#xff09;和DFS&#xff08;深度优先搜索&#xff09;这两种基础算法&#xff0c;简单到小学数学就能搞定&#xff1f;但真的是这样吗&#xff1f;很多人都这么认为&#xff0c;但真的对吗&#xff1f;今天&#xff0c;我们不只是走马观花…...

【Rust光年纪】Rust异步编程利器:异步DNS、高性能Web服务器一网打尽

构建高效网络应用必备&#xff1a;解读Rust异步编程神器 前言 Rust 是一种快速流行的系统编程语言&#xff0c;它以其内存安全和并发性能而闻名。在 Rust 生态系统中&#xff0c;有许多优秀的库和框架可以帮助开发者构建高性能、可靠的应用程序。本文将介绍几个在 Rust 中备受…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...