前缀和算法
算法总览
题目
1371.每个元音包含偶数次的最长子字符串
1371.每个元音包含偶数次的最长子字符串


参考博主的讲解
思路分析:就是得使用前缀和记录情况,dp[i][j]表示s[0] 到s[i] 中,j出现的次数
前缀和+剪枝

class Solution:def findTheLongestSubstring(self, s: str) -> int:# 使用字典将元音映射为数字,方便后续的记录i_mapper = {"a": 0,"e": 1,"i": 2,"o": 3,"u": 4}n = len(s)# pre[i][j]表示s[0] 到 s[i] 之间字符j所出现的次数pre = [[0] * 5 for _ in range(n)]# prefor i in range(n):for j in range(5):# 注意这里其实没有对i=0进行处理,因为-1在python中表示最后一个元素,所以不会越界报错if s[i] in i_mapper and i_mapper[s[i]] == j:pre[i][j] = pre[i - 1][j] + 1else:pre[i][j] = pre[i - 1][j]# check(l,r)表示查询s[l]到s[r]中的情况def check(l, r):for i in range(5):# 特别处理s[l]的情况,不然就是 pre[r][i] - pre[l-1][i],这个时候就得判断l==0的情况if s[l] in i_mapper and i == i_mapper[s[l]]: cnt = 1else: cnt = 0if (pre[r][i] - pre[l][i] + cnt) % 2 != 0: return Falsereturn True# 由于是剪枝,i从最长的子序列的长度对应的末尾的下标开始计算for i in range(n - 1, -1, -1):# j表示长度为i的子序列的开始的下标for j in range(n - i):if check(j, i + j):return i + 1return 0
前缀和+状态压缩
class Solution:def findTheLongestSubstring(self, s: str) -> int:mapper = {"a": 1,"e": 2,"i": 4,"o": 8,"u": 16}# seen使用哈希表存储每一个状态组合所第一次出现的下标,最多就是2^5就是32种情况seen = {0: -1}# res 用于记录更新答案,cur用于计算当前的奇偶组合的值res = cur = 0for i in range(len(s)):if s[i] in mapper:cur ^= mapper.get(s[i])# 全部奇偶性都相同,相减一定都是偶数if cur in seen:res = max(res, i - seen.get(cur))else:seen[cur] = ireturn res
class Solution:def maxDifference(self, s: str, k: int) -> int:s = list(map(int, s))ans = -inffor x in range(5):for y in range(5):if y == x:continue#cur_s 记录当前0,1,2,3,4出现的次数,pre_s则是先前的情况# cur_s是维护0-i的情况,pre_s是维护0-left的情况cur_s = [0] * 5pre_s = [0] * 5# min_s = [[inf, inf], [inf, inf]]left = 0for i, v in enumerate(s):cur_s[v] += 1r = i + 1# 一直在维护左边界的情况,r-left>=kwhile r - left >= k and cur_s[x] > pre_s[x] and cur_s[y] > pre_s[y]:# 检验是奇数还是偶数,奇数&1为1,偶数&1为0p, q = pre_s[x] & 1, pre_s[y] & 1min_s[p][q] = min(min_s[p][q], pre_s[x] - pre_s[y])pre_s[s[left]] += 1left += 1if r >= k:# cur_s[x] & 1 ^ 1 和 cur_s[y] & 1 奇偶不同ans = max(ans, cur_s[x] - cur_s[y] - min_s[cur_s[x] & 1 ^ 1][cur_s[y] & 1])return ans相关文章:
前缀和算法
文章目录 算法总览题目1371.每个元音包含偶数次的最长子字符串 算法总览 题目 1371.每个元音包含偶数次的最长子字符串 1371.每个元音包含偶数次的最长子字符串 参考博主的讲解 思路分析:就是得使用前缀和记录情况,dp[i][j]表示s[0] 到s[i] 中&…...
Qt常用控件 输入类控件
文章目录 1.QLineEdit1.1 常用属性1.2 常用信号1.3 例子1,录入用户信息1.4 例子2,正则验证手机号1.5 例子3,验证输入的密码1.6 例子4,显示密码 2. QTextEdit2.1 常用属性2.2 常用信号2.3 例子1,获取输入框的内容2.4 例…...
《最小阻力之路》关于愿景的理解和思考
一、愿景的形成机制 1. 愿景的三层来源 来源层级形成机制案例潜在偏差风险① 本能冲动层对快感/痛苦的即时反应"想暴富"源于缺钱焦虑易被短期情绪劫持② 社会镜像层内化外界标准(家庭/社会/文化)"必须考研"因家人期待混淆他人需求…...
Ubuntu 22.04系统安装部署Kubernetes v1.29.13集群
Ubuntu 22.04系统安装部署Kubernetes v1.29.13集群 简介Kubernetes 的工作流程概述Kubernetes v1.29.13 版本Ubuntu 22.04 系统安装部署 Kubernetes v1.29.13 集群 1 环境准备1.1 集群IP规划1.2 初始化步骤(各个节点都需执行)1.2.1 主机名与IP地址解析1.…...
虚幻基础17:动画层接口
能帮到你的话,就给个赞吧 😘 文章目录 animation layer interface animation layer interface 动画层接口:动画图表的集。仅有名字。 添加到动画蓝图中,由动画蓝图实现动画图表。...
无人机PX4飞控 | PX4源码添加自定义uORB消息并保存到日志
PX4源码添加自定义uORB消息并保存到日志 0 前言 PX4的内部通信机制主要依赖于uORB(Micro Object Request Broker),这是一种跨进程的通信机制,一种轻量级的中间件,用于在PX4飞控系统的各个模块之间进行高效的数据交换…...
HTMLCSS :下雪了
这段代码创建了一个动态的雪花飘落加载动画,通过 CSS 技术实现了雪花的下落和消失效果,为页面添加了视觉吸引力和动态感。 大家复制代码时,可能会因格式转换出现错乱,导致样式失效。建议先少量复制代码进行测试,若未能…...
如何处理 Typecho Joe 主题被抄袭或盗版的问题
在开源社区中,版权保护是一个非常重要的话题。如果你发现自己的主题(如 Joe 主题)被其他主题(如子比主题)抄袭或盗版,你可以采取以下措施来维护自己的权益。 一、确认侵权行为 在采取任何行动之前…...
利用Vue和javascript分别编写一个“Hello World”的定时更新
目录 一、利用Vue编写一个“Hello World”的定时更新(1)vue编码在Html文件中(2)vue编码在js文件中 二、利用javascript编写一个“Hello World”的定时更新 一、利用Vue编写一个“Hello World”的定时更新 (1ÿ…...
volatile变量需要减少读取次数吗
问题说明 本人在前期读Netty源码时看到这样一段源码和注释: private boolean invokeHandler() {// Store in local variable to reduce volatile reads.int handlerState this.handlerState;return handlerState ADD_COMPLETE || (!ordered && handlerS…...
bootstrap.yml文件未自动加载问题解决方案
在添加bootstrap.yml文件后,程序未自动扫描到,即图标是这样的: 查了一些资料,是缺少bootstrap相关依赖,虽然已经添加了spring-cloud-context依赖,但是这个依赖并未引入bootstrap依赖,可能是版本问题,需要手动引入 <dependency><groupId>org.springframework.cloud&…...
编程AI深度实战:AI编程工具哪个好? Copilot vs Cursor vs Cody vs Supermaven vs Aider
系列文章: 编程AI深度实战:私有模型deep seek r1,必会ollama-CSDN博客 编程AI深度实战:自己的AI,必会LangChain-CSDN博客 编程AI深度实战:给vim装上AI-CSDN博客 编程AI深度实战:火的编程AI,都在用语法树(AST)-CSDN博客 编程AI深度实战:让verilog不再是 AI …...
前端知识速记--CSS篇:display
前端知识速记–CSS篇:display 一、什么是 display 属性? display 属性用于指定一个元素如何被显示在网页上。它不仅影响元素的显示形式,还对元素的布局、结构以及与其他元素之间的关系产生重要影响。 二、常用 display 属性值 1. block …...
51单片机 01 LED
一、点亮一个LED 在STC-ISP中单片机型号选择 STC89C52RC/LE52RC;如果没有找到hex文件(在objects文件夹下),在keil中options for target-output- 勾选 create hex file。 如果要修改编程 :重新编译-下载/编程-单片机重…...
WPF进阶 | WPF 动画特效揭秘:实现炫酷的界面交互效果
WPF进阶 | WPF 动画特效揭秘:实现炫酷的界面交互效果 前言一、WPF 动画基础概念1.1 什么是 WPF 动画1.2 动画的基本类型1.3 动画的核心元素 二、线性动画详解2.1 DoubleAnimation 的使用2.2 ColorAnimation 实现颜色渐变 三、关键帧动画深入3.1 DoubleAnimationUsin…...
分页按钮功能
前言 在前端开发中,分页功能是一个常见的需求,特别是当需要展示大量数据时,它能有效提升用户体验。该文章结合运用了HTML,CSS,JS实现网页的分页按钮功能,并且可以选择每页显示的条数试试更新总页数及显示当…...
数据分析系列--⑦RapidMiner模型评价(基于泰坦尼克号案例含数据集)
一、前提 二、模型评估 1.改造⑥ 2.Cross Validation算子说明 2.1Cross Validation 的作用 2.1.1 模型评估 2.1.2 减少过拟合 2.1.3 数据利用 2.2 Cross Validation 的工作原理 2.2.1 数据分割 2.2.2 迭代训练与测试 2.2.3 结果汇总 …...
集合通讯概览
集合通信概览 (1)通信的算法 是根据通讯的链路组成的 (2)因为通信链路 跟硬件强相关,所以每个CCL的库都不一样 芯片与芯片、不同U之间是怎么通信的 多卡训练:多维并行(xxx并行在上一期已经讲述…...
【FreeRTOS 教程 八】直达任务通知
目录 一、FreeRTOS 直达任务通知: (1)直达任务通知基本介绍: (2)更新目标通知的值: (3)性能优势和使用限制: 二、直达任务通知 API: &#…...
Ubuntu 18.04安装Emacs 26.2问题解决
个人博客地址:Ubuntu 18.04安装Emacs 26.2问题解决 | 一张假钞的真实世界 no X development libraries were found checking for X... no checking for X... true configure: error: You seem to be running X, but no X development libraries were found. You …...
铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密
在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》
这段 Python 代码是一个完整的 知识库数据库操作模块,用于对本地知识库系统中的知识库进行增删改查(CRUD)操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 📘 一、整体功能概述 该模块…...
WebRTC从入门到实践 - 零基础教程
WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC? WebRTC(Web Real-Time Communication)是一个支持网页浏览器进行实时语音…...
