05力扣普通数组

53. 最大子数组和

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]输出：6解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

就是前缀和 class Solution: def maxSubArray(self, nums: List[int]) -> int: #遍历前缀和 pre = 0 #最小前缀和 min_presum = 0 #最大值 max_value = -inf for i in nums: pre += i max_value = max(max_value , pre - min_presum) min_presum = min(pre , min_presum) return max_value

56. 合并区间

class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: 左端点排序 intervals.sort(key = lambda x:x[0]) 返回数组 ref = [] for i in intervals: ref不为空且ref最后一项右端点>=当前i的左端点 if ref and i[0] <= ref[-1][1]: 合并 ref[-1][1] = max(ref[-1][1],i[1]) else: ref.append(i) return ref

189. 轮转数组

class Solution: def rotate(self, nums: List[int], k: int) -> None: k = k % len(nums) def reverse(left:int ,right:int): while left < right: nums[left],nums[right] = nums[right],nums[left] left += 1 right -= 1 三次反转 if k != 0: reverse(0,len(nums)-1) reverse(0,k-1) reverse(k,len(nums)-1)

238. 除了自身以外数组的乘积

原数组： [1 2 3 4] 左部分的乘积： 1 1 1*2 1*2*3 右部分的乘积： 2*3*4 3*4 4 1 结果： 1*2*3*4 1*3*4 1*2*4 1*2*3*1

class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: left_value=[1]*len(nums) tmp = 1 for i in range(1,len(nums)): left_value[i] = left_value[i-1]*nums[i-1] for i in range(len(nums)-2,-1,-1): tmp = tmp * nums[i+1] left_value[i] = left_value[i]*tmp return left_value

41. 缺失的第一个正数

class Solution: def firstMissingPositive(self, nums: list[int]) -> int: n = len(nums) for i in range(n): # 如果当前学生的学号在 [1,n] 中，但（真身）没有坐在正确的座位上 while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]: # 那么就交换 nums[i] 和 nums[j]，其中 j 是 i 的学号 j = nums[i] - 1 # 减一是因为数组下标从 0 开始 nums[i], nums[j] = nums[j], nums[i] # 找第一个学号与座位编号不匹配的学生 for i in range(n): if nums[i] != i + 1: return i + 1 # 所有学生都坐在正确的座位上 return n + 1