本文主要是介绍2024.8.24 Python，链表异常断裂问题，双链表的建立问题，全排列中的引用机制与copy的使用，最大子数组和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.浏览器系统设计
你有一个只支持单个标签页的 浏览器 ，最开始你浏览的网页是 homepage ，你可以访问其他的网站 url ，也可以在浏览历史中后退 steps 步或前进 steps 步。
请你实现 BrowserHistory 类：
BrowserHistory(string homepage) ，用 homepage 初始化浏览器类。
void visit(string url) 从当前页跳转访问 url 对应的页面 。执行此操作会把浏览历史前进的记录全部删除。
string back(int steps) 在浏览历史中后退 steps 步。如果你只能在浏览历史中后退至多 x 步且 steps > x ，那么你只后退 x 步。请返回后退 至多 steps 步以后的 url 。
string forward(int steps) 在浏览历史中前进 steps 步。如果你只能在浏览历史中前进至多 x 步且 steps > x ，那么你只前进 x 步。请返回前进 至多 steps步以后的 url 。
***方法一：***我的办法，单链表：
class ListNode:def __init__(self, val: str, next=None):self.val = valself.next = nextclass BrowserHistory:def __init__(self, homepage: str):self.head = ListNode(homepage)self.cur = self.headdef visit(self, url: str) -> None:# 创建新节点new_node = ListNode(url)# 当前节点的 next 指向新节点self.cur.next = new_node# 将当前节点移到新节点self.cur = new_node# 确保新节点之后没有其他节点self.cur.next = Nonedef back(self, steps: int) -> str:temp = self.headtotal_step = 0# 计算当前节点的位置距离头的位置，n个节点走n-1步while temp != self.cur:temp = temp.nexttotal_step += 1# 如果步数超过了实际步数，只回退到起始点，这步很重要forward_step = max(0, total_step - steps)# 找到目标节点，从头开始走forward步temp = self.headfor _ in range(forward_step):temp = temp.next# 更新当前节点为目标节点self.cur = tempreturn self.cur.val def forward(self, steps: int) -> str:for _ in range(steps):if self.cur.next is None: # 如果已经到达最后一个页面，无法再前进breakself.cur = self.cur.nextreturn self.cur.val
从早上开始到现在我一直没搞懂为什么我的代码有问题，我以为是back的问题，其实back也有问题，back和forward我都没有加限制条件，在测试用例中，他含有超过范围的特殊值，所以要给他加限定条件，我的代码的最大问题在于我的visit是这样写的：
def visit(self, url: str) -> None:self.cur=self.cur.next self.cur=ListNode(url)
###上面的代码是错误的，下面的是对的
def visit(self, url: str) -> None:self.cur.next=ListNode(url)self.cur=self.cur.next
chat说我的代码这样写链表会导致前面的链表断了。所以他一直在back中报错，说我的temp=temp.next中temp已经是None了，那么temp的next毫无意义。所以我一直在找back的问题。现在来看chat对于我的链表断裂问题是怎么说的：
1.在这段代码中，首先你将 self.cur 移动到 self.cur.next，然后将 self.cur 指向一个新的 ListNode(url) 节点。这会导致你丢失原本的链表结构。
2.具体来说，当你执行 self.cur = self.cur.next 后，self.cur 指向了原链表中的下一个节点。然而，你马上用 self.cur = ListNode(url) 创建了一个新的节点，并且 self.cur 再也不会指向原来的链表中的那个节点。也就是说，你原来链表的前一个节点的 next 指针仍然指向这个旧节点，而不是新的节点。这就导致前进操作不可行，因为你丢失了历史记录。
啊啊啊啊，也就是说，我应该先给next赋值，再移动指针，我的错误在于先移动了指针，再才建立了联系。
方法二：双链表
class ListNode:def __init__(self, val: str):self.val = valself.prev = Noneself.next = Noneclass BrowserHistory:def __init__(self, homepage: str):self.cur = ListNode(homepage)def visit(self, url: str) -> None:new_node = ListNode(url)self.cur.next = new_nodenew_node.prev = self.curself.cur = new_node # 将当前指针更新为新页面new_node.next = None # 断开当前节点的前进记录def back(self, steps: int) -> str:while steps > 0 and self.cur.prev is not None:self.cur = self.cur.prevsteps -= 1return self.cur.valdef forward(self, steps: int) -> str:while steps > 0 and self.cur.next is not None:self.cur = self.cur.nextsteps -= 1return self.cur.val
# Your BrowserHistory object will be instantiated and called as such:
# obj = BrowserHistory(homepage)
# obj.visit(url)
# param_2 = obj.back(steps)
# param_3 = obj.forward(steps)
双链表的定义和上面单链表的类似，用next定义下一个节点，然后next的上一个是cur，cur的下一个是next，这样一个新的结点就定义完了。只有这样才能让链表把数据串起来，
def visit(self, url: str) -> None:self.cur.next = ListNode(url) self.cur.next.prev = self.curself.cur = self.cur.next # 将当前指针更新为新页面def visit(self, url: str) -> None:new_node = ListNode(url)self.cur.next = new_nodenew_node.prev = self.curself.cur = new_node # 将当前指针更新为新页面new_node.next = None # 断开当前节点的前进记录
这两个是一样的，所以一定要细致的去思考这个关系
方法三：动态数组
class BrowserHistory:def __init__(self, homepage: str):# 初始化浏览器历史记录，`history` 存储所有访问过的页面self.history = [homepage]# `current_index` 表示当前页面在历史记录中的位置self.current_index = 0def visit(self, url: str) -> None:# 删除当前页面之后的所有页面，因为新访问的页面会替代它们self.history = self.history[:self.current_index + 1]# 将新访问的页面添加到历史记录中self.history.append(url)# 更新当前页面的位置self.current_index += 1def back(self, steps: int) -> str:# 计算需要回退的步数，但不超过历史记录的开始位置self.current_index = max(0, self.current_index - steps)# 返回回退后的页面return self.history[self.current_index]def forward(self, steps: int) -> str:# 计算需要前进的步数，但不超过历史记录的末尾self.current_index = min(self.current_index + steps, len(self.history) - 1)# 返回前进后的页面return self.history[self.current_index]# Your BrowserHistory object will be instantiated and called as such:
# obj = BrowserHistory(homepage)
# obj.visit(url)
# param_2 = obj.back(steps)
# param_3 = obj.forward(steps)
这个代码没什么好说的，这是一个对于数组的很好的操作，我觉得这些代码中的max(0,index-step)还有min(index+steps,len(self.history)-1)这两个操作来去限制back和forward，是值得我去学习的。不一定非得要用if来加限制条件，有些限制条件是可以去想办法简化的
2.全排列，接8.16号的全排列
今天自行的做了一遍全排列的题，出现了一些问题，我的代码如下：
#这个代码是错的
class Solution:def permute(self, nums: List[int]) -> List[List[int]]:def backtrack(letter,remaining):if remaining==[]:res.append(letter)return n=len(remaining)for i in range(n):letter+=[remaining[i]]backtrack(letter,remaining[0:i]+remaining[i+1:n])res=[]backtrack([],nums)return res
看起来逻辑是没什么问题的，但是实际的输出极其糟糕，大概是这样的：
[[1,2,3,3,2,2,1,3,3,1,3,1,2,2,1],[1,2,3,3,2,2,1,3,3,1,3,1,2,2,1],[1,2,3,3,2,2,1,3,3,1,3,1,2,2,1],[1,2,3,3,2,2,1,3,3,1,3,1,2,2,1],[1,2,3,3,2,2,1,3,3,1,3,1,2,2,1],[1,2,3,3,2,2,1,3,3,1,3,1,2,2,1]]
我以为是我对数据类型的操控有问题，检查了半天，我也没能看出问题，所以我就查了之前的代码，完全找不出和之前的代码有什么区别，之前代码如下：
class Solution:def permute(self,nums:List[int])->List[List[int]]:res=[]def backtrack(path,remaining):if not remaining:res.append(path)returnfor i in range(len(remaining)):backtrack(path+[remaining[i]],remaining[:i]+remaining[i+1:])backtrack([],nums)return res
我无非就是用了path和letter的区别，为什么这么大呢，原因在于，正确的代码里，应该带入的是letter加remaining[i]，而这一层的letter的值并没有实际的改变，但是我的代码中，letter+=后，letter变了，带入的时候就在i=0的时候就改变了，那你想，在i=1的时候，letter不为空了，就继续算进去了，然后append这个函数也怪的很，他是一个引用机制，即便是现在你把当前的letter用append加入进res了，他仍然会因为后续的改变而改变当前的值，所以只用pop是不够的，还需要给letter一个复制版
具体的代码如下：
class Solution:def permute(self, nums: List[int]) -> List[List[int]]:def backtrack(letter,remaining):if remaining==[]:res.append(letter[:]) #改的部分return n=len(remaining)for i in range(n):letter+=[remaining[i]]backtrack(letter,remaining[0:i]+remaining[i+1:n])letter.pop() #改的部分res=[]backtrack([],nums)return res
我没有完全理解这个引用机制
方法二：仍然是做错了，交换法：
#以下是错误代码
class Solution:def permute(self,nums:List[int])->List[List[int]]:if nums==[]:return []n=len(nums)res=[]def backtrack(first):for i in range(first,n):nums[i],nums[first]=nums[first],nums[i]backtrack(first+1)nums[i],nums[first]=nums[first],nums[i]return res.append(nums[:])backtrack(0)return res
输出是：[[1,2,3],[1,2,3],[1,3,2],[1,3,2],[1,2,3],[2,1,3],[2,1,3],[2,3,1],[2,3,1],[2,1,3],[3,2,1],[3,2,1],[3,1,2],[3,1,2],[3,2,1],[1,2,3]]
这次的问题在于，没有给backtrack设定好合理的出口，nums[:]这次注意了，但是出口不对，不是在for循环里出的，而是要加一个if。当所有的事情完成的时候，再出去。最终的代码应该是：
class Solution:def permute(self,nums:List[int])->List[List[int]]:if nums==[]:return []n=len(nums)res=[]def backtrack(first):if first==n:res.append(nums[:])return for i in range(first,n):nums[i],nums[first]=nums[first],nums[i]backtrack(first+1)nums[i],nums[first]=nums[first],nums[i]backtrack(0)return res
3.最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
**方法一：**暴力法，略，两个循环求就完事了，但是两个循环循死你时间复杂度O(N²)
**方法二：**暴力法但一遍遍历： 这个办法本来都不想看了，但是细细一看还是挺有意思的，虽然没有普适性，但是对于开阔思路有帮助：
class Solution:def maxSubArray(self,nums:List[int])->int:tmp=nums[0]n=len(nums)res=tmpfor i in range(1,n):if tmp+nums[i]>nums[i]:res=max(res,tmp+nums[i])tmp+=nums[i]else:res=max(res,tmp+nums[i],tmp,nums[i])tmp=nums[i]return res
代码逻辑：
1.初始化:tmp=nums[0]：tmp 用于记录当前子数组的和，初始化为第一个元素的值。
res=tmp：res 用于记录迄今为止找到的最大子数组的和，初始化为第一个元素的值。
2.遍历数组:for i in range(1,n)：从数组的第二个元素开始遍历。
动态更新当前子数组和：
if tmp + nums[i] > nums[i]：判断是否将当前元素 nums[i] 加入到当前子数组（即 tmp + nums[i]）中会得到一个更大的子数组和。如果是，说明当前子数组可以继续扩展。
tmp += nums[i]：如果当前子数组可以继续扩展，更新 tmp 为扩展后的和。
否则，tmp = nums[i]：如果扩展后的子数组和不如当前元素 nums[i] 本身大，说明之前的子数组和可能有负作用，应当从当前元素重新开始构建子数组。
3.更新最大子数组和:res=max(res,tmp)：在每一步更新 res，使其始终保持为最大子数组的和。
4.返回结果:最终返回 res，即遍历整个数组后找到的最大子数组和。
为什么这段代码能够遍历完所有可能：
在每次遍历元素时，tmp 代表以当前元素结尾的最大子数组和。通过比较 tmp + nums[i] 和 nums[i]，我们判断是否继续扩展子数组还是重新开始新的子数组。
res 始终保持遍历过程中遇到的最大子数组和，所以最终结果一定是全局最大的。
这段代码的核心思想是，既然我们需要找到最大和的子数组，那么在每一步都要判断当前子数组是否有扩展的潜力，如果没有，就从当前元素重新开始构建子数组。这样，最终遍历完成时，res 就会是最大和的子数组。
动态规划思想：这个过程实际上是在动态规划中使用了「状态转移」的思想，通过维护一个局部最优解 tmp，并逐步更新全局最优解 res。
方法三：分治法
它的最大子序和要么在左半边，要么在右半边，要么是穿过中间，对于左右边的序列，情况也是一样，因此可以用递归处理。中间部分的则可以直接计算出来，时间复杂度应该是 O(nlogn)。代码如下：
class Solution:def maxSubArray(self, nums: List[int]) -> int:n = len(nums)#递归终止条件if n == 1:return nums[0]else:#递归计算左半边最大子序和max_left = self.maxSubArray(nums[0:len(nums) // 2])#递归计算右半边最大子序和max_right = self.maxSubArray(nums[len(nums) // 2:len(nums)])#计算中间的最大子序和，从右到左计算左边的最大子序和，从左到右计算右边的最大子序和，再相加max_l = nums[len(nums) // 2 - 1]tmp = 0for i in range(len(nums) // 2 - 1, -1, -1):tmp += nums[i]max_l = max(tmp, max_l)max_r = nums[len(nums) // 2]tmp = 0for i in range(len(nums) // 2, len(nums)):tmp += nums[i]max_r = max(tmp, max_r)#返回三个中的最大值return max(max_right,max_left,max_l+max_r)
方法四：动态规划：
class Solution:def maxSubArray(self, nums: List[int]) -> int:for i in range(1, len(nums)):nums[i] += max(nums[i - 1], 0)return max(nums)
这篇关于2024.8.24 Python，链表异常断裂问题，双链表的建立问题，全排列中的引用机制与copy的使用，最大子数组和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
