算法笔记(十二)—— Manacher算法(回文子串)
计算字符串内的最大回文子串,常用的暴力扩散在应对长度为偶数的回文时会遇到一些问题。
Manacher基础:对字符串进行填充,在字符串开头结尾以及字符间填充‘#’,以来应对偶数回文时的问题。(这是采用暴力扩再除2,可以得到正确的结果)
填充的字符不一定需要添加字符串内没有出现的字符
时间复杂度:O(N^2)
Manacher算法 - O(N^2)
概念:
回文直径:每个字符暴力扩的最大回文子串长度
回文半径:回文直径的一半
回文半径数组:将每个字符对应的回文半径信息存储起来
之前所扩的所有位置中所达到的最右边界 init R = -1
C:取最远边界时,中心点在哪
情况处理:
1. 当前来到的点不在右边界内: 暴力扩
2. 当前点在R内,R关于C的对称点L,当前点关于C的对称点i'
2.1 i'的回文区域彻底在[L R]的内部,则当前点的回文半径等于i'的回文半径
2.2 i'的回文区域有一部分在[L R]外,则i的回文半径等于R-i+1
2.3 i'的回文区域压在了[L R]上,i的回文半径从R开始暴力扩计算即可
// Manacher 这里将R设置为有效区再右一个位置
// manecher
class Solution {
public:string longestPalindrome(string s) {string str = "#";for(auto ch : s){str += ch;str += '#';}string temp = "";int num = INT_MIN;int R = -1;int C = -1;vector<int> arr(str.size() , 0);for(int i = 0 ; i<str.size() ; i++){arr[i] = R>i?min(arr[2*C-i] , R-i):1;while(i+arr[i]<str.size() && i-arr[i]>-1){if(str[i+arr[i]]==str[i-arr[i]])++arr[i];else break;}num = max(num , arr[i]);if(num==arr[i])temp = str.substr(i-arr[i]+1 , 2*arr[i]-1);}string res = "";for(auto ch : temp){if(ch!='#'){res += ch;}}return res;}
};
滑动窗口
使用双指针来代表一个当前窗口,左指针和右指针都只能往右滑动(L不能超过R)

1. 准备一个双端队列,存储数组下标,保证队列内数据单调排序
2. 右指针右滑,队列为空直接进,如果不为空,判断是否小于队列尾部数据,直接进;如果大于等于,弹出队列数据,直到满足队列为空或小于条件
3. 左指针右滑,判断队列头部数据对应下标是不是左指针左方的下标,如果是,从头部弹出
单调栈
知道每一个数左边最近的大数和右边最近的大数是谁(无重复数),并且时间复杂度O(N)
1. 栈空直接进,如果不为空判断该数是否小于栈顶元素,若小于,直接进;否则弹出栈内数据,生成该数的左右信息,弹出的数左信息为压着的,右信息为当前数,满足条件后近栈
2. 遍历结束,进入清算阶段,依次出栈并生成信息
如果有重复数据的话,用链表来存放即可,哈希表<链表<下标>,数据值>
相关文章:
算法笔记(十二)—— Manacher算法(回文子串)
计算字符串内的最大回文子串,常用的暴力扩散在应对长度为偶数的回文时会遇到一些问题。 Manacher基础:对字符串进行填充,在字符串开头结尾以及字符间填充‘#’,以来应对偶数回文时的问题。(这是采用暴力扩再除2&#x…...
【数据结构】顺序表和链表的区别和联系(详解)
顺序表和链表的区别(详解) 文章目录顺序表和链表的区别(详解)前言一、顺序表和链表的关系二、顺序表1.优点2.缺点三、链表1.优点2.缺点四、区别表格总结前言 本文给大家介绍顺序表和链表的各自的优缺点和区别与联系,结…...
【Linux操作系统】【综合实验三 用户帐号、文件系统与系统安全管理】【更新中】
文章目录一、实验目的二、实验要求三、实验内容四、实验报告要求一、实验目的 要求掌握Linux系统用户的创建、删除与管理操作;熟悉Linux文件系统的管理模式,学会创建用户文件系统并装载和卸载文件系统;掌握超级用户的管理方式与权限…...
华为OD机试真题 用 C++ 实现 - 整数分解 | 多看题,提高通过率
最近更新的博客 华为OD机试 - 入栈出栈(C++) | 附带编码思路 【2023】 华为OD机试 - 箱子之形摆放(C++) | 附带编码思路 【2023】 华为OD机试 - 简易内存池 2(C++) | 附带编码思路 【2023】 华为OD机试 - 第 N 个排列(C++) | 附带编码思路 【2023】 华为OD机试 - 考古…...
Java集合(一)---List和set
1.Java集合有哪些?集合类型主要有3种:set(集)、list(列表)和map(映射)Map接口和Collection接口是所有集合框架的父接口:1. Collection接口的子接口包括:Set接口和List接口2. Map接口的实现类主要有…...
手撸一个Table组件(Table组件不过如此)
一、前言 手写Table组件这个文章我一直都想写,今天终于得空来写它了。小编认为Table组件是组件库里"较为复杂"的一个组件,因为它的扩展性非常强,并且它的基础样式如何去写都非常考究,那么今天我就带大家来实现一个基础…...
Python|Leetcode刷题日寄Part01
Python|Leetcode刷题日寄Part0101:两数之和02:无重复字符的最长子串03:两数相加04:反转链表05:有效的括号06:回文数07:删除有序数组中的重复项08:删除链表的倒数第N个结点09…...
微信小程序更改头像昵称
背景 前面写了一篇关于小程序头像昵称获取更改的方案,有很多小伙伴私信我发一个整体的逻辑思路! 解决思路 前面的这篇文章中我们给出了页面中获取头像昵称的代码: <view class"headInfo" data-weui-theme"{{theme}}&qu…...
Linux 基础知识之文件系统
目录一、文件系统1.文件种类2.Linux和Windows文件后缀的不同3.查看文件类型3.绝对路径与相对路径二、系统分区三、目录结构一、文件系统 1.文件种类 Linux中一切皆文件。目光所及,皆是文件。文件的种类共有七种,每种文件都有自己的独特标识:…...
LeetCode 36. 有效的数独
LeetCode 36. 有效的数独 难度:middle\color{orange}{middle}middle 题目描述 请你判断一个 9x99 x 99x9 的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。 数字 1−91-91−9 在每一行只能出现一次。数字 1−91-91−9 在每一列…...
2023-02-22 cascades-columbia-核心处理记录
摘要: columbia是哥伦比亚对于cascades的一个改进, 并且paper写的也相对详尽. 虽然cacades的实现有很多,比较出名的就是greenplum的gporca, 不过columbia也有其显著的优点. 本文通过对columbia的分析展开对cascades优化器思想的探讨. 参考: 2023-02-10 哥伦比亚cascades-xu-…...
华为分布式存储(FusionStorage)
Server SAN SAN:存储区域网络 IP SAN:以太网交换机和普通网线连接的存储,交换机之间做堆叠FC SAN:FC(光纤)交换机和光纤连接的存储,交换机之间做级联Server SAN:可以使用以太网交换机…...
说说 React 中 fiber、DOM、ReactElement、实例对象之间的引用关系
原生组件 fiber 原生组件 fiber,指的就是 type 为 “span”、“div” 的 fiber。 1.fiber.stateNode 指向真实 DOM 节点;2.node["__reactFiber$" randomKey] 指向对应 fiber,使用随机数是防止和业务代码的属性名冲突,…...
LaTex公式使用(Word中的公式编辑,尤其是方程组等联合公式)
文章目录 LaTex公式使用(Word中的公式编辑,尤其是方程组等联合公式)refnotedemoLaTex公式使用(Word中的公式编辑,尤其是方程组等联合公式) ref markdown中公式编辑教程 在 Microsoft Word 中使用 LaTeX 输入数学公式【比较全,介绍了支持的语法和不支持的语法】 用wo…...
S5P6818_系统篇(2)源码编译及烧录
源码获取 源码获取和操作流程 1.下载liunux下的系统制作脚本,可以烧录系统和构建镜像 git clone https://github.com/friendlyarm/sd-fuse_s5p6818.git 如果出现git错误可使用如下方法: git config --global http.sslverify false 2.阅读该工具rea…...
LDPC码的编译码原理简述
关于fpga调用ldpc IP core的相关参数问题可以看我的另一篇文章 LDPC码由Gallager在1962年提出,全称为 Low Density Parity-check Codes 低密度奇偶校验码 它的译码性能可以逼近Shannon信道容量限,广富盛名的Turbo码也被证明是LDPC码的一个特例。并且LDPC…...
网络安全——数链路层据安全协议
作者简介:一名云计算网络运维人员、每天分享网络与运维的技术与干货。 座右铭:低头赶路,敬事如仪 个人主页:网络豆的主页 目录 前言 一.数据链路层安全协议简介 1.数据链路安全性 二.局域网数据链路层协议 1.…...
spring的启动过程(一) :IOC容器的启动过程
一、web容器的加载 首先我们要先知道一个web项目的启动过程。 将Web项目部署到Tomcat中的方法之一,是部署没有封装到WAR文件中的Web项目。要使用这一方法部署未打包的webapp目录,只要把我们的项目(编译好的发布项目,非开发项目&am…...
这次,我的CentOS又ping不通www.baidu.com了(gateway配置)
当我们保证了宿主机与虚拟机的ip地址在同一网段,并且我们使用虚拟机ping宿主机,与宿主机ping虚拟机都可以互相ping通的情况下虚拟机却ping不通外网了,由于涉及到了跨越网络访问,所以我们应该把问题聚焦在网关的配置上!…...
启智社区“我为开源狂”第六期活动小白教程之基础活跃榜
一、写在前面 春天来啦~启智社区第六期活动也来啦! 有奖金的哦~~ 基础活跃榜奖金根据用户活跃程度进行100-300元的激励。 挑战升级榜需要用户完成相应任务,达标者可获得300-1000元的激励。 邀请助力榜根据用户邀请情况进行积分累加,按实际达…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关
在水泥厂的生产流程中,工业自动化网关起着至关重要的作用,尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关,为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多,其中不少设备采用Devicenet协议。Devicen…...
Python网页自动化Selenium中文文档
1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API,让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API,你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...
【51单片机】4. 模块化编程与LCD1602Debug
1. 什么是模块化编程 传统编程会将所有函数放在main.c中,如果使用的模块多,一个文件内会有很多代码,不利于组织和管理 模块化编程则是将各个模块的代码放在不同的.c文件里,在.h文件里提供外部可调用函数声明,其他.c文…...
虚幻基础:角色旋转
能帮到你的话,就给个赞吧 😘 文章目录 移动组件使用控制器所需旋转:组件 使用 控制器旋转将旋转朝向运动:组件 使用 移动方向旋转 控制器旋转和移动旋转 缺点移动旋转:必须移动才能旋转,不移动不旋转控制器…...
