LeetCode Hot100刷题日志D3

283. 移动零 (Move Zeroes)题目描述给定一个数组nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。请注意必须在不复制数组的情况下原地对数组进行操作。复盘笔记这题的核心是快慢双指针同向奔跑。可以把快指针想象成“探路者”无脑往前冲去找非零数字慢指针想象成“收纳盒”停在前面等待接收。探路者一旦找到非零数字就直接和收纳盒里的东西互换然后大家一起往前走一步。这样遍历一次所有的 0 自然就被“挤”到末尾了。class Solution: def moveZeroes(self, nums: List[int]) - None: n len(nums) left 0 right 0 while right n: if nums[right] ! 0: nums[left], nums[right] nums[right], nums[left] left 1 right 153. 最大子数组和 (Maximum Subarray)题目描述给你一个整数数组nums请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。复盘笔记主要用到了分治法线段树的核心思想。 它的核心思路是把数组不断对半劈开直到变成单个元素然后再一层层向上合并pushUp。 最烧脑的地方在于为了能让父区间正确合并每一个子区间都必须维护四个状态iSum区间的总和。lSum靠着左边界的最大子段和。rSum靠着右边界的最大子段和。mSum整个区间内的最大子段和也就是我们最终要求的答案。在做的时候合并逻辑pushUp一开始很容易想不清楚。比如父区间的mSum它可能完全在左子区间也可能完全在右子区间还可能是跨越了中间边界左子区间的rSum 右子区间的lSum。必须用max()把这三种情况都考虑进去。class Status: def __init__(self, lSum: int, rSum: int, mSum: int, iSum: int): self.lSum lSum # 包含左端点的最大子段和 self.rSum rSum # 包含右端点的最大子段和 self.mSum mSum # 该区间内的最大子段和 self.iSum iSum # 该整个区间的和 class Solution: def pushUp(self, l: Status, r: Status) - Status: # 整个区间的和 左子区间的和 右子区间的和 iSum l.iSum r.iSum # 包含左端点的最大和 max(左子区间的 lSum, 左子区间的全部和 右子区间的 lSum) lSum max(l.lSum, l.iSum r.lSum) # 包含右端点的最大和 max(右子区间的 rSum, 右子区间的全部和 左子区间的 rSum) rSum max(r.rSum, r.iSum l.rSum) # 区间内的最大和 max(左子区间的最大和, 右子区间的最大和, 横跨左右子区间的最大和) # 注意Python 的 max 函数可以直接接收多个参数 mSum max(l.mSum, r.mSum, l.rSum r.lSum) return Status(lSum, rSum, mSum, iSum) def get(self, a: list[int], l: int, r: int) - Status: # 递归的 base case区间长度为 1直接返回该元素的值 if l r: return Status(a[l], a[l], a[l], a[l]) # 位运算求中间索引等同于 (l r) // 2 m (l r) 1 # 分治分别求解左右子区间 lSub self.get(a, l, m) rSub self.get(a, m 1, r) # 合并左右子区间的状态 return self.pushUp(lSub, rSub) def maxSubArray(self, nums: list[int]) - int: # 获取整个数组 [0, len(nums)-1] 的 Status并提取其中的 mSum全局最大子段和 return self.get(nums, 0, len(nums) - 1).mSum