动态规划回文子串
647. 回文子串
方法:双指针
回文子串有长度为奇数和偶数两种,extend(s, i, i, n); extend(s, i, i + 1, n);就分别对应长度为奇数和偶数的情况
class Solution {
private:int extend(const string& s, int i, int j, int n) {int res = 0;while (i >= 0 && j < n && s[i] == s[j]) {++j;--i;++res;}return res;}
public:int countSubstrings(string s) {int n = s.size(), ans = 0;for (int i = 0; i < n; ++i) {ans += extend(s, i, i, n);ans += extend(s, i, i + 1, n);}return ans;}
};$时间复杂度O(
),空间复杂度O(n);
方法:dp
状态表示:以i为起始坐标到j为终止坐标的子字符串是否为回文的字符串的集合
属性:是与否
状态计算:当s[i] == s[j]时,分成两种情况。一种是j - i <= 1例如:aa与a都是回文字符串,另一种情况是j-i>1就得判断dp[i+1][j-1]是不是回文了。
状态依赖dp[i+1][j-1]这种状态,所以i的遍历就得倒过来,这样才能确保dp[i+1][j-1]已经判断是否为回文。
class Solution {
public:int countSubstrings(string s) {int n = s.size();vector<vector<bool>> dp(n, vector<bool> (n, false));int res = 0;for (int i = n - 1; i >= 0; --i) for (int j = i; j < n; ++j) {if (s[i] == s[j] && (j - i <= 1 || dp[i+1][j-1])) {++res;dp[i][j] = true;}}return res;}
};$时间复杂度O(
),空间复杂度O(
);
516. 最长回文子序列
方法:dp
状态表示:以i为起始坐标到j为终止坐标的子字符串最长回文的字符串的长度
属性::长度
预处理长度为1的回文子序列
状态计算:当s[i] == s[j]时,dp[i][j] == dp[i+1][j-1] + 2(为一的情况已经预处理)
不相同时则取dp[i+1][j],与dp[i][j-1]中的大值;
与上一题一样遍历顺序是从下到上从左到右
class Solution {#define maxn 1010int dp[maxn][maxn];
public:int longestPalindromeSubseq(string s) {int n = s.size();for (int i = 0; i < n; ++i) dp[i][i] = 1;for (int i = n - 1; i >= 0; --i) for (int j = i + 1; j < n; ++j) {if (s[i] == s[j]) dp[i][j] = dp[i+1][j-1] + 2;else dp[i][j] = max(dp[i+1][j], dp[i][j-1]);}return dp[0][n-1];}
};$时间复杂度O(
),空间复杂度O(
);
相关文章:
动态规划回文子串
647. 回文子串方法:双指针回文子串有长度为奇数和偶数两种,extend(s, i, i, n); extend(s, i, i 1, n);就分别对应长度为奇数和偶数的情况class Solution { private:int extend(const string& s, int i, int j, int n) {int res 0;while (i > 0…...
windows 域控提权CVE-2014-6324CVE-2020-1472CVE-2021-42287CVE-2022-26923
一、CVE-2014-6324复现 环境:god.org域,两台主机,一台win2008域控,另一台web服务器win2008 工具:ms14-068.exe(漏洞exp) mimikatz psexec 利用条件: 1.域用户账号密码 2.获得一台主机权限(本地administ…...
1、JDK 安装 Java环境变量配置
jdk下载(Java8) (下载时间不同,小版本号会有变化,不影响后续安装) 官网下载地址:https://www.oracle.com/java/technologies/downloads/#java8-windows 下载完后安装 JDK 环境变量配置 Win…...
[c++]list模拟实现
目录 前言: 学习类的方式: 1 类成员变量 1.1 list成员变量 1.2 结点结构体变量 1.3 迭代器成员变量 2 默认函数——构造 2.1 结点结构体构造函数 2.2 list构造函数 2.3 迭代器构造函数 3 迭代器实现 3.1 list部分 3.2 迭代器结构体部分 3.2…...
实用的仓库管理软件有哪些,盘点2023年5大仓库管理软件!
对于做批发生意的老板或工厂老板来说,选择一款实用的仓库管理软件是至关重要的。仓库管理软件除了可以帮你降低仓库管理成本,提高经营管理的效率,还能够在手机上随时随地掌控仓库员工和商品的最新信息,与客户、供应商的订单情况能…...
(八十二)透彻研究通过explain命令得到的SQL执行计划(1)
今天我们正式进入研究explain命令得到的SQL执行计划的内容了,只要把explain分析得到的SQL执行计划都研究透彻,完全能看懂,知道每个执行计划在底层是怎么执行的,那么后面学习SQL语句的调优就非常容易了。 首先,我们现在…...
【Linux】旋转锁 | 读写锁
在之前的线程学习中,用到的锁都是挂起等待锁,如果申请不到锁,那就会在锁中等待; 自旋锁则不大相似 文章目录1.自旋锁1.1 概念1.2 接口1.2.1 pthread_spin_init/destroy1.2.2 pthread_spin_lock1.2.3 pthread_spin_unlock2.读写锁…...
EasyExcell导出excel添加水印
EasyExcell导出excel添加水印1、添加easyExcel相关依赖2、准备基础工具类3、创建水印handler类4、创建单元测试类WriteTest.class5、测试结果1、添加easyExcel相关依赖 <dependency><groupId>org.apache.poi</groupId><artifactId>poi</artifactId&…...
SpringCloud:Nacos配置管理
Nacos除了可以做注册中心,同样可以做配置管理来使用。 1.1.统一配置管理 当微服务部署的实例越来越多,达到数十、数百时,逐个修改微服务配置就会让人抓狂,而且很容易出错。我们需要一种统一配置管理方案,可以集中管理…...
正则表达式引擎NFA自动机的回溯解决方案总结
前几天线上一个项目监控信息突然报告异常,上到机器上后查看相关资源的使用情况,发现 CPU 利用率将近 100%。通过 Java 自带的线程 Dump 工具,我们导出了出问题的堆栈信息。 我们可以看到所有的堆栈都指向了一个名为 validateUrl 的方法&#…...
卷积神经网络之AlexNet
目录概述AlexNet特点激活函数sigmoid激活函数ReLu激活函数数据增强层叠池化局部相应归一化DropoutAlexnet网络结构网络结构分析AlexNet各层参数及其数量模型框架形状结构关于数据集训练学习keras代码示例概述 由于受到计算机性能的影响,虽然LeNet在图像分类中取得了…...
React中setState什么时候是同步的,什么时候是异步的?
本文内容均针对于18.x以下版本 setState 到底是同步还是异步?很多人可能都有这种经历,面试的时候面试官给了你一段代码,让你说出输出的内容,比如这样: constructor(props) {super(props);this.state {val: 0}}compo…...
优秀开源软件的类,都是怎么命名的?
日常编码中,代码的命名是个大的学问。能快速的看懂开源软件的代码结构和意图,也是一项必备的能力。 Java项目的代码结构,能够体现它的设计理念。Java采用长命名的方式来规范类的命名,能够自己表达它的主要意图。配合高级的 IDEA&…...
绘制CSP的patterns矩阵图
最近在使用FBCSP处理数据,然后就想着看看处理后的样子,用地形图的形式表现出来,但是没有符合自己需求的函数可以实现,就自己尝试的实现了一下,这里记录一下,方便以后查阅。 绘制CSP的patterns矩阵图 对数据做了FBCSP处理,但是想画一下CSP计算出来的patterns的地形图,并…...
Datatables展示数据(表格合并、日期计算、异步加载数据、分页显示、筛选过滤)
系列文章目录 datatable 自定义筛选按钮的解决方案Echarts实战案例代码(21):front-endPage的CJJTable前端分页插件ajax分页异步加载数据的解决方案 文章目录系列文章目录前言一、html容器构建1.操作按钮2.表格构建二、时间日期计算三、dataTables属性配置1.调用2.过…...
Python decimal模块的使用
Python decimal 模块Python中的浮点数默认精度是15位。Decimal对象可以表示任意精度的浮点数。getcontext函数用于获取当前的context环境,可以设置精度、舍入模式等参数。#在context中设置小数的精度 decimal.getcontext().prec 100通过字符串初始化Decimal类型的变…...
pycharm常用快捷键
编辑类: Ctrl D 复制选定的区域或行 Ctrl Y 删除选定的行 Ctrl Alt L 代码格式化 Ctrl Alt O 优化导入(去掉用不到的包导入) Ctrl 鼠标 简介/进入代码定义 Ctrl / 行注释 、取消注释 Ctrl 左方括号 快速跳到代码开头 Ctrl 右方括…...
useCallback 与 useMemo 的区别 作用
useCallback 缓存钩子函数,useMemo 缓存返回值(计算结果)。 TS声明如下:type DependencyList ReadonlyArray<any>;function useCallback<T extends (...args: any[]) > any>(callback: T, deps: DependencyList)…...
Mybatis的学习
01-mybatis传统dao开发模式 概述 mybatis有两种使用模式: ①传统dao开发模式, ②dao接口代理开发模式 ①传统dao开发模式 dao接口 dao实现子类 mapper映射文件dao实现子类来决定了dao接口的方法和mapper映射文件的statement的关系 代码实现 public class StudentDaoImpl im…...
PyTorch深度学习实战 | 计算机视觉
深度学习领域技术的飞速发展,给人们的生活带来了很大改变。例如,智能语音助手能够与人类无障碍地沟通,甚至在视频通话时可以提供实时翻译;将手机摄像头聚焦在某个物体上,该物体的相关信息就会被迅速地反馈给使用者&…...
大数据学习栈记——Neo4j的安装与使用
本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装:Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...
Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...
基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
【C++进阶篇】智能指针
C内存管理终极指南:智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...
篇章二 论坛系统——系统设计
目录 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 1. 数据库设计 1.1 数据库名: forum db 1.2 表的设计 1.3 编写SQL 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 通过需求分析获得概念类并结合业务实现过程中的技术需要&#x…...
