HOT 100 | 【子串】76.最小覆盖子串、【平凡数组】53.最大子数组和、【平凡 ...

一、【子串】76.最小覆盖子串

1. 解题思绪

        定义两个哈希表分别用于 t 统计字符串 t 的字符个数，另一个sub_s用于统计字符串 t 在 s 的子串内里字符出现的频率。
        为了低沉时间复杂度，定义一个变量t_count用于统计 t 哈希表中元素的个数。哈希表sub_s是一边遍历字符串s一边构建的，所以定义一个变量have用于统计有几个元素满足了t哈希表的条件。当且仅当t_count == have，则表明子串sub_s是涵盖t中全部字符。
        暴力枚举全部s的子串，然后在满足条件的子串中选出长度最小的返回即可，但是这种方法时间复杂度为O(n^2)，我们可以选择时间复杂度更优的滑动窗口来解决（时间复杂度O(n)）。
        （1）从s开始进行遍历，如果该字符在t中存在，那么更新sub_s和have后，若没有满足条件t_count == have，那么则移动滑动窗口的右边界；如果该字符在t中不存在，那么窗口右边界直接继续向右移动。
        （2）直到满足条件t_count == have，则记录当前窗口的长度length和起点start，然后将窗口的左边界向右移动后，更新sub_s和have。
        （3）如果sub_s和have不满足t_count == have，则重复步调（1）。
        （4）如果再次碰到满足条件的子串，则判断其长度是否小于length，如果是则更新length和start。
2. 代码实现

1. class Solution:
2.     def minWindow(self, s:str, t:str)->str:
3.         ans_left = -1
4.         ans_right = len(s)
5.         cnt_s = Counter()
6.         cnt_t = Counter(t)
7.         
8.         left = 0
9.         for right, c in enumerate(s):
10.             cnt_s[c] += 1
11.             while cnt_s >= cnt_t:
12.                 if right-left < ans_right-ans_left:
13.                     ans_left, ans_right = left, right
14.                 cnt_s[s[left]] -= 1
15.                 left += 1
16.         return "" if ans_left < 0 else s[ans_left:ans_right+1]
17.                     

复制代码

二、【平凡数组】53.最大子数组和

1. 解题思绪

        本题采用动态规划五部曲进行解答。
        （1）定义dp数组：dp体现的是以nums末端的最大连续子序列的和。
        （2）递推公式：可以发现，连续子序列的和dp分为两种状态可以得到，一是dp[i-1]+nums，也就是连续前面的子序列；另一种是nums，也就是从该元素开始的子序列。因此，得到递推公式：dp = max(dp[i-1]+nums, nums )
        （3）初始化：dp[0]必须初始化为数组的头元素，即dp[0] = nums[0]，别的的元素可以初始化任意值，因为随着状态转移其真正的值会覆盖初始值。
        （4）遍历顺序：正常的遍历顺序即可。
        （5）打印：注意最后输出的不是dp，因为最大子数组和不一定是最后一个元素末端的。
2. 代码实现

1. class Solution:
2.     def maxSubArray(self, nums: List[int])->int:
3.         dp = [0] * len(nums)
4.         dp[0] = nums[0]
5.         for i in range(1, len(nums)):
6.             dp[i] = max(dp[i-1]+nums[i], nums[i])
7.         return max(dp)

复制代码

三、【平凡数组】56.归并区间

1. 解题思绪

        本题采用贪心算法。
        （1）为了方便对区间进行归并，必要对区间按照左边界大概右边界进行排序。
        （2）判断区间是否发生重叠：当前区间的左边界是否小于即是上一个区间的右边界，如果是则分析这两个区间发生了重叠，那么必要归并区间；如果不是则分析没有发生重叠，那么定义一个新数组存放将当前区间。
        （3）注意：在归并区间的过程中，是更新区间的右边界，但最新的右边界并不一定是当前区间的右边界，因为大概存在上一个区间右边界大于当前区间右边界的情况，所以在进行归并的时候，更新右边界应该是取当前区间右边界和上一个区间右边界的最大值。

2. 代码实现

1. class Solution:
2.     def merge(self, intervals:List[List[int]])->List[List[int]]:
4.         # 定义一个变量result用于存放结果集
5.         result = []
7.         # 判断给出的intervals是否为空
8.         if len(intervals) == 0:
9.             return result
11.         # 按照左边界对区间进行排序
12.         intervals.sort(key = lambda x: x[0])
13.         
14.         # 将第一个区间加入到结果集中，再进行更新即可
15.         result.append(intervals[0])
17.         # 遍历区间，从1开始是因为为了防止i-1异常
18.         for i in range(1, len(intervals)):
19.             # 判断区间是否重叠
20.             if result[-1][1]>=intervals[i][0]:
21.                 result[-1][1] = max(result[-1][1], intervals[i][1])
22.             else:
23.                 result.append(intervals[i])
24.         return result

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。