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

leetcode 647. 回文子串、516. 最长回文子序列

647. 回文子串

给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。

示例 1:

输入:s = "abc"
输出:3
解释:三个回文子串: "a", "b", "c"

示例 2:

输入:s = "aaa"
输出:6
解释:6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
思路:

        /*

            dp[i][j]表示i到j的字符串是否是回文串

            i==j   dp[i][j] = true;

            j-i==1 dp[i][j] = true;

            j-i>1  if(dp[i+1][j-1] = true) dp[i][j] = true;

            初始化为false

            遍历顺序 从底往上,从左到右

            打印dp数组

        */

代码:
class Solution {
public:int countSubstrings(string s) {/*dp[i][j]表示i到j的字符串是否是回文串i==j   dp[i][j] = true;j-i==1 dp[i][j] = true;j-i>1  if(dp[i+1][j-1] = true) dp[i][j] = true;初始化为false遍历顺序 从底往上,从左到右打印dp数组*/vector<vector<int>>dp(s.size(),vector<int>(s.size(),0));int result = 0;for(int i = s.size()-1;i>=0;i--){for(int j = i;j<s.size();j++){if(s[i]==s[j]){if(j-i<=1){ dp[i][j] = true;result++;}else{if(dp[i+1][j-1]){dp[i][j] = true;result++;}}}}}return result;}
};

516. 最长回文子序列

给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。

子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。

示例 1:

输入:s = "bbbab"
输出:4
解释:一个可能的最长回文子序列为 "bbbb" 。

示例 2:

输入:s = "cbbd"
输出:2
解释:一个可能的最长回文子序列为 "bb" 。

思路:

        /*

            dp[i][j]表示从i到j的最长回文子序列长度

            s[i]==s[j]

            dp[i][j] = dp[i+1][j-1]+2;

            s[i]!= s[j]

            dp[i][j] = max(dp[i][j-1],dp[i+1][j]);

            初始化为1

            遍历顺序 从左到右,从下到上

            打印dp数组

        */

代码:
class Solution {
public:int longestPalindromeSubseq(string s) {/*dp[i][j]表示从i到j的最长回文子序列长度s[i]==s[j]dp[i][j] = dp[i+1][j-1]+2;s[i]!= s[j]dp[i][j] = max(dp[i][j-1],dp[i+1][j]);初始化为1遍历顺序 从左到右,从下到上打印dp数组*/vector<vector<int>>dp(s.size(),vector<int>(s.size(),0));for(int i = 0;i<s.size();i++) dp[i][i] = 1;for(int i = s.size()-1;i>=0;i--){for(int j = i+1;j<s.size();j++){if(s[i]==s[j]) dp[i][j] = dp[i+1][j-1]+2;elsedp[i][j] = max(dp[i][j-1],dp[i+1][j]);}}return dp[0][s.size()-1];}
};

还有很多瑕疵,还需继续坚持!

相关文章:

leetcode 647. 回文子串、516. 最长回文子序列

647. 回文子串 给你一个字符串 s &#xff0c;请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串&#xff0c;即使是由相同的字符组成&#…...

Vue Router 刷新当前页面

Vue项目, 在实际工作中, 有些时候需要在 加载完某些数据之后对当前页面进行刷新, 以期 onMounted 等生命周期函数, 或者 数据重新加载. 总之是期望页面可以重新加载一次. 目前总结有三种途径可实现以上需求: 一, reload 直接刷新页面 window.location.reload(); $router.go(…...

lstm 回归实战、 分类demo

预备知识 lstm 参数 输入、输出格式 nn.LSTM(input_dim&#xff0c;hidden_dim,num_layers); imput_dim 特征数 input:(样本数、seq, features_num) h0,c0 (num_layers&#xff0c;seq, hidden_num) output: (样本数、seq, hidden_dim) 再加一个全连接层&#xff0c;将 outpu…...

实践DDD模拟电商系统总结

目录 一、事件风暴 二、系统用例 三、领域上下文 四、架构设计 &#xff08;一&#xff09;六边形架构 &#xff08;二&#xff09;系统分层 五、系统实现 &#xff08;一&#xff09;项目结构 &#xff08;二&#xff09;提交订单功能实现 &#xff08;三&#xff0…...

`SQL`编写判断是否为工作日函数编写

SQL编写判断是否为工作日函数编写 最近的自己在写一些功能,遇到了对于工作日的判断,我就看了看sql,来吧!~(最近就是好疲惫) 我们一起看看(针对ORACLE) 1.声明: CREATE OR REPLACE PACKAGE GZYW_2109_1214.PKG_FUN_GETDAY_HDAY AS /** * 通过节假日代码获取指定的日期[查找基…...

零信任身份管理平台,构建下一代网络安全体系

随着数字化时代的到来&#xff0c;网络安全已成为企业和组织面临的一项重要挑战。传统的网络安全方法已经无法满足不断演变的威胁和技术环境。近期&#xff0c;中国信息通信研究院&#xff08;简称“中国信通院”&#xff09;发布了《零信任发展研究报告&#xff08; 2023 年&a…...

《数据结构、算法与应用C++语言描述》使用C++语言实现链表队列

《数据结构、算法与应用C语言描述》使用C语言实现链表队列 定义 队列的定义 队列&#xff08;queue&#xff09;是一个线性表&#xff0c;其插入和删除操作分别在表的不同端进行。插入元素的那一端称为队尾&#xff08;back或rear&#xff09;&#xff0c;删除元素的那一端称…...

RT-Thread学习笔记(四):RT-Thread Studio工具使用

RT-Thread Studio工具使用 官网详细资料实用操作1. 查看 RT-Thread RTOS API 文档2.打开已创建的工程3.添加头文件路径4. 如何设置生成hex文件5.新建工程 官网详细资料 RT-Thread Studio 用户手册 实用操作 1. 查看 RT-Thread RTOS API 文档 2.打开已创建的工程 如果打开项目…...

【计算机网络笔记】OSI参考模型中端-端层(传输层、会话层、表示层、应用层)功能介绍

系列文章目录 什么是计算机网络&#xff1f; 什么是网络协议&#xff1f; 计算机网络的结构 数据交换之电路交换 数据交换之报文交换和分组交换 分组交换 vs 电路交换 计算机网络性能&#xff08;1&#xff09;——速率、带宽、延迟 计算机网络性能&#xff08;2&#xff09;…...

RabbitMQ高级知识点

以下是一些 RabbitMQ 的高级知识点&#xff1a; 1. Exchange&#xff1a; RabbitMQ 中的 Exchange 是消息路由器&#xff0c;用来接收消息并且转发到对应的 Queue 中。Exchange 有四种类型&#xff1a;Direct Exchange、Fanout Exchange、Topic Exchange 和 Headers Exchange。…...

Node直接执行ts文件

Node直接执行ts文件 1、常规流程 node 执行 【ts 文件】 流程&#xff1a; 1、编写ts代码 2、编译成js代码 [命令如 &#xff1a;tsc xx.ts] 3、执行js代码 [node xx.js]2、直接执行 想要直接执行 ts 文件&#xff0c;需要安装如下依赖工具。 执行如下命令&#xff1a; # 安装…...

log4j的级别的说明

一 log4j的级别 1.1 级别类型 TRACE 》DEBUG 》 INFO 》 WARN 》 ERROR 》 FATAL 级别高低顺序为&#xff1a; trace级别最低 &#xff0c;Fatal级别最高。由左到右&#xff0c;从低到高 1.2 包含范围 原则&#xff1a; 本级别包含本级别以及大于本级别的内容&#xff0c;…...

头脑风暴之约瑟夫环问题

一 问题的引入 约瑟夫问题的源头完全可以命名为“自杀游戏”。本着和谐友爱和追求本质的目的&#xff0c;可以把问题描述如下&#xff1a; 现有n个人围成一桌坐下&#xff0c;编号从1到n&#xff0c;从编号为1的人开始报数。报数也从1开始&#xff0c;报到m人离席&#xff0c…...

【四:Spring整合Junit】

目录 相同点不同点1、导入依赖增加2、编写的位置不同。。路径一定要与实现类一致 相同点 前面都一样和Spring整合mybatis&#xff08;基于注解形式&#xff09;一样Spring整合Mybatis 不同点 1、导入依赖增加 <!-- 单元测试 --><dependency><groupId>junit&…...

openHarmony UI开发

常用组件和布局方式 组件 ArkUI有丰富的内置组件&#xff0c;包括文本、按钮、图片、进度条、输入框、单选框、多选框等。和布局一样&#xff0c;我们也可以将基础组件组合起来&#xff0c;形成自定义组件。 按钮&#xff1a; Button(Ok, { type: ButtonType.Normal, stateEf…...

Qt 目录操作(QDir 类)及展示系统文件实战 QFilelnfo 类介绍和获取文件属性项目实战

一、目录操作(QDir 类) QDir 类提供访问系统目录结构 QDir 类提供对目录结构及其内容的访问。QDir 用于操作路径名、访问有关路径和文件的信息以及操作底层文件系统。它还可以用于访问 Qt 的资源系统 Qt 使用“/”作为通用目录分隔符&#xff0c;与“/”在 URL 中用作路径分…...

2023-9-12 阿里健康2024秋招后端开发-体检及泛医疗二面

1 自我介绍 2 快手实习 2.1 说说你在实习期间遇到的挑战、收获 &#xff08;1&#xff09;在设计模式的应用能力上&#xff0c;有了很大的提高&#xff0c;使用模板设计模式&#xff0c;架构实例反向同步到架构定义&#xff0c;使用了策略模式 &#xff08;2&#xff09; …...

Qt扫盲-QBrush理论使用总结

Q 理论使用总结 一、概述1. 填充模式2. 笔刷颜色3. 纹理 二、 Qt::GlobalColor 一、概述 QBrush类定义了由 QPainter 绘制的形状的填充模式。画笔有样式、颜色、渐变和纹理。 brush style() 使用Qt::BrushStyle 枚举定义填充模式。默认的笔刷样式是 Qt::NoBrush(取决于你如何…...

互联网Java工程师面试题·Java 面试篇·第三弹

目录 39、JRE、JDK、JVM 及 JIT 之间有什么不同&#xff1f; 40、解释 Java 堆空间及 GC&#xff1f; 41、你能保证 GC 执行吗&#xff1f; 42、怎么获取 Java 程序使用的内存&#xff1f;堆使用的百分比&#xff1f; 43、Java 中堆和栈有什么区别&#xff1f; 44、“ab”…...

如何使用VSCode将iPad Pro转化为功能强大的开发工具?

文章目录 前言1. 本地环境配置2. 内网穿透2.1 安装cpolar内网穿透(支持一键自动安装脚本)2.2 创建HTTP隧道 3. 测试远程访问4. 配置固定二级子域名4.1 保留二级子域名4.2 配置二级子域名 5. 测试使用固定二级子域名远程访问6. iPad通过软件远程vscode6.1 创建TCP隧道 7. ipad远…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; 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…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...