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

最长回文子串【Java实现】

题目描述

现有一个字符串s,求s的最长回文子串的长度

输入描述

一个字符串s,仅由小写字母组成,长度不超过100

输出描述

输出一个整数,表示最长回文子串的长度

样例

输入

lozjujzve

输出

// 最长公共子串为zjujz,长度为5
5

思路分析

  • 长度由0~n的字符串都可能是回文子串,若要使得下标[i,j]指向的字符串是回文子串,则必须保证下标[i+1,j-1]指向的字符串是回文子串,这说明回文子串内部存在一定依赖关系,由此可以考虑使用动态规划
  • 设置数组dp[n][n],其中n是字符串长度,dp[i][j]==true代表下标[i,j]指向的字符串arr[]是回文字符串
    • 易知,dp[i][i]初始为true,因为长度为1的字符串一定是回文字符串
    • 进入二重循环,第一重定义当前要判断的回文字符串长度,第二重确定当前字符串的起始下标i与终止下标j
    • 如果arr[i]==arr[j],那么说明当前[i,j]有可能是回文子串,需要由dp[i+1][j-1]是否为true决定
    • 其中有一种特殊情况,即i+1==j,此时说明当前判断的回文子串长度为2,此时首尾字符又相等,那么当前一定是回文子串
    • 每次确定下一个回文子串后就更新最大长度max
  • 最后输出结果max即可

代码实现

import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);char[] arr = scanner.next().toCharArray();boolean dp[][] = new boolean[arr.length][arr.length];for (int i = 0; i < arr.length; i++) {// 长度为 1 一定是回文串dp[i][i] = true;}int max = 1;for (int len = 2; len <= arr.length; len++) {for (int i = 0; i + len - 1 < arr.length; i++) {// i 指向字符串开头元素,j 指向字符串最后一个元素int j = i + len - 1;// 当前首尾元素相同,并且原来中间部分也是回文串,则当前字符串是回文串// 当首尾元素相同且字符串长度为 2 时,当前字符串也是回文串if (arr[i] == arr[j] && (i + 1 == j || dp[i + 1][j - 1])) {dp[i][j] = true;max = len;}}}System.out.println(max);}}

相关文章:

最长回文子串【Java实现】

题目描述 现有一个字符串s&#xff0c;求s的最长回文子串的长度 输入描述 一个字符串s&#xff0c;仅由小写字母组成&#xff0c;长度不超过100 输出描述 输出一个整数&#xff0c;表示最长回文子串的长度 样例 输入 lozjujzve输出 // 最长公共子串为zjujz&#xff0c;长度为…...

LeetCode 438. Find All Anagrams in a String

LeetCode 438. Find All Anagrams in a String 题目描述 Given two strings s and p, return an array of all the start indices of p’s anagrams in s. You may return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a…...

MyBatis-1:基础概念+环境配置

什么是MyBatis&#xff1f;MyBatis是一款优秀的持久层框架&#xff0c;支持自定义sql&#xff0c;存储过程以及高级映射。MyBatis就是可以让我们更加简单的实现程序和数据库之间进行交互的一个工具。可以让我们更加简单的操作和读取数据库的内容。MyBatis的官网&#xff1a;htt…...

R语言基础(五):流程控制语句

R语言基础(一)&#xff1a;注释、变量 R语言基础(二)&#xff1a;常用函数 R语言基础(三)&#xff1a;运算 R语言基础(四)&#xff1a;数据类型 6.流程控制语句 和大多数编程语言一样&#xff0c;R语言支持选择结构和循环结构。 6.1 选择语句 选择语句是当条件满足的时候才执行…...

【Java开发】设计模式 02:工厂模式

1 工厂模式介绍工厂模式&#xff08;Factory Pattern&#xff09;是 Java 中最常用的设计模式之一。这种类型的设计模式属于创建型模式&#xff0c;它提供了一种创建对象的最佳方式。在工厂模式中&#xff0c;我们在创建对象时不会对客户端暴露创建逻辑&#xff0c;并且是通过使…...

合并两个链表(自定义位置合并与有序合并)LeetCode--OJ题详解

图片: csdn 自定义位置合并 问题&#xff1a; 给两个链表 list1 和 list2 &#xff0c;它们包含的元素分别为 n 个和 m 个。 请你将 list1 中 下标从 a 到 b 的全部节点都删除&#xff0c;并将list2 接在被删除节点 的位置。 比如&#xff1a; 输入&#xff1a;list1 [1…...

Java编程问题总结

Java编程问题总结 整理自 https://github.com/giantray/stackoverflow-java-top-qa 基础语法 将InputStream转换为String apache commons-io String content IOUtils.toString(new FileInputStream(file), StandardCharsets.UTF_8); //String value FileUtils.readFileT…...

binutils工具集——objcopy的用法

以下内容源于网络资源的学习与整理&#xff0c;如有侵权请告知删除。 一、工具简介 objcopy主要用来转换目标文件的格式。 在实际开发中&#xff0c;我们会用该工具进行格式转换与内容删除。 &#xff08;1&#xff09;在链接完成后&#xff0c;将elf格式的.out文件转化为bi…...

Windows使用Stable Diffusion时遇到的各种问题和知识点整理(更新中...)

Stable Diffusion安装完成后&#xff0c;在使用过程中会出现卡死、文件不存在等问题&#xff0c;在本文中将把遇到的问题陆续记录下来&#xff0c;有兴趣的朋友可以参考。 如果要了解如何安装sd&#xff0c;则参考本文《Windows安装Stable Diffusion WebUI及问题解决记录》。如…...

MySQL workbench基本查询语句

1.查询所有字段所有记录 SELECT * FROM world.city; select 表示查询&#xff1b;“*” 称为通配符&#xff0c;也称为“标配符”。表示将表中所有的字段都查询出来&#xff1b;from 表示从哪里查询&#xff1b;world.city 表示名为world的数据库中的city表&#xff1b; 上面…...

软件测试详解

文章目录一、软件危机&#xff08;一&#xff09;概念&#xff08;二&#xff09;产生软件危机的原因&#xff08;三&#xff09;消除软件危机的途径二、软件过程模型&#xff08;一&#xff09;软件生命周期概念&#xff08;二&#xff09;软件开发模型1. 瀑布模型2. 螺旋模型…...

YOLOS学习记录

在前面&#xff0c;博主已经完成了YOLOS项目的部署与调试任务&#xff0c;并在博主自己构造的数据集上进行了实验&#xff0c;实验结果表明效果并不显著&#xff0c;其实这一点并不意外&#xff0c;反而是在情理之中。众所周知&#xff0c;Transformer一直以来作为NLP领域的带头…...

数组边遍历(for循环)边删除为什么删不干净 及三种实现删除的方法

文章目录1、为什么删不干净倒序删迭代器lambda表达式删除为什么说数组边for循环遍历边删除会出现删不干净的情况1、为什么删不干净 先写一个例子&#xff1a;可以先猜一下控制台会打印出什么内容&#xff1f; public class removeIterator {public static void main(String[]…...

环境配置之Keepass

前言很久以前&#xff0c;就有了想要一个自己密码管理器的念头。毕竟&#xff0c;即使浏览器能记住各个网站的账号密码&#xff0c;但是在登录单独客户端的时候&#xff0c;仍然要翻找密码。为了省事&#xff0c;也曾经是一个密码走天下。然后被劫持了QQ给同学发黄色小网站&…...

Java 电话号码的组合

电话号码的字母组合中等给定一个仅包含数字 2-9 的字符串&#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下&#xff08;与电话按键相同&#xff09;。注意 1 不对应任何字母。示例 1&#xff1a;输入&#xff1a;digits "23…...

MATLAB——将直接型转化为并联型和级联型

题目1(IIR)&#xff1a; 已知一个系统的传递函数为&#xff1a; H&#xff08;z&#xff09;8−4z−111z−2−2z−31−1.25z−10.75z−2−0.125z−3H&#xff08;z&#xff09;\frac{8-4z^{-1}11z^{-2}-2z^{-3}}{1-1.25z^{-1}0.75z^{-2}-0.125z^{-3}}H&#xff08;z&#xff09…...

.NET Framework .NET Core与 .NET 的区别

我们在创建C#程序时,经常会看到目标框架以下的选项,那么究竟有什么区别? 首先 .NET是一种用于构建多种应用的免费开源开发平台,可以使用多种语言,编辑器和库开发Web应用、Web API和微服务、云中的无服务器函数、云原生应用、移动应用、桌面应用、Windows WPF、Windows窗体…...

carla与ros2的自动驾驶算法-planning与control算法开发与仿真

欢迎仪式 carla与ros2的自动驾驶算法-planning与control算法开发与仿真欢迎大家来到自动驾驶Player(L5Player)的自动驾驶算法与仿真空间&#xff0c;在这个空间我们将一起完成这些事情&#xff1a; 控制算法构建基础模块并仿真调试&#xff1a;PID、LQR、Stanley 、MPC、滑膜控…...

corn表达式

简单理解corn表达式&#xff1a;在使用定时调度任务的时候&#xff0c;我们最常用的&#xff0c;就是cron表达式了。通过cron表达式来指定任务在某个时间点或者周期性的执行。cron表达式配置起来简洁方便&#xff0c;无论是Spring的Scheduled还是用Quartz框架&#xff0c;都支持…...

推荐系统中对抗性机器学习-文献综述与未来发展整理分享

对抗学习是一种机器学习技术&#xff0c;旨在通过提供欺骗性输入来欺骗模型。最常见的原因是导致机器学习模型出现故障。大多数机器学习技术旨在处理特定的问题集&#xff0c;其中从相同的统计分布&#xff08;IID&#xff09;生成训练和测试数据。当这些模型应用于现实世界时&…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu ​ 2、Hello World fn main() { println…...

uniapp 实现腾讯云IM群文件上传下载功能

UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中&#xff0c;群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS&#xff0c;在uniapp中实现&#xff1a; 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...

【安全篇】金刚不坏之身:整合 Spring Security + JWT 实现无状态认证与授权

摘要 本文是《Spring Boot 实战派》系列的第四篇。我们将直面所有 Web 应用都无法回避的核心问题&#xff1a;安全。文章将详细阐述认证&#xff08;Authentication) 与授权&#xff08;Authorization的核心概念&#xff0c;对比传统 Session-Cookie 与现代 JWT&#xff08;JS…...

鸿蒙HarmonyOS 5军旗小游戏实现指南

1. 项目概述 本军旗小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;采用DevEco Studio实现&#xff0c;包含完整的游戏逻辑和UI界面。 2. 项目结构 /src/main/java/com/example/militarychess/├── MainAbilitySlice.java // 主界面├── GameView.java // 游戏核…...