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

算法修炼Day57|647. 回文子串 ● 516.最长回文子序列

LeetCode:647. 回文子串

647. 回文子串 - 力扣(LeetCode)

1.思路

暴力思路见对应代码…

动规解法:画图推导动规公式,当前状态由左侧和左下角推出,所以首层应该采用倒序的方式,内部采用正序的方式。

2.代码实现

// 暴力解法
// 思路:两次for循环,一层定起始位置,一层定结束位置,对每个连续的子串进行遍历判断,定义区间判断子串是否为回文串的方法。
class Solution {public int countSubstrings(String s) {int count = 0;for (int i = 0; i < s.length(); i++) { // 定子串开始位置for (int j = i; j < s.length(); j++) { // 定子串结束位置if (isValid(s, i, j)) { count++; // 符合条件进行++;}}}return count;}// 判断是否为回文串private boolean isValid(String s, int start, int end) {while (start < end) {if (s.charAt(start) != s.charAt(end)) {return false;}start++;end--;}return true;}
}// 动规思路:在暴力解法的基础上,对是否为回文串进行动态判断
class Solution {public int countSubstrings(String s) {char[] ch = s.toCharArray();int len = ch.length;boolean[][] dp = new boolean[len][len];int result = 0;for (int i = len - 1; i >= 0; i--) {for (int j = i; j >= 0; j--) {if (ch[i] == ch[j]) {if (j - i <= 1) { // 表示同一个字符 或 相邻字符result++;dp[i][j] = true;} else if (dp[i + 1][j - 1]) { //间隔大于1时,判断内侧字符是否为回文串result++;dp[i][j] = true;}} }}return result;}
}

3.复杂度分析

时间复杂度:O(n^2).
空间复杂度:O(n^2).定义dp数组

LeetCode:516.最长回文子序列

516. 最长回文子序列 - 力扣(LeetCode)

1.思路

最长回文子序列,不一定连续。方格倒退一下可以获取遍历顺序为倒序,内部为正序。每个字符均为1,也即dp[i][i] = 1;

2.代码实现

class Solution {public int longestPalindromeSubseq(String s) {int len = s.length();int[][] dp = new int[len + 1][len + 1];for (int i = len - 1; i >= 0; i--) {dp[i][i] = 1;for (int j = i + 1; j < len; 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], Math.max(dp[i][j], dp[i][j - 1]));}}}return dp[0][len - 1];}
}

3.复杂度分析

时间复杂度:O(n^2).
空间复杂度:O(n^2).

相关文章:

算法修炼Day57|647. 回文子串 ● 516.最长回文子序列

LeetCode:647. 回文子串 647. 回文子串 - 力扣&#xff08;LeetCode&#xff09; 1.思路 暴力思路见对应代码… 动规解法&#xff1a;画图推导动规公式&#xff0c;当前状态由左侧和左下角推出&#xff0c;所以首层应该采用倒序的方式&#xff0c;内部采用正序的方式。 2.…...

呈现数据的精妙之道:选择合适的可视化方法

在当今数据时代&#xff0c;数据可视化已成为理解和传达信息的重要手段。然而&#xff0c;选择适合的数据可视化方法对于有效地呈现数据至关重要。不同的数据和目标需要不同的可视化方法&#xff0c;下面我们将探讨如何选择最佳的数据可视化方法来呈现数据。 1. 理解数据类型&a…...

数据结构(Java实现)-java对象的比较

元素的比较 基本类型的比较 在Java中&#xff0c;基本类型的对象可以直接比较大小。 对象比较的问题 Java中引用类型的变量不能直接按照 > 或者 < 方式进行比较 默认情况下调用的就是equal方法&#xff0c;但是该方法的比较规则是&#xff1a;没有比较引用变量引用对象的…...

Wolfram Mathematica 13 for Mac 数学计算工具

Wolfram Mathematica for Mac是一款功能强大、划时代的科学计算软件。它结合了数字和符号计算引擎、图形系统、编程语言、文本系统以及与其他应用程序的高级连接&#xff0c;在许多功能方面处于世界领先地位&#xff0c;截至2009年&#xff0c;它是使用最广泛的数学软件之一。人…...

系统架构设计高级技能 · Web架构

现在的一切都是为将来的梦想编织翅膀&#xff0c;让梦想在现实中展翅高飞。 Now everything is for the future of dream weaving wings, let the dream fly in reality. 点击进入系列文章目录 系统架构设计高级技能 Web架构 一、Web架构介绍1.1 Web架构涉及技术1.2 单台服务…...

再写CentOS7升级OpenSSL-1.0.1U

本文在CentOS7.4以及TencentOS 2.4上测试通过。 原系统自带OpenSSL 1.0.2k-fips。 编译安装方法跟之前的没啥区别。 从官网下载1.0.1u版https://www.openssl.org/source/ 使用tar解包 tar xfz openssl-1.0.1u.tar.gz 依次执行如下&#xff1a; cd openssl-1.0.1u ./con…...

HBase--技术文档--基本概念--《快速扫盲》

官网 Apache HBase – Apache HBase™ Home 阿里云hbase 云数据库HBase_大数据存储_订单风控_数据库-阿里云 云数据库 HBase-阿里云帮助中心 基本概念 HBase是一种分布式、可扩展、支持海量数据存储的NoSQL数据库。它基于Hadoop&#xff0c;采用列式存储方式&#xff0c;可…...

如何利用SFTP协议远程实现更安全的文件传输 ——【内网穿透】

&#x1f3ac; 鸽芷咕&#xff1a;个人主页 &#x1f525; 个人专栏: 《高效编程技巧》《cpolar》 ⛺️生活的理想&#xff0c;就是为了理想的生活! 文章目录 1. 安装openSSH1.1 安装SSH1.2 启动ssh 2. 安装cpolar2.1 配置termux服务 3. 远程SFTP连接配置3.1 查看生成的随机公…...

深度学习8:详解生成对抗网络原理

目录 大纲 生成随机变量 可以伪随机生成均匀随机变量 随机变量表示为操作或过程的结果 逆变换方法 生成模型 我们试图生成非常复杂的随机变量…… …所以让我们使用神经网络的变换方法作为函数&#xff01; 生成匹配网络 培养生成模型 比较基于样本的两个概率分布 …...

sql入门-多表查询

案例涉及表 ----------------------------------建表语句之前翻看之前博客文章 多表查询 -- 学生表 create table studen ( id int primary key auto_increment comment id, name varchar(50) comment 姓名, no varchar(10) comment 学号 ) comment 学生表; insert…...

软考A计划-网络工程师-必考知识点-上

点击跳转专栏>Unity3D特效百例点击跳转专栏>案例项目实战源码点击跳转专栏>游戏脚本-辅助自动化点击跳转专栏>Android控件全解手册点击跳转专栏>Scratch编程案例点击跳转>软考全系列点击跳转>蓝桥系列 &#x1f449;关于作者 专注于Android/Unity和各种游…...

kafka复习:(17)seekToBeginning的用法

从分区的开始进行消费&#xff0c;因为kafka会定期清理历史数据&#xff0c;所以分区开始的位移不一定为0。seekToBeginning只是从目前保留的数据中最小的offset进行消费 package com.cisdi.dsp.modules.metaAnalysis.rest.kafka2023;import org.apache.kafka.clients.consume…...

C# textBox1.Text=““与textBox1.Clear()的区别

一、区别 textbox.Text "" 和 textbox.Clear() 都可以用于清空文本框的内容&#xff0c;但它们之间有一些细微的区别。 textbox.Text "": 这种方式会将文本框的 Text 属性直接设置为空字符串。这样会立即清除文本框的内容&#xff0c;并将文本框显示为空…...

CnetSDK .NET OCR SDK Crack

CnetSDK .NET OCR SDK Crack CnetSDK.NET OCR库SDK是一款高度准确的.NET OCR扫描仪软件&#xff0c;用于使用手写、文本和其他符号等图像进行字符识别。它是一款.NET OCR库软件&#xff0c;使用Tesseract OCR引擎技术&#xff0c;可将字符识别准确率提高99%。通过将此.NET OCR扫…...

Python最新面试题汇总及答案

一、基础部分 1、什么是Python&#xff1f;为什么它会如此流行&#xff1f;Python是一种解释的、高级的、通用的编程语言。Python的设计理念是通过使用必要的空格与空行&#xff0c;增强代码的可读性。它之所以受欢迎&#xff0c;就是因为它具有简单易用的语法 2、为什么Pytho…...

设计模式(单例模式,工厂模式),线程池

目录 什么是设计模式? 单例模式 饿汉模式 懒汉模式 工厂模式 线程池 线程池种类 ThreadPoolExcutor的构造方法: 手动实现一个线程池 什么是设计模式? 计算机行业程序员水平层次不齐,为了让所有人都能够写出规范的代码,于是就有了设计模式,针对一些典型的场景,给出一…...

在mybatis中的mapper.xml中如何使用parameterType实现方法单个传参,对象传参,多参数传参.

在MyBatis的mapper.xml文件中&#xff0c;可以使用parameterType属性来指定方法的参数类型。parameterType属性用于指定传递给映射方法的参数类型&#xff0c;这将影响到MyBatis在映射方法执行时如何处理参数。 以下是三种不同情况下如何在mapper.xml中使用parameterType实现方…...

No120.精选前端面试题,享受每天的挑战和学习

文章目录 浏览器强制缓存和协商缓存cookie&#xff0c;localStorage、sessionStoragejs闭包&#xff0c;原型&#xff0c;原型链箭头函数和普通函数的区别promise的状态扭转 浏览器强制缓存和协商缓存 浏览器缓存是浏览器用于提高网页加载速度的一种机制。浏览器缓存分为强制缓…...

c# 访问sqlServer数据库时的连接字符串

//sql server 身份验证的场合&#xff0c; 连接字符串 private string ConnstrSqlServer "server服务器名称;uid登录名称;pwd登录密码;database数据库名称"; //windows 身份验证连接字符串 private string ConnstrWindows "server服务器名称;database数据库…...

排序算法概述

1.排序算法分类 **比较类算法排序&#xff1a;**通过比较来决定元素的时间复杂度的相对次序&#xff0c;由于其时间复杂度不能突破 O ( n l o g n ) O(nlogn) O(nlogn)&#xff0c;因此也称为非线性时间比较类算法 **非比较类算法排序&#xff1a;**不通过比较来决定元素间的…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

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 …...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...

CVPR2025重磅突破:AnomalyAny框架实现单样本生成逼真异常数据,破解视觉检测瓶颈!

本文介绍了一种名为AnomalyAny的创新框架&#xff0c;该方法利用Stable Diffusion的强大生成能力&#xff0c;仅需单个正常样本和文本描述&#xff0c;即可生成逼真且多样化的异常样本&#xff0c;有效解决了视觉异常检测中异常样本稀缺的难题&#xff0c;为工业质检、医疗影像…...