2024.9.1 Python,跳跃游戏,贪心算法,回溯算法复原 IP 地址,关于回溯过程中列表的[:]以及copy问题再讨论

本文主要是介绍2024.9.1 Python,跳跃游戏,贪心算法,回溯算法复原 IP 地址,关于回溯过程中列表的[:]以及copy问题再讨论,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

先祝各位C友们9月快乐,生活幸福。

1.跳跃游戏,贪心算法

昨天的三个代码我写到最后没时间去盘了,今天来盘一下,昨天我写的第一个代码从逻辑上就有问题,所以不停的报错不停的报错,我在报错的过程中不断地去加可能性,但是加一种可能就只解决一种问题,所以说明问题没有在根本上解决,所以我便在今天去看之前的代码有什么问题,我的代码如下:

#错的
class Solution:def jump(self, nums: List[int]) -> int:n=len(nums)if n==1:return 0index=0step=0if nums[0]>=n:return 1while index<n-1:max_step=nums[index] tmp_index=0tmp=[]while tmp_index<max_step:if index+tmp_index+1< n: #假设max_step是2那么tmp_index就可以取0,1tmp.append(nums[index+tmp_index+1])  #+1是为了模拟跳数,因为没有0跳tmp_index+=1#此时的tmp已经好了,接下来要找tmp的最大值和最大下标max_value, max_index=self.find_max_with_index(tmp)step+=1index+=max_index+1return stepdef find_max_with_index(self,lst):# 假设最大值的索引为0max_value = max(lst)for i in range(len(lst)-1,-1,-1):if lst[i]==max_value:max_index=ibreakreturn max_value, max_index

我的逻辑就是,在现在当下能够得着的地方去找最大的数,然后把光标移到他的下面,然后接着进行这样的循环,但是这样的逻辑其实不是贪心算法,他并不贪心,比如这样[3,4,3,3],按照我的逻辑会选择4去接着找下一个,但是这里应该找的是最后一个三,也就是说:
我想的:在当前范围内找max要最大,实际上是,在当前范围内找max+index要最大,正确代码如下:

class Solution:def jump(self, nums: List[int]) -> int:n = len(nums)if n == 1: #1.return 0index = 0step = 0while index < n - 1:			#2.max_step = nums[index]       	#max_step指的是当前index的最大步数if index + max_step >= n - 1:  # 如果当前可以直接跳到最后位置return step + 1# 找出从当前 index 开始,能够跳跃到的最远位置max_reach = 0next_index = index		#3.for i in range(1, max_step + 1):   #4.这里的i指的是当前index往后数第几个元素,+1是为了让max_step能取到if index + i < n and index + i + nums[index + i] > max_reach: #5.第一个index+i<n完全可以不需要考虑max_reach = index + i + nums[index + i]next_index = index + iindex = next_index #6.step += 1return step

代码逻辑:
1.给一些初始判断,一个是如果当前就一个元素,那就return 0
2.进入判断循环,大的循环条件是当前元素的下标index不能超过n-1,到n-1了就该停了,第二,如果你在的这个index里的max_reach已经>=n-1的时候就可以直接return了
3.next_index是用来从for循环中传递出参数的选项,这里的next_index我最开始思考了一下能否优化出来,但是事实是不行的,因为之后的for循环中index在下一个循环中还要用,你这个时候把index+=的话,全都乱了
4.for循环遍历的是你现在能够到的所有元素,其中两个循环限制条件的解读如下:第一个完全可以省略,因为在前面已经判断过当前max_step如果足够大超过n的情况了,那也就是说这里的index+i再折腾都不会超过n。第二个判断是整个代码的核心,也就是这个判断才造就了这个代码贪心的地方。那就是要让index+i+nums[index+i]要最大,最大的赋值给max_reach
5.如果比max_reach大,那么干两件事,一:更新max_reach。二:更新下一个index为index+i
6.循环完之后此时的代码中index=next_index,完成了一次循环,那么给step+=1,最后return

2.复原 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”]
方法一:暴力法,这个题用暴力法也不是不行,毕竟一个ip地址最多也才12位,就算三层循环下来也不是什么大问题

from typing import List
class Solution:def restoreIpAddresses(self, s: str) -> List[str]:n=len(s)res=[]for d1 in range(1,n-2):for d2 in range(d1+1,n-1):for d3 in range(d2+1,n):                    s1=self.is_digit(s[0:d1])s2=self.is_digit(s[d1:d2])s3=self.is_digit(s[d2:d3])s4=self.is_digit(s[d3:n])if s1 and s2 and s3 and s4:ans=''ans=s[0:d1]+'.'+s[d1:d2]+'.'+s[d2:d3]+'.'+s[d3:n]res.append(ans)return res             def is_digit(self,s:str)->bool:n=len(s)if n==1:        #只有个位就返回对return Trueelif n>=4:      #超过三位数就返回错 return Falseelse:           #有二三位进行判断if s[0]=='0':   #第一位是0就返错  return Falseelse:       s=int(s)if 0<=s<=255:return Trueelse:return False

硬算,没啥好说的,夸一下自己考虑情况考虑的还挺好的,第一次放进编译器就通过。nice。如果要强行优化的话,应该是把判断是否为大于4的部分直接放进原主函数代码的for循环中,for循环没必要循环超过4的部分,for循环的最大值可以是,d1->[1,1,min(n,4)] d2->[d1+1,min(n,i+4)] d3->[j+1,min(n,j+4)]
方法二:dfs回溯
这个方法还是比较合理一些的,我将在之后详细写出代码的逻辑

class Solution:def restoreIpAddresses(self, s: str) -> List[str]:SEG_COUNT = 4ans = []segments = [0] * SEG_COUNT  #1.def dfs(segId: int, segStart: int): #2.# 如果找到了 4 段 IP 地址并且遍历完了字符串,那么就是一种答案if segId == SEG_COUNT:          #3.if segStart == len(s):		#4.ipAddr = ".".join(str(seg) for seg in segments)  #5.这里很重要ans.append(ipAddr)      #6.return# 如果还没有找到 4 段 IP 地址就已经遍历完了字符串,那么提前回溯if segStart == len(s):return# 由于不能有前导零,如果当前数字为 0,那么这一段 IP 地址只能为 0if s[segStart] == "0":segments[segId] = 0dfs(segId + 1, segStart + 1)return# 一般情况,枚举每一种可能性并递归addr = 0for segEnd in range(segStart, len(s)): #7.addr = addr * 10 + int(s[segEnd])  # 直接使用 int() 转换字符为数字if 0 < addr <= 0xFF:  # 确保每一段 IP 地址在 1 到 255 之间segments[segId] = addrdfs(segId + 1, segEnd + 1)else:break       dfs(0, 0)return ans

评价:
这个代码写的挺好的,但是就是说我们自己来写很难写成这个样子,因为会出现可能会漏情况或者情况重复的可能,我将一步一步的分析这个代码,并学习这种分段式dfs的思路,和之前的回溯算法的思想是类似的。
代码逻辑:
1.初始定义,segment这里的定义很好,将分段存储每个ip
2.dfs的定义segId指的是当前段的段号,segStart指的是本层深度中的起始下标
3.这里就是回溯算法经典的末端设计,如果segId(0,1,2,3)等于4说明已经到第五层了,进行了四次操作了,可以进入导出操作了
4.能否将字符串导出还得进行判断起始下标是否已经到头了,等于len(s)说明所有的字符已经进入过循环了。说明正确
5.这里的join我很奇怪,当时第一次用join我记得是一个列表,然后把一整个列表变成了字符串,但是这里的str(seg) for seg in segments是一个迭代对象,他还没有完全的成为一个列表,那么为什么可以这样用呢,经查证:join是一个非常强大的函数,他既可以吃掉列表,也可以吃掉迭代对象,但是要求可迭代对象中的所有元素都必须是字符串类型
以下代码是一样的

# 生成器表达式
ipAddr = '.'.join(str(seg) for seg in segments)
# 列表推导式
ipAddr = '.'.join([str(seg) for seg in segments])

6.这里我当初很奇怪,在以往的回溯算法的时候,我们都避免使用这样的表述,会使用ipAddr[:]这样的表述,为什么这里反而用了ipAddr,原因是这里的ipAddr是字符串,所以他可以直接粘进去,而不需要考虑会更改的问题。在下一个大类里我会再次强调[:]的使用场景。
7.这个代码的核心层面,那就是逐行遍历,只要满足条件,就进行一次dfs,注意在每一次循环当中都需要给该层的segment更改,然后再进入下一层dfs,如果有一次错误,那就break,这一层的可能性就跑完了已经。
这个代码的思路还是老思路,但是让我们自己写写不出来的。

3.关于回溯过程中列表的[:]以及copy问题再讨论

假设我们有一个简单的回溯算法,目标是找到所有可能的组合。我们要从 [1, 2, 3] 中选出所有的子集。例如:

#错误
def backtrack(nums, path, ans):ans.append(path)  # 将当前路径添加到结果中for i in range(len(nums)):# 选择当前元素并继续递归path.append(nums[i])backtrack(nums[i+1:], path, ans)path.pop()  # 撤销选择,回溯nums = [1, 2, 3]
ans = []
backtrack(nums, [], ans)
print(ans)#输出是[[], [], [], [], [], [], [], []]

代码要点:
path 是一个列表,用来存储当前路径。
在每次递归调用时,path 可能会增加新的元素。
pop() 用于回溯到上一状态,撤销当前递归中的选择。
使用这两种代码会产生完全不一样的结果

ans.append(path)
ans.append(path[:])#输出是[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

原因:
1.递归的路径是可变对象:path 是一个列表,它是一个可变对象。当你递归修改 path 时,所有对 path 的引用(包括 ans 中的引用)都会感知到这些修改。
2.保存的引用而不是副本:当你在 ans.append(path) 中添加 path 时,实际上只是将 path 的引用添加到 ans 中,而不是保存 path 的一个独立副本。
3.递归继续修改 path:递归进行时,path 会不断变化,而 ans 中保存的所有引用都指向同一个 path。所以,最后 ans 中的所有元素都会指向同一个被修改后的 path,导致最终结果不正确。
总结:
1.在递归中使用可变对象(如列表)时,必须非常小心,以确保你在保存结果时保存的是对象的副本,而不是对象的引用。
2.使用 [:] 可以创建列表的副本,确保递归中的修改不会影响已经保存的结果
这段下来对列表的认知就又增加了一层。

4.消除游戏

列表 arr 由在范围 [1, n] 中的所有整数组成,并按严格递增排序。请你对 arr 应用下述算法:
从左到右,删除第一个数字,然后每隔一个数字删除一个,直到到达列表末尾。
重复上面的步骤,但这次是从右到左。也就是,删除最右侧的数字,然后剩下的数字每隔一个删除一个。
不断重复这两步,从左到右和从右到左交替进行,直到只剩下一个数字。
给你整数 n ,返回 arr 最后剩下的数字。
示例 1:
输入:n = 9
输出:6
解释:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
arr = [2, 4, 6, 8]
arr = [2, 6]
arr = [6]
示例 2:
输入:n = 1
输出:1

class Solution:def lastRemaining(self, n: int) -> int:arr=[]self.res=0for i in range(1,n+1):arr.append(i)def dfs(arr):if len(arr)==1:self.res=arr[0]returntmp=[]for i in range(1,len(arr),2):tmp.append(arr[i])if len(tmp)==1:self.res=tmp[0]returnarr=[]for i in range(len(tmp)-2,-1,-2):arr.append(tmp[i])tmp=[]for i in range(len(arr)-1,-1,-1):tmp.append(arr[i])dfs(tmp)dfs(arr)return self.res

这是我写的,chat精简以后:

class Solution:def lastRemaining(self, n: int) -> int:def dfs(arr):if len(arr) == 1:return arr[0]# 从左到右删除arr = arr[1::2]# 递归调用,继续处理剩下的部分return dfs(arr[::-1])  # 逆序传递给递归# 生成初始数组并调用递归函数return dfs(list(range(1, n + 1)))

看完chat的答案我感觉自己被秀了,哈哈哈哈哈哈,但是最后内存还是超了,所以还是需要找到一个简单的办法
答案是个数学问题,我不想做了,感觉没什么意义:

class Solution:def lastRemaining(self, n: int) -> int:a1 = 1k, cnt, step = 0, n, 1while cnt > 1:if k % 2 == 0:  # 正向a1 += stepelse:  # 反向if cnt % 2:a1 += stepk += 1cnt >>= 1step <<= 1return a1

这篇关于2024.9.1 Python,跳跃游戏,贪心算法,回溯算法复原 IP 地址,关于回溯过程中列表的[:]以及copy问题再讨论的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

python获取指定名字的程序的文件路径的两种方法

《python获取指定名字的程序的文件路径的两种方法》本文主要介绍了python获取指定名字的程序的文件路径的两种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要... 最近在做项目,需要用到给定一个程序名字就可以自动获取到这个程序在Windows系统下的绝对路径,以下

oracle 11g导入\导出(expdp impdp)之导入过程

《oracle11g导入导出(expdpimpdp)之导入过程》导出需使用SEC.DMP格式,无分号;建立expdir目录(E:/exp)并确保存在;导入在cmd下执行,需sys用户权限;若需修... 目录准备文件导入(impdp)1、建立directory2、导入语句 3、更改密码总结上一个环节,我们讲了

使用Python批量将.ncm格式的音频文件转换为.mp3格式的实战详解

《使用Python批量将.ncm格式的音频文件转换为.mp3格式的实战详解》本文详细介绍了如何使用Python通过ncmdump工具批量将.ncm音频转换为.mp3的步骤,包括安装、配置ffmpeg环... 目录1. 前言2. 安装 ncmdump3. 实现 .ncm 转 .mp34. 执行过程5. 执行结

Python实现批量CSV转Excel的高性能处理方案

《Python实现批量CSV转Excel的高性能处理方案》在日常办公中,我们经常需要将CSV格式的数据转换为Excel文件,本文将介绍一个基于Python的高性能解决方案,感兴趣的小伙伴可以跟随小编一... 目录一、场景需求二、技术方案三、核心代码四、批量处理方案五、性能优化六、使用示例完整代码七、小结一、

Python中 try / except / else / finally 异常处理方法详解

《Python中try/except/else/finally异常处理方法详解》:本文主要介绍Python中try/except/else/finally异常处理方法的相关资料,涵... 目录1. 基本结构2. 各部分的作用tryexceptelsefinally3. 执行流程总结4. 常见用法(1)多个e

Vue3绑定props默认值问题

《Vue3绑定props默认值问题》使用Vue3的defineProps配合TypeScript的interface定义props类型,并通过withDefaults设置默认值,使组件能安全访问传入的... 目录前言步骤步骤1:使用 defineProps 定义 Props步骤2:设置默认值总结前言使用T

Python中logging模块用法示例总结

《Python中logging模块用法示例总结》在Python中logging模块是一个强大的日志记录工具,它允许用户将程序运行期间产生的日志信息输出到控制台或者写入到文件中,:本文主要介绍Pyt... 目录前言一. 基本使用1. 五种日志等级2.  设置报告等级3. 自定义格式4. C语言风格的格式化方法

Python实现精确小数计算的完全指南

《Python实现精确小数计算的完全指南》在金融计算、科学实验和工程领域,浮点数精度问题一直是开发者面临的重大挑战,本文将深入解析Python精确小数计算技术体系,感兴趣的小伙伴可以了解一下... 目录引言:小数精度问题的核心挑战一、浮点数精度问题分析1.1 浮点数精度陷阱1.2 浮点数误差来源二、基础解决

使用Python实现Word文档的自动化对比方案

《使用Python实现Word文档的自动化对比方案》我们经常需要比较两个Word文档的版本差异,无论是合同修订、论文修改还是代码文档更新,人工比对不仅效率低下,还容易遗漏关键改动,下面通过一个实际案例... 目录引言一、使用python-docx库解析文档结构二、使用difflib进行差异比对三、高级对比方

ShardingProxy读写分离之原理、配置与实践过程

《ShardingProxy读写分离之原理、配置与实践过程》ShardingProxy是ApacheShardingSphere的数据库中间件,通过三层架构实现读写分离,解决高并发场景下数据库性能瓶... 目录一、ShardingProxy技术定位与读写分离核心价值1.1 技术定位1.2 读写分离核心价值二