LeetCode 1542.找出最长的超赞子字符串:前缀异或和(位运算)
【LetMeFly】1542.找出最长的超赞子字符串:前缀异或和(位运算)
力扣题目链接:https://leetcode.cn/problems/find-longest-awesome-substring/
给你一个字符串 s 。请返回 s 中最长的 超赞子字符串 的长度。
「超赞子字符串」需满足满足下述两个条件:
- 该字符串是
s的一个非空子字符串 - 进行任意次数的字符交换后,该字符串可以变成一个回文字符串
示例 1:
输入:s = "3242415" 输出:5 解释:"24241" 是最长的超赞子字符串,交换其中的字符后,可以得到回文 "24142"
示例 2:
输入:s = "12345678" 输出:1
示例 3:
输入:s = "213123" 输出:6 解释:"213123" 是最长的超赞子字符串,交换其中的字符后,可以得到回文 "231132"
示例 4:
输入:s = "00" 输出:2
提示:
1 <= s.length <= 10^5s仅由数字组成
解题方法:前缀和+哈希表+位运算
回文串有两种情况:
- 所有字符都出现了偶数次、
- 有且仅有一个字符出现了奇数次。
也就是说我们只用关心每个字符出现次数是奇数还是偶数即可。因此我们可以使用一个数 m a s k mask mask, m a s k mask mask的第 i i i位表示数字 i i i出现次数是否为奇数次。
加入在 m a s k mask mask的基础上又出现了 i i i,则新的 m a s k mask mask的计算公式为:
mask ^= 1 << i。
我们只需要遍历一遍字符串,并且使用哈希表,哈希表 m a [ m a s k ] ma[mask] ma[mask]为前面所有数字结果为 m a s k mask mask的第一次出现位置。则遍历过程中有“
- 若当前 m a s k mask mask出现过,则这两次出现位置之间所有字符都出现了偶数次,满足回文串要求;
- 若当前 m a s k mask mask变化一位后在哈希表中存在,则这两次出现位置之间的字符串只有一个出现了奇数次,满足回文串要求。
遍历结束,算法结束。
- 时间复杂度 O ( l e n ( s ) × C ) O(len(s)\times C) O(len(s)×C),其中 C C C是字符个数,这里 C = 10 C=10 C=10
- 空间复杂度 O ( min { l e n ( s ) , 2 C } ) O(\min\{len(s), 2^C\}) O(min{len(s),2C})
AC代码
C++
class Solution {
public:int longestAwesome(string s) {int mask = 0, ans = 1;unordered_map<int, int> ma;ma[0] = -1;for (int i = 0; i < s.size(); i++) {mask ^= (1 << (s[i] - '0'));if (ma.count(mask)) {ans = max(ans, i - ma[mask]);}else {ma[mask] = i;}// 一个奇数次字符for (int j = 0; j < 10; j++) {int mask2 = mask ^ (1 << j);if (ma.count(mask2)) {ans = max(ans, i - ma[mask2]);}}}return ans;}
};
Python
class Solution:def longestAwesome(self, s: str) -> int:mask, ans = 0, 1ma = {0: -1}for i in range(len(s)):mask ^= 1 << (ord(s[i]) - ord('0'))if mask in ma:ans = max(ans, i - ma[mask])else:ma[mask] = ifor j in range(10):mask2 = mask ^ (1 << j)if mask2 in ma:ans = max(ans, i - ma[mask2])return ans
同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/139077950
相关文章:
LeetCode 1542.找出最长的超赞子字符串:前缀异或和(位运算)
【LetMeFly】1542.找出最长的超赞子字符串:前缀异或和(位运算) 力扣题目链接:https://leetcode.cn/problems/find-longest-awesome-substring/ 给你一个字符串 s 。请返回 s 中最长的 超赞子字符串 的长度。 「超赞子字符串」需…...
LLM企业应用落地场景中的问题概览
三个问题 AI思维快速工具:需要对接LLM的API、控制幻觉、管理知识库。POC验证四个难点 私有化部署的环境:包括网络和服务器环境。交互友好意想不到的情况方向选择:让客户做目标和方向的选择问题 一、RAG 多跳问题 通常发生在报告编写的数据整理环节,比如要从一堆报表中找…...
基于灰狼优化算法优化支持向量机(GWO-SVM)时序预测
代码原理及流程 基于灰狼优化算法优化支持向量机(GWO-SVM)的时序预测代码的原理和流程如下: 1. **数据准备**:准备时序预测的数据集,将数据集按照时间顺序划分为训练集和测试集。 2. **初始化灰狼群体和SVM模型参数…...
C++中获取int最大与最小值
不知道大家有没有遇到过这种要求:“返回值必须是int,如果整数数超过 32 位有符号整数范围 [−2^31, 2^31 − 1] ,需要截断这个整数,使其保持在这个范围内。例如,小于 −2^31 的整数应该被固定为 −2^31 ,大…...
学习通高分免费刷课实操教程
文章目录 概要整体架构流程详细步骤云上全平台登录步骤小结 概要 我之前提到过一个通过浏览器的三个脚本就可以免费高分刷课的文章,由于不方便拍视频进行实操演示,然后写下了这个实操教程,之前的三个脚本划到文章末尾 整体架构流程 整体大…...
缓存降级
当Redis缓存出现问题或者无法正常工作时,需要有一种应对措施,避免直接访问数据库而导致整个系统瘫痪。缓存降级就是这样一种机制。 主要的缓存降级策略包括: 本地缓存降级 当Redis缓存不可用时,可以先尝试使用本地进程内缓存,如Guava Cache或Caffeine等。这样可以减少对Redis…...
PyQt6--Python桌面开发(32.QMenuBar菜单栏控件)
QMenuBar菜单栏控件 选择Main Window...
golang创建式设计模式---工厂模式
创建式设计模式—工厂模式 目录导航 创建式设计模式---工厂模式1)什么是工厂模式2)使用场景3)实现方式4)实践案例5)优缺点分析 1)什么是工厂模式 工厂模式(Factory Method Pattern)是一种设计模式,旨在创建对象时,将对象的创建与使用进行分离。通过定义…...
高精度定位平板主要应用在哪些领域
高精度定位平板是一种集成了高精度定位技术和强大计算能力的设备,能够提供亚米级甚至厘米级的定位精度。其应用领域广泛,涵盖测绘、精准农业、工程建设、地理信息系统(GIS)、公共安全等多个方面。这种设备凭借其高精度和耐用性&am…...
conda使用常用命令
Conda是一个非常常用的Python包管理器,也是Anaconda Python发行版的一部分。它可以帮助用户安装、更新、卸载Python包,以及管理Python虚拟环境。在这篇博客中,我们将总结一些常用的Conda命令及其用法。 安装和更新Conda 在使用Conda之前&…...
22-LINUX--多线程and多进程TCP连接
一.TCP连接基础知识 1.套接字 所谓套接字(Socket),就是对网络中不同主机上的应用进程之间进行双向通信的端点的抽象。一个套接字就是网络上进程通信的一端,提供了应用层进程利用网络协议交换数据的机制。从所处的地位来讲,套接字上联应用进程…...
像素级创意:深入浅出PixelCNN图像合成技术
参考 https://arxiv.org/pdf/1601.06759 https://blog.csdn.net/zcyzcyjava/article/details/126559327 需要熟悉熵的一些理论、和极大释然估计等价于最小化交叉熵等知识 1. pixelcnn建模方法 pixelcnn做生成模型的想必都有耳闻。它是一种自回归模型,什么是自回归…...
MyBatisPlus使用流程
引入依赖 <dependency><groupId>com.baomidou</groupId><artifactId>mybatis-plus-boot-starter</artifactId><version>3.5.4</version> </dependency> 版本号根据需要选取 在实体类上加注解声明,表信息 根据数…...
爬虫技术升级:如何结合DrissionPage和Auth代理插件实现数据采集
背景/引言 在大数据时代,网络爬虫技术已经成为数据收集的重要手段之一。爬虫技术可以自动化地从互联网上收集数据,节省大量人力和时间成本。然而,当使用需要身份验证的代理服务器时,许多现有的爬虫框架并不直接支持代理认证。这就…...
go 微服务框架kratos错误处理的使用方法及原理探究
通过go语言原生http中响应错误的实现方法,逐步了解和使用微服务框架 kratos 的错误处理方式,以及探究其实现原理。 一、go原生http响应错误信息的处理方法 处理方法: ①定义返回错误信息的结构体 ErrorResponse // 定义http返回错误信息的…...
AI播客下载:Dwarkesh Podcast(关于AI的深度访谈)
Dwarkesh Podcast 是由 Dwarkesh Patel 主持的播客,专注于深度访谈和探讨各种复杂且有趣的话题。该播客在业界获得了极高的评价,被认为是对话和思想交流的平台。 Dwarkesh Podcast 的内容涵盖了多个领域,包括经济学、哲学以及科技等。例如&am…...
C++11function包装器的使用
类模板std::function是一种通用、多态的函数包装。std::function的实例可以对任何可以调用的目标实体进行存储、 复制和调用操作。这些目标实体包括普通函数、Lambda表达式、函数指针、以及其他函数对象等。std::function对象是对 C中现有的可调用实体的一种类型安全的包裹&…...
Vue3判断变量和对象不为null和undefined
Vue3判断变量和对象不为null和undefined 一、判断变量二、判断对象 一、判断变量 在 Vue 3 中,你可以使用 JavaScript 提供的常规方式来检查变量是否不为 null 和不为 undefined。你可以分别使用严格不等运算符 ! 来比较变量是否不为 null 和不为 undefined。以下是…...
C++进阶:C++11(列表初始化、右值引用与移动构造移动赋值、可变参数模版...Args、lambda表达式、function包装器)
C进阶:C11(列表初始化、右值引用与移动构造移动赋值、可变参数模版…Args、lambda表达式、function包装器) 今天接着进行语法方面知识点的讲解 文章目录 1.统一的列表初始化1.1{}初始化1.2 initializer_listpair的补充 2.声明相关关键字2.1a…...
Vue.js Promise 与 async/await 的比较
在现代 Web 开发中,异步操作是不可避免的。在处理异步数据获取时,开发人员通常会使用 Promise 或 async/await。虽然两者都可以实现相同的功能,但它们在代码风格、可读性和错误处理等方面有所不同。本文将对这两种方法进行比较,并…...
stm32G473的flash模式是单bank还是双bank?
今天突然有人stm32G473的flash模式是单bank还是双bank?由于时间太久,我真忘记了。搜搜发现,还真有人和我一样。见下面的链接:https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...
基于Java+MySQL实现(GUI)客户管理系统
客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息,对客户进行统一管理,可以把所有客户信息录入系统,进行维护和统计功能。可通过文件的方式保存相关录入数据,对…...
Razor编程中@Html的方法使用大全
文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...
