回文子串的数量[寻找回文子串的完整思路过程]
寻找回文子串的完整思路过程
- 前言
- 一、回文串的数量
- 二、动态规划
- 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总结参考文献前言 回文字符串,就是从左遍历和从右遍历的字符是相同顺序的,转换一下,就是该字符串是对称的。寻找回文子串面临两个直接的问题,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
题目链接:https://leetcode.cn/problems/implement-stack-using-queues/ 1. 题目介绍(225. 用队列实现栈) 请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(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 库ÿ…...

中间件安全—Apache常见漏洞
中间件安全—Apache常见漏洞1.Apache常见漏洞1.1.Apache介绍1.2.Apache HTTPD 换行解析漏洞(CVE-2017-15715)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 对于我们所有的类对象进行了统一抽象,抽象为 BeanDefinition ,即 Bean 的定义,其中定义了类的全限定类名、加载机制、初始化方式、作用域等信息,用于对我们要自动装配的类进行生成。 Sprin…...
【DRF】Django Rest Framework(5.DRF中的通用视图类-GenericAPIView方法说明与使用说明)
1. GenericAPIView [通用视图类],概述 继承自 APIView增加了操作序列化器和数据库查询的方法,作用是为下面Mixin扩展类的执行提供方法支持。通常在使用时,可搭配一个或者多个Mixin扩展类源码 当我们查看 GenericAPIView 的源码时,…...

STM32 OTA应用开发——自制BootLoader
STM32 OTA应用开发——自制BootLoader 目录STM32 OTA应用开发——自制BootLoader前言1 环境搭建2 BootLoader工作原理以及常见分区介绍3 BootLoader的制作4 烧录下载配置5 运行测试结束语前言 什么是OTA? 百度百科:空中下载技术(Over-the-Ai…...
时域和频域的简单理解
目录文章背景结论举例说明说回频域连续或离散总结文章背景 时域和频域在傅里叶变换和拉普拉斯变换,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: 否定联结词定义2: 合取联结词定义3: 析取联结词定义4: 异或联结词1.1.3 条件语句 定义5: 条件语句定义6: 双条件语句1.1.1 命题 1.命题:是…...
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两个属性,是使用的ThreadLocal进行修饰的,并且,在执行请求的过程中,通过反射修改属性值,能够记录下当前线程的req…...

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

关于机器人状态估计(12)-VIO/VSLAM的稀疏与稠密
VIO三相性与世界观室内ALL IN ONE 首先以此链接先对近期工作的视频做个正经的引流,完成得这么好的效果,仅仅是因为知乎限流1分钟以内的视频,导致整个浏览量不到300,让人非常不爽。 这套系统已经完成了,很快将正式发布…...

Python每日一练(20230220)
目录 1. 存在重复元素 II 2. 按要求实现程序功能 3. 分割链表 附录 链表 1. 存在重复元素 II 给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] nums [j],并且 i 和 j 的差的 绝对值 至多为 k。 …...
技术总监的“技术提升”
技术负责人的能力要求是什么?成本中心技术负责人最重要的工作是让其他CXO理解、认可并且支持技术部的工作,否则作为成本部门,在公司的地位会很低。技术创新光是让其他部门理解还不行,技术还需要创造价值,所以需要做技术创新。上面…...

kettle安装部署_简单认识_Spoon勺子界面---大数据之kettle工作笔记002
然后我们来看一下这个kettle的安装,很简单,下载解压就可以了 上面的地址是官网很烂 下面的地址好一些 这个是官网可以看到很慢,很不友好 这个是下面那个地址,可以看到 最新的是9.0了,一般都用 一般都用8.2 这里下载这个就可以了 下载以后可以看到有个pdi...

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

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...

家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...

什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...

ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...
06 Deep learning神经网络编程基础 激活函数 --吴恩达
深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...