904. 水果成篮
- 思路
- example
- 两个篮子，返回你可以收集的水果的 最大 数目
- 等价于“最长的含两个不同数字的连续子序列长度”
- Two Pointer, Sliding Window, -->-->
- left, right = 0, 0
- use hash, i.e., dict to record the fruits
- dict[num] = freq
- len(dict) is always <= 2
- [left, right] is feasible if len(dict) <= 2，左闭右闭，可行窗口
- 注意最大与最小的处理逻辑不同。
本题
遍历 right:
处理right
循环收缩left找到可行窗口
处理可行窗口
- 复杂度. 时间：O(n), 空间: O(1)
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
n = len(fruits)
left, right = 0, 0
basket = collections.defaultdict(int)
res = 0
while right < n:
# "add"/test current fruit into the basket
basket[fruits[right]] += 1
# then check the feasibility
while len(basket) > 2: # more than 2 types of fruits, [left, right] is not feasible
# move left
basket[fruits[left]] -= 1
if basket[fruits[left]] == 0:
del basket[fruits[left]] # need to del this otherwise we could not use len(basket)
left += 1
# [left, right] is feasible, update res
res = max(res, right - left + 1)
# move right
right += 1
return res
- try this
import collections
dict1 = collections.defaultdict(int)
print(dict1)
print(dict1[2])
print(len(dict1))
print(dict1[3])
print(len(dict1))
print(dict1)
76. 最小覆盖子串
- 思路
- example
- 等价于“最短的连续子串(包含t)"
- sliding window, -->-->
- left, right = 0, 0
- two hashes, cnt_s, cnt_t, "cnt[ch] = freq"
- feasible window [left, right]
- valid == len(t) (valid always <= len(t))
- it's possible that cnt_s[ch] > cnt_t[ch] for some ch in s[left: right+1]
- once find a feasible window, keep moving left to update the result (needs smallest substring)
-
Key: for a feasible window, cnt_s[s[right]] is exactly equal to cnt_t[s[right]]
hash: cnt_s (变化），cnt_t (不变）
valid记录当前窗口含有ｔ元素的个数。（valid 最大值ｎ）
遍历right:
处理right (更新cnt_s, valid)
如果窗口可行(size=n), 循环收缩left找到满足要求的最小窗口 （更新cnt_s, valid, 答案)
- 复杂度. 时间：O(n), 空间: O(1)
class Solution:
def minWindow(self, s: str, t: str) -> str:
m, n = len(s), len(t)
if m < n:
return ''
# fix cnt_t
cnt_t = collections.defaultdict(int)
for ch in t:
cnt_t[ch] += 1
#
cnt_s = collections.defaultdict(int)
left, right = 0, 0
valid = 0
start, end = 0, -1
min_len = float('inf') # smallest length of feasible window
while right < m:
ch = s[right]
cnt_s[ch] += 1
if cnt_s[ch] <= cnt_t[ch]: # add one valid char
valid += 1
while valid == n: # [left, right] is a feasible, keep moving left to find the smallest window
cur_len = right - left + 1
if cur_len < min_len:
min_len = cur_len
start, end = left, right # record
cnt_s[s[left]] -= 1
if cnt_s[s[left]] < cnt_t[s[left]]: # cnt_t[s[left]] is at least 0 (defaultdict)
valid -= 1
left += 1
# move right
right += 1
return s[start:end+1]
- version 2: 每一步都把left指针移动到“最佳“位置。
-
Key: for a feasible window, cnt_s[s[left]] is exactly equal to cnt_t[s[left]]
-
hash: cnt_s (变化），cnt_t (不变）
valid记录当前窗口含有ｔ元素的个数。（valid 最大值ｎ）
遍历right:
处理right (更新cnt_s, valid)
循环收缩left直到左边界处在最佳位置 (cnt_s[s[left]] == cnt_t[s[left]])，结束后得到“预可行”窗口（valid < n)
如果窗口可行，更新最小值
class Solution:
def minWindow(self, s: str, t: str) -> str:
m, n = len(s), len(t)
if m < n:
return ''
# fix cnt_t
cnt_t = collections.defaultdict(int)
for ch in t:
cnt_t[ch] += 1
#
cnt_s = collections.defaultdict(int)
left, right = 0, 0
valid = 0
start, end = 0, -1
min_len = float('inf') # smallest length of feasible window
while right < m:
ch = s[right]
cnt_s[ch] += 1
if cnt_s[ch] <= cnt_t[ch]: # add one valid char
valid += 1
# keep moving left to remove the unnecessary char, until cnt_s[s[left]] == cnt_t[s[left]]
while left <= right and cnt_s[s[left]] > cnt_t[s[left]]:
cnt_s[s[left]] -= 1
left += 1
# check feasibility
if valid == n: # now [left, right] will be the shortest feasible substring
cur_len = right - left + 1
if cur_len < min_len:
min_len = cur_len
start, end = left, right
# move right
right += 1
return s[start:end+1]
54. 螺旋矩阵
- 思路
- example
- size of matrix:
- slightly change the update style inside the loop
- 贪心策略：右，下，左，上。每个方向都尽可能搜索，这样可以方便处理单行单列的情况。
- deal with the boundary case (eg., one row, one column)
- should work for m==n case
- 复杂度. 时间：
, 空间: O(1)
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
m, n = len(matrix), len(matrix[0])
top, bottom = 0, m-1
left, right = 0, n-1
res = []
while top <= bottom and left <= right:
#-->
for j in range(left, right+1):
res.append(matrix[top][j])
# downward (right column)
for i in range(top+1, bottom+1):
res.append(matrix[i][right])
#<--
if top < bottom and left < right: # extra row or column updates
for j in range(right-1, left-1, -1):
res.append(matrix[bottom][j])
for i in range(bottom-1, top, -1):
res.append(matrix[i][left])
# update indices
top += 1
bottom -= 1
left += 1
right -= 1
return res
48. 旋转图像
- 思路
- example
- size of matrix:
先按主对角线翻转
再每一行进行翻转
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
def reverse(nums):
n = len(nums)
left, right = 0, n-1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
# step 1
n = len(matrix)
for i in range(n):
for j in range(i+1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# step 2
for i in range(n):
reverse(matrix[i])
数组总结
- 二分搜索
- 左闭右闭
- 左闭右开
- 双指针
- 快慢，前后， 。。。
- 滑动窗口
- 同向移动 -->-->
- left, right 初始化
- 外层循环：right
- 内层：left
- 判断当前窗口可行性，移动left
- 计数
- hash技术
-
滑动窗口：本质是满足了单调性,即左右指针只会往一个方向走且不会回头。收缩的本质即去掉不再需要的元素。也就是做题我们可以先固定移动右指针，判断条件是否可以收缩左指针算范围。大家可以好好理解一下。From 芒果冰
- <--*-->
- -->*<--
