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

回文子串的数量[寻找回文子串的完整思路过程]

寻找回文子串的完整思路过程

  • 前言
  • 一、回文串的数量
  • 二、动态规划
    • 1、完整思考过程
    • 2、go
  • 总结
  • 参考文献

前言

回文字符串,就是从左遍历和从右遍历的字符是相同顺序的,转换一下,就是该字符串是对称的。寻找回文子串面临两个直接的问题,1-如何确定一个子串?2-如何判断该子串是否为回文串?

一、回文串的数量

在这里插入图片描述

二、动态规划

1、完整思考过程

两个直观的问题,
1)如何确定子串?两层for循环O(n2)定位左右边界。
2)如何判定子串是回文子串?for循环O(n)判定是否对称。
复杂度:O(n3)

子串/子数组问题,联想前缀/滑动窗口/单调栈/动态规划,
回文内在特点)一个回文串本身有什么特点?去头去尾也是回文,利用这个规律,记录内串是否为回文,从内到外递进判断,可以减少for循环的对称判断,则可将时间复杂度降为O(n2)

方案)由内到外,从少到多,先判断s[:0]子串,再判断s[:1]子串,依次类推。

2、go

func countSubstrings(s string) int {f := make([]bool,len(s))cnt := 0for i := 0;i < len(s);i++ {f[i] = truecnt++ // 每个字符串都是一个回文,这里cnt++配合f[i] = ture,相互理解,而不是cnt := len(s)// 需要用到f[j+1],所以正序遍历,防止覆盖。for j := 0;j < i;j++ {f[j] = false // 复用一层数组,需要覆盖前面的值,保持严格递推。if s[i] == s[j] && (j + 1 == i || f[j + 1]) {f[j] = truecnt++}}}return cnt
}

总结

1)写下完整的思路过程,有助于清晰的理解问题,记忆问题的解答思路。
2)动态规划本质,将问题分解成规模不同性质相同的子问题,找到子问题之间的内在联系,此时便可记录这种联系点,以空间换时间。
3)动态规划常常涉及空间压缩,而压缩面临直观的两个问题,1-这个记录的状态是否过时?2-这个记录的状态是否太新?(才覆盖了)

参考文献

[1] LeetCode 回文串的数量

相关文章:

回文子串的数量[寻找回文子串的完整思路过程]

寻找回文子串的完整思路过程前言一、回文串的数量二、动态规划1、完整思考过程2、go总结参考文献前言 回文字符串&#xff0c;就是从左遍历和从右遍历的字符是相同顺序的&#xff0c;转换一下&#xff0c;就是该字符串是对称的。寻找回文子串面临两个直接的问题&#xff0c;1-…...

CCNP350-401学习笔记(301-350题)

301、Drag and drop the virtual component from the left onto their descriptions on the right. 302、Which two actions, when applied in the LAN network segment, will facilitate Layer 3 CAPWAP discovery for lightweight AP? (Choose two.)A. Utilize DHCP option …...

【LeetCode】No.225. 用队列实现栈 -- Java Version

题目链接&#xff1a;https://leetcode.cn/problems/implement-stack-using-queues/ 1. 题目介绍&#xff08;225. 用队列实现栈&#xff09; 请你仅使用两个队列实现一个后入先出&#xff08;LIFO&#xff09;的栈&#xff0c;并支持普通栈的全部四种操作&#xff08;push、t…...

45个写规范代码的小技巧

目录 1、规范命名 2、规范代码格式 3、写好代码注释 4、try catch 内部代码抽成一个方法 5、方法别太长 6、抽取重复代码 7、多用return 8、if条件表达式不要太复杂 9、优雅地参数校验 10、统一返回值 11、统一异常处理 12、尽量不传递null值 13、尽量不返回null值…...

MindFusion Diagramming for Java, 最新版 Crack

Diagramming for Java, V4.6.1 A unique Java Swing library for any type of flowchart.您需要的每一个图表功能 图表、方案、图形、网络、算法、树、图表 - 所有这些都是使用 MindFusion Diagramming for Java 工具快速轻松地构建的。结果令人着迷。 Java Dagram 库&#xff…...

中间件安全—Apache常见漏洞

中间件安全—Apache常见漏洞1.Apache常见漏洞1.1.Apache介绍1.2.Apache HTTPD 换行解析漏洞&#xff08;CVE-2017-15715&#xff09;1.2.1.漏洞介绍1.2.2.漏洞环境1.2.2.1.运行漏洞环境1.2.2.2.访问漏洞环境1.2.3.漏洞复现1.2.3.1.拦截1.2.3.2.添加换行1.2.3.3.访问文件1.3.Apa…...

Spring IOC 容器 Bean 加载过程

Spring IOC 容器 Bean 加载过程 Spring 对于我们所有的类对象进行了统一抽象&#xff0c;抽象为 BeanDefinition &#xff0c;即 Bean 的定义&#xff0c;其中定义了类的全限定类名、加载机制、初始化方式、作用域等信息&#xff0c;用于对我们要自动装配的类进行生成。 Sprin…...

【DRF】Django Rest Framework(5.DRF中的通用视图类-GenericAPIView方法说明与使用说明)

1. GenericAPIView [通用视图类]&#xff0c;概述 继承自 APIView增加了操作序列化器和数据库查询的方法&#xff0c;作用是为下面Mixin扩展类的执行提供方法支持。通常在使用时&#xff0c;可搭配一个或者多个Mixin扩展类源码 当我们查看 GenericAPIView 的源码时&#xff0c…...

STM32 OTA应用开发——自制BootLoader

STM32 OTA应用开发——自制BootLoader 目录STM32 OTA应用开发——自制BootLoader前言1 环境搭建2 BootLoader工作原理以及常见分区介绍3 BootLoader的制作4 烧录下载配置5 运行测试结束语前言 什么是OTA&#xff1f; 百度百科&#xff1a;空中下载技术&#xff08;Over-the-Ai…...

时域和频域的简单理解

目录文章背景结论举例说明说回频域连续或离散总结文章背景 时域和频域在傅里叶变换和拉普拉斯变换&#xff0c;z变换中经常提到的高频词。本文的重点就是想说明怎么理解 “频域” 这个名词。 结论 频域就是一个信号 所有组成频率的取值范围的集合 举例说明 以大家从中小学开…...

华为OD机试 - 第 K 个最小码值的字母 | 机试题算法思路 【2023】

最近更新的博客 华为OD机试 - 简易压缩算法(Python) | 机试题算法思路 【2023】 华为OD机试题 - 获取最大软件版本号(JavaScript) 华为OD机试 - 猜字谜(Python) | 机试题+算法思路 【2023】 华为OD机试 - 删除指定目录(Python) | 机试题算法思路 【2023】 华为OD机试 …...

离散数学笔记_第一章:逻辑和证明(1)

1.1命题逻辑1.1.1 命题 1.1.2 逻辑运算符 定义1&#xff1a; 否定联结词定义2&#xff1a; 合取联结词定义3&#xff1a; 析取联结词定义4&#xff1a; 异或联结词1.1.3 条件语句 定义5&#xff1a; 条件语句定义6&#xff1a; 双条件语句1.1.1 命题 1.命题&#xff1a;是…...

Rust FFI 与C语言互相调用

参考 https://cloud.tencent.com/developer/article/2077534 https://github.com/shepmaster/rust-ffi-omnibus cbindgen 简介 二进制方式构建 $ cargo install cbindgen //默认构建C头文件 C语言需要 --lang C $ cd /path/to/my/project && cbindgen . -o target/…...

从全局变量寻找到Tomcat回显方式

前言 对于回显的获取主要是在ApplicationFilterChain类的lastServicedRequest / lastServicedResponse两个属性&#xff0c;是使用的ThreadLocal进行修饰的&#xff0c;并且&#xff0c;在执行请求的过程中&#xff0c;通过反射修改属性值&#xff0c;能够记录下当前线程的req…...

Tapdata Connector 实用指南:数据入仓场景之数据实时同步到 BigQuery

【前言】作为中国的 “Fivetran/Airbyte”, Tapdata 是一个以低延迟数据移动为核心优势构建的现代数据平台&#xff0c;内置 60 数据连接器&#xff0c;拥有稳定的实时采集和传输能力、秒级响应的数据实时计算能力、稳定易用的数据实时服务能力&#xff0c;以及低代码可视化操作…...

关于机器人状态估计(12)-VIO/VSLAM的稀疏与稠密

VIO三相性与世界观室内ALL IN ONE 首先以此链接先对近期工作的视频做个正经的引流&#xff0c;完成得这么好的效果&#xff0c;仅仅是因为知乎限流1分钟以内的视频&#xff0c;导致整个浏览量不到300&#xff0c;让人非常不爽。 这套系统已经完成了&#xff0c;很快将正式发布…...

Python每日一练(20230220)

目录 1. 存在重复元素 II 2. 按要求实现程序功能 3. 分割链表 附录 链表 1. 存在重复元素 II 给定一个整数数组和一个整数 k&#xff0c;判断数组中是否存在两个不同的索引 i 和 j&#xff0c;使得 nums [i] nums [j]&#xff0c;并且 i 和 j 的差的 绝对值 至多为 k。 …...

技术总监的“技术提升”

技术负责人的能力要求是什么?成本中心技术负责人最重要的工作是让其他CXO理解、认可并且支持技术部的工作&#xff0c;否则作为成本部门&#xff0c;在公司的地位会很低。技术创新光是让其他部门理解还不行&#xff0c;技术还需要创造价值&#xff0c;所以需要做技术创新。上面…...

kettle安装部署_简单认识_Spoon勺子界面---大数据之kettle工作笔记002

然后我们来看一下这个kettle的安装,很简单,下载解压就可以了 上面的地址是官网很烂 下面的地址好一些 这个是官网可以看到很慢,很不友好 这个是下面那个地址,可以看到 最新的是9.0了,一般都用 一般都用8.2 这里下载这个就可以了 下载以后可以看到有个pdi...

第三章 Kafka生产问题总结及性能优化实践

第三章 Kafka生产问题总结及性能优化实践 1、线上环境规划 JVM参数设置 kafka 是 scala 语言开发&#xff0c;运行在 JVM 上&#xff0c;需要对 JVM 参数合理设置&#xff0c;参看 JVM 调优专题 修改 bin/kafka-start-server.sh 中的 JVM 设置&#xff0c;假设机器是 32G 内…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

多模态图像修复系统:基于深度学习的图片修复实现

多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...

认识CMake并使用CMake构建自己的第一个项目

1.CMake的作用和优势 跨平台支持&#xff1a;CMake支持多种操作系统和编译器&#xff0c;使用同一份构建配置可以在不同的环境中使用 简化配置&#xff1a;通过CMakeLists.txt文件&#xff0c;用户可以定义项目结构、依赖项、编译选项等&#xff0c;无需手动编写复杂的构建脚本…...