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

【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是否相等。

01234
babad

相当于判断最后一个字符和要判断子串的第一个字符是否相等,外加判断内部子串是否是回文子串。

123
aba

那么抽象一下,就可以得出:判断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镜像地址

官方镜像列表&#xff0c;下拉查找 官方镜像列表&#xff1a;https://mirrors.rockylinux.org/mirrormanager/mirrorsCN 开头的站点。 一键更改镜像地址脚本 以下是更改从默认更改到阿里云地址 cat <<EOF>>/RackyLinux_Update_repo.sh #!/bin/bash # -*- codin…...

Linux rm命令由于要删的文件太多报-bash: /usr/bin/rm:参数列表过长,无法删除的解决办法

银河麒麟系统&#xff0c;在使用rm命令删除文件时报了如下错误&#xff0c;删不掉&#xff1a; 查了一下&#xff0c;原因就是要删除的文件太多了&#xff0c;例如我当前要删的文件共有这么多&#xff1a; 查到了解决办法&#xff0c;记录在此。需要使用xargs命令来解决参数列表…...

【包管理】Node.JS与Ptyhon安装

文章目录 Node.JSPtyhon Node.JS Node.js的安装通常包括以下几个步骤&#xff1a; 访问Node.js官网&#xff1a; 打开Node.js的官方网站&#xff08;如&#xff1a;https://nodejs.org/zh-cn/download/&#xff09;。 下载安装包&#xff1a; 根据你的操作系统选择对应的Node…...

SpringMVC系列四: Rest-优雅的url请求风格

Rest请求 &#x1f49e;Rest基本介绍&#x1f49e;Rest风格的url-完成增删改查需求说明代码实现HiddenHttpMethodFilter机制注意事项和细节 &#x1f49e;课后作业 上一讲, 我们学习的是SpringMVC系列三: Postman(接口测试工具) 现在打开springmvc项目 &#x1f49e;Rest基本介…...

Hexo 搭建个人博客(ubuntu20.04)

1 安装 Nodejs 和 npm 首先登录NodeSource官网&#xff1a; Nodesource Node.js DEB 按照提示安装最新的 Node.js 及其配套版本的 npm。 &#xff08;1&#xff09;以 sudo 用户身份运行下面的命令&#xff0c;下载并执行 NodeSource 安装脚本&#xff1a; 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&#xff09;A类ip给谁用&#xff1a; 给广域网用&#xff0c;公网ip使用A类地址&#xff0c;作为公网ip时&#xff0c;Ip地址是全球唯一的。 2&#xff09;基本介绍 ip地址范围 - 理论范围 0.0.0.0 ~127.255.255.255&#xff1a;00000000 00000000 00000000 00000000 ~ 0111…...

HTML5基本语法

文章目录 HTML5基本语法一、基础标签1、分级标题2、段标签3、换行及水平线标签4、文本格式标签 二、图片标签1、格式2、属性介绍 三、音频标签1、格式2、属性介绍 四、视频标签1、格式2、属性介绍 五、链接标签1、格式2、显示特点3、属性介绍4、补充&#xff08;空链接&#xf…...

正则表达式常用表示

视频教程&#xff1a;10分钟快速掌握正则表达式 正则表达式在线测试工具&#xff08;亲测好用&#xff09;&#xff1a;测试工具 正则表达式常用表示 限定符 a*&#xff1a;a出现0次或多次a&#xff1a;a出现1次或多次a?&#xff1a;a出现0次或1次a{6}&#xff1a;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 标准库的组成

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:「stormsha的主页」…...

【UG\NX二次开发】UF 调用Grip例子(实现Grip调用目标dll)(UF_call_grip)

此例子是对&#xff1a;【UG\NX二次开发】UF 加载调用与卸载目标dll(UF_load_library、UF_unload_library)_ug二次开发dll自动加载-CSDN博客的补充。 ①创建txt文本&#xff0c;编写以下内容(功能&#xff1a;接收路径&#xff0c;调用该路径的dll)。改后缀为Grip文件(.grs)。…...

[算法刷题积累] 两数之和以及进阶引用

两数之和很经典&#xff0c;通常对于首先想到的就是暴力的求解&#xff0c;当然这没有问题&#xff0c;但是我们如果想要追求更优秀算法&#xff0c;就需要去实现更加简便的复杂度。 这里就要提到我们的哈希表法: 我们可以使用unordered_map去实现&#xff0c;也可以根据题目&a…...

pytest+parametrize+yaml实例

# 一、yaml格式 # # yaml是一种数据类型&#xff0c;可以和json之间灵活的切换&#xff0c;支持注释、换行、字符串等。可以用于配置文件或编写测试用例。 # # 数据结构&#xff1a;一般是键值对的方式出现。注意编写时值前面必须有空格&#xff0c;键&#xff1a;&#xff08;…...

【HarmonyOS】鸿蒙应用模块化实现

【HarmonyOS】鸿蒙应用模块化实现 一、Module的概念 Module是HarmonyOS应用的基本功能单元&#xff0c;包含了源代码、资源文件、第三方库及应用清单文件&#xff0c;每一个Module都可以独立进行编译和运行。一个HarmonyOS应用通常会包含一个或多个Module&#xff0c;因此&am…...

深入Node.js:实现网易云音乐数据自动化抓取

随着互联网技术的飞速发展&#xff0c;数据已成为企业和个人获取信息、洞察市场趋势的重要资源。音频数据&#xff0c;尤其是来自流行音乐平台如网易云音乐的数据&#xff0c;因其丰富的用户交互和内容多样性&#xff0c;成为研究用户行为和市场动态的宝贵资料。本文将深入探讨…...

【Docker实战】jenkins卡在编译Dockerfile的问题

我们的项目是标准的CI/CD流程&#xff0c;也即是GitlabJenkinsHarborDocker的容器自动化部署。 经历了上上周的docker灾难&#xff0c;上周的服务器磁盘空间灾难&#xff0c;这次又发生了jenkins卡住的灾难。 当然&#xff0c;这些灾难有一定的连锁反应&#xff0c;是先发生的d…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现指南针功能

指南针功能是许多位置服务应用的基础功能之一。下面我将详细介绍如何在HarmonyOS 5中使用DevEco Studio实现指南针功能。 1. 开发环境准备 确保已安装DevEco Studio 3.1或更高版本确保项目使用的是HarmonyOS 5.0 SDK在项目的module.json5中配置必要的权限 2. 权限配置 在mo…...

echarts使用graphic强行给图增加一个边框(边框根据自己的图形大小设置)- 适用于无法使用dom的样式

pdf-lib https://blog.csdn.net/Shi_haoliu/article/details/148157624?spm1001.2014.3001.5501 为了完成在pdf中导出echarts图&#xff0c;如果边框加在dom上面&#xff0c;pdf-lib导出svg的时候并不会导出边框&#xff0c;所以只能在echarts图上面加边框 grid的边框是在图里…...