代码随想录 回溯算法-分割

news/2024/4/19 13:22:11/文章来源:https://blog.csdn.net/m0_74267125/article/details/136520160

目录

131.分割回文串 

93.复原IP地址 


131.分割回文串 

131. 分割回文串

中等

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1:

输入:s = "aab"
输出:[["a","a","b"],["aa","b"]]

示例 2:

输入:s = "a"
输出:[["a"]]

提示:

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成

其实切割问题类似组合问题

例如对于字符串abcdef:

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

 解读题意:每存在一种方式可将字符串分割为回文子串时,就将分割好的回文子串存到一个List集合中,再存入List结果集合中

// Solution类,包含了分割字符串为回文子串的方法  
class Solution {  // 用于存储所有可能的分割方案,每个方案是一个字符串列表  List<List<String>> lists = new ArrayList<>();  // 用于临时存储当前分割方案的回文子串  List<String> substring = new ArrayList<>();  // public方法,接收一个字符串s,返回所有可能的回文子串分割方案  public List<List<String>> partition(String s) {  // 调用回溯方法开始分割字符串  backTracking(s, 0);  // 返回所有分割方案  return lists;  }  // 私有方法,使用回溯法分割字符串  private void backTracking(String s, int startIndex) {  // 如果起始位置超过了字符串的长度,说明已经找到了一个完整的分割方案  if (startIndex == s.length()) {  // 将当前方案添加到结果列表中(注意这里要添加deque的副本)  lists.add(new ArrayList<>(substring));  return;  }  // 遍历从起始位置到字符串末尾的每个位置  for (int i = startIndex; i < s.length(); i++) {  // 检查从startIndex到i的子串是否是回文的  if (isPalindrome(s, startIndex, i)) {  // 如果是回文子串,则添加到当前方案中  String str = s.substring(startIndex, i + 1);  substring.add(str);  } else {  // 如果不是回文子串,则跳过当前位置,继续向后检查  continue;  }  // 回溯,将起始位置后移一位,继续寻找下一个回文子串  backTracking(s, i + 1);  // 回溯,移除当前方案中的最后一个回文子串,尝试其他可能性  substring.removeLast();  }  }  // 私有辅助方法,用于判断一个子串是否是回文的  private boolean isPalindrome(String s, int startIndex, int end) {  // 使用双指针法,一个指针从起始位置开始,另一个指针从结束位置开始  for (int i = startIndex, j = end; i < j; i++, j--) {  // 如果两个指针指向的字符不相等,则子串不是回文的  if (s.charAt(i) != s.charAt(j)) {  return false;  }  }  // 如果所有字符都相等,则子串是回文的  return true;  }  
}

93.复原IP地址 

93. 复原 IP 地址

中等

有效 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 '.' 分隔。

  • 例如:"0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址,但是 "0.011.255.245""192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ,用以表示一个 IP 地址,返回所有可能的有效 IP 地址,这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1:

输入:s = "25525511135"
输出:["255.255.11.135","255.255.111.35"]

示例 2:

输入:s = "0000"
输出:["0.0.0.0"]

示例 3:

输入:s = "101023"
输出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示:

  • 1 <= s.length <= 20
  • s 仅由数字组成

 

class Solution {  List<String> result = new ArrayList<>(); // 用于存放所有可能的IP地址  StringBuilder builder = new StringBuilder(); // 用于构建当前的IP地址  public List<String> restoreIpAddresses(String s) {  backtracking(s, 0, 0); // 从字符串的开头开始回溯,还没有任何段被选择  return result; // 返回所有可能的IP地址列表  }  public void backtracking(String s, int begin, int numCount) {  // 如果已经遍历完整个字符串,并且已经选择了4个段,说明找到了一个可能的IP地址  if (begin == s.length() && numCount == 4) {  result.add(builder.toString());  return;  }  // 如果已经遍历完整个字符串,或者已经选择了4个段,但字符串还没有遍历完,说明当前路径不可能构成IP地址  if (begin == s.length() || numCount == 4) {  return;  }  // 遍历可能的段结束位置  for (int i = begin; i < s.length(); i++) {  // 检查当前子串是否可以作为一个IP地址的段  if (isvalid(s, begin, i)) {  // 将当前段添加到构建器中  builder.append(s.substring(begin, i + 1));  numCount++; // 已选段数加一  // 如果当前选择的段数小于4,说明还需要继续选择段,因此添加一个点作为分隔符  if (numCount < 4) {  builder.append(".");  }  // 继续回溯,选择下一个段  backtracking(s, i + 1, numCount);  // 回溯,删除当前段以及分隔的点(如果存在)  // 注意:删除的是当前段的最后一个字符到构建器末尾的所有字符,即整个段和可能存在的点  //从开始位置+加入的点的位置开始builder.delete(begin + numCount - 1, builder.length());  numCount--; // 已选段数减一  } else {  // 如果当前子串不能作为一个IP地址的段,则跳出循环,尝试下一个可能的开始位置 //如果不是一段有几种情况,长度大于一且0开头,数字大于255,长度大于3,往下遍历没有意义 break;  }  }  }  //这里的begin和end是左闭右闭的区间  public boolean isvalid(String s, int begin, int end) {  // 如果开始位置大于结束位置,说明子串为空,不是有效的段  if (begin > end) {  return false;  }  // 如果子串表示的整数大于255,不是有效的段  if (Integer.parseInt(s.substring(begin, end + 1)) > 255) {  return false;  }  // 如果子串长度大于3,不是有效的段(IP地址段最多3位数字)  if (end - begin + 1 > 3) {  return false;  }  // 如果子串以0开头且长度大于1(除了单个0的情况),不是有效的段  if (s.charAt(begin) == '0' && end - begin > 0) {  return false;  }  // 如果以上条件都不满足,说明子串是一个有效的段  return true;  }  
}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_997464.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【PHP+代码审计】PHP基础——变量和常量的定义和使用

&#x1f36c; 博主介绍&#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 hacker-routing &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【应急响应】 【Java、PHP】 【VulnHub靶场复现】【面试分析】 &#x1f389;点赞➕评论➕收…

【算法沉淀】刷题笔记:并查集 带权并查集+实战讲解

&#x1f389;&#x1f389;欢迎光临&#x1f389;&#x1f389; &#x1f3c5;我是苏泽&#xff0c;一位对技术充满热情的探索者和分享者。&#x1f680;&#x1f680; &#x1f31f;特别推荐给大家我的最新专栏《数据结构与算法&#xff1a;初学者入门指南》&#x1f4d8;&am…

使用modinfo对比内核版本号

加载内核&#xff0c;出现版本不一样 cat /proc/verison查看内核板本 模块版本&#xff1a;显示模块的版本号。 $ modinfo [OPTIONS] [MODULE] 参数说明-F, --field <field>: 指定要显示的字段&#xff0c;可以使用逗号分隔多个字段。-k, --kernel <kernel>: 指定…

如何解决微服务的数据一致性分发问题?

介绍 系统架构微服务化以后,根据微服务独立数据源的思想,每个微服务一般具有各自独立的数据源,但是不同微服务之间难免需要通过数据分发来共享一些数据,这个就是微服务的数据分发问题。Netflix/Airbnb等一线互联网公司的实践[参考附录1/2/3]表明,数据一致性分发能力,是构…

OpenHarmony教程指南—ArkUI中组件、通用、动画、全局方法的集合

介绍 本示例为ArkUI中组件、通用、动画、全局方法的集合。 本示例使用 Tabs容器组件搭建整体应用框架&#xff0c;每个 TabContent内容视图 使用 div容器组件 嵌套布局&#xff0c;在每个 div 中使用 循环渲染 加载此分类下分类导航数据&#xff0c;底部导航菜单使用 TabCont…

基于springboot+vue的企业员工薪酬关系系统

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、阿里云专家博主、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战&#xff0c;欢迎高校老师\讲师\同行交流合作 ​主要内容&#xff1a;毕业设计(Javaweb项目|小程序|Pyt…

【Spring底层原理高级进阶】Spring Batch清洗和转换数据,一键处理繁杂数据!Spring Batch是如何实现IO流优化的?本文详解!

&#x1f389;&#x1f389;欢迎光临&#xff0c;终于等到你啦&#x1f389;&#x1f389; &#x1f3c5;我是苏泽&#xff0c;一位对技术充满热情的探索者和分享者。&#x1f680;&#x1f680; &#x1f31f;持续更新的专栏《Spring 狂野之旅&#xff1a;从入门到入魔》 &a…

猫毛过敏又不想扔掉猫怎么办?如何养猫?热门宠物空气净化器分享

养了猫咪一年多&#xff0c;忽然发现自己患上了过敏性鼻炎和结膜炎&#xff0c;就是那种一靠近猫咪就会不断打喷嚏、流鼻涕、流眼泪的症状。有时候还会感到眼睛发痒&#xff0c;发红。有没有什么好的方法治疗过敏性鼻炎呢&#xff1f; 医生建议&#xff0c;从根本上解决问题需…

【C++ 编程指南】

C 编程指南 ■ C环境安装■ C 基本语法■ 预定义宏■ # 和 ## 运算符■ C 引用■ C 命名空间■ 定义命名空间■ using 指令■ 嵌套的命名空间 ■ String类■ 类■ 类的static静态成员 ■ C 继承■ 继承类型 public、protected 或 private■ 访问控制和继承■ 多继承■ 数据抽象…

微信小程序-生命周期

页面生命周期 onLoad: 页面加载时触发的方法&#xff0c;在这个方法中可以进行页面初始化的操作&#xff0c;如获取数据、设置页面状态等。 onShow: 页面显示时触发的方法&#xff0c;在用户进入页面或从其他页面返回该页面时会调用此方法。可以在此方法中进行页面数据刷新、动…

医药行业五大难题深度剖析:CRM解决方案助力突围

医疗行业关系着民生、经济乃至战备&#xff0c;是国民经济的重要组成部分。虽然近20年来我国医疗行业年均增长率维持在15%之上&#xff0c;但行业发展仍存在诸多问题。引进CRM管理系统可能是一个行之有效的解决方法。文中将为您整理医疗行业目前的五大挑战&#xff0c;以及CRM如…

MPLS(多协议标签交换)-基础原理与配置

标签交换--包交换&#xff08;路由数据传递) 数据包在进入到的 MPLS 的域内后.转发该数据包时&#xff0c;最初在包交换仅支持原始交换时 将在第2层和3层中间压入标签号&#xff0c;使得域内的路由器在基于 2.5 层的标签号仅需要查询本地的一张(LFIB 表(标签转发信息数据库) 标…

01背包问题 刷题笔记

思路 dp 用f[i][j]来表示当体积为j时 考虑前i件物品可以获得的 最大值 记住f[i][j]本身是个价“价值” 考虑两种状态 是否将第i件物品放入背包里面 将背包的体积从小到大递增来进行考虑 首先 考虑条件 如果当前增加的体积放不下下一件物品 则该体积 可以获得的最大值可以直接…

c++复习

基础 内存分区 栈&#xff1a; 存放函数的局部变量、函数参数、返回地址等&#xff0c;由编译器自动分配和释放。 堆&#xff1a; 动态申请的内存空间&#xff0c;就是由 malloc 分配的内存块&#xff0c;由程序员控制它的分配和释放&#xff0c;如果程序执行结束还没有释放…

YOLO-World:实时开放词汇目标检测

摘要 Open Vocabulary&#xff1a;开放词汇 论文链接&#xff1a;https://arxiv.org/pdf/2401.17270.pdf You Only Look Once (YOLO) 系列检测器已经确立了自己作为高效和实用工具的地位。然而&#xff0c;它们对预定义和训练过的对象类别的依赖限制了它们在开放场景中的适用…

在多文件编译时,如果模板类的成员函数的定义和模板类不在一个文件下会怎么样?

编译器将找不到成员函数的定义&#xff0c;哪怕你将存放成员函数定义的test.cpp一块编译&#xff0c;编译器也无法找到该模板类的成员函数的定义。 正确的做法是&#xff1a; 将模板类的声明和成员函数定义都定义在.h文件下

数位dp 笔记

小技巧1:求区间[X, Y]可以转换为求F(Y) - F(X-1) F(X)表示0~X中满足条件的数字个数 小技巧2&#xff1a;可以用树的形式来看 遍历最高位&#xff0c;每一位分为两种情况&#xff1a;未达到上界和达到上界 如果走到右边最底端需加1 度的数量 求给定区间 [X,Y]中满足下列条件的…

Linux——线程同步互斥(线程安全)

线程互斥 进程线程间的互斥相关背景概念 临界资源&#xff1a;多线程执行流共享的资源就叫做临界资源临界区&#xff1a;每个线程内部&#xff0c;访问临界资源的代码&#xff0c;就叫做临界区互斥&#xff1a;任何时刻&#xff0c;互斥保证有且只有一个执行流进入临界区&…

System Verilog学习笔记(十八)——线程控制

线程控制 发生器把激励传给代理时&#xff0c;环境类需要知道发生器什么时候完成任务&#xff0c;以便及时终止测试平台中还在运行的线程&#xff0c;这个过程就需要借助线程间的通信来完成。常用的线程间通信有事件控制、wait语句、SV信箱和旗语等。 Verilog对语句有两种分组…

SpringCloud-数据认证加密总结

一、数据加密认证介绍 在当今分布式系统的日益复杂和信息传递的广泛网络化环境中&#xff0c;确保通信的安全性至关重要。数据的加密和认证作为保障信息传递安全的关键手段&#xff0c;在分布式系统中扮演着不可或缺的角色。Spring Cloud&#xff0c;作为一套构建微服务架构的…