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

相关文章

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程,特意画了如下的类图,包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口,接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

python: 多模块(.py)中全局变量的导入

文章目录 global关键字可变类型和不可变类型数据的内存地址单模块(单个py文件)的全局变量示例总结 多模块(多个py文件)的全局变量from x import x导入全局变量示例 import x导入全局变量示例 总结 global关键字 global 的作用范围是模块(.py)级别: 当你在一个模块(文件)中使用 global 声明变量时,这个变量只在该模块的全局命名空

作业提交过程之HDFSMapReduce

作业提交全过程详解 (1)作业提交 第1步:Client调用job.waitForCompletion方法,向整个集群提交MapReduce作业。 第2步:Client向RM申请一个作业id。 第3步:RM给Client返回该job资源的提交路径和作业id。 第4步:Client提交jar包、切片信息和配置文件到指定的资源提交路径。 第5步:Client提交完资源后,向RM申请运行MrAp

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig