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

day57|● 647. 回文子串 ● 516.最长回文子序列

647. 回文子串

https://leetcode.cn/problems/palindromic-substrings/solution/by-lfool-2mvg/

Given a string s, return the number of palindromic substrings in it.
A string is a palindrome when it reads the same backward as forward.
A substring is a contiguous sequence of characters within the string.

dp[i][j] 表示子串 [i…j] 是否为回文子串

当我们判断 [i…j] 是否为回文子串时,只需要判断 s[i] == s[j],同时判断 [i-1…j-1] 是否为回文子串即可

需要注意有两种特殊情况:[i, i] or [i, i + 1],即:子串长度为 1(s = “a”) 或者 2 (s = “aa”)。所以加了一个条件限定 j - i < 2

状态转移方程如下:

dp[i][j] = (s[i] == s[j]) && (j - i < 2 || dp[i + 1][j - 1])

初始化默认为不匹配,false。

这里注意遍历顺序,因为dp[i][j]是由dp[i+1][j-1]来判断是不是回文子串,所以i应当从大到小,j从小到大。
所以一定要从下到上,从左到右遍历,这样保证dp[i + 1][j - 1]都是经过计算的。
在这里插入图片描述

class Solution {public int countSubstrings(String s) {boolean[][] dp = new boolean[s.length()][s.length()];int res = 0;for (int i = s.length()-1; i >= 0; i--) {for (int j = i; j < s.length(); j++) {if (s.charAt(i) == s.charAt(j)) {if (j < i+2 || dp[i+1][j-1]) {dp[i][j] = true;res++;}}}}return res;}
}
class Solution {public int countSubstrings(String s) {boolean[][] dp = new boolean[s.length()][s.length()];int res = 0;for (int j = 0; j < s.length(); j++) {for (int i = j; i >= 0; i--) {if (s.charAt(i) == s.charAt(j)) {if (j < i+2 || dp[i+1][j-1]) {dp[i][j] = true;res++;}}}}return res;}
}

中心扩散法
center expansion

private int ans = 0;
public int countSubstrings(String s) {for (int i = 0; i < s.length(); i++) {// 以单个字母为中心的情况isPalindromic(s, i, i);// 以两个字母为中心的情况isPalindromic(s, i, i + 1);}return ans;
}
private void isPalindromic(String s, int i, int j) {while (i >= 0 && j < s.length()) {if (s.charAt(i) != s.charAt(j)) return ;i--;j++;ans++;}
}

在这里插入图片描述

516.最长回文子序列

https://leetcode.cn/problems/longest-palindromic-subsequence/solution/zi-xu-lie-wen-ti-tong-yong-si-lu-zui-chang-hui-wen/

Given a string s, find the longest palindromic subsequence’s length in s.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Input: s = “bbbab”
Output: 4
Explanation: One possible longest palindromic subsequence is “bbbb”.

注意区分子串和子序列:
回文子串是要连续的,回文子序列可不是连续的!

在子串 s[i…j] 中,最长回文子序列的长度为 dp[i][j]。

求dp[i][j], 假设已知子问题dp[i+1][j-1]的值,
只要s[i] = s[j],那么它俩加上 s[i+1…j-1] 中的最长回文子序列就是 s[i…j] 的最长回文子序列。
如果s[i]与s[j]不相同,说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度,
或者说如果 s[i] ≠ s[j],则 s[i] 和 s[j] 不可能同时作为同一个回文子序列的首尾,
那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。
在这里插入图片描述
遍历顺序:必须从下到上,从左到右
在这里插入图片描述

class Solution {public int longestPalindromeSubseq(String s) {int[][] dp = new int[s.length()][s.length()];for (int i = 0; i < s.length(); i++) {dp[i][i] = 1;}for (int i = s.length()-1; i >= 0; i--) {for (int j = i+1; j < s.length(); j++) {if (s.charAt(i) == s.charAt(j)) {dp[i][j] = dp[i+1][j-1] + 2;} else {dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);}}}return dp[0][s.length()-1];}
}
class Solution {public int longestPalindromeSubseq(String s) {int[][] dp = new int[s.length()][s.length()];for (int i = s.length()-1; i >= 0; i--) {for (int j = i; j < s.length(); j++) {if (s.charAt(i) == s.charAt(j)) {if (i == j){dp[i][j] = 1;} else {dp[i][j] = dp[i+1][j-1] + 2;}} else {dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);}}}return dp[0][s.length()-1];}
}

相关文章:

day57|● 647. 回文子串 ● 516.最长回文子序列

647. 回文子串 https://leetcode.cn/problems/palindromic-substrings/solution/by-lfool-2mvg/ Given a string s, return the number of palindromic substrings in it. A string is a palindrome when it reads the same backward as forward. A substring is a contiguous…...

docker compose.yml学习

docker compose 安装docker-compose sudo curl -L "https://github.com/docker/compose/releases/download/v2.2.2/docker-compose-$(uname -s)-$(uname -m)" -o /usr/local/bin/docker-composechmod x /usr/local/bin/docker-composeln -s /usr/local/bin/docker-…...

【业务功能篇55】Springboot+easyPOI 导入导出

Apache POI是Apache软件基金会的开源项目&#xff0c;POI提供API给Java程序对Microsoft Office格式档案读和写的功能。 Apache POI 代码实现复杂&#xff0c;学习成本较高。 Easypoi 功能如同名字easy,主打的功能就是容易,让一个没见接触过poi的人员 就可以方便的写出Excel导出…...

对顶堆算法

对顶堆可以动态维护一个序列上的第k大的数&#xff0c;由一个大根堆和一个小根堆组成&#xff0c; 小根堆维护前k大的数(包含第k个)大根堆维护比第k个数小的数 [CSP-J2020] 直播获奖 题目描述 NOI2130 即将举行。为了增加观赏性&#xff0c;CCF 决定逐一评出每个选手的成绩&a…...

node.js的优点

提示&#xff1a;node.js的优点 文章目录 一、什么是node.js二、node.js的特性 一、什么是node.js 提示&#xff1a;什么是node.js? Node.js发布于2009年5月&#xff0c;由Ryan Dahl开发&#xff0c;是一个基于ChromeV8引擎的JavaScript运行环境&#xff0c;使用了一个事件驱…...

golang编译跨平台

golang可以在windows上编译出linux、MacOS等系统上的程序。 go编译器windows下可变翼linux程序&#xff0c;例如&#xff0c;GOARCHamd64 和 GOOSlinux 可以用于编译 64 位的 Linux 平台上的可执行文件。&#xff1a; set GOARCHamd64 set GOOSlinux go build main.go通过设置…...

关于Spring的bean的相关注解以及其简单使用方法

一、前置工作 第一步&#xff1a;创建一个maven项目 第二步&#xff1a;在resource中创建一个名字叫做spring-config.xml的文件&#xff0c;并把以下代码复制粘贴 <?xml version"1.0" encoding"UTF-8"?> <beans xmlns"http://www.sprin…...

【计算机视觉】BLIP:源代码示例demo(含源代码)

文章目录 一、Image Captioning二、VQA三、Feature Extraction四、Image-Text Matching 一、Image Captioning 首先配置代码&#xff1a; import sys if google.colab in sys.modules:print(Running in Colab.)!pip3 install transformers4.15.0 timm0.4.12 fairscale0.4.4!g…...

TWILIGHT靶场详解

TWILIGHT靶场详解 下载地址&#xff1a;https://download.vulnhub.com/sunset/twilight.7z 这是一个比较简单的靶场&#xff0c;拿到IP后我们扫描发现开启了超级多的端口 其实这些端口一点用都没有&#xff0c;在我的方法中 但是也有不同的方法可以拿权限&#xff0c;就需要…...

【案例】--GPT衍生应用案例

目录 一、前言二、GPT实现智能问答架构2.1、基本的GPT实现智能问答架构2.2、可应用的GPT实现智能问答架构1、语义转换2、相似度关键字矩阵3、ES中搜索相似度关键字矩阵三、后续一、前言 GPT,全称Generative Pre-trained Transformer ,中文名可译作生成式预训练Transformer。…...

Sip网络音频对讲广播模块, sip网络寻呼话筒音频模块

Sip网络音频对讲广播模块&#xff0c; sip网络寻呼话筒音频模块 一、模块介绍 SV-2101VP和 SV-2103VP网络音频对讲广播模块 是一款通用的独立SIP音频功能模块&#xff0c;可以轻松地嵌入到OEM产品中。该模块对来自网络的SIP协议及RTP音频流进行编解码。 该模块支持多种网络协议…...

leetcode1219. 黄金矿工(java)

黄金矿工 leetcode1219. 黄金矿工题目描述回溯算法代码 回溯算法 leetcode1219. 黄金矿工 难度: 中等 eetcode 1219 黄金矿工 题目描述 你要开发一座金矿&#xff0c;地质勘测学家已经探明了这座金矿中的资源分布&#xff0c;并用大小为 m * n 的网格 grid 进行了标注。每个单元…...

Svelte框架入门

关键词 前端框架、编译器、响应式、模板 介绍 Svelte /svelt/ adj. 苗条的&#xff1b;线条清晰的&#xff1b;和蔼的 Svelte是一个前端组件框架&#xff0c;就像它的英文名字一样&#xff0c;Svelte的目标是打造一个更高性能的响应性前端框架。 Svelte类似于React和Vue框架&am…...

在linux中进行arm交叉编译体验tiny6410裸机程序开发流程

在某鱼上找了一个友善之臂的Tiny6410开发板用来体验一下嵌入式开发。这次先体验一下裸机程序的开发流程&#xff0c;由于这个开发板比较老旧了&#xff0c;官方文档有很多过期的内容&#xff0c;所以记录一下整个过程。 1. 交叉编译器安装 按照光盘A中的文档《04- Tiny6410 L…...

SpringBoot实战(二十三)集成 SkyWalking

目录 一、简介二、拉取镜像并部署1.拉取镜像2.运行skywalking-oap容器3.运行skywalking-ui容器4.访问页面 三、下载解压 agent1.下载2.解压 四、创建 skywalking-demo 项目1.Maven依赖2.application.yml3.DemoController.java 五、构建启动脚本1.startup.bat2.执行启动脚本3.发…...

深度学习实践——卷积神经网络实践:裂缝识别

深度学习实践——卷积神经网络实践&#xff1a;裂缝识别 系列实验 深度学习实践——卷积神经网络实践&#xff1a;裂缝识别 深度学习实践——循环神经网络实践 深度学习实践——模型部署优化实践 深度学习实践——模型推理优化练习 深度学习实践——卷积神经网络实践&#xff…...

linux | vscode | makefile | c++编译和调试

简单介绍环境&#xff1a; vscode 、centos、 gcc、g、makefile 简单来说就是&#xff0c;写好项目然后再自己写makefile脚本实现编译。所以看这篇博客的用户需要了解gcc编译的一些常用命令以及makefile语法。在网上看了很多教程&#xff0c;以及官网也看了很多次&#xff0c;最…...

Spring | Bean 作用域和生命周期

一、通过一个案例来看 Bean 作用域的问题 Spring 是用来读取和存储 Bean&#xff0c;因此在 Spring 中 Bean 是最核心的操作资源&#xff0c;所以接下来我们深入学习⼀下 Bean 对象 假设现在有⼀个公共的 Bean&#xff0c;提供给 A 用户和 B 用户使用&#xff0c;然而在使用的…...

培训(c++题解)

题目描述 某培训机构的学员有如下信息&#xff1a; 姓名&#xff08;字符串&#xff09;年龄&#xff08;周岁&#xff0c;整数&#xff09;去年 NOIP 成绩&#xff08;整数&#xff0c;且保证是 5 的倍数&#xff09; 经过为期一年的培训&#xff0c;所有同学的成绩都有所提…...

ansible-playbook编写 lnmp 剧本

ansible-playbook编写 lnmp 剧本 vim /opt/lnmp/lnmp.yaml执行剧本 ansible-playbook lnmp.yaml...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...

认识CMake并使用CMake构建自己的第一个项目

1.CMake的作用和优势 跨平台支持&#xff1a;CMake支持多种操作系统和编译器&#xff0c;使用同一份构建配置可以在不同的环境中使用 简化配置&#xff1a;通过CMakeLists.txt文件&#xff0c;用户可以定义项目结构、依赖项、编译选项等&#xff0c;无需手动编写复杂的构建脚本…...

微服务通信安全:深入解析mTLS的原理与实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言&#xff1a;微服务时代的通信安全挑战 随着云原生和微服务架构的普及&#xff0c;服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...

【大模型】RankRAG:基于大模型的上下文排序与检索增强生成的统一框架

文章目录 A 论文出处B 背景B.1 背景介绍B.2 问题提出B.3 创新点 C 模型结构C.1 指令微调阶段C.2 排名与生成的总和指令微调阶段C.3 RankRAG推理&#xff1a;检索-重排-生成 D 实验设计E 个人总结 A 论文出处 论文题目&#xff1a;RankRAG&#xff1a;Unifying Context Ranking…...

C++ Saucer 编写Windows桌面应用

文章目录 一、背景二、Saucer 简介核心特性典型应用场景 三、生成自己的项目四、以Win32项目方式构建Win32项目禁用最大化按钮 五、总结 一、背景 使用Saucer框架&#xff0c;开发Windows桌面应用&#xff0c;把一个html页面作为GUI设计放到Saucer里&#xff0c;隐藏掉运行时弹…...