力扣 Hot100 普通数组题目 Python 实现

思路 2：动态规划

定义 dp[i] 表示以 nums[i] 结尾的最大子数组和。当来到第 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(res[-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
        reverse(0, n - 1)
        reverse(0, k - 1)
        reverse(k, n - 1)

代码 2：使用 Python 内置 reverse

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