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_value56. 合并区间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 ref189. 轮转数组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*1class 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[i1] left_value[i] left_value[i]*tmp return left_value41. 缺失的第一个正数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