当前位置: 首页 > 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 如果…...

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 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 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 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

站群服务器的应用场景都有哪些?

站群服务器主要是为了多个网站的托管和管理所设计的&#xff0c;可以通过集中管理和高效资源的分配&#xff0c;来支持多个独立的网站同时运行&#xff0c;让每一个网站都可以分配到独立的IP地址&#xff0c;避免出现IP关联的风险&#xff0c;用户还可以通过控制面板进行管理功…...