【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…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...
从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践
作者:吴岐诗,杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言:融合数据湖与数仓的创新之路 在数字金融时代,数据已成为金融机构的核心竞争力。杭银消费金…...
Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案
在大数据时代,海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构,在处理大规模数据抓取任务时展现出强大的能力。然而,随着业务规模的不断扩大和数据抓取需求的日益复杂,传统…...
Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践
在 Kubernetes 集群中,如何在保障应用高可用的同时有效地管理资源,一直是运维人员和开发者关注的重点。随着微服务架构的普及,集群内各个服务的负载波动日趋明显,传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...
数据库——redis
一、Redis 介绍 1. 概述 Redis(Remote Dictionary Server)是一个开源的、高性能的内存键值数据库系统,具有以下核心特点: 内存存储架构:数据主要存储在内存中,提供微秒级的读写响应 多数据结构支持&…...
Python环境安装与虚拟环境配置详解
本文档旨在为Python开发者提供一站式的环境安装与虚拟环境配置指南,适用于Windows、macOS和Linux系统。无论你是初学者还是有经验的开发者,都能在此找到适合自己的环境搭建方法和常见问题的解决方案。 快速开始 一分钟快速安装与虚拟环境配置 # macOS/…...
ffmpeg(三):处理原始数据命令
FFmpeg 可以直接处理原始音频和视频数据(Raw PCM、YUV 等),常见场景包括: 将原始 YUV 图像编码为 H.264 视频将 PCM 音频编码为 AAC 或 MP3对原始音视频数据进行封装(如封装为 MP4、TS) 处理原始 YUV 视频…...
联邦学习带宽资源分配
带宽资源分配是指在网络中如何合理分配有限的带宽资源,以满足各个通信任务和用户的需求,尤其是在多用户共享带宽的情况下,如何确保各个设备或用户的通信需求得到高效且公平的满足。带宽是网络中的一个重要资源,通常指的是单位时间…...
