力扣hot100_普通数组_python版本

一、53. 最大子数组和

• 思路1：前缀和。
• 代码

classSolution:defmaxSubArray(self, nums: List[int])->int:iflen(nums)==1:return nums[0] preSum =[0]*(len(nums)+1)for idx, n inenumerate(nums): preSum[idx+1]= preSum[idx]+ n res =-inf for idx, p inenumerate(preSum):for i inrange(idx): res =max(res, p-preSum[i])return res # 前缀和比较好写，但是上面复杂度太高，没法AK# 其实每次我们只需要减去最小的前缀和，维护一个最小的前缀和，就不需要多一层循环。优化如下classSolution:defmaxSubArray(self, nums):iflen(nums)==1:return nums[0] res =-inf preSum =0 minPreSum =0for n in nums: preSum += n res =max(res, preSum - minPreSum) minPreSum =min(minPreSum, preSum)return res 

• 思路2：dp
  • 定义dp[i]，表示以nums[i]j结尾的最大子数组和。当来到第i个位置，有两种可能
1. 以dp[i] = nums[i]，单独成一个子数组
2. dp[i] = dp[i-1] + nums[i]，这种情况需要dp[i-1] >＝0
• 代码

classSolution:defmaxSubArray(self, nums): dp =[0]*len(nums) dp[0]= nums[0]for i inrange(1,len(nums)): dp[i]=max(dp[i-1],0)+ nums[i]returnmax(dp)

二、56. 合并区间

• 思路：先将intervals中的区间按起始排序。这样每个新来的区间就不用和已经确定好没要交集的区间比较了。
• 代码

classSolution:defmerge(self, intervals: List[List[int]])-> List[List[int]]: intervals.sort(key=lambda p:p[0]) res =[]for p in intervals:if res and p[0]<= res[-1][1]: res[-1][1]=max(ans[-1][1], p[1])else:# 这是第一个区间 或者 新来的区间和之前的区间没有交集 res.append(p)return res 

三、189. 轮转数组

• 思路：这道题可以推公式出来，如果不想推的话直接根据结果反转。注意不要使用切片或者列表的insert语法。这都会产生额外的空间
• 代码1：

classSolution:defrotate(self, nums: List[int], k:int)->None:defreverse(i, j):while i < j: nums[i], nums[j]= nums[j], nums[i] i +=1 j -=1 n =len(nums) k %= n # 防止k比数组大 reverse(0, n-1) reverse(0, k-1) reverse(k, n-1)

• 代码2：使用python自带的reverse语法

defrotate2(self, nums: List[int], k:int)->None:# python也有自带的reverse语法 n =len(nums) k %= n nums.reverse() nums[:k]=reversed(nums[:k]) nums[k:]=reversed(nums[k:])

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

• 思路：前后缀分解。维护一个pre[i]:表示0到i-1的乘积，suf[i]表示i+1到n-1的乘积。
• 代码

classSolution:defproductExceptSelf(self, nums: List[int])-> List[int]: n =len(nums) pre =[1]*n for i inrange(1, n): pre[i]= pre[i-1]* nums[i-1] suf =[1]*n for i inrange(n-2,-1,-1): suf[i]= suf[i+1]* nums[i+1]return[p * s for p, s inzip(pre, suf)]

五、41. 缺失的第一个正数

• 思路：将每个数字放到自己值对应的索引上
• 代码：

classSolution:deffirstMissingPositive(self, nums: List[int])->int: n =len(nums)for i inrange(n):# 当前数字大小在列表范围内且没有放到对应的索引位置上。while1<= nums[i]<= n and nums[nums[i]-1]!= nums[i]: nums[nums[i]-1], nums[i]= nums[i], nums[nums[i]-1]for i inrange(n):if nums[i]!= i +1:return i +1# 如果都对上了return n +1