*算法训练(leetcode)第四十天 | 647. 回文子串、516. 最长回文子序列

刷题记录

  • *647. 回文子串
  • *516. 最长回文子序列

*647. 回文子串

leetcode题目地址

dp[i][j]存储 i-j 的子串是否是回文串。使用额外的计数器对回文串个数进行记录。

单个字符本身就是回文子串。当子串长度大于1时,两侧的字符相同,则需要判断中间的子串是否是回文串。

时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( n ) O(n) O(n)

// c++
class Solution {
public:int countSubstrings(string s) {vector<vector<bool>> dp(s.size()+1, vector<bool>(s.size()+1, false));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]) {result++;dp[i][j] = true;}}}}return result;}
};

*516. 最长回文子序列

leetcode题目地址

求的是最长回文子序列而不是子串,因此不需要连续。
dp[i][j]存储的是字符串 s 中 i-j 之间的最长回文子序列长度。

  • 当s[i] != s[j]时,dp[i][j] = max(dp[i][j-1], dp[i+1][j]);
  • 当s[i] == s[j]时,有两种情况:
    • j-i <= 1,即j和i指向同一个字符或相邻的两个字符,则最长子序列长度为1(同一字符)或2(相邻两个字符):
      • dp[i][j] = j - i + 1;
    • j-i > 1,则需要查看中间子串的最长回文子序列的长度,用中间串的最长回文子序列的长度加上当前两个字符(i和j指向的字符)
      • dp[i][j] = dp[i+1][j-i] + 2;

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

// c++
class Solution {
public:int longestPalindromeSubseq(string s) {vector<vector<int>> dp(s.size()+1, vector<int>(s.size()+1, 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]) dp[i][j] = max(dp[i][j-1], dp[i+1][j]);else{if(j-i<=1) dp[i][j] = j-i+1;else dp[i][j] = dp[i+1][j-1]+2;}if(dp[i][j]>result) result = dp[i][j];}/*// 输出dpfor(int j=0; j<s.size(); j++) cout<<dp[i][j]<<" ";cout<<endl;*/}return result;}
};

动态规划系列完结

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/393671.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基于springboot+vue+uniapp的“口腔助手”小程序

开发语言&#xff1a;Java框架&#xff1a;springbootuniappJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包&#…

Python开发: 飞机大战 小游戏

玩法 你可以控制飞机左右移动&#xff0c;躲避敌机子弹&#xff0c;同时发射自己的炮弹&#xff0c;将敌人击落&#xff01; 部署方案&#xff1a; 1、代码如下图&#xff1b; 2、将代码保存到一个python中&#xff0c;比如planeFight.py&#xff1b; 3、在你的电脑中安装p…

为什么需要云仓?

云仓&#xff0c;即云端仓储管理&#xff0c;是指通过互联网技术整合和管理仓储资源&#xff0c;实现高效、低成本的库存管理和物流服务。随着电子商务的发展和企业供应链全球化的加剧&#xff0c;云仓成为现代企业管理的一种重要手段。 1、云仓可以显著提高仓储管理效率&#…

算法测试.

一.CodeForces 1829A 题意&#xff1a; 题目意思就是给你t个字符串&#xff0c;让你找出每个串与codeforces这个串有多少不同的字母&#xff1b; 题解&#xff1a; 定义一个变量循环比较字符串&#xff0c;不相同计数即可&#xff1b; 代码&#xff1a; #include <iost…

SQL二次注入

目录 1.什么是二次注入&#xff1f; 2.二次注入过程 2.1寻找注入点 2.2注册admin#用户 2.3修改密码 1.什么是二次注入&#xff1f; 当用户提交的恶意数据被存入数据库后&#xff0c;因为被过滤函数过滤掉了&#xff0c;所以无法生效&#xff0c;但应用程序在从数据库中拿…

TCP Analysis Flags 之 TCP Window Full

前言 默认情况下&#xff0c;Wireshark 的 TCP 解析器会跟踪每个 TCP 会话的状态&#xff0c;并在检测到问题或潜在问题时提供额外的信息。在第一次打开捕获文件时&#xff0c;会对每个 TCP 数据包进行一次分析&#xff0c;数据包按照它们在数据包列表中出现的顺序进行处理。可…

supermap制作发布二三维地图服务

一、下载安装 软件版本&#xff1a; SuperMap iDesktopX 11i(2023) SP1 for Windows SuperMap iServer 11i(2023) SP1 for Windows 下载地址&#xff1a; http://support.supermap.com.cn/DownloadCenter/ProductPlatform.aspx 二、运行 服务端&#xff1a;双击iserver的…

C# Unity 面向对象补全计划 设计者模式 之 单例模式

本文仅作学习笔记与交流&#xff0c;不作任何商业用途&#xff0c;作者能力有限&#xff0c;如有不足还请斧正 本系列作为七大原则和设计模式的进阶知识&#xff0c;看不懂没关系 了解我的专栏C#面向对象与进阶:http://t.csdnimg.cn/mIitr&#xff0c;尤其是关于类的那篇文章即…

Python(模块---pandas+matplotlib+pyecharts)

import pandas as pd import matplotlib.pyplot as plt dfpd.read_excel(简易数据.xlsx) # print(df) plt.rcParams[font.sans-serif][SimHei] #设置画布的大小 plt.figure(figsize(10,6)) labelsdf[电影中文名] ydf[国籍] # print(labels) # print(y)# import pandas as pd im…

在Stable Diffusion中驱动Tesla P40

一、安装P40显卡 在前面我的“在win10电脑上搭建python环境下的本地AI绘画工具Stable Diffusion”博文中&#xff0c;Stable Diffusion的运行完全依赖CPU和内存&#xff0c;因此每生成一次图片&#xff0c;需几小时之多&#xff0c;我常是在临下班时开始生成&#xff0c;到第二…

Go语言标准库中的双向链表的基本用法

什么是二分查找区间&#xff1f; 什么是链表&#xff1f; 链表节点的代码实现&#xff1a; 链表的遍历&#xff1a; 链表如何插入元素&#xff1f; go语言标准库的链表&#xff1a; 练习代码&#xff1a; package mainimport ("container/list""fm…

连接一切:Web3如何重塑物联网的未来

传统物联网的挑战 物联网&#xff08;IoT&#xff09;正在迅速改变我们的世界&#xff0c;通过将各种设备连接到互联网&#xff0c;它使得设备能够相互交流&#xff0c;提供智能化的服务和解决方案。然而&#xff0c;随着物联网的迅猛发展&#xff0c;安全性、隐私保护和设备互…

React 知识点(二)

文章目录 一、React 组件二、React 组件通信 - 父子通信三、React 组件通信 - 子父通信四、React 组件通信 - 兄弟通信五、React 组件通信 - 跨组件通信(祖先)六、结合组件通信案例七、props-children 属性八、props-类型校验九、React 生命周期十、setState 扩展 一、React 组…

MySQL的简单介绍

文章目录 数据库关系型数据库非关系型数据”数据库的概念和用途MySQL数据库服务器、数据库和表的关系数据库的创建和删除表创建表修改常见的数据类型和约束字符串类型日期和时间类型PRIMARY KEY使用AUTO_INCREMENT使用UNIQUE使用FOREIGN KEY使用 SQL语言基础SQL语言简介SQL分类…

C++入门基础知识

在之前我们学习了C语言和初阶数据结构的相关知识&#xff0c;现在已经有了一定的代码能力和对数据结构也有了基础的认识&#xff0c;接下来我们将进入到新的专题当中&#xff0c;这个专题就是C。在C中我们需要花费更大的精力和更长的时间去学习这门建立在C语言基础之上的计算机…

接了一个2000块的小活,大家进来看看值不值,附源码

如题&#xff0c;上周的一天&#xff0c;朋友圈的一个旧友找到了我&#xff0c;说让我帮他开发一个小工具&#xff0c;虽然活不大&#xff0c;但没个几年的全栈经验还不一定能接下来&#xff0c;因为麻雀虽小&#xff0c;涉及的内容可不少&#xff1a; 需求分析 原型设计 详细…

LSPatch制作内置模块应用软件无需root 教你制作内置应用

前言 LSPatch功能非常强大&#xff0c;它是一款基于LSPosed核心的免Root Xposed框架软件。这意味着用户无需进行手机root操作&#xff0c;即可轻松植入内置Xposed模块&#xff0c;享受更多定制化的功能和体验&#xff0c;比如微某内置模块版等&#xff0c;这为那些不想root手机…

vue项目部署在子路径中前端配置

vue.config.JS router/index.js或者是man.js

【开发踩坑】windows查看jvm gc信息

windows查看jvm gc信息 EZ 找出java进程PID 控制面板----搜索任务管理器---- 任务管理器----搜索 java----详细信息 这里PID是4856 cmd jstat gc面板 reference&#xff1a; jstat命令