53. 最大子数组和
Python算法
力扣 Hot100 普通数组题目 Python 实现
力扣 Hot100 普通数组题目 Python 实现。涵盖最大子数组和、合并区间、轮转数组、除自身以外数组的乘积及缺失的第一个正数。采用前缀和优化、动态规划、原地反转、前后缀分解及索引映射等算法策略。代码经过语法修正与逻辑梳理，提供多种解法对比，适用于算法面试准备与基础巩固。
力扣 Hot100 普通数组题目 Python 实现。涵盖最大子数组和、合并区间、轮转数组、除自身以外数组的乘积及缺失的第一个正数。采用前缀和优化、动态规划、原地反转、前后缀分解及索引映射等算法策略。代码经过语法修正与逻辑梳理，提供多种解法对比，适用于算法面试准备与基础巩固。
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 = -float('inf')
for idx, p in enumerate(preSum):
for i in range(idx):
res = max(res, p - preSum[i])
return res
注：前缀和写法简单但时间复杂度高，无法通过所有测试用例。
每次只需减去最小的前缀和，维护一个最小前缀和即可。
class Solution:
def maxSubArray(self, nums):
if len(nums) == 1:
return nums[0]
res = -float('inf')
preSum = 0
minPreSum = 0
for n in nums:
preSum += n
res = max(res, preSum - minPreSum)
minPreSum = min(minPreSum, preSum)
return res
定义 dp[i] 表示以 nums[i] 结尾的最大子数组和。当来到第 i 个位置，有两种可能：
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)
先将 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
这道题可以推公式出来，如果不想推的话直接根据结果反转。注意不要使用切片或者列表的 insert 语法，这都会产生额外的空间。
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)
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:])
前后缀分解。维护一个 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)]
将每个数字放到自己值对应的索引上。
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
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
解析常见 curl 参数并生成 fetch、axios、PHP curl 或 Python requests 示例代码。 在线工具，curl 转代码在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online