Top 100 Linked Question 修炼------第75题、第76题
75. Sort Colors
题目解释：给出n个物体，它们的颜色分别是红色、白色或者是蓝色，将它们按照颜色顺序进行排序，要求相邻的物体颜色是一样的，同时这个物体颜色的排列顺序为红色、白色、蓝色。
要求：空间复杂度为O(1)
题目给的示例如下：
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]其中0是代表红色，1是代表白色，2是代表蓝色。
题目分析：总体的来说，这个题目和之前做过的‘荷兰国旗颜色分类’题目是一模一样的，在这里也总结一下思路吧。想明白我们本题其实很简单，我们可以设计三个指针：i，j，k.三个指针的作用如下：其中i是工作指针，是遍历整个数组的，j指针之前全都是红色，k指针之后全都是蓝色，这样，当完成了一次遍历之后，我们的颜色就能完美的区分开来了。下面的代码是完全基于这个算法思想的：
def sortColors(self, nums):
"""
Do not return anything, modify nums in-place instead.
"""
i,j,k=0,0,len(nums)-1
while j<=k:
if nums[j]==0:
nums[i],nums[j]=nums[j],nums[i]
i+=1
j+=1
continue
if nums[j]==1:
j+=1
continue
elif nums[j]==2:
nums[j], nums[k] = nums[k], nums[j]其中大家可以思考一下，为什么当nums[j]==2的条件之后，我们不需要将j指针加1？
76. Minimum Window Substring
题目解释：给出一个字符串S和字符串T，在S中找到最小的子串，使其能够包含T中所有的字符。
Example:
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"要求：时间复杂度为O(n)
注意：
- 要是s中不存在这样的子串包含所有的T中的字符，那么就需要返回""
- 如果存在这样的子串，保证在S中始终只有一个唯一的最小窗口。
PS：为了简单的理解，本人将窗口类似的翻译全都转换为了求子串的翻译，本质是一样的。
题目分析：在这里给leetcode中的Solution给我们提供了一种新的方法，个人感觉学习起来是非常有意思的：
算法步骤：
-
我们使用两个指针，刚开始的时候，left和right指针都是指向字符串S的首部
-
将right指针右移，直到left和righ之间的字符串能够包含T中的所有的字符
-
向前移动left指针，如果移动之后left和right之间的字符串仍然是包含T中所有的字符，那么我们将减小这个移动的窗口，继续向前移动left指针；
-
当移动left指针后不包含了字符串T中所有的字符，那么我们跳到步骤2，直到所有的元素都被遍历一遍
当遍历完所有的元素的时候，最小的窗口将会被返回
有了这个思想，我们很容易的写出相关的代码：
def minWindow(self, s, t):
if not t or not s:
return ""
dict_t = Counter(t)
required = len(dict_t)
l, r = 0, 0
formed = 0
window_counts = {}
ans = float("inf"), None, None
while r < len(s):
character = s[r]
window_counts[character] = window_counts.get(character, 0) + 1
if character in dict_t and window_counts[character] == dict_t[character]:
formed += 1
while l <= r and formed == required:
character = s[l]
if r - l + 1 < ans[0]:
ans = (r - l + 1, l, r)
window_counts[character] -= 1
if character in dict_t and window_counts[character] < dict_t[character]:
formed -= 1
l += 1
r += 1
return "" if ans[0] == float("inf") else s[ans[1]: ans[2] + 1]总结
学无止境....
Reference
https://leetcode.com/problems/minimum-window-substring/solution/