【马拉车算法/动态规划】最长回文字串
最长回文字串
- 1.问题描述
- 2.中心扩展法(O(N^2))
- 3.动态规划
- 4.Manacher(马拉车算法)
1.问题描述
常用有3种算法:中心扩展法、动态规划和Manacher算法
2.中心扩展法(O(N^2))
解释:
从中心向外扩展。
分为两种情况:第一种当回文串长度为奇数的情况;第二种当回文串长度为偶数的情况。
左右同时向外扩展,当左右不相同时停止扩展,记录最长回文串长度及起始位置。
public String longestPalindrome(String str) {if (Objects.isNull(str) || str.isEmpty()) {return "";}int maxStart = 0;int maxLength = 1;for (int i = 0; i < str.length(); i++) {for (int k = 0; k < 2; ++k) {int leftIndex = i - k; // k = 0表示偶数长度,k = 1表示奇数长度int rightIndex = i + 1;while (leftIndex >= 0&& rightIndex < str.length()&& str.charAt(leftIndex) == str.charAt(rightIndex)) {leftIndex--;rightIndex++;}if (maxLength < rightIndex - leftIndex - 1) { // 当前length = (rightIndex - 1) - (leftIndex + 1) + 1maxLength = rightIndex - leftIndex - 1;maxStart = leftIndex + 1;}}}return str.substring(maxStart, maxStart + maxLength);}
3.动态规划
4.Manacher(马拉车算法)
相关文章:

【马拉车算法/动态规划】最长回文字串
最长回文字串 1.问题描述2.中心扩展法(O(N^2))3.动态规划4.Manacher(马拉车算法) 1.问题描述 常用有3种算法:中心扩展法、动态规划和Manacher算法 2.中心扩展法(O(N^2)) 解释: 从中心向外扩展。 分为两种…...
什么是 fail-fast? 什么是fail-safe?
面试回答 在系统设计中,快速失效(fail-fast)系统一种可以立即报告任何可能表明故障的情况的系统。快速失效系统通常设计用于停止正常操作,而不是试图继续可能存在缺陷的过程。 其实,这是一种理念,说白了就是…...

第三届计算机、物联网与控制工程国际学术会议(CITCE 2023)
第三届计算机、物联网与控制工程国际学术会议(CITCE 2023) The 3rd International Conference on Computer, Internet of Things and Control Engineering(CITCE 2023) 第三届计算机、物联网与控制工程国际学术会议(CITCE 2023)…...
react antd 日期选择 WeekPicker MonthPicker 取值转为起止日期
默认WeekPicker 取值,返回的是2023年34周,这样后台用起来不方便。可以转化成指定周的起止日期 const startDate moment(weekData).day(1).format(YYYY-MM-DD); // 周一日期 const endDate moment(weekData).day(7).format(YYYY-MM-DD); // 周日日期同…...

table,设置 数据相同时, 合并列
<el-table :data"tableData" :span-method"objectSpanMethod" border style"width: 100%" show-summary><el-table-column type"index" label"序号" width"100" /><el-table-column prop"dat…...
kotlin如何接收前端传递过来的数据
Kotlin 可以使用 Spring Boot 等框架来接收前端传递过来的数据。 在 Spring Boot 中,你可以使用 RequestBody 注解来将前端传递的 JSON 格式数据转换为相应的 Kotlin 对象。 示例代码: RestController RequestMapping("/api") class UserCo…...

《中国区块链发展报告(2023)》发布 和数集团推动区块链发展
北京区块链技术应用协会与社会科学文献出版社日前在京共同发布《区块链蓝皮书:中国区块链发展报告(2023)》。蓝皮书归纳梳理了2022年区块链产业发展现状及趋势,并结合行业热点Web3.0、AIGC,探讨我国区块链发展的热点话…...

FreeSWITCH 1.10.10 简单图形化界面3 - 阿里云NAT设置
FreeSWITCH 1.10.10 简单图形化界面3 - 阿里云NAT设置 0、 界面预览1、 查看IP地址2、 修改协议配置3、 开放阿里云安全组4、 设置ACL5、 设置协议中ACL,让PBX匹配内外网6、 重新加载SIP模块7、 查看状态8、 测试一下 0、 界面预览 http://myfs.f3322.net:8020/ 用…...

Android SDK 上手指南||第五章 用户界面设计
第五章 用户界面设计 在本篇教程中我们将为应用程序项目添加布局方案,在这方面XML与Eclipse ADT接口将成为工作中的得力助手——不过在后面两节中还会用到一部分Java开发知识。XML与Java在Android平台的开发工作当中可谓无处不在,如果大家对二者还缺乏基…...
std::list和std::vector删除指定下标的元素
list和vector都可以使用erase函数移除指定下标的元素,注意输入的是迭代器,返回值为指向下一个元素的位置。: iterator erase(iterator position); iterator erase(iterator first,iterator last); 如果下标是index,直接调用即可:…...
Apache POI 以及 导出Excel表
一、Apache POI 1、介绍 Apache POI 是一个处理Miscrosoft Office各种文件格式的开源项目。简单来说就是,我们可以使用 POI 在 Java 程序中对Miscrosoft Office各种文件进行读写操作。 一般情况下,POI 都是用于操作 Excel 文件。 2、Apache POI 怎么…...

RabbitMQ从原理到实战—基于Golang【万字详解】
文章目录 前言一、MQ是什么?优势劣势 二、MQ的用途1、应用解耦2、异步加速3、削峰填谷4、消息分发 三、RabbitMQ是什么1、AMQP 协议2、RabbitMQ 包含的要素3、RabbitMQ 基础架构 四、实战1、Simple模式(即最简单的收发模式)2、Work Queues 模型3、Publish/Subscribe…...

机器学习——KNN算法
1、:前提知识 KNN算法是机器学习算法中用于分类或者回归的算法,KNN全称为K nearest neighbour(又称为K-近邻算法) 原理:K-近邻算法采用测量不同特征值之间的距离的方法进行分类。 优点:精度高 缺点&…...

Kali 软件管理测试案例
案例1 :显示目录树 tree ┌──(root㉿kali)-[~] └─# tree --help usage: tree [-acdfghilnpqrstuvxACDFJQNSUX] [-L level [-R]] [-H baseHREF][-T title] [-o filename] [-P pattern] [-I pattern] [--gitignore][--gitfile[]file] [--matchdirs] [--metafirs…...
【分布式】Zookeeper
Java开发者视角下的Zookeeper—— 在什么场景下使用,怎么用 可以参考:https://zhuanlan.zhihu.com/p/62526102 Zookeeper是什么? ZooKeeper 是一个分布式的,开放源码的分布式应用程序协同服务。ZooKeeper 的设计目标是将那些复…...

ScheduleJS Crack,新的“信息列”水平滚动功能
ScheduleJS Crack,新的“信息列”水平滚动功能 增加了对Angular 16的支持 新的“信息列”水平滚动功能。 新的“信息列”固定功能。 添加了输入属性以处理组件模板中的偶数和奇数ScheduleRowPlainBackgroundColor以及CSS变量。 改进了“信息列”和角度甘特组件的类型。 Schedul…...
curl封装
一。由于工作的原因,需要对curl做一些封装,附加上我们的证书,提供给第三个C和jAVA使用。 二。头文件封闭四个函数,get,post,download,upload #ifndef CURLHTTP_H #define CURLHTTP_H#include …...
C语言数据类型和变量
C语言数据类型和变量 数据类型分类内置类型【C语言本身就具有的类型】自定义类型【自己来创建类型】取值范围 变量变量的创建变量创建的语法形式变量的分类全局变量局部变量 栈区、堆区、静态区 算术操作符赋值操作符连续赋值复合赋值符 单目操作符:、--、、-强制类…...

分布式训练 最小化部署docker swarm + docker-compose落地方案
目录 背景: 前提条件: 一、docker环境初始化配置 1. 安装nvidia-docker2 2. 安装docker-compose工具 3. 获取GPU UUID 4. 修改docker runtime为nvidia,指定机器的UUID 二、docker-swarm 环境安装 1. 初始化swarm管理节点 2. 加入工…...

QT学习笔记-开发环境编译Qt MySql数据库驱动与交叉编译Qt MySql数据库驱动
QT学习笔记-开发环境编译Qt MySql数据库驱动与交叉编译Qt MySql数据库驱动 0、背景1、基本环境2、开发环境编译Qt MySql数据库驱动2.1 依赖说明2.2 MySQL驱动编译过程 3、交叉编译Qt MySql数据库驱动3.1 依赖说明3.3.1 如何在交叉编译服务器上找到mysql.h及相关头文件3.3.2 如果…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...

dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...

uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...

分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...

七、数据库的完整性
七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...
Webpack性能优化:构建速度与体积优化策略
一、构建速度优化 1、升级Webpack和Node.js 优化效果:Webpack 4比Webpack 3构建时间降低60%-98%。原因: V8引擎优化(for of替代forEach、Map/Set替代Object)。默认使用更快的md4哈希算法。AST直接从Loa…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能
1. 开发环境准备 安装DevEco Studio 3.1: 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK 项目配置: // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...