904. 水果成籃
- 思路
- example
- 兩個(gè)籃子，返回你可以收集的水果的 最大 數(shù)目
- 等價(jià)于“最長的含兩個(gè)不同數(shù)字的連續(xù)子序列長度”
- 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
循環(huán)收縮left找到可行窗口
處理可行窗口
- 復(fù)雜度. 時(shí)間：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
- 等價(jià)于“最短的連續(xù)子串(包含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記錄當(dāng)前窗口含有ｔ元素的個(gè)數(shù)。（valid 最大值ｎ）
遍歷right:
處理right (更新cnt_s, valid)
如果窗口可行(size=n), 循環(huán)收縮left找到滿足要求的最小窗口 （更新cnt_s, valid, 答案)
- 復(fù)雜度. 時(shí)間：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指針移動(dòng)到“最佳“位置。
-
Key: for a feasible window, cnt_s[s[left]] is exactly equal to cnt_t[s[left]]
-
hash: cnt_s (變化），cnt_t (不變）
valid記錄當(dāng)前窗口含有ｔ元素的個(gè)數(shù)。（valid 最大值ｎ）
遍歷right:
處理right (更新cnt_s, valid)
循環(huán)收縮left直到左邊界處在最佳位置 (cnt_s[s[left]] == cnt_t[s[left]])，結(jié)束后得到“預(yù)可行”窗口（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
- 貪心策略：右，下，左，上。每個(gè)方向都盡可能搜索，這樣可以方便處理單行單列的情況。
- deal with the boundary case (eg., one row, one column)
- should work for m==n case
- 復(fù)雜度. 時(shí)間：
, 空間: 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. 旋轉(zhuǎn)圖像
- 思路
- example
- size of matrix:
先按主對(duì)角線翻轉(zhuǎn)
再每一行進(jìn)行翻轉(zhuǎn)
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])
數(shù)組總結(jié)
- 二分搜索
- 左閉右閉
- 左閉右開
- 雙指針
- 快慢，前后， 。。。
- 滑動(dòng)窗口
- 同向移動(dòng) -->-->
- left, right 初始化
- 外層循環(huán)：right
- 內(nèi)層：left
- 判斷當(dāng)前窗口可行性，移動(dòng)left
- 計(jì)數(shù)
- hash技術(shù)
-
滑動(dòng)窗口：本質(zhì)是滿足了單調(diào)性,即左右指針只會(huì)往一個(gè)方向走且不會(huì)回頭。收縮的本質(zhì)即去掉不再需要的元素。也就是做題我們可以先固定移動(dòng)右指針，判斷條件是否可以收縮左指針?biāo)惴秶４蠹铱梢院煤美斫庖幌?。From 芒果冰
- <--*-->
- -->*<--
