代码随想录Day28:回溯算法Part4

2024-04-04 15:04

本文主要是介绍代码随想录Day28:回溯算法Part4,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Leetcode 93. 复原IP地址

讲解前:

这道题其实在做完切割回文串之后,学会了使用切割的方法来找到字符串的possible 子串之后,思路就会很快找到,细想一下其实无非也就是对given string然后进行切割,只是深度是固定的因为ip只能有四组数字组成,也就是四个sub string,然后呢我们就需要找到所有的possible组合,并且确保组合中每一个substring是符合规则的

并且当我们发现在for循环中,这一整个循环的加入的第一个path都是0开头的长度大于1的substring 的时候,就可以break 整个loop,但是按照我目前的思路,这道题还是有太多细节需要处理,所以我觉得先看题解

讲解后:
 
class Solution:def restoreIpAddresses(self, s: str) -> List[str]:res = []path = []# helper function to check if the current substring# is a valid ip addressdef is_valid(string):if not string:return Falseif string[0] == '0' and len(string) > 1:return Falseelif int(string) > 255:return Falseelse:return Truedef backtracking(s, res, path, start_index, count):# base case# if we already added three substring to path# check the remaining one is valid or notprint(path, '-', count)if count == 3:last_string = s[start_index:]if is_valid(last_string):path.append(last_string)res.append('.'.join(path[:]))path.pop()count = count - 1return# recursive casefor i in range(start_index, len(s)):cur_string = s[start_index: i + 1]print(cur_string)if is_valid(cur_string):path.append(cur_string)count = count + 1backtracking(s, res, path, i + 1, count)path.pop()count = count - 1backtracking(s, res, path, 0, 0)return res 

听完了卡哥的讲解之后发现其实这道题没有那么复杂,关键就在于当对substring是否是一个valid的id进行检查的时候,既然检查的条件会比较多比较繁琐,那么就直接封装成一个函数就好了,然后呢思路就和其他切割字符串的题没区别了,就是检查每一个substring,如果符合要求,就在基础上继续递归找下一个符合条件的,唯一比较特殊的是,在base case中,这里我们只有三条切割线,最后第四个substring需要我们在找完三次之后直接取剩余的string作为第四个,所以在base case中我们还需要再对path进行一次添加,同时这里要注意,这一次添加也需要做回溯操作也就是对path进行pop以及减少count的值


Leetcode 78. 子集

讲解前:

这道题的思路其实很简单,题目中需要求的子集其实我们同样把树形结构画出来之后就发现,只不过是在递归的过程中把path的值收集一下,因为如果我们没有特定的组合的要求,那么每一个path在递归的过程中就是一个组合,并且通过我们对i的递增,还可以保证不会重复

class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:res = []res.append([])path = []def backtracking(nums, res, path, start_index):for i in range(start_index, len(nums)):path.append(nums[i])res.append(path[:])backtracking(nums, res, path, i + 1)path.pop()backtracking(nums, res, path, 0)return res 
讲解后:

看了卡哥的讲解发现我其实没必要在for循环里面直接加入res,并且在一开始把空列表先加进去,因为我一开始害怕我们进入函数之后,在重新从2开始递归之前还会出现一次path为空的情况,包括3也是,但其实并不会,在pop了之后,我们还是继续循环并且把数字加入到path之后才会再递归,所以把加入res的代码写在backtracking的第一行就可以了

class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:res = []path = []def backtracking(nums, res, path, start_index):# every recursive call, add the current path to resres.append(path[:])for i in range(start_index, len(nums)):path.append(nums[i])backtracking(nums, res, path, i + 1)path.pop()backtracking(nums, res, path, 0)return res 

Leetcode 90. 子集II

讲解前:

这道题其实就是之前组合问题的变种,关键就在于去重,就如下图中所示的

[1, 2] 和 [2] 会反复出现,但是我们不能重复取,这里其实思路就是如果我们是在纵向搜索,也就是说是在继续增加数字然后扩大子集,那么就没关系,但是如果是横向的代表集合由前一个数字开头的已经全部找完了,那么如果我们再从这里开始并且当前这个数字和之前的那个一样,那么我们一定会再end up with the same set,那么这里其实还有个更简单的方法如果我们当前的index和上一位相等并且是在i比startindex大的情况下,因为这时候证明我们是在纵向递归,并且要记得这种方法的前提是我们要先把nums变成递增顺序才可以,这样两个相同的数字才会next to each other

class Solution:def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:res = []path = []nums.sort()def backtracking(nums, res, path, start_index):# add the current path to res each recursionres.append(path[:])for i in range(start_index, len(nums)):if i > 0 and nums[i] == nums[i - 1] and i > start_index:continuepath.append(nums[i])backtracking(nums, res, path, i + 1)path.pop()backtracking(nums, res, path, 0)return res 
讲解后:

卡哥的解法就和之前讲解组合去重问题时候一样,利用了一个used数组,思路依然很清晰,但是这里我的写法更加简便一点,虽然需要在理解了used数组的解法之上去想明白才能看懂

这里是文字解法中利用used数组的解法

class Solution:def subsetsWithDup(self, nums):result = []path = []used = [False] * len(nums)nums.sort()  # 去重需要排序self.backtracking(nums, 0, used, path, result)return resultdef backtracking(self, nums, startIndex, used, path, result):result.append(path[:])  # 收集子集for i in range(startIndex, len(nums)):# used[i - 1] == True,说明同一树枝 nums[i - 1] 使用过# used[i - 1] == False,说明同一树层 nums[i - 1] 使用过# 而我们要对同一树层使用过的元素进行跳过if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:continuepath.append(nums[i])used[i] = Trueself.backtracking(nums, i + 1, used, path, result)used[i] = Falsepath.pop()

这篇关于代码随想录Day28:回溯算法Part4的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

使用 sql-research-assistant进行 SQL 数据库研究的实战指南(代码实现演示)

《使用sql-research-assistant进行SQL数据库研究的实战指南(代码实现演示)》本文介绍了sql-research-assistant工具,该工具基于LangChain框架,集... 目录技术背景介绍核心原理解析代码实现演示安装和配置项目集成LangSmith 配置(可选)启动服务应用场景

Python中顺序结构和循环结构示例代码

《Python中顺序结构和循环结构示例代码》:本文主要介绍Python中的条件语句和循环语句,条件语句用于根据条件执行不同的代码块,循环语句用于重复执行一段代码,文章还详细说明了range函数的使... 目录一、条件语句(1)条件语句的定义(2)条件语句的语法(a)单分支 if(b)双分支 if-else(

MySQL数据库函数之JSON_EXTRACT示例代码

《MySQL数据库函数之JSON_EXTRACT示例代码》:本文主要介绍MySQL数据库函数之JSON_EXTRACT的相关资料,JSON_EXTRACT()函数用于从JSON文档中提取值,支持对... 目录前言基本语法路径表达式示例示例 1: 提取简单值示例 2: 提取嵌套值示例 3: 提取数组中的值注意

CSS3中使用flex和grid实现等高元素布局的示例代码

《CSS3中使用flex和grid实现等高元素布局的示例代码》:本文主要介绍了使用CSS3中的Flexbox和Grid布局实现等高元素布局的方法,通过简单的两列实现、每行放置3列以及全部代码的展示,展示了这两种布局方式的实现细节和效果,详细内容请阅读本文,希望能对你有所帮助... 过往的实现方法是使用浮动加

JAVA调用Deepseek的api完成基本对话简单代码示例

《JAVA调用Deepseek的api完成基本对话简单代码示例》:本文主要介绍JAVA调用Deepseek的api完成基本对话的相关资料,文中详细讲解了如何获取DeepSeekAPI密钥、添加H... 获取API密钥首先,从DeepSeek平台获取API密钥,用于身份验证。添加HTTP客户端依赖使用Jav

Java实现状态模式的示例代码

《Java实现状态模式的示例代码》状态模式是一种行为型设计模式,允许对象根据其内部状态改变行为,本文主要介绍了Java实现状态模式的示例代码,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来... 目录一、简介1、定义2、状态模式的结构二、Java实现案例1、电灯开关状态案例2、番茄工作法状态案例

nginx-rtmp-module模块实现视频点播的示例代码

《nginx-rtmp-module模块实现视频点播的示例代码》本文主要介绍了nginx-rtmp-module模块实现视频点播,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录预置条件Nginx点播基本配置点播远程文件指定多个播放位置参考预置条件配置点播服务器 192.

CSS自定义浏览器滚动条样式完整代码

《CSS自定义浏览器滚动条样式完整代码》:本文主要介绍了如何使用CSS自定义浏览器滚动条的样式,包括隐藏滚动条的角落、设置滚动条的基本样式、轨道样式和滑块样式,并提供了完整的CSS代码示例,通过这些技巧,你可以为你的网站添加个性化的滚动条样式,从而提升用户体验,详细内容请阅读本文,希望能对你有所帮助...

深入解析Spring TransactionTemplate 高级用法(示例代码)

《深入解析SpringTransactionTemplate高级用法(示例代码)》TransactionTemplate是Spring框架中一个强大的工具,它允许开发者以编程方式控制事务,通过... 目录1. TransactionTemplate 的核心概念2. 核心接口和类3. TransactionT

Java实现Elasticsearch查询当前索引全部数据的完整代码

《Java实现Elasticsearch查询当前索引全部数据的完整代码》:本文主要介绍如何在Java中实现查询Elasticsearch索引中指定条件下的全部数据,通过设置滚动查询参数(scrol... 目录需求背景通常情况Java 实现查询 Elasticsearch 全部数据写在最后需求背景通常情况下