【马拉车算法/动态规划】最长回文字串
最长回文字串
- 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 如果…...

css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
站群服务器的应用场景都有哪些?
站群服务器主要是为了多个网站的托管和管理所设计的,可以通过集中管理和高效资源的分配,来支持多个独立的网站同时运行,让每一个网站都可以分配到独立的IP地址,避免出现IP关联的风险,用户还可以通过控制面板进行管理功…...