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

相关文章

将Mybatis升级为Mybatis-Plus的详细过程

《将Mybatis升级为Mybatis-Plus的详细过程》本文详细介绍了在若依管理系统(v3.8.8)中将MyBatis升级为MyBatis-Plus的过程,旨在提升开发效率,通过本文,开发者可实现... 目录说明流程增加依赖修改配置文件注释掉MyBATisConfig里面的Bean代码生成使用IDEA生

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整

Python Websockets库的使用指南

《PythonWebsockets库的使用指南》pythonwebsockets库是一个用于创建WebSocket服务器和客户端的Python库,它提供了一种简单的方式来实现实时通信,支持异步和同步... 目录一、WebSocket 简介二、python 的 websockets 库安装三、完整代码示例1.

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

Python使用自带的base64库进行base64编码和解码

《Python使用自带的base64库进行base64编码和解码》在Python中,处理数据的编码和解码是数据传输和存储中非常普遍的需求,其中,Base64是一种常用的编码方案,本文我将详细介绍如何使... 目录引言使用python的base64库进行编码和解码编码函数解码函数Base64编码的应用场景注意

Python基于wxPython和FFmpeg开发一个视频标签工具

《Python基于wxPython和FFmpeg开发一个视频标签工具》在当今数字媒体时代,视频内容的管理和标记变得越来越重要,无论是研究人员需要对实验视频进行时间点标记,还是个人用户希望对家庭视频进行... 目录引言1. 应用概述2. 技术栈分析2.1 核心库和模块2.2 wxpython作为GUI选择的优

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》:本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程(增删改)3. 查询数据三、事务处

JSON Web Token在登陆中的使用过程

《JSONWebToken在登陆中的使用过程》:本文主要介绍JSONWebToken在登陆中的使用过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录JWT 介绍微服务架构中的 JWT 使用结合微服务网关的 JWT 验证1. 用户登录,生成 JWT2. 自定义过滤