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

7.6分割回文串(LC131-M)

算法:

有很多分割结果,按照for循环去做肯定做不来

这个时候就要想到回溯!那就要画树!

画树

分割的画树过程其实和组合很像。

例如对于字符串aab:

  • 组合问题:选取一个a之后,在ab中再去选取第二个,选取a之后b中再选取第三个.....。
  • 切割问题:切割一个a之后,在ab中再去切割第二段,切割a之后在b再切割第三段.....。

回溯三部曲:

1.确定返回值和参数

返回值:void

参数:

string s 题目自带的

int startindex 确定每次递归从哪个字符开始切割

2.确定终止条件

切割到字符串最后,就是终止

startindex就是切割线:

startindex >= s.length()

并且要收集结果

3.单层递归逻辑:

子串怎么表示的?

答:[startindex, i]

i是这样定义的:

for (int i = startIndex; i < s.length(); i++)

收集结果:

若子串是回文(要定义一个新的函数,判断子串是否为回文),

将子串add入path,收集

若不是回文,continue,跳出该递归

递归:

注意切割过的位置,不能重复切割,所以,backtracking(s, i + 1); 传入下一层的起始位置为i + 1

backtracking (s, i+1)

回溯:

弹出本次已经添加的子串

path.removeLast()

判断回文子串

最后我们看一下回文子串要如何判断了,判断一个字符串是否是回文。

可以使用双指针法,一个指针从前向后,一个指针从后向前,如果前后指针所指向的元素是相等的,就是回文字符串了。

调试过程:

第一次调试:

class Solution {//全局变量path和resultList<List<String>> result = new LinkedList<>();List<String> path = new LinkedList<>();public List<List<String>> partition(String s) {backtracking (s, 0);return result;}void backtracking (String s, int startindex){//终止条件,收集结果if (startindex >= s.length()){result.add(new LinkedList (path));return;}//单层递归逻辑//判断子串是否为回文if (isplalindrome (s, startindex, i)){//若是,加入pathpath.add (s[startindex, i]);}else {continue;}//递归backtracking (s, i+1);//回溯path.removeLast();}//判断回文plalindrome,左闭右闭boolean isplalindrome (String s, int start, int end){//双指针法for (int i, int j; i <= s.length(), j >=i; i++, j--){if (s[i] == s[j]) return true;return false;}}
}

原因:

1.path.add (s[startindex, i]);` 这一行存在语法错误。想要将子串添加到 `path` 列表中。为了修正这个问题,应该使用 `substring` 方法而不是方括号。修正后的代码应该是:path.add(s.substring(startIndex, i + 1));

在Java中,方括号主要用于数组的索引访问,而不用于提取子串(方括号是适用于python的,java不能用)。

对于字符串提取子串,可以使用`substring`方法,该方法接受起始索引和结束索引作为参数,以提取指定范围内的子串。[左闭右开)

String str = "Hello, World!";  
String sub = str.substring(startIndex, endIndex);  

在这里,`str`是要提取子串的字符串,`startIndex`是子串的起始索引,`endIndex`是子串的结束索引(不包括在内)。提取的子串将包括从`startIndex``endIndex-1`的字符。

因此,在您的代码中,`path.add(s.substring(startIndex, i + 1));`将会提取`s`字符串中从`startIndex``i`(包括`i`)的子串,并将其添加到`path`列表中。

2.`isPalindrome` 方法中的for循环存在几个语法错误。看起来您想要在for循环中声明和初始化多个变量,但是语法是不正确的。让我们进行以下更正:

for (int i = start, j = end; i <= j; i++, j--) {  // ... (代码的其余部分)  
}  

在 Java 中,当在 for 循环中声明多个变量时,不需要在每个变量前都加上 `int`

在 for 循环的初始化部分,只需要在第一个变量声明前加上类型,而后续的变量声明则只需要写变量名和初始值即可。

修改后:

原因:单层递归时忘记加for循环了

第二次调试:

原因:

string不能用方括号

应改为:

s.charAt(i) == s.charAt(j)

第三次调试:

原因:把字符串本身也输出了。

主要问题在判断回文的逻辑上

判断是否为xxx,一定要先判错!有错即错!

当发现不是回文,就要立刻false;有不对的就不往下遍历了。一旦我们找到了一个不同的字符对,我们就可以确定这个字符串不是回文,因此可以立即返回 `false`。这样可以提前结束检查,因为一旦发现不匹配,就不需要继续向后检查。

我原来判断的是,先判断前后是否相等,若相等,则true。

假设字符串是 “abca”。如果我们在检查第一个和最后一个字符相等时就提前返回 `true`那么我们会错误地认为 “abca” 是一个回文字符串,因为我们没有检查中间的字符。而且,当我们找到不同的字符时,就无法及时结束检查,而需要继续检查下去,这会降低算法的效率。

正确代码:

class Solution {//全局变量path和resultList<List<String>> result = new LinkedList<>();List<String> path = new LinkedList<>();public List<List<String>> partition(String s) {backtracking (s, 0);return result;}void backtracking (String s, int startindex){//终止条件,收集结果if (startindex >= s.length()){result.add(new LinkedList (path));return;}//单层递归逻辑//判断子串是否为回文for (int i=startindex; i<s.length();i++){ if (isplalindrome (s, startindex, i)){//若是,加入pathpath.add(s.substring(startindex, i+1));}else {continue;}//递归backtracking (s, i+1);//回溯path.removeLast();}}//判断回文plalindrome,左闭右闭boolean isplalindrome (String s, int start, int end){//双指针法for (int i=start, j=end; j >=i; i++, j--){if (s.charAt(i) != s.charAt(j)) return false;   }return true;}
}

时间空间复杂度:

相关文章:

7.6分割回文串(LC131-M)

算法&#xff1a; 有很多分割结果&#xff0c;按照for循环去做肯定做不来 这个时候就要想到回溯&#xff01;那就要画树&#xff01; 画树 分割的画树过程其实和组合很像。 例如对于字符串aab&#xff1a; 组合问题&#xff1a;选取一个a之后&#xff0c;在ab中再去选取第…...

stata回归结果输出中,R方和F值到底是用来干嘛的?

先直接回答问题&#xff0c;R方表示可决系数&#xff0c;反映模型的拟合优度&#xff0c;也就是模型的解释能力如何&#xff0c;也可以理解为模型中的各个解释变量联合起来能够在多大程度上解释被解释变量&#xff1b;F值用于模型整体的统计显著性&#xff0c;对应的P值越小&am…...

Windows搭建RTMP视频流服务(Nginx服务器版)

文章目录 引言1、安装FFmpeg2、安装Nginx服务器3、实现本地视频推流服务4、使用VLC或PotPlayer可视化播放器播放视频5、RTSP / RTMP系列文章 引言 RTSP和RTMP视频流的区别 RTSP &#xff08;Real-Time Streaming Protocol&#xff09;实时流媒体协议。 RTSP定义流格式&#xff…...

IP地址SSL证书

IP地址SSL证书是一种专门针对公网IP地址颁发的数字证书。与常规的域名SSL证书类似&#xff0c;其主要目标是提供数据加密和身份验证。以下几点概述了IP地址SSL证书的重要特性及其申请过程&#xff1a; 1. 保护直接IP访问&#xff1a; 当用户直接通过IP地址访问服务时&#xff…...

关于“Python”的核心知识点整理大全49

目录 16.2.10 加亮颜色主题 16.3 小结 第&#xff11;7 章 使用API 17.1 使用 Web API 17.1.1 Git 和 GitHub 17.1.2 使用 API 调用请求数据 17.1.3 安装 requests 17.1.4 处理 API 响应 python_repos.py 注意 17.1.5 处理响应字典 python_repos.py import json i…...

爬虫学习(1)--requests模块的使用

前言 什么是爬虫 爬虫是一种自动化工具&#xff0c;用于从互联网或其他计算机网络上获取数据。它可以模拟人的行为&#xff0c;自动访问网页&#xff0c;提取感兴趣的数据&#xff0c;并将其存储到本地计算机或数据库中。爬虫通常用于搜索引擎、数据分析、信息聚合等领域&…...

【Vue2 + ElementUI】el-table中校验表单

一. 案例 校验金额 阐述&#xff1a;校验输入的金额是否正确。如下所示&#xff0c;点击【编辑图标】会变为input输入框当&#xff0c;输入金额。当输入框失去焦点时&#xff0c;若正确则调用接口更新金额且变为不可输入状态&#xff0c;否则返回不合法金额提示 <templat…...

PgSQL技术内幕 - ereport ERROR跳转机制

PgSQL技术内幕 - ereport ERROR跳转机制 使用客户端执行SQL的时候经常遇到报ERROR错误&#xff0c;然后SQL语句就退出了。当然&#xff0c;事务也会回滚掉。本文我们看下它是如何做到退出SQL语句并回滚事务的。 1、以insert一个numeric类型值为例 表一个字段为numeric(10,2)类型…...

【验证概括 SV的数据类型_2023.12.18】

验证概括 验证的过程是保证芯片实现符合规格说明书&#xff08;Specification&#xff0c;spec&#xff09;的过程 验证的两项任务&#xff1a; RTL sim&#xff1a;前仿真&#xff0c;验证功能 GLS-Gate (Level Simulation)&#xff1a;后仿真&#xff0c;验证功能和时序 验…...

如何在无公网IP环境下远程访问Serv-U FTP服务器共享文件

文章目录 1. 前言2. 本地FTP搭建2.1 Serv-U下载和安装2.2 Serv-U共享网页测试2.3 Cpolar下载和安装 3. 本地FTP发布3.1 Cpolar云端设置3.2 Cpolar本地设置 4. 公网访问测试5. 结语 1. 前言 科技日益发展的今天&#xff0c;移动电子设备似乎成了我们生活的主角&#xff0c;智能…...

电子工程师如何接私活赚外快?

对电子工程师来说&#xff0c;利用业余时间接私活是个很常见的技术&#xff0c;不仅可以赚取额外收入&#xff0c;也能提升巩固技术&#xff0c;可以说国内十个工程师&#xff0c;必有五个在接私活养家糊口&#xff0c;如果第一次接私活&#xff0c;该如何做&#xff1f; 很多工…...

数据库进阶教学——读写分离(Mycat1.6+Ubuntu22.04主+Win10从)

目录 1、概述 2、环境准备 3、读写分离实验 3.1、安装jdk 3.2、安装Mycat 3.3、配置Mycat 3.3.1、配置schema.xml ​​​​3.3.2、配置server.xml 3.4、修改主从机远程登陆权限 3.4.1、主机 3.4.2、从机 3.5、启动Mycat 3.6、登录Mycat 3.7、验证 1、概述 读写分…...

MidJourney笔记(9)-daily_theme-docs-describe

/daily_theme 切换 #daily-theme 频道更新的通知。 但我发现在对话框那里,是没有这个命令的: 但官网是有介绍,不知道是不是版本问题还是这个命令已经无效。 但后来,我发现这个命令是要在Midjourney服务对话框那里才有,在我们后面添加的Mid...

鸿蒙 - arkTs:网络请求封装和使用

1. module.json5文件配置网络请求 {"module": {"requestPermissions": [{"name": "ohos.permission.INTERNET"}]} } 2. 在pages同级创建一个文件夹&#xff0c;起名为api 3. api文件夹下创建index.ts文件&#xff0c;文件内容&…...

多功能演示工具ProVideoPlayer2 mac特色介绍

ProVideoPlayer2 mac是用于大多数任何生产的首选多功能演示工具。ProVideoPlayer 2是一种动态视频播放和处理媒体服务器&#xff0c;可将视频映射&#xff08;包括播放和实时视频输入&#xff09;实时控制到一个或多个输出。包括实时效果&#xff0c;调度&#xff0c;网络同步和…...

java设计模式学习之【责任链模式】

文章目录 引言责任链模式简介定义与用途实现方式 使用场景优势与劣势在Spring框架中的应用日志示例代码地址 引言 在现实生活中&#xff0c;常常会遇到这样的场景&#xff1a;一个请求或命令需要经过多个层级的处理。例如&#xff0c;一个行政审批流程可能需要通过多个部门的审…...

docker 安装可视化工具 Protainer 以及 汉化

一、创建保存数据的卷 安装网址&#xff1a;Install Portainer BE with Docker on Linux - Portainer Documentation docker pull portainer/portainer二、根据portainer镜像创建容器 docker run -d -p 8000:8000 -p 9000:9000\ --name portainer --restartalways \ -v /var/r…...

【SpringBoot篇】详解Bean的管理(获取bean,bean的作用域,第三方bean)

文章目录 &#x1f354;Bean的获取&#x1f384;注入IOC容器对象⭐代码实现&#x1f6f8;根据bean的名称获取&#x1f6f8;根据bean的类型获取&#x1f6f8;根据bean的名称和类型获取 &#x1f384;Bean的作用域⭐代码实现&#x1f388;注意 &#x1f384;第三方Bean⭐代码实现…...

彭涛:2023年终复盘,工作,团队,个人!

眨眼2023即将结束&#xff0c;2024即将开启&#xff0c;每年这个时候&#xff0c;都会简单总结下自己这一年&#xff0c;既是对今年的一个复盘和回顾&#xff0c;也是对新一年的向往和期待。 我的2023年&#xff0c;大概分为 「个人」&#xff0c;「家庭」&#xff0c;「团队」…...

【数据结构和算法】---二叉树(2)--堆的实现和应用

目录 一、堆的概念及结构二、堆结构的实现2.1堆向下调整算法2.2堆向上调整算法2.3删除堆顶元素2.4插入元素2.5其他函数接口 三、堆结构的应用3.1堆排序3.2Top-k问题 四、堆概念及结构相关题目 一、堆的概念及结构 如果有一个数字集合&#xff0c;并把它的所有元素按完全二叉树…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...