【数据结构-前缀异或和】力扣1371. 每个元音包含偶数次的最长子字符串

devtools/2024/10/22 9:58:51/

给你一个字符串 s ,请你返回满足以下条件的最长子字符串的长度:每个元音字母,即 ‘a’,‘e’,‘i’,‘o’,‘u’ ,在子字符串中都恰好出现了偶数次。

示例 1:
输入:s = “eleetminicoworoep”
输出:13
解释:最长子字符串是 “leetminicowor” ,它包含 e,i,o 各 2 个,以及 0 个 a,u 。

示例 2:
输入:s = “leetcodeisgreat”
输出:5
解释:最长子字符串是 “leetc” ,其中包含 2 个 e 。

示例 3:
输入:s = “bcbcbc”
输出:6
解释:这个示例中,字符串 “bcbcbc” 本身就是最长的,因为所有的元音 a,e,i,o,u 都出现了 0 次。
在这里插入图片描述

class Solution {
public:int findTheLongestSubstring(string s) {int ans = 0, status = 0, n = s.length();//1<<5即32vector<int> pos(1 << 5, -1);for (int i = 0; i < n; ++i) {if (s[i] == 'a') {status ^= 1<<0;} else if (s[i] == 'e') {status ^= 1<<1;} else if (s[i] == 'i') {status ^= 1<<2;} else if (s[i] == 'o') {status ^= 1<<3;} else if (s[i] == 'u') {status ^= 1<<4;}if (pos[status] == -1 && status) {pos[status] = i ;} else {        ans = max(ans, i - pos[status]);}}return ans;}
};

首先

vector<int> pos(1 << 5, -1);

等价于vector<int> pos(32, -1);

接着遍历字符串s,status用一个二进制数并使用异或来记录元音字符出现次数,为0说明出现次数为偶数,为1说明出现次数为奇数。

更新完status的时候,进行逻辑判断,由于status被初始化为0,需要&& status,让当到i位置时候的字符串的元音字符都是偶数的时候,直接计算开始到i位置的字符串的长度,而不是更新pos[status] = i 的位置。

当pos[status] = -1的时候,说明之前没有出现过这个status,那么这时候pos[status]则是第一次出现status时候的位置,那么后面遇到相同status的时候,会计算子串的位置,而不会更新pos[status] = -1的位置,然后返回最长的ans即可。


http://www.ppmy.cn/devtools/104643.html

相关文章

机器视觉-3 光学成像之明场与暗场

一. 原理介绍 在机器视觉中&#xff0c;光学成像的明场&#xff08;Bright Field&#xff09;和暗场&#xff08;Dark Field&#xff09;是两种常见的成像技术&#xff0c;分别用于不同的检测和分析场景。它们通过不同的光照方式来突出对象的特征&#xff0c;从而帮助识…

RK3568平台(UART篇)uart_driver 注册流程

一.串口子系统框架 串口子系统框架是 Linux 内核中专门用于处理串口设备的模块化框架: 在上图中,包含了多个层级,每个层级负责处理不同的功能和任务,从而实现串口设备的 完整驱动和管理。接下来依次介绍每个层级的作用。 应用层:位于最顶层,是串口子系统中用户空间应用程…

SQL 注入之 Oracle 注入

在 SQL 注入攻击的领域中&#xff0c;Oracle 数据库的注入攻击具有一定的特殊性和复杂性。Oracle 作为一种广泛使用的关系型数据库管理系统&#xff0c;其安全性一直备受关注。然而&#xff0c;由于应用程序开发中的漏洞或者不当配置&#xff0c;Oracle 数据库仍然可能成为 SQL…

Leetcode3244. 新增道路查询后的最短距离 II

Every day a Leetcode 题目来源&#xff1a;3244. 新增道路查询后的最短距离 II 解法1&#xff1a;贪心 由于题目保证添加的边&#xff08;捷径&#xff09;不会交叉&#xff0c;从贪心的角度看&#xff0c;遇到捷径就走捷径是最优的。所有被跳过的城市都不可能再出现在最短…

css中的伪类

什么是伪类 伪类&#xff08;Pseudo-classes&#xff09;是 CSS 中的一个重要概念&#xff0c;它们用于定义元素的特定状态。伪类可以基于元素的特定属性或状态来选择和样式化文档树中的元素&#xff0c;而不需要使用类或 ID。伪类通常以冒号 : 开头。 用法 :link - 选择未被…

【大模型LLM第十一篇】微调自动化数据选择方式之MoDS

前言 来自中科院自动化所的paper MoDS: Model-oriented Data Selection for Instruction Tuning link&#xff1a;https://arxiv.org/pdf/2311.15653 github&#xff1a;https://github.com/CASIA-LM/MoDS 一、摘要 sft已经成为让LLM遵循用户指令的一种方式。通常&#xf…

前端缓存机制及其特点

1、localStorage localStorage 是一种 Web 存储&#xff08;Web Storage&#xff09;技术&#xff0c;它属于浏览器提供的客户端存储机制。localStorage 的特点使它被广泛用于持久性的数据存储&#xff0c;即使在浏览器关闭并重新打开之后&#xff0c;数据仍然保留。 localSt…

白盒测试及其测试方法

什么是白盒测试 是针对程序的逻辑结构进行测试&#xff0c;主要适用于单元测试阶段 与黑盒测试不同的是&#xff0c;黑盒测试是根据业务需求设计用例的输入输出&#xff0c;白盒测试是对程序系统的内部逻辑实现设计输入输出。 通常的流程是先静态测试&#xff0c;后动态测试…