力扣hot100_普通数组_python版本

一、53. 最大子数组和

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

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        preSum = [0] * (len(nums)+1)
        for idx, n in enumerate(nums):
            preSum[idx+1] = preSum[idx] + n
            
        res = -inf
        for idx, p in enumerate(preSum):
            for i in range(idx):
                res = max(res, p-preSum[i])
        return res
# 前缀和比较好写，但是上面复杂度太高，没法AK
# 其实每次我们只需要减去最小的前缀和，维护一个最小的前缀和，就不需要多一层循环。优化如下
class Solution:
    def maxSubArray(self, nums):
        if len(nums) == 1:
            return nums[0]
        res = -inf
        preSum = 0
        minPreSum = 0
        for 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
• 代码

class Solution:
    def maxSubArray(self, nums):
        dp =[0] * len(nums)
        dp[0] = nums[0]
        for i in range(1, len(nums)):
            dp[i] = max(dp[i-1], 0) + nums[i]
        return max(dp)

二、56. 合并区间

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

class Solution:
    def merge(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：

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        def reverse(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语法

    def rotate2(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的乘积。
• 代码

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        pre = [1]*n
        for i in range(1, n):
            pre[i] = pre[i-1] * nums[i-1]

        suf = [1]*n
        for i in range(n-2, -1, -1):
            suf[i] = suf[i+1] * nums[i+1]
            
        return [p * s for p, s in zip(pre, suf)]

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

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

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