笔记:代码随想录算法训练营day46:LeetCode647. 回文子串\516.最长回文子序列

学习资料:代码随想录

647. 回文子串

力扣题目链接

其实个人感觉这里的动规也是一个双指针的方法

// 定义:dp[i][j]表示区间范围为[i,j]左闭右闭的子串是否为回文子串,布尔类型
// 递推公式:如过s[i]==s[j],那么i,j包括两个数或1个数的情况是回文子串,如果包含超过两个数,那么dp[i+1][j-1]是true的话,也返回true,当然不相等就直接false了
// 初始化:可以先都初始化为false
// 遍历顺序:看递推公式
// 打印

// 定义:dp[i][j]表示区间范围为[i,j]左闭右闭的子串是否为回文子串,布尔类型
// 递推公式:如过s[i]==s[j],那么i,j包括两个数或1个数的情况是回文子串,如果包含超过两个数,那么dp[i+1][j-1]是true的话,也返回true,当然不相等就直接false了
// 初始化:可以先都初始化为false
// 遍历顺序:看递推公式
// 打印
class Solution {
public:int countSubstrings(string s) {vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));int result = 0;              //记录一下,要不最后不知道返回啥 for(int i=s.size();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;}
};

双指针:从中心往两边扩散,以一个数为中心时处理的是奇数的回文子串,以两个数为中心时处理的是偶数的回文子串

class Solution {
public:int countSubstrings(string s) {int result = 0;for(int i=0;i<s.size();i++){result+=extend(s,i,i,s.size());     //处理奇数回文子串,如abaresult+=extend(s,i,i+1,s.size());   //处理偶数回文子串,如abba}return result;}int extend(const string& s,int i,int j,int n){int res;while(i>=0&&j<n&&s[i]==s[j]){i--;j++;res++;}return res;}
};

516.最长回文子序列

力扣题目链接

思路:

// 定义:dp[i][j]表示区间[i][j]左闭右闭内的最长回文子序列

// 递推公式:如果s[i]==s[j],那么当前的长度是上一状态dp[i+1][j-1]再加上两个长度,有一种向两侧扩散比较的感觉,否则,就比较去掉s[i]或s[j]的状态,继承dp[i+1][j]或dp[i][j-1].

// 初始化:dp[i][j]在i=j的时候都得是1,首先看递推公式,i=0的话访问j如果从0开始遍历,那访问-1肯定是访问不到,j从j+1开始遍历,这样的话,dp[i][i] 的情况是遍历不到的.或者就单看dp[i][j] = dp[i + 1][j - 1] + 2,也没有遍历dp[i][i]的准备

// 遍历顺序,j要从i+1开始遍历了

// 打印

// 定义:dp[i][j]表示区间[i][j]左闭右闭内的最长回文子序列
// 递推公式:如果s[i]==s[j],那么当前的长度是上一状态dp[i+1][j-1]再加上两个长度,有一种向两侧扩散比较的感觉,否则,就比较去掉s[i]或s[j]的状态,继承dp[i+1][j]或dp[i][j-1].
// 初始化:dp[i][j]在i=j的时候都得是1,首先看递推公式,i=0的话访问j如果从0开始遍历,那访问-1肯定是访问不到,j要从j+1开始遍历,这样的话,dp[i][i] 的情况是遍历不到的.或者就单看dp[i][j] = dp[i + 1][j - 1] + 2,也没有遍历dp[i][i]的准备
// 遍历顺序,j要从i+1开始遍历了
// 打印
class Solution {
public:int longestPalindromeSubseq(string s) {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;}else{dp[i][j]=max(dp[i][j-1],dp[i+1][j]);}}}return dp[0][s.size()-1];}
};

其实也可以用上一题的方法来初始化,也AC了

class Solution {
public:int longestPalindromeSubseq(string s) {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;j<s.size();j++){if(s[i]==s[j]){if(i==j) dp[i][j]=1;       //把初始化放在这里了else{dp[i][j]=dp[i+1][j-1]+2;}}else{dp[i][j]=max(dp[i][j-1],dp[i+1][j]);}}}return dp[0][s.size()-1];}

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

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

相关文章

BigFoot Decursive lua

BigFoot Decursive lua 一键驱散脚本 国际化 ogg语音提示 初始化

2024山东大学计算机复试上机真题

2024山东大学计算机复试上机真题 2024山东大学计算机复试机试真题 历年山东大学计算机复试上机真题 历年山东大学计算机复试机试真题 在线评测&#xff1a;传动门&#xff1a;pgcode.cn 最长递减子序列 题目描述 输入数字 n&#xff0c;和 n 个整数&#xff0c;输出该数字…

【AI News | 20250316】每日AI进展

AI Repos 1、ReActMCP 将网络搜索能力集成到AI助手中的一个MCP服务&#xff1a;ReActMCP Web Search&#xff0c;相当于给AI装了个搜索引擎&#xff0c;可以实时查找最新的内容。它基于Exa API执行基本和高级网络搜索&#xff0c;高级搜索比如限制搜索的网站范围、指定日期范围…

【大模型实战篇】使用GPTQ量化QwQ-32B微调后的推理模型

1. 量化背景 之所以做量化&#xff0c;就是希望在现有的硬件条件下&#xff0c;提升性能。量化能将模型权重从高精度&#xff08;如FP32&#xff09;转换为低精度&#xff08;如INT8/FP16&#xff09;&#xff0c;内存占用可减少50%~75%。低精度运算&#xff08;如INT8&#xf…

Unity 笔记:在EditorWindow中绘制 Sorting Layer

在Unity开发过程中&#xff0c;可能会对旧资源进行批量修改&#xff0c;一个个手动修改费人费事&#xff0c;所以催生出了一堆批量工具。 分享一下在此过程中绘制 Sorting Layer 面板的代码脚本。 示意图&#xff1a; 在 EditorGUI 和 EditorGUILayer 中内置了 SortingLayerF…

idea更新git代码报错No Git Roots

idea更新git代码报错&#xff1a; No Git Roots None of configured Git roots are under Git. The configured directory must have ".git directory in it.但是本地项目里是存在.git文件的&#xff0c;就是突然间不能更新代码了 然后尝试重新拉新项目代码提示: Git i…

失败的面试经历(ʘ̥∧ʘ̥)

一.面向对象的三大特性 1.封装&#xff1a;将对象内部的属性私有化&#xff0c;外部对象不能够直接访问&#xff0c;但是可以提供一些可以使外部对象操作内部属性的方法。 2.继承&#xff1a;类与类之间会有一些相似之处&#xff0c;但也会有一些异处&#xff0c;使得他们与众…

qt加载VeloView工程

接上一篇点云软件配置与编译&#xff0c;使用qt加载需要先完成编译。编译完成后到编译目录下lidarview-superbuild\common-superbuild\lidarview\build 找到CmakeCache.txt&#xff0c;如下是我的编译目录。 使用QT6.5.3加载了CmakeCache.txt&#xff0c;QT5.14还加载不了cmake…

Windows Qt动态监测系统分辨率及缩放比变化

前言 Windows 显示设置中&#xff0c;可以修改缩放比&#xff0c;所有界面和文字会同比例放大或缩小&#xff0c;在开发桌面程序时&#xff0c; 实时监测Qt应用程序在不同缩放比例下的表现&#xff0c;可以及时调整程序界面以适应不同显示屏幕的需求。 正文 本文通过Qt相关…

CVE-2017-5645(使用 docker 搭建)

介绍: 是一个与 Apache Log4j2 相关的安全漏洞,属于远程代码执行,它可能允许攻击者通过构造恶意的日志信息 在目标系统上执行任意代码 Log4j2 介绍 Log4j2 是 Apache 的一个日志记录工具,属于 Java 应用的日志框架,它是 Log4j 的升级版,性能更好,功能更多.它被广泛的适用于 J…

交互式可视化进阶(Plotly Dash构建疫情仪表盘)

这里写目录标题 交互式可视化进阶(Plotly Dash构建疫情仪表盘)1. 引言2. 项目背景与意义3. 数据集生成与介绍4. GPU加速在数据处理中的应用5. 交互式仪表盘构建与Plotly Dash6. PyQt GUI集成与美化7. 工程整体架构8. 部分代码实现9. 代码自查与BUG排查10. 总结与展望交互式可…

RabbitMQ(补档)

RabbitMQ 是一个开源的消息队列软件&#xff08;有时也被称为消息代理&#xff09;&#xff0c;它实现了高级消息队列协议&#xff08;AMQP&#xff09;。它主要用于应用程序之间&#xff0c;或者软件组件之间的消息通信。通过使用 RabbitMQ&#xff0c;可以实现异步的、可靠的…

平方矩阵问题

Ⅰ 回字形二维数组 #include <iostream> #include <iomanip> using namespace std; int main(){int n;while(cin>>n,n){for(int i0; i<n;i){for(int j0; j<n; j){int upi, downn-i1, leftj, rightn-j1;cout<<min(min(up,down),min(left,right)…

电子电气架构 --- 智能座舱和车载基础软件简介

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 人生是一场骗局,最大的任务根本不是什么买车买房,也不是及时行乐,这就是欲望,不是理想,是把自己对生命的希望寄托在外物上,正确的做法应该是内…

Qt 通过MSVC编译运行项目

第一步下载Qt 把Qt能选的插件都选上&#xff0c;有的是连接数据库必须得插件&#xff0c;有的是做图表必须得插件&#xff0c;有的是运行MSVC必须得插件&#xff0c;能选尽量都选上。 第二步安装VS2017&#xff0c;当然我们安装2017的目的主要是用C的编译器&#xff0c;这里提…

高效手机检测:视觉分析技术的优势

在当今社会&#xff0c;手机已成为人们日常生活和工作中不可或缺的工具。然而&#xff0c;在某些特定场合&#xff0c;如考场、工作场所等&#xff0c;手机的使用却可能带来负面影响。因此&#xff0c;如何有效监测和防止在这些场合偷用手机的行为&#xff0c;成为了一个亟待解…

Gitee重新远程连接仓库(Linux)

Gitee重新远程连接仓库&#xff08;Linux&#xff09; 因为虚拟机重新安装了一回&#xff0c;所以需要重新和远程仓库连接&#xff0c;在网上找了很久没有找到相关操作&#xff0c;自己实操成功&#xff0c;记录下本博客&#xff0c;帮助有需要的人 确保新虚拟机安装Git 在新虚…

【论文笔记】FFA-Net: Feature Fusion Attention Network for Single Image Dehazing

文章目录 1. 研究背景2. FFA - Net网络结构3. 实验结果4. 研究贡献5. 重点详解1. 通道注意力&#xff08;Channel Attention, CA&#xff09;通道注意力的实现步骤&#xff1a; 2. 像素注意力&#xff08;Pixel Attention, PA&#xff09;像素注意力的实现步骤&#xff1a; 3. …

计算机视觉cv2入门之图像的读取,显示,与保存

在计算机视觉领域&#xff0c;Python的cv2库是一个不可或缺的工具&#xff0c;它提供了丰富的图像处理功能。作为OpenCV的Python接口&#xff0c;cv2使得图像处理的实现变得简单而高效。 示例图片 目录 opencv获取方式 图像基本知识 颜色空间 RGB HSV 图像格式 BMP格式 …