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

最长回文子串-LeetCode5 动态规划

在这里插入图片描述

由于基础还不是很牢固 一时间只能想到暴力的解法:

取遍每个子串 总数量n+n-1+n-2+…+1 =O(n^2)
判断每个子串是否属于回文串 O(n)
故总时间复杂度为O(n^3)

class Solution {
public:string longestPalindrome(string s) {
int max=0;string ret;for(int i=0;i<s.size();i++)for(int j=1;j<=s.size()-i;j++){string s1=s.substr(i,j);if(Judeg(s1)>max){max=Judeg(s1);ret=s1;}}return ret;}int Judeg(string s)
{int i,j;for(i=0,j=s.size()-1;i<=j;i++,j--){if(s[i]!=s[j])return 0;}return s.size();
}
};

在查阅题解以后 比较简单易懂的还是动态规划算法
设某子串的左下标为i 右下标为j
则该子串是不是回文串可以走如下流程:
1.s[i]和s[j]不相等 那么一定不是回文子串 dp[i][j]=false
2.在s[i]和s[j]已经相等的基础上 若子串的长度<=3 那么一定是回文串 dp[i][j]=true
3.最后一种情况 dp[i][j]=dp[i+1][j-1]
一个很长的子串是不是回文串 取决于去掉首尾字符以后 中间的子串是不是回文串(动态规划套娃)

时间复杂度为遍历dp数组 故为O(n^2)
空间复杂度为开辟dp数组 故为O(n^2)

string longestPalindrome(string s) 
{int max=1,begin=0;int len=s.size();if(len<2)return s;bool **dp=new bool*[len];for(int i=0;i<len;i++){dp[i]=new bool [len];}for(int j=1;j<len;j++){for(int i=0;i<j;i++){if(s[i]!=s[j])dp[i][j]=false;else{if(j-i+1<=3)dp[i][j]=true;else{dp[i][j]=dp[i+1][j-1];}}if(dp[i][j]&&j-i+1>max){max=j-i+1;begin=i;}}}return s.substr(begin,max);
}

相关文章:

最长回文子串-LeetCode5 动态规划

由于基础还不是很牢固 一时间只能想到暴力的解法: 取遍每个子串 总数量nn-1n-2…1 O(n^2) 判断每个子串是否属于回文串 O(n) 故总时间复杂度为O(n^3) class Solution { public:string longestPalindrome(string s) { int max0;string ret;for(int i0;i<s.size();i)for(int…...

mysql简单备份和恢复

版本&#xff1a;mysql8.0 官方文档 &#xff1a;MySQL :: MySQL 8.0 Reference Manual :: 7 Backup and Recovery 1.物理备份恢复 物理备份是以数据文件形式备份。这种方式效率高点&#xff0c;适合大型数据库备份。物理备份可冷备可热备。 使用mysqlbackup 命令进行物理备…...

JMeter介绍

1. JMeter是什么&#xff1f; 是Apache组织开发基于Java的接口测试工具&#xff0c;性能测试工具 2.JMeter的优缺点 优点&#xff1a; 开源&#xff0c;免费 跨平台 支持多协议 轻量级别 缺点&#xff1a; 不支持IP欺骗 不可验证页面UI 3.JMeter可以用来做什么&#xff1f; …...

flink job同时使用BroadcastProcessFunction和KeyedBroadcastProcessFunction例子

背景&#xff1a; 广播状态可以用于规则表或者配置表的实时更新&#xff0c;本文就是用一个欺诈检测的flink作业作为例子看一下BroadcastProcessFunction和KeyedBroadcastProcessFunction的使用 BroadcastProcessFunction和KeyedBroadcastProcessFunction的使用 1.首先看主流…...

数据中心系统解决方案

设计思路 系统设计过程中充分考虑各个子系统的信息共享要求&#xff0c;对各子系统进行结构化和标准化设计&#xff0c;通过系统间的各种联动方式将其整合成一个有机的整体&#xff0c;使之成为一套整体的、全方位的数据中心大楼综合管理系统&#xff0c;达到人防、物防和技防…...

服务器开设新账户,创建账号并设置密码

实验室又进新同学了&#xff0c;服务器开设新账号搞起来 1、创建用户&#xff1a; 在root权限下&#xff0c;输入命令useradd -m 用户名&#xff0c;如下 sudo useradd -m yonghuming 2、设置密码&#xff1a; 输入命令passwd 用户名 回车&#xff0c;接着输入密码操作&…...

【C++】关于构造函数后面冒号“:“的故事------初始化列表(超详细解析,小白一看就懂)

目录 一、前言 二、 初始化的概念区分 三、初始化列表 &#xff08;重点&#xff09; &#x1f4a6;初始化列表的概念理解 &#x1f4a6;初始化列表的注意事项 四、共勉 一、前言 在之前的博客学习中&#xff0c;我们已经学习了【C】的六大默认成员函数 &#xff0c;想必大…...

【Shell 系列教程】shell基本运算符(四)

文章目录 往期回顾关系运算符布尔运算符逻辑运算符字符串运算符文件测试运算符其他检查符&#xff1a; 往期回顾 【Shell 系列教程】shell介绍&#xff08;一&#xff09;【Shell 系列教程】shell变量&#xff08;二&#xff09;【Shell 系列教程】shell数组&#xff08;三&am…...

MongoDB安装及开发系例全教程

一、系列文章目录 一、MongoDB安装教程—官方原版 二、MongoDB 使用教程(配置、管理、监控)_linux mongodb 监控 三、MongoDB 基于角色的访问控制 四、MongoDB用户管理 五、MongoDB基础知识详解 六、MongoDB—Indexs 七、MongoDB事务详解 八、MongoDB分片教程 九、Mo…...

ffmpeg命令帮助文档

一&#xff1a;帮助文档的命令格式 ffmpeg -h帮助的基本信息ffmpeg -h long帮助的高级信息ffmpeg -h full帮助的全部信息 ffmpeg的命令使用方式&#xff1a;ffmpeg [options] [[infile options] -i infile] [[outfile options] outfile] 二&#xff1a;将帮助文档输出到文件 …...

回归预测 | Matlab实现SO-CNN-SVM蛇群算法优化卷积神经网络-支持向量机的多输入单输出回归预测

Matlab实现SO-CNN-SVM蛇群算法优化卷积神经网络-支持向量机的多输入单输出回归预测 目录 Matlab实现SO-CNN-SVM蛇群算法优化卷积神经网络-支持向量机的多输入单输出回归预测效果一览基本介绍程序设计参考资料 效果一览 基本介绍 1.SO-CNN-SVM蛇群算法优化卷积神经网络-支持向量…...

【原创】java+swing+mysql校园共享单车管理系统设计与实现

摘要&#xff1a; 校园共享单车作为一种绿色、便捷的出行方式&#xff0c;在校园内得到了广泛的应用。然而&#xff0c;随着单车数量的增加&#xff0c;管理难度也不断加大。如何提高单车的利用率和管理效率&#xff0c;成为校园共享单车发展面临的重要问题。本文针对这一问题…...

(自适应手机端)响应式新闻博客知识类pbootcms网站模板 自媒体运营博客网站源码下载

(自适应手机端)响应式新闻博客知识类pbootcms网站模板 自媒体运营博客网站源码下载 带后台系统PbootCMS内核开发的网站模板&#xff0c;该模板适用于新闻博客网站、自媒体运营网站等企业&#xff0c;当然其他行业也可以做&#xff0c;只需要把文字图片换成其他行业的即可&#…...

SystemC入门完整编写示例:全加器测试平台

导读: 本文将完整演示基于systemC编写一个全加器的测试平台。具体内容包括&#xff1a;激励平台&#xff0c;监控平台&#xff0c;待测单元的编写&#xff0c;波形文件读取。 1&#xff0c;main函数模块 搭建一个测试平台主要由&#xff1a;Driver, Monitor, DUT(design under …...

动手学深度学习:2.线性回归pytorch实现

动手学深度学习&#xff1a;2.线性回归pytorch实现 1.手动构造数据集2.小批量读取数据集3.定义模型和损失函数4.初始化模型参数5.小批量随机梯度下降优化算法6.训练完整代码Q&A 1.手动构造数据集 import torch from torch.utils import data from d2l import torch as d2l…...

重要的linux指令

系统管理命令 切换用户 su 用户名管理员身份运行 sudo 命令实时显示进程信息(linux下任务管理器) top查看进程信息(ps) ps -efps -ef | grep 进程名 ps -aux | grep 进程名参数说明e 显示所有进程f 全格式a 显示所有程序u 以用户为主的格式来显示程序状况x 显示无控制终端…...

delphi7安装并使用皮肤控件

1、下载控件 我已经上传到云盘&#xff0c;存储位置 2、下载后并解压。 3、打开dephi7&#xff0c;File-Open&#xff0c;打开路径D:\LC\Desktop\vclskin2_XiaZaiBa\d7&#xff0c; 然后将 D:\LC\Desktop\vclskin2_XiaZaiBa\d7文件夹中所有后缀.dcu的文件复制粘贴到delphi安装路…...

安徽省黄山景区免9天门票为哪般?

今日浑浑噩噩地睡了大半天&#xff0c;强撑起身子写网文......可是&#xff0c;题材不好选&#xff0c;本“人民体验官”只得推广人民日报官方微博文化产品《这两个月“黄山每周三免门票”》。 图&#xff1a;来源“人民体验官”推广平台 因年事渐高&#xff0c;又有未愈的呼吸…...

MFC 窗体插入图片

1.制作BMP图像1.bmp 放到res文件夹下&#xff0c;资源视图界面导入res文件夹下的1.bmp 2.添加控件 控件类型修改为Bitmap 图像&#xff0c;选择IDB_BITMAP1 3.效果...

关于中间件技术

中间件是一种独立的系统软件或服务程序&#xff0c;可以帮助分布式应用软件在不同的技术之间共享资源。中间件可以&#xff1a; 1、负责客户机与服务器之间的连接和通信&#xff0c;以及客户机与应用层之间的高效率通信机制。 2、提供应用的负载均衡和高可用性、安全机制与管…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

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

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...