算法修炼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. 回文子串 - 力扣(LeetCode) 1.思路 暴力思路见对应代码… 动规解法:画图推导动规公式,当前状态由左侧和左下角推出,所以首层应该采用倒序的方式,内部采用正序的方式。 2.…...
呈现数据的精妙之道:选择合适的可视化方法
在当今数据时代,数据可视化已成为理解和传达信息的重要手段。然而,选择适合的数据可视化方法对于有效地呈现数据至关重要。不同的数据和目标需要不同的可视化方法,下面我们将探讨如何选择最佳的数据可视化方法来呈现数据。 1. 理解数据类型&a…...
数据结构(Java实现)-java对象的比较
元素的比较 基本类型的比较 在Java中,基本类型的对象可以直接比较大小。 对象比较的问题 Java中引用类型的变量不能直接按照 > 或者 < 方式进行比较 默认情况下调用的就是equal方法,但是该方法的比较规则是:没有比较引用变量引用对象的…...
Wolfram Mathematica 13 for Mac 数学计算工具
Wolfram Mathematica for Mac是一款功能强大、划时代的科学计算软件。它结合了数字和符号计算引擎、图形系统、编程语言、文本系统以及与其他应用程序的高级连接,在许多功能方面处于世界领先地位,截至2009年,它是使用最广泛的数学软件之一。人…...
系统架构设计高级技能 · Web架构
现在的一切都是为将来的梦想编织翅膀,让梦想在现实中展翅高飞。 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 依次执行如下: cd openssl-1.0.1u ./con…...
HBase--技术文档--基本概念--《快速扫盲》
官网 Apache HBase – Apache HBase™ Home 阿里云hbase 云数据库HBase_大数据存储_订单风控_数据库-阿里云 云数据库 HBase-阿里云帮助中心 基本概念 HBase是一种分布式、可扩展、支持海量数据存储的NoSQL数据库。它基于Hadoop,采用列式存储方式,可…...
如何利用SFTP协议远程实现更安全的文件传输 ——【内网穿透】
🎬 鸽芷咕:个人主页 🔥 个人专栏: 《高效编程技巧》《cpolar》 ⛺️生活的理想,就是为了理想的生活! 文章目录 1. 安装openSSH1.1 安装SSH1.2 启动ssh 2. 安装cpolar2.1 配置termux服务 3. 远程SFTP连接配置3.1 查看生成的随机公…...
深度学习8:详解生成对抗网络原理
目录 大纲 生成随机变量 可以伪随机生成均匀随机变量 随机变量表示为操作或过程的结果 逆变换方法 生成模型 我们试图生成非常复杂的随机变量…… …所以让我们使用神经网络的变换方法作为函数! 生成匹配网络 培养生成模型 比较基于样本的两个概率分布 …...
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编程案例点击跳转>软考全系列点击跳转>蓝桥系列 👉关于作者 专注于Android/Unity和各种游…...
kafka复习:(17)seekToBeginning的用法
从分区的开始进行消费,因为kafka会定期清理历史数据,所以分区开始的位移不一定为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() 都可以用于清空文本框的内容,但它们之间有一些细微的区别。 textbox.Text "": 这种方式会将文本框的 Text 属性直接设置为空字符串。这样会立即清除文本框的内容,并将文本框显示为空…...
CnetSDK .NET OCR SDK Crack
CnetSDK .NET OCR SDK Crack CnetSDK.NET OCR库SDK是一款高度准确的.NET OCR扫描仪软件,用于使用手写、文本和其他符号等图像进行字符识别。它是一款.NET OCR库软件,使用Tesseract OCR引擎技术,可将字符识别准确率提高99%。通过将此.NET OCR扫…...
Python最新面试题汇总及答案
一、基础部分 1、什么是Python?为什么它会如此流行?Python是一种解释的、高级的、通用的编程语言。Python的设计理念是通过使用必要的空格与空行,增强代码的可读性。它之所以受欢迎,就是因为它具有简单易用的语法 2、为什么Pytho…...
设计模式(单例模式,工厂模式),线程池
目录 什么是设计模式? 单例模式 饿汉模式 懒汉模式 工厂模式 线程池 线程池种类 ThreadPoolExcutor的构造方法: 手动实现一个线程池 什么是设计模式? 计算机行业程序员水平层次不齐,为了让所有人都能够写出规范的代码,于是就有了设计模式,针对一些典型的场景,给出一…...
在mybatis中的mapper.xml中如何使用parameterType实现方法单个传参,对象传参,多参数传参.
在MyBatis的mapper.xml文件中,可以使用parameterType属性来指定方法的参数类型。parameterType属性用于指定传递给映射方法的参数类型,这将影响到MyBatis在映射方法执行时如何处理参数。 以下是三种不同情况下如何在mapper.xml中使用parameterType实现方…...
No120.精选前端面试题,享受每天的挑战和学习
文章目录 浏览器强制缓存和协商缓存cookie,localStorage、sessionStoragejs闭包,原型,原型链箭头函数和普通函数的区别promise的状态扭转 浏览器强制缓存和协商缓存 浏览器缓存是浏览器用于提高网页加载速度的一种机制。浏览器缓存分为强制缓…...
c# 访问sqlServer数据库时的连接字符串
//sql server 身份验证的场合, 连接字符串 private string ConnstrSqlServer "server服务器名称;uid登录名称;pwd登录密码;database数据库名称"; //windows 身份验证连接字符串 private string ConnstrWindows "server服务器名称;database数据库…...
排序算法概述
1.排序算法分类 **比较类算法排序:**通过比较来决定元素的时间复杂度的相对次序,由于其时间复杂度不能突破 O ( n l o g n ) O(nlogn) O(nlogn),因此也称为非线性时间比较类算法 **非比较类算法排序:**不通过比较来决定元素间的…...
JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
Opencv中的addweighted函数
一.addweighted函数作用 addweighted()是OpenCV库中用于图像处理的函数,主要功能是将两个输入图像(尺寸和类型相同)按照指定的权重进行加权叠加(图像融合),并添加一个标量值&#x…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
MMaDA: Multimodal Large Diffusion Language Models
CODE : https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA,它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)
Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败,具体原因是客户端发送了密码认证请求,但Redis服务器未设置密码 1.为Redis设置密码(匹配客户端配置) 步骤: 1).修…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
