代码随想录算法训练营第二十八天| 93.复原IP地址,78.子集,90.子集II

本文主要是介绍代码随想录算法训练营第二十八天| 93.复原IP地址,78.子集,90.子集II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 题目与题解

93.复原IP地址

题目链接:93.复原IP地址

代码随想录题解:93.复原IP地址

视频讲解:回溯算法如何分割字符串并判断是合法IP?| LeetCode:93.复原IP地址_哔哩哔哩_bilibili

解题思路:

        这道题跟之前做回文分割的题总体思路差不多,不一样的地方在于判断分割结果是否合法的条件,以及因此产生的剪枝方法。

        递归三部曲:

        参数包括输出的结果result,中途用于记录分割结果的list,以及每一轮递归起点startIndex

        终止条件为:已经分割完成(startIndex >= s.length())且分割结果符合ip地址要求,则将list中的每一位取出,组合成string的ip地址,并将其加入result,否则继续下一次的单层遍历。

        单层遍历逻辑:取从startIndex到i(startIndex <= i < s.length())之间的子字符串,将其加入list,然后递归的调用i+1之后的字符串,再将刚刚的子字符串弹出。

        剪枝:ip地址一共有四位,所以当list中的元素已经有4位,但是不满足终止条件时,可以直接return进行下一次递归;另外,ip地址每一部分最多有三位,所以i < startIndex+3即可

        判断ip地址是否符合要求:首先list中的元素必须是四个,其次每个元素必须在0-255之间,如果该元素不是0而且开头为0,则不符合要求。

总体代码如下:

class Solution { List<String> result = new ArrayList<>();LinkedList<String> address = new LinkedList<>();public List<String> restoreIpAddresses(String s) {restoreIpAddresses(s, 0);return result;}public void restoreIpAddresses(String s, int startIndex) {if (startIndex >= s.length() && isIpAddress(address)) {StringBuilder currentAddress = new StringBuilder();for (int i = 0; i < address.size(); i++) {if (!"".contentEquals(currentAddress))currentAddress.append(".");currentAddress.append(address.get(i));}result.add(new String(currentAddress));return;}if (address.size() >= 4) return;for (int i = startIndex; i < s.length() && i < startIndex + 3; i++) {String partAddress = s.substring(startIndex, i+1);address.add(partAddress);restoreIpAddresses(s, i+1);address.pollLast();}}public boolean isIpAddress(List<String> address) {if (address.size() != 4) return false;for (int i = 0; i < address.size(); i++) {String num = address.get(i);if (num.length() > 1 && num.charAt(0) == '0'|| num.length() > 3 || num.length() < 1)return false;int number = Integer.parseInt(num);if (number > 255 || number < 0) return false;}return true;}
}

看完代码随想录之后的想法 

        基本思路差的不多,细节上有些做法不一样。比如随想录用逗点数量是否为3判断分割是否完成,这样可以边拼接生成字符串边判断其是否符合要求,效率更高一点,不过随之的递归和删除元素都要注意逗点,递归时要用i+2而非i+1,回溯删除也要删除逗点。

        判断子串是否合法时,虽然题目说了输入的是一串数字,但是为了严谨,还说应该在判断ip地址时先判断一下每个字符是否都是数字,防止输入错误。

参考答案:

class Solution {List<String> result = new ArrayList<>();public List<String> restoreIpAddresses(String s) {if (s.length() > 12) return result; // 算是剪枝了backTrack(s, 0, 0);return result;}// startIndex: 搜索的起始位置, pointNum:添加逗点的数量private void backTrack(String s, int startIndex, int pointNum) {if (pointNum == 3) {// 逗点数量为3时,分隔结束// 判断第四段⼦字符串是否合法,如果合法就放进result中if (isValid(s,startIndex,s.length()-1)) {result.add(s);}return;}for (int i = startIndex; i < s.length(); i++) {if (isValid(s, startIndex, i)) {s = s.substring(0, i + 1) + "." + s.substring(i + 1);    //在str的后⾯插⼊⼀个逗点pointNum++;backTrack(s, i + 2, pointNum);// 插⼊逗点之后下⼀个⼦串的起始位置为i+2pointNum--;// 回溯s = s.substring(0, i + 1) + s.substring(i + 2);// 回溯删掉逗点} else {break;}}}// 判断字符串s在左闭⼜闭区间[start, end]所组成的数字是否合法private Boolean isValid(String s, int start, int end) {if (start > end) {return false;}if (s.charAt(start) == '0' && start != end) { // 0开头的数字不合法return false;}int num = 0;for (int i = start; i <= end; i++) {if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到⾮数字字符不合法return false;}num = num * 10 + (s.charAt(i) - '0');if (num > 255) { // 如果⼤于255了不合法return false;}}return true;}
}
//方法一:但使用stringBuilder,故优化时间、空间复杂度,因为向字符串插入字符时无需复制整个字符串,从而减少了操作的时间复杂度,也不用开新空间存subString,从而减少了空间复杂度。
class Solution {List<String> result = new ArrayList<>();public List<String> restoreIpAddresses(String s) {StringBuilder sb = new StringBuilder(s);backTracking(sb, 0, 0);return result;}private void backTracking(StringBuilder s, int startIndex, int dotCount){if(dotCount == 3){if(isValid(s, startIndex, s.length() - 1)){result.add(s.toString());}return;}for(int i = startIndex; i < s.length(); i++){if(isValid(s, startIndex, i)){s.insert(i + 1, '.');backTracking(s, i + 2, dotCount + 1);s.deleteCharAt(i + 1);}else{break;}}}//[start, end]private boolean isValid(StringBuilder s, int start, int end){if(start > end)return false;if(s.charAt(start) == '0' && start != end)return false;int num = 0;for(int i = start; i <= end; i++){int digit = s.charAt(i) - '0';num = num * 10 + digit;if(num > 255)return false;}return true;}
}//方法二:比上面的方法时间复杂度低,更好地剪枝,优化时间复杂度
class Solution {List<String> result = new ArrayList<String>();StringBuilder stringBuilder = new StringBuilder();public List<String> restoreIpAddresses(String s) {restoreIpAddressesHandler(s, 0, 0);return result;}// number表示stringbuilder中ip段的数量public void restoreIpAddressesHandler(String s, int start, int number) {// 如果start等于s的长度并且ip段的数量是4,则加入结果集,并返回if (start == s.length() && number == 4) {result.add(stringBuilder.toString());return;}// 如果start等于s的长度但是ip段的数量不为4,或者ip段的数量为4但是start小于s的长度,则直接返回if (start == s.length() || number == 4) {return;}// 剪枝:ip段的长度最大是3,并且ip段处于[0,255]for (int i = start; i < s.length() && i - start < 3 && Integer.parseInt(s.substring(start, i + 1)) >= 0&& Integer.parseInt(s.substring(start, i + 1)) <= 255; i++) {// 如果ip段的长度大于1,并且第一位为0的话,continueif (i + 1 - start > 1 && s.charAt(start) - '0' == 0) {continue;}stringBuilder.append(s.substring(start, i + 1));// 当stringBuilder里的网段数量小于3时,才会加点;如果等于3,说明已经有3段了,最后一段不需要再加点if (number < 3) {stringBuilder.append(".");}number++;restoreIpAddressesHandler(s, i + 1, number);number--;// 删除当前stringBuilder最后一个网段,注意考虑点的数量的问题stringBuilder.delete(start + number, i + number + 2);}}
}

遇到的困难

        一开始想用逗点作判断的,但是在回溯的时候没考虑清楚在有逗点的条件下如何递归和删除元素,出错了很多次,后来放弃了直接拼接字符串进行判断的方法,转成list以后增删元素会轻松很多。

        判断是否终止既可以写在递归函数里面,也可以写在判断是否是ip地址的函数里,本质是一样的。这题难点在于要考虑的点很全面,容易写错,即使把N叉树画出来了,也得注意条件边界。

78.子集

题目链接:78.子集

代码随想录题解:78.子集

视频讲解:回溯算法解决子集问题,树上节点都是目标集和! | LeetCode:78.子集_哔哩哔哩_bilibili

解题思路:

        这一题跟前面做的组合问题非常相似,属于换汤不换药的题,不同点在于这里是允许空集出现的,也就是说,画N叉树时,每一层可以有一个叶子的元素为空。

        递归三部曲逻辑也很简单,参数同样有result,list,startIndex,这里不需要终止条件,因为终止条件实际上是startIndex>=nums.length,与后面单层遍历的边界条件相同,所以每次一进入回溯函数就直接将当前list加入result再返回即可,单层遍历只需要每次将当前nums[i]加入list,并用startIndex=i+1调用递归函数,出来时弹出nums[i]即可。

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> list = new LinkedList<>();public List<List<Integer>> subsets(int[] nums) {subsets(nums, 0);return result;}void subsets(int[] nums, int startIndex) {result.add(new ArrayList<>(list));for (int i = startIndex; i < nums.length; i++) {list.add(nums[i]);subsets(nums, i + 1);list.pollLast();}}
}

看完代码随想录之后的想法 

        如果把 子集问题、组合问题、分割问题都抽象为一棵树的话,那么组合问题和分割问题都是收集树的叶子节点,而子集问题是找树的所有节点!

        那么既然是无序,取过的元素不会重复取,写回溯算法的时候,for就要从startIndex开始,而不是从0开始!求排列问题的时候,就要从0开始。

遇到的困难

        无

90.子集II

题目链接:​​​​​​​90.子集II

代码随想录题解:90.子集II

视频讲解:回溯算法解决子集问题,如何去重?| LeetCode:90.子集II_哔哩哔哩_bilibili

解题思路:

        这题就是在上一题的基础上,加了去重的操作,而去重的题目在之前做组合的时候也做过了,所以函数都是非常简单的。

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> list = new LinkedList<>();public List<List<Integer>> subsetsWithDup(int[] nums) {Arrays.sort(nums);subsetsWithDup(nums, 0);return result;}void subsetsWithDup(int[] nums, int startIndex) {result.add(new ArrayList<>(list));for (int i = startIndex; i < nums.length; i++) {if (i > startIndex && nums[i] == nums[i-1]) continue;list.add(nums[i]);subsetsWithDup(nums, i + 1);list.pollLast();}}
}

看完代码随想录之后的想法 

        可以用used数组来去重,也可以像我写的一样直接通过前后元素是否相同去重。

遇到的困难

        无

今日收获

        继续巩固回溯算法,除了判断ip地址这种涉及条件较多的分割问题比较难,其他都是换汤不换药的重复题,掌握套路都很简单。

这篇关于代码随想录算法训练营第二十八天| 93.复原IP地址,78.子集,90.子集II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/875915

相关文章

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN

Java实现自定义table宽高的示例代码

《Java实现自定义table宽高的示例代码》在桌面应用、管理系统乃至报表工具中,表格(JTable)作为最常用的数据展示组件,不仅承载对数据的增删改查,还需要配合布局与视觉需求,而JavaSwing... 目录一、项目背景详细介绍二、项目需求详细介绍三、相关技术详细介绍四、实现思路详细介绍五、完整实现代码

Go语言代码格式化的技巧分享

《Go语言代码格式化的技巧分享》在Go语言的开发过程中,代码格式化是一个看似细微却至关重要的环节,良好的代码格式化不仅能提升代码的可读性,还能促进团队协作,减少因代码风格差异引发的问题,Go在代码格式... 目录一、Go 语言代码格式化的重要性二、Go 语言代码格式化工具:gofmt 与 go fmt(一)

HTML5实现的移动端购物车自动结算功能示例代码

《HTML5实现的移动端购物车自动结算功能示例代码》本文介绍HTML5实现移动端购物车自动结算,通过WebStorage、事件监听、DOM操作等技术,确保实时更新与数据同步,优化性能及无障碍性,提升用... 目录1. 移动端购物车自动结算概述2. 数据存储与状态保存机制2.1 浏览器端的数据存储方式2.1.

基于 HTML5 Canvas 实现图片旋转与下载功能(完整代码展示)

《基于HTML5Canvas实现图片旋转与下载功能(完整代码展示)》本文将深入剖析一段基于HTML5Canvas的代码,该代码实现了图片的旋转(90度和180度)以及旋转后图片的下载... 目录一、引言二、html 结构分析三、css 样式分析四、JavaScript 功能实现一、引言在 Web 开发中,

Spring Boot 实现 IP 限流的原理、实践与利弊解析

《SpringBoot实现IP限流的原理、实践与利弊解析》在SpringBoot中实现IP限流是一种简单而有效的方式来保障系统的稳定性和可用性,本文给大家介绍SpringBoot实现IP限... 目录一、引言二、IP 限流原理2.1 令牌桶算法2.2 漏桶算法三、使用场景3.1 防止恶意攻击3.2 控制资源

Python如何去除图片干扰代码示例

《Python如何去除图片干扰代码示例》图片降噪是一个广泛应用于图像处理的技术,可以提高图像质量和相关应用的效果,:本文主要介绍Python如何去除图片干扰的相关资料,文中通过代码介绍的非常详细,... 目录一、噪声去除1. 高斯噪声(像素值正态分布扰动)2. 椒盐噪声(随机黑白像素点)3. 复杂噪声(如伪