python编程实战（二）

题目一：

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 子数组是数组中的一个连续部分。

关键数据结构：

列表 List[int]，本质上是一维数组

关键思路：

任意一个连续子数组，都是以nums中的某个元素num[i]结尾，用dp[i]表示以nums[i]元素结尾的数组。如果dp[i-1]>0，会让nums[i]变大；反之如果是负数只会让nums[i]变小，不如从nums[i]重新开始。

dp[i]可以通过递归思想来表示，即dp[i]=dp[i-1]+nums[i]（i>1）；dp[0]=nums[0](i=0)

代码:

class Solution: def maxSubArray(self, nums: List[int]) -> int: # curr_sum 表示以当前元素结尾的最大子数组和 # max_sum 表示全局最大子数组和 curr_sum = max_sum = nums[0] for num in nums[1:]: # 如果 curr_sum 是负数，那么它对 num 没有贡献，应该从 num 重新开始 # 如果 curr_sum 是正数，那么加上 num 可能更好 # 下面的 max(num, curr_sum + num) 就是做这个选择 curr_sum = max(num, curr_sum + num) # 更新全局最大值 max_sum = max(max_sum, curr_sum) return max_sum

题目二：

给定一个整数数组nums，将数组中的元素向右轮转k个位置，其中k是非负数。

关键数据结构：

列表

关键思路：

将一个数组向右轮转k个位置，可以如此理解：

先将整个数组翻转，然后在位置k处将数组分割成两部分，再把两部分的数组翻转回去。

如[1,2,3,4,5,6]向右轮转2个位置，可以先把数组翻转：[6,5,4,3,2,1]

然后分割为[6,5][4,3,2,1]分别翻转，得到[5,6,1,2,3,4]，即所要求的结果

显然此种翻转是具有周期性的；当k>>n时，可以通过k%n获得等价翻转次数

代码中通过翻转函数来实现翻转操作，翻转函数本身使用了双指针定义。

代码：

class Solution: def rotate(self, nums: List[int], k: int) -> None: n = len(nums) k = k % n # 辅助反转函数 def reverse(start, end): while start < end: nums[start], nums[end] = nums[end], nums[start] start += 1 end -= 1 # 三次反转 reverse(0, n - 1) # 反转整个数组 reverse(0, k - 1) # 反转前k个 reverse(k, n - 1) # 反转剩余部分

题目三：

以数组intervals表示若干个区间的集合，其中单个区间为intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

关键数据结构：

List[List[int]]，即列表的列表

关键方法：

intervals.sort(key=lambda x: x[0]) 按照x元素中的第一个位置的大小排序

关键思路：

如果要合并重叠区间，最好的方法是首先把区间按左端点大小排列起来，使得可以合并的区间都是相邻的；判断两个区间是否重叠，实际上就是判断一个区间的终点是否大于另一个区间的起点。区间通过列表来表示，区间的集合则通过列表的列表来表示。

代码：

class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: intervals.sort(key=lambda x: x[0]) # 按起点排序 merged = [] for interval in intervals: # 如果结果为空或不重叠，直接添加 if not merged or merged[-1][1] < interval[0]: #merged[-1]表示取merged中最后一个元素 merged.append(interval) else: # 重叠则合并，取最大右端点 merged[-1][1] = max(merged[-1][1], interval[1]) return merged