当前位置: 首页 > 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;并把它的所有元素按完全二叉树…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...