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

【马拉车算法/动态规划】最长回文字串

最长回文字串

  • 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.中心扩展法&#xff08;O(N^2)&#xff09;3.动态规划4.Manacher(马拉车算法) 1.问题描述 常用有3种算法&#xff1a;中心扩展法、动态规划和Manacher算法 2.中心扩展法&#xff08;O(N^2)&#xff09; 解释&#xff1a; 从中心向外扩展。 分为两种…...

什么是 fail-fast? 什么是fail-safe?

面试回答 在系统设计中&#xff0c;快速失效&#xff08;fail-fast&#xff09;系统一种可以立即报告任何可能表明故障的情况的系统。快速失效系统通常设计用于停止正常操作&#xff0c;而不是试图继续可能存在缺陷的过程。 其实&#xff0c;这是一种理念&#xff0c;说白了就是…...

第三届计算机、物联网与控制工程国际学术会议(CITCE 2023)

第三届计算机、物联网与控制工程国际学术会议&#xff08;CITCE 2023) The 3rd International Conference on Computer, Internet of Things and Control Engineering&#xff08;CITCE 2023) 第三届计算机、物联网与控制工程国际学术会议&#xff08;CITCE 2023&#xff09;…...

react antd 日期选择 WeekPicker MonthPicker 取值转为起止日期

默认WeekPicker 取值&#xff0c;返回的是2023年34周&#xff0c;这样后台用起来不方便。可以转化成指定周的起止日期 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 中&#xff0c;你可以使用 RequestBody 注解来将前端传递的 JSON 格式数据转换为相应的 Kotlin 对象。 示例代码&#xff1a; RestController RequestMapping("/api") class UserCo…...

《中国区块链发展报告(2023)》发布 和数集团推动区块链发展

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

FreeSWITCH 1.10.10 简单图形化界面3 - 阿里云NAT设置

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

Android SDK 上手指南||第五章 用户界面设计

第五章 用户界面设计 在本篇教程中我们将为应用程序项目添加布局方案&#xff0c;在这方面XML与Eclipse ADT接口将成为工作中的得力助手——不过在后面两节中还会用到一部分Java开发知识。XML与Java在Android平台的开发工作当中可谓无处不在&#xff0c;如果大家对二者还缺乏基…...

std::list和std::vector删除指定下标的元素

list和vector都可以使用erase函数移除指定下标的元素&#xff0c;注意输入的是迭代器&#xff0c;返回值为指向下一个元素的位置。: iterator erase(iterator position); iterator erase(iterator first,iterator last); 如果下标是index&#xff0c;直接调用即可&#xff1a…...

Apache POI 以及 导出Excel表

一、Apache POI 1、介绍 Apache POI 是一个处理Miscrosoft Office各种文件格式的开源项目。简单来说就是&#xff0c;我们可以使用 POI 在 Java 程序中对Miscrosoft Office各种文件进行读写操作。 一般情况下&#xff0c;POI 都是用于操作 Excel 文件。 2、Apache POI 怎么…...

RabbitMQ从原理到实战—基于Golang【万字详解】

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

机器学习——KNN算法

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

Kali 软件管理测试案例

案例1 &#xff1a;显示目录树 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—— 在什么场景下使用&#xff0c;怎么用 可以参考&#xff1a;https://zhuanlan.zhihu.com/p/62526102 Zookeeper是什么&#xff1f; ZooKeeper 是一个分布式的&#xff0c;开放源码的分布式应用程序协同服务。ZooKeeper 的设计目标是将那些复…...

ScheduleJS Crack,新的“信息列”水平滚动功能

ScheduleJS Crack,新的“信息列”水平滚动功能 增加了对Angular 16的支持 新的“信息列”水平滚动功能。 新的“信息列”固定功能。 添加了输入属性以处理组件模板中的偶数和奇数ScheduleRowPlainBackgroundColor以及CSS变量。 改进了“信息列”和角度甘特组件的类型。 Schedul…...

curl封装

一。由于工作的原因&#xff0c;需要对curl做一些封装&#xff0c;附加上我们的证书&#xff0c;提供给第三个C和jAVA使用。 二。头文件封闭四个函数&#xff0c;get&#xff0c;post&#xff0c;download&#xff0c;upload #ifndef CURLHTTP_H #define CURLHTTP_H#include …...

C语言数据类型和变量

C语言数据类型和变量 数据类型分类内置类型【C语言本身就具有的类型】自定义类型【自己来创建类型】取值范围 变量变量的创建变量创建的语法形式变量的分类全局变量局部变量 栈区、堆区、静态区 算术操作符赋值操作符连续赋值复合赋值符 单目操作符&#xff1a;、--、、-强制类…...

分布式训练 最小化部署docker swarm + docker-compose落地方案

目录 背景&#xff1a; 前提条件&#xff1a; 一、docker环境初始化配置 1. 安装nvidia-docker2 2. 安装docker-compose工具 3. 获取GPU UUID 4. 修改docker runtime为nvidia&#xff0c;指定机器的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, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

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

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

uniapp微信小程序视频实时流+pc端预览方案

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

分布式增量爬虫实现方案

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

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...