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

前缀和算法

news 来源：原创 2025/5/15 21:11:09

文章目录

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

算法总览

题目

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] 中&…...

编程日记 2025/5/15 21:11:09

稀疏混合专家架构语言模型（MoE）

注：本文为 “稀疏混合专家架构语言模型（MoE）” 相关文章合辑。手把手教你，从零开始实现一个稀疏混合专家架构语言模型（MoE） 机器之心 2024年02月11日 12:21 河南选自huggingface 机器之心编译机器之心…...

编程日记 2025/5/14 23:57:23

深入理解 `box-sizing: border-box；`：CSS 布局的利器

深入理解 box-sizing: border-box;：CSS 布局的利器默认行为示例代码使用 box-sizing: border-box;示例代码全局应用 box-sizing: border-box;示例代码实际应用场景1. 表单布局2. 网格布局总结在 CSS 中，box-sizing 属性决定了元素的总宽度和高度是…...

编程日记 2025/5/12 14:18:26

MySQL不适合创建索引的11种情况

文章目录前言1. **数据量小的表**2. **频繁更新的列**3. **低选择性的列**4. **频繁插入和删除的表**5. **查询中很少使用的列**6. **大文本或BLOB列**7. **复合索引中未使用的前导列**8. **频繁进行批量插入的表**9. **查询返回大部分数据的表**10. **临时表**11. **列值频繁…...

编程日记 2025/5/12 9:47:58

shell呈现数据——在脚本中重定向

重定向输出只需简单地重定向相应的文件描述符，就可以在脚本中用文件描述符STDOUT和STDERR在多个位置生成输出。在脚本中重定向输出的方法有两种。临时重定向每一行。永久重定向脚本中的所有命令。下面将具体展示这两种方法的工作原理。 1.临时重定向如果你…...

编程日记 2025/5/13 9:41:03

vector容器（详解）

本文最后是模拟实现全部讲解，文章穿插有彩色字体，是我总结的技巧和关键 1.vector的介绍及使用 1.1 vector的介绍 https://cplusplus.com/reference/vector/vector/（vector的介绍） 了解 1. vector是表示可变大小数组的序列容器。…...

编程日记 2025/5/15 20:43:27

【初/高中生讲机器学习】0. 本专栏 “食用” 指南——写在一周年之际⭐

创建时间：2025-01-27 首发时间：2025-01-29 最后编辑时间：2025-01-29 作者：Geeker_LStar 你好呀~这里是 Geeker_LStar 的人工智能学习专栏，很高兴遇见你~ 我是 Geeker_LStar，一名高一学生，热爱计…...

编程日记 2025/5/13 3:28:35

SAP SD学习笔记28 - 请求计划(开票计划)之2 - Milestone请求(里程碑开票)

上一章讲了请求计划（开票计划）中的定期请求。 SAP SD学习笔记27 - 请求计划(开票计划)之1 - 定期请求-CSDN博客本章继续来讲请求计划（开票计划）的其他内容： Milestone请求(里程碑请求)。目录 1，Miles…...

编程日记 2025/5/15 2:12:06

【PyTorch介绍】

PyTorch 是什么？ PyTorch 是一个开源的深度学习框架，由 Facebook 的人工智能研究实验室（FAIR）开发和维护。它是一个基于 Python 的库，专为深度学习和人工智能研究设计，支持动态计算图（dynamic …...

编程日记 2025/5/15 17:49:53

语言月赛 202412【正在联系教练退赛】题解（AC）

》》》点我查看「视频」详解》》》 [语言月赛 202412] 正在联系教练退赛题目背景在本题中，我们称一个字符串 y y y 是一个字符串 x x x 的子串，当且仅当从 x x x 的开头和结尾删去若干个（可以为 0 0 0 个）字符后剩余的字…...

编程日记 2025/5/14 9:29:12

【C++】B2122 单词翻转

博客主页： [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C 文章目录 💯前言💯题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 💯一、我的做法代码实现：代码解析思路分析 💯二、老师的第一种做法代码实现&a…...

编程日记 2025/5/11 22:07:00

redis基本数据结构

基本数据结构 String String是Redis中最常见的数据存储类型： 其基本编码方式是RAW，基于简单动态字符串（SDS）实现，存储上限为512mb。如果存储的SDS长度小于44字节，则会采用EMBSTR编码，此时ob…...

编程日记 2025/5/12 10:25:30

基于STM32景区环境监测系统的设计与实现（论文+源码）

1系统方案设计根据系统功能的设计要求，展开基于STM32景区环境监测系统设计。如图2.1所示为系统总体设计框图。系统以STM32单片机作为系统主控模块，通过DHT11传感器、MQ传感器、声音传感器实时监测景区环境中的温湿度、空气质量以及噪音数据。系统监测环…...

编程日记 2025/5/13 10:09:19

1.冒泡排序 #define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h>int main() {int arr[] { 0,2,5,3,4,8,9,7,6,1 };int sz sizeof(arr) / sizeof(arr[0]);//冒泡排序一共排序 sz-1 趟for (int i 0; i < sz - 1; i){//标志位，如果有序，直接…...

编程日记 2025/5/14 17:33:54

探秘Linux IO虚拟化：virtio的奇幻之旅

在当今数字化时代，虚拟化技术早已成为推动计算机领域发展的重要力量。想象一下，一台物理主机上能同时运行多个相互隔离的虚拟机，每个虚拟机都仿佛拥有自己独立的硬件资源，这一切是如何实现的呢？今天，就让我…...

编程日记 2025/5/15 16:01:14

在React中使用redux

一、首先安装两个插件 1.Redux Toolkit 2.react-redux 第一步：创建模块counterStore 第二步：在store的入口文件进行子模块的导入组合第三步：在index.js中进行store的全局注入第四步：在组件中进行使用第五步：在组件中…...

编程日记 2025/5/14 4:35:11

从 C 到 C++：理解结构体中字符串的存储与操作

对于刚入门 C/C 的程序员来说，字符串的存储和操作可能是个容易混淆的知识点。在 C 中，std::string 提供了非常友好的接口，我们可以轻松地在结构体中使用字符串类型，无需关注底层细节。然而，在 C 语言中，字符…...

编程日记 2025/5/15 5:59:12

2.3学习总结

图： 1.图的基本概念 2.图的存储和遍历 3.最小生成树 4.最短路径 5.拓扑排序和关键路径一、图的基本概念图的定义：不允许没有顶点，但边集可以为空 {无向图 {有向图：边弧，弧头（有箭头）…...

编程日记 2025/5/13 9:24:20

wordpress代码结构解析

WordPress 是一个基于 PHP 和 MySQL 的开源内容管理系统（CMS），广泛用于构建网站和博客。要解析 WordPress 代码，首先需要了解其核心结构、主要文件和常用的函数。以下是 WordPress 代码解析的基本指南： --- ### 1. *…...

编程日记 2025/5/10 1:20:40

使用 Numpy 自定义数据集，使用pytorch框架实现逻辑回归并保存模型，然后保存模型后再加载模型进行预测，对预测结果计算精确度和召回率及F1分数

1. 导入必要的库首先，导入我们需要的库：Numpy、Pytorch 和相关工具包。 import numpy as np import torch import torch.nn as nn import torch.optim as optim from sklearn.metrics import accuracy_score, recall_score, f1_score2. 自定义数据集 …...

编程日记 2025/5/12 9:05:37

FPGA|例化生成的PLL功能IP核

1、例化上一篇文章中调用的IP核，新建文件PLL_test.v 2、代码如图 timescale 1ns / 1ps module PLL_test(input clk,input rst_n,output clkout0,output clkout1,output clkout2,output clkout3,output clkout4);wire locked;PLL pll_inst(.inclk0(clk),.c0(clkout0)…...

编程日记 2025/5/15 13:53:53

K个不同子数组的数目--滑动窗口--字节--亚马逊

Stay hungry, stay foolish 题目描述给定一个正整数数组 nums和一个整数 k，返回 nums 中「好子数组」的数目。如果 nums 的某个子数组中不同整数的个数恰好为 k，则称 nums 的这个连续、不一定不同的子数组为「好子数组」。例如，[1,2,…...

编程日记 2025/5/15 16:23:36

手机连接WIFI可以上网，笔记本电脑连接WIFI却不能上网？解决方法？

原因：DNS受污染了解决办法 step 1：清空域名解析记录（清空DNS） ipconfig /flushdns (Windows cmd命令行输入) step 2：重新从DHCP 获取IP ipconfig /release（释放当前IP地址） ipconfig /renew &…...

编程日记 2025/5/15 16:23:35

大模型综述一镜到底（全文八万字） ——《Large Language Models: A Survey》

论文链接：https://arxiv.org/abs/2402.06196 摘要：自2022年11月ChatGPT发布以来，大语言模型（LLMs）因其在广泛的自然语言任务上的强大性能而备受关注。正如缩放定律所预测的那样，大语言模型通过在大量文本数…...

编程日记 2025/5/15 16:23:34

C语言按位取反【~】详解，含原码反码补码的0基础讲解【原码反码补码严格意义上来说属于计算机组成原理的范畴，不过这也是学好编程初级阶段的必修课】

目录概述【适合0基础看的简要描述】： 上述加粗下划线的内容提取版： 从上述概述中提取的核心知识点，需背诵： 整数【包含整数，负整数和0】的原码反码补码相互转换的过程图示： 过程详细刨析：…...

编程日记 2025/5/15 16:23:32

本地部署与使用SenseVoice语音大模型简析

前言 SenseVoice 是一种语音基础模型，具有多种语音理解功能，包括自动语音识别 (ASR)、口语识别 (LID)、语音情感识别 (SER) 和音频事件检测 (AED)。本博客将指导您安装和使用 SenseVoice 模型，使其尽可能方便用户使用。 Github 仓库链接: ht…...

编程日记 2025/5/15 16:23:31

QMK启用摇杆和鼠标按键功能

虽然选择了触摸屏，我仍选择为机械键盘嵌入摇杆模块，这本质上是对"操作连续性"的执着。值得深思的是，本次开发过程中借助DeepSeek的代码生成与逻辑推理，其展现的能力已然颠覆传统编程范式，需求描述可自动…...

编程日记 2025/5/15 16:23:30

排序算法与查找算法

1.十大经典排序算法我们希望数据以一种有序的形式组织起来，无序的数据我们要尽量将其变得有序一般说来有10种比较经典的排序算法简单记忆为Miss D----D小姐时间复杂度 ：红色<绿色<蓝色空间复杂度：圆越大越占空间稳定性&…...

编程日记 2025/5/15 16:23:29

基于Spring Security 6的OAuth2 系列之九 - 授权服务器--token的获取

之所以想写这一系列，是因为之前工作过程中使用Spring Security OAuth2搭建了网关和授权服务器，但当时基于spring-boot 2.3.x，其默认的Spring Security是5.3.x。之后新项目升级到了spring-boot 3.3.0，结果一看Spring Security也升级…...

编程日记 2025/5/15 3:36:32

【思维导图】redis

学习计划：将目前已经学的知识点串成一个思维导图。在往后的学习过程中，不断往思维导图里补充，形成自己整个知识体系。对于思维导图里的每个技术知识，自己用简洁的话概括出来， 训练自己的表达能力。...

编程日记 2025/5/14 23:50:55

【Git】使用笔记总结

目录概述安装Git注册GitHub配置Git常用命令常见场景1. 修改文件2. 版本回退3. 分支管理常见问题1. git add [中文文件夹] 无法显示中文问题2. git add [文件夹] 文件名中含有空格3. git add 触发 LF 回车换行警告4. git push 提示不存在 Origin 仓库5. Git与GitHub中默认分支…...

编程日记 2025/5/14 17:24:00

cf div3 998 E(并查集）

E : 给出两个简单无向图 （没有重边和自环）f g . 可以对f 进行删边和加边的操作。问至少操作多少次 ，使得 f 和 g 的点的联通情况相同（并查集的情况相同） 首先思考删边 ： 对于我 f 图存在边 e &#x…...

编程日记 2025/5/15 16:23:25

【C++】string类(上)：string类的常用接口介绍

文章目录前言一、C中设计string类的意义二、string类的常用接口说明1. string类对象的常见构造2. string类对象的容量操作2.1 size、capacity 和 empty的使用2.2 clear的使用2.3 reserve的使用2.4 resize的使用 3. string类对象的访问及遍历操作3.1 下标[ ] 和 at3.2 迭代器it…...

编程日记 2025/5/15 16:23:24

[SAP ABAP] ABAP SQL跟踪工具

事务码ST05 操作步骤步骤1：使用事务码ST05之前，将要检测的程序生成的页面先呈现出来，这里我们想看下面程序的取数操作，所以停留在选择界面步骤2： 新建一个GUI窗口，输入事务码ST05，点击 Acti…...

编程日记 2025/5/15 16:23:23

OpenGL学习笔记（六）：Transformations 变换（变换矩阵、坐标系统、GLM库应用）

文章目录向量变换使用GLM变换（缩放、旋转、位移）将变换矩阵传递给着色器坐标系统与MVP矩阵三维变换绘制3D立方体 & 深度测试（Z-buffer）练习1——更多立方体现在我们已经知道了如何创建一个物体、着色、加入纹理。但它们都还…...

编程日记 2025/5/15 16:23:23

PHP 常用函数2025.02

PHP implode() 函数语法 implode(separator,array) 参数描述separator可选。规定数组元素之间放置的内容。默认是 ""（空字符串）。array必需。要组合为字符串的数组。技术细节返回值：返回一个由数组元素组合成的字符串。PHP 版…...

编程日记 2025/5/15 16:23:21

17.3.4 颜色矩阵

编程日记 2025/5/15 16:23:20

1. 【.NET 8 实战--孢子记账--从单体到微服务--转向微服务】--前言

在我们的专栏《单体开发》中，我们实现了一个简单的记账软件的服务端，并且成功上线。随着用户数量的不断增长，问题逐渐开始显现。访问量逐渐增加，服务端的压力也随之加大。随着访问量的攀升，服务端的响应时间变得越来越…...

编程日记 2025/5/12 4:20:46

02.04 数据类型

请写出以下几个数据的类型： 整数 a ----->int a的地址 ----->int* 存放a的数组b ----->int[] 存放a的地址的数组c ----->int*[] b的地址 ----->int* c的地址 ----->int** 指向printf函数的指针d ----->int (*)(const char*, ...) …...

编程日记 2025/5/11 18:20:02

WPS动画：使图形平移、围绕某个顶点旋转一定角度

1、平移案例三角形如下图，需求：该三角形的A点平移至原点 （1）在预想动画结束的位置绘制出图形 （2）点击选中原始图像，插入/动画/绘制自定义路径/直线 （3）十字星绘制的直线…...

编程日记 2025/5/13 9:24:16

想表示消息返回值为Customer集合

道奈特(240***10) 14:34:55 EA中序列图。我想表示消息返回值为 Customer 集合。目前只有一个Customer实体类，我需要另外新建一个CustomerList 类吗？ 潘加宇(35***47) 17:01:26 不需要。如果是分析，在类的操作中，定义一个参数&…...

编程日记 2025/5/15 16:23:19

93，【1】buuctf web [网鼎杯 2020 朱雀组]phpweb

进入靶场页面一直在刷新在 PHP 中，date() 函数是一个非常常用的处理日期和时间的函数，所以应该用到了再看看警告的那句话 Warning: date(): It is not safe to rely on the systems timezone settings. You are *required* to use the date.timez…...

编程日记 2025/5/15 16:23:18

五、定时器实现呼吸灯

5.1 定时器与计数器简介定时器是一种通过对内部时钟脉冲计数来测量时间间隔的模块。它的核心是一个递增或递减的寄存器（计数器值）。如果系统时钟为 1 MHz，定时器每 1 μs 计数一次。计数器是一种对外部事件（如脉冲信号&#xff…...

编程日记 2025/5/15 16:23:17

顺序打印数字的进一步理解

之前博客写了篇博文，面试时要求使用多线程顺序打印ABC循环20次，这是我当时使用join函数实现代码： public class TestABCJoin {public static void main(String[] args) {// 创建任务Runnable taskA () -> {for (int i 0; i < 5; i) …...

编程日记 2025/5/13 23:52:58

使用React和Material-UI构建TODO应用的前端UI

使用React和Material-UI构建TODO应用的前端UI 引言环境准备代码解析1. 导入必要的模块2. 创建React组件3. 定义函数3.1 获取TODO列表3.2 创建TODO项3.3 更新TODO项3.4 删除TODO项3.5 处理编辑点击事件3.6 关闭编辑对话框3.7 保存编辑内容 4. 使用Effect钩子5. 渲染组件功能实现…...

编程日记 2025/5/12 14:41:17

开屏广告-跳过神器

给大家介绍一款超实用的软件——SKIP，它堪称李跳跳的最佳平替！这款软件已经在Github开源免费，完全无需担心内置源问题，也无需导入任何规则。安装完成后，即可直接使用，非常便捷！ 首次打开软件时…...

编程日记 2025/5/12 3:18:32

bat脚本实现自动化漏洞挖掘

bat脚本 BAT脚本是一种批处理文件，可以在Windows操作系统中自动执行一系列命令。它们可以简化许多日常任务，如文件操作、系统配置等。 bat脚本执行命令 echo off#下面写要执行的命令 httpx 自动存活探测 echo off httpx.exe -l url.txt -o 0.txt nuc…...

编程日记 2025/5/14 8:15:13

如何运行Composer安装PHP包安装JWT库

1. 使用Composer Composer是PHP的依赖管理工具，它允许你轻松地安装和管理PHP包。对于JWT，你可以使用firebase/php-jwt这个库，这是由Firebase提供的官方库。安装Composer（如果你还没有安装的话）： 访问Co…...

编程日记 2025/5/15 7:24:15

(回溯递归dfs 电话号码的字母组合 remake)leetcode 17

只找边界条件和非边界条件，剩下的交给数学归纳法就行，考虑子问题的重复性 [class Solution {vector<string>str { "","","abc","def","ghi","jkl","mno","pqrs"…...

编程日记 2025/5/15 8:32:20

it基础使用--5---git远程仓库

文章目录 it基础使用--5---git远程仓库1. 按顺序看2. 什么是远程仓库3. Gitee操作3.1 新建远程仓库3.2 远程操作基础命令3.3 查看当前所有远程地址别名 git remote -v3.4 创建远程仓库别名 git remote add 别名远程地址3.4 推送本地分支到远程仓库 git push 别名分支3.5 拉取…...

编程日记 2025/5/15 0:36:56

文章目录

算法总览

题目

1371.每个元音包含偶数次的最长子字符串

相关文章：