当前位置: 首页 > 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 中备受…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...

Kafka主题运维全指南:从基础配置到故障处理

#作者&#xff1a;张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1&#xff1a;主题删除失败。常见错误2&#xff1a;__consumer_offsets占用太多的磁盘。 主题日常管理 …...

Pydantic + Function Calling的结合

1、Pydantic Pydantic 是一个 Python 库&#xff0c;用于数据验证和设置管理&#xff0c;通过 Python 类型注解强制执行数据类型。它广泛用于 API 开发&#xff08;如 FastAPI&#xff09;、配置管理和数据解析&#xff0c;核心功能包括&#xff1a; 数据验证&#xff1a;通过…...

yaml读取写入常见错误 (‘cannot represent an object‘, 117)

错误一&#xff1a;yaml.representer.RepresenterError: (‘cannot represent an object’, 117) 出现这个问题一直没找到原因&#xff0c;后面把yaml.safe_dump直接替换成yaml.dump&#xff0c;确实能保存&#xff0c;但出现乱码&#xff1a; 放弃yaml.dump&#xff0c;又切…...

flow_controllers

关键点&#xff1a; 流控制器类型&#xff1a; 同步&#xff08;Sync&#xff09;&#xff1a;发布操作会阻塞&#xff0c;直到数据被确认发送。异步&#xff08;Async&#xff09;&#xff1a;发布操作非阻塞&#xff0c;数据发送由后台线程处理。纯同步&#xff08;PureSync…...

聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇

根据 QYResearch 发布的市场报告显示&#xff0c;全球市场规模预计在 2031 年达到 9848 万美元&#xff0c;2025 - 2031 年期间年复合增长率&#xff08;CAGR&#xff09;为 3.7%。在竞争格局上&#xff0c;市场集中度较高&#xff0c;2024 年全球前十强厂商占据约 74.0% 的市场…...