1 53. 最大子数组和
给你一个整数数组
nums
,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。子数组是数组中的一个连续部分。
示例 1:
输入:nums = [-2,1,-3,4,-1,2,1,-5,4] 输出:6 解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。示例 2:
输入:nums = [1] 输出:1示例 3:
输入:nums = [5,4,-1,7,8] 输出:23思考:
1 这个题目有点印象否,连续自数组,可以使用前缀和求解,不过这个要O(N**2);
2 动态规划。
分析题目,只要求解最大连续子数组的和,那么我们就把所有访问到当前位置的最大连续子数据保存下来,存放在cum_sums = [];
i ==0: cum_sums[0] =
nums[0]
len(nums)>i>0: cum_sums[i] = max(cum_sums[i-1]+
nums[i],nums[i]
)什么意思?
当前的最大连续:当前位置数据是否与前一个位置最大连续子数据合并?哪一个大用那一个
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
# 使用前缀法
left ,right = 0, 1
cum_sum = nums[:]
# 存储到当前位置的最大值
while right < len(nums):
cum_sum[right] = max(cum_sum[right-1]+nums[right],nums[right])
right += 1
#print(cum_sum)
return max(cum_sum)
2 56. 合并区间
以数组
intervals
表示若干个区间的集合,其中单个区间为intervals[i] = [starti, endi]
。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。1 区间相互有序;
2 区间合并;
区间相互有序: 这是要保证嵌套序列(第一维)从左到右序列有序;,这样方便比较;
合并:【(x1,y1),(x2,y2)】
如果y1< x2, 那么就需要合并两个区间; 合并之后(x1, max(y1,y2))
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda x:x[0])
n = len(intervals)
res = []
for x, y in intervals:
if res and x<=res[-1][1]:
res[-1][1] = max(res[-1][1], y)
else:
res.append([x, y])
return res
3 238. 除自身以外数组的乘积
给你一个整数数组
nums
,返回 数组answer
,其中answer[i]
等于nums
中除nums[i]
之外其余各元素的乘积 。题目数据 保证 数组
nums
之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。请 不要使用除法,且在
O(n)
时间复杂度内完成此题。示例 1:
输入: nums =[1,2,3,4]
输出:[24,12,8,6]
示例 2: 输入: nums = [-1,1,0,-3,3] 输出: [0,0,9,0,0]思考:
如果允许使用除法,把所有的元素乘起来,然后浏览当前元素,所总积除以当前元素即可;
不使用除法:
备用数组:
1 left_mult[i] = 保存当前位置所有左边乘积;
2 right_mult[i] = 保存当前位置所有右边乘积;
class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: # 保存所有左边乘积,含有当前的元素 # 保存所有右边乘积 left_mult = nums[:] right_mult = nums[:] for i in range(1,len(nums)): left_mult[i] = nums[i] * left_mult[i-1] for i in range(len(nums)-2,0,-1): right_mult[i] = nums[i] * right_mult[i+1] reuslts = nums[:] for i in range(1,len(nums)-1): reuslts[i] = left_mult[i-1] * right_mult[i+1] reuslts[0] = right_mult[1] reuslts[-1] = left_mult[-2] return reuslts
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)]