【LeetCode 5.】 最长回文子串
一道题能否使用动态规划就在于判断最优结构是否是通过最优子结构推导得到?如果显然具备这个特性,那么就应该朝动态规划思考。如果令dp[i][j]表示串s[i:j+1]是否是回文子串,那么判断
dp[i][j]是否是回文子串,相当于判断s[i] 与 s[j] 是否相等 + dp[i+1][j-1] 是否是回文串。
1. 题目
2. 分析
这道题我写了一个小时才写出来,相比之前看答案写题是有进步的。估计这道题我这半个月都不会忘记了。一道题能否使用动态规划就在于判断最优结构是否是通过最优子结构推导得到?如果显然具备这个特性,那么就应该朝动态规划思考。
具体看一个样例:s="babad",判断这个字符串是否是最长回文子串,相当于判断aba是否是回文子串和b与d是否相等。
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| b | a | b | a | d |
相当于判断最后一个字符和要判断子串的第一个字符是否相等,外加判断内部子串是否是回文子串。
| 1 | 2 | 3 |
|---|---|---|
| a | b | a |
那么抽象一下,就可以得出:判断dp[i][j] 是否是回文子串,相当于判断s[i] 与 s[j] 是否相等 + dp[i+1][j-1] 是否为1。
3. 代码
class Solution:def longestPalindrome(self, s: str) -> str:dp = [[0] * len(s) for i in range(len(s))]for cur_length in range(1, len(s)+1):for i in range(0, len(s)):j = i + cur_length - 1 # 终点下标if j >= len(s): # 越界处理continueif j == i:dp[i][j] = 1continueif cur_length == 2: # 长度为2的区间if s[j] == s[i]:dp[i][j] = 1continueif s[j] == s[i] and dp[i+1][j-1]: # 如果起点和终点相同dp[i][j] = 1# print(dp)max_len = 0res = ""for i in range(len(s)):for j in range(len(s)):if dp[i][j] == 1:if j-i+1 > max_len:max_len = max(max_len, j-i+1)res = s[i:j+1]return res
相关文章:
【LeetCode 5.】 最长回文子串
一道题能否使用动态规划就在于判断最优结构是否是通过最优子结构推导得到?如果显然具备这个特性,那么就应该朝动态规划思考。如果令dp[i][j]表示串s[i:j1]是否是回文子串,那么判断dp[i][j] 是否是回文子串,相当于判断s[i] 与 s[j]…...
联邦学习周记|第四周
论文:Active Federated Learning 链接 将主动学习引入FL,每次随机抽几个Client拿来train,把置信值低的Client概率调大,就能少跑几次。 论文:Active learning based federated learning for waste and natural disast…...
机器学习课程复习——逻辑回归
1. 激活函数 Q:激活函数有哪些? SigmoidS型函数Tanh 双曲正切函数...
Rocky Linux 更换CN镜像地址
官方镜像列表,下拉查找 官方镜像列表:https://mirrors.rockylinux.org/mirrormanager/mirrorsCN 开头的站点。 一键更改镜像地址脚本 以下是更改从默认更改到阿里云地址 cat <<EOF>>/RackyLinux_Update_repo.sh #!/bin/bash # -*- codin…...
Linux rm命令由于要删的文件太多报-bash: /usr/bin/rm:参数列表过长,无法删除的解决办法
银河麒麟系统,在使用rm命令删除文件时报了如下错误,删不掉: 查了一下,原因就是要删除的文件太多了,例如我当前要删的文件共有这么多: 查到了解决办法,记录在此。需要使用xargs命令来解决参数列表…...
【包管理】Node.JS与Ptyhon安装
文章目录 Node.JSPtyhon Node.JS Node.js的安装通常包括以下几个步骤: 访问Node.js官网: 打开Node.js的官方网站(如:https://nodejs.org/zh-cn/download/)。 下载安装包: 根据你的操作系统选择对应的Node…...
SpringMVC系列四: Rest-优雅的url请求风格
Rest请求 💞Rest基本介绍💞Rest风格的url-完成增删改查需求说明代码实现HiddenHttpMethodFilter机制注意事项和细节 💞课后作业 上一讲, 我们学习的是SpringMVC系列三: Postman(接口测试工具) 现在打开springmvc项目 💞Rest基本介…...
Hexo 搭建个人博客(ubuntu20.04)
1 安装 Nodejs 和 npm 首先登录NodeSource官网: Nodesource Node.js DEB 按照提示安装最新的 Node.js 及其配套版本的 npm。 (1)以 sudo 用户身份运行下面的命令,下载并执行 NodeSource 安装脚本: sudo curl -fsSL…...
【论文阅读】-- Attribute-Aware RBFs:使用 RT Core 范围查询交互式可视化时间序列颗粒体积
Attribute-Aware RBFs: Interactive Visualization of Time Series Particle Volumes Using RT Core Range Queries 摘要1 引言2 相关工作2.1 粒子体渲染2.2 RT核心方法 3 渲染彩色时间序列粒子体积3.1 场重构3.1.1 密度场 Φ3.1.2 属性字段 θ3.1.3 优化场重建 3.2 树结构构建…...
A类IP介绍
1)A类ip给谁用: 给广域网用,公网ip使用A类地址,作为公网ip时,Ip地址是全球唯一的。 2)基本介绍 ip地址范围 - 理论范围 0.0.0.0 ~127.255.255.255:00000000 00000000 00000000 00000000 ~ 0111…...
HTML5基本语法
文章目录 HTML5基本语法一、基础标签1、分级标题2、段标签3、换行及水平线标签4、文本格式标签 二、图片标签1、格式2、属性介绍 三、音频标签1、格式2、属性介绍 四、视频标签1、格式2、属性介绍 五、链接标签1、格式2、显示特点3、属性介绍4、补充(空链接…...
正则表达式常用表示
视频教程:10分钟快速掌握正则表达式 正则表达式在线测试工具(亲测好用):测试工具 正则表达式常用表示 限定符 a*:a出现0次或多次a:a出现1次或多次a?:a出现0次或1次a{6}:a出现6次a…...
【OpenHarmony4.1 之 U-Boot 2024.07源码深度解析】007 - evb-rk3568_defconfig 配置编译全过程
【OpenHarmony4.1 之 U-Boot 2024.07源码深度解析】007 - evb-rk3568_defconfig 配置编译全过程 一、编译后目录列表二、make distclean三、生成.config文件:make V=1 ARCH=arm64 CROSS_COMPILE=aarch64-linux-gnu- evb-rk3568_defconfig四、开始编译:CROSS_COMPILE=aarch64-…...
11.1 Go 标准库的组成
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「stormsha的主页」…...
【UG\NX二次开发】UF 调用Grip例子(实现Grip调用目标dll)(UF_call_grip)
此例子是对:【UG\NX二次开发】UF 加载调用与卸载目标dll(UF_load_library、UF_unload_library)_ug二次开发dll自动加载-CSDN博客的补充。 ①创建txt文本,编写以下内容(功能:接收路径,调用该路径的dll)。改后缀为Grip文件(.grs)。…...
[算法刷题积累] 两数之和以及进阶引用
两数之和很经典,通常对于首先想到的就是暴力的求解,当然这没有问题,但是我们如果想要追求更优秀算法,就需要去实现更加简便的复杂度。 这里就要提到我们的哈希表法: 我们可以使用unordered_map去实现,也可以根据题目&a…...
pytest+parametrize+yaml实例
# 一、yaml格式 # # yaml是一种数据类型,可以和json之间灵活的切换,支持注释、换行、字符串等。可以用于配置文件或编写测试用例。 # # 数据结构:一般是键值对的方式出现。注意编写时值前面必须有空格,键:(…...
【HarmonyOS】鸿蒙应用模块化实现
【HarmonyOS】鸿蒙应用模块化实现 一、Module的概念 Module是HarmonyOS应用的基本功能单元,包含了源代码、资源文件、第三方库及应用清单文件,每一个Module都可以独立进行编译和运行。一个HarmonyOS应用通常会包含一个或多个Module,因此&am…...
深入Node.js:实现网易云音乐数据自动化抓取
随着互联网技术的飞速发展,数据已成为企业和个人获取信息、洞察市场趋势的重要资源。音频数据,尤其是来自流行音乐平台如网易云音乐的数据,因其丰富的用户交互和内容多样性,成为研究用户行为和市场动态的宝贵资料。本文将深入探讨…...
【Docker实战】jenkins卡在编译Dockerfile的问题
我们的项目是标准的CI/CD流程,也即是GitlabJenkinsHarborDocker的容器自动化部署。 经历了上上周的docker灾难,上周的服务器磁盘空间灾难,这次又发生了jenkins卡住的灾难。 当然,这些灾难有一定的连锁反应,是先发生的d…...
K8S认证|CKS题库+答案| 11. AppArmor
目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作: 1)、切换集群 2)、切换节点 3)、切换到 apparmor 的目录 4)、执行 apparmor 策略模块 5)、修改 pod 文件 6)、…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
智能AI电话机器人系统的识别能力现状与发展水平
一、引言 随着人工智能技术的飞速发展,AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术,在客户服务、营销推广、信息查询等领域发挥着越来越重要…...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
Python Einops库:深度学习中的张量操作革命
Einops(爱因斯坦操作库)就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库,用类似自然语言的表达式替代了晦涩的API调用,彻底改变了深度学习工程…...
从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践
作者:吴岐诗,杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言:融合数据湖与数仓的创新之路 在数字金融时代,数据已成为金融机构的核心竞争力。杭银消费金…...
