根據(jù)數(shù)據(jù)結(jié)構(gòu)和算法的分類來進(jìn)行刷題，有時(shí)候會(huì)有一種被劇透了的感覺箱亿，思考方向會(huì)不自覺靠著對(duì)應(yīng)算法上去想。如果出現(xiàn)一道沒有見過的題目弃秆，有時(shí)候很難想到對(duì)應(yīng)的解法届惋，通過一些關(guān)鍵詞的常見套路，可以很快找到解題思路菠赚。
一脑豹、看數(shù)據(jù)范圍大小
通過提供的數(shù)據(jù)范圍大小可以大致判斷出所需算法的時(shí)間復(fù)雜度
時(shí)間復(fù)雜度對(duì)應(yīng)的算法
二、數(shù)據(jù)結(jié)構(gòu)
看處理對(duì)象的數(shù)據(jù)結(jié)構(gòu)衡查，比較常見的有：一維數(shù)組瘩欺，二維數(shù)組寓涨，字符串怎栽，二叉樹
1. 一維數(shù)組
根據(jù)我個(gè)人的做題經(jīng)驗(yàn)贵试，將數(shù)組問題大致劃分為以下幾個(gè)方向：數(shù)組有序沮脖，數(shù)組無序，子數(shù)組問題拍埠，子序列問題阁吝，多個(gè)數(shù)組問題。
數(shù)組有序
如果題目沒有要求保留原來順序的械拍，都可以將數(shù)組進(jìn)行排序突勇。
a. 數(shù)組有序/有單調(diào)性
如果數(shù)組本身具有單調(diào)性，需要尋找的是數(shù)組中的某個(gè)值坷虑，可以考慮二分搜索甲馋。
33 搜索旋轉(zhuǎn)排序數(shù)組
整數(shù)數(shù)組 nums 按升序排列，數(shù)組中的值 互不相同 迄损。
在傳遞給函數(shù)之前定躏，nums 在預(yù)先未知的某個(gè)下標(biāo) k（0 <= k < nums.length）上進(jìn)行了 旋轉(zhuǎn)，使數(shù)組變?yōu)?[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下標(biāo) 從 0 開始 計(jì)數(shù)）芹敌。例如痊远， [0,1,2,4,5,6,7] 在下標(biāo) 3 處經(jīng)旋轉(zhuǎn)后可能變?yōu)?[4,5,6,7,0,1,2] 。
給你 旋轉(zhuǎn)后 的數(shù)組 nums 和一個(gè)整數(shù) target 氏捞，如果 nums 中存在這個(gè)目標(biāo)值 target 碧聪，則返回它的下標(biāo)，否則返回 -1 液茎。
雖然數(shù)組在某處進(jìn)行了旋轉(zhuǎn)逞姿，但依舊是部分有序的，仍然可以使用二分搜索捆等。將數(shù)組分為左右兩部分時(shí)可以發(fā)現(xiàn)滞造，必定有一部分是有序，根據(jù)有序的部分可以判斷上下界的迭代栋烤。
def search(self, nums: List[int], target: int) -> int:
if not nums:
return -1
l, r = 0, len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
return mid
if nums[0] <= nums[mid]:
if nums[0] <= target < nums[mid]:
r = mid - 1
else:
l = mid + 1
else:
if nums[mid] < target <= nums[len(nums) - 1]:
l = mid + 1
else:
r = mid - 1
return -1
4 尋找兩個(gè)正序數(shù)組的中位數(shù)（歸并+二分）
81 搜索旋轉(zhuǎn)排序數(shù)組 II
153 尋找旋轉(zhuǎn)排序數(shù)組中的最小值
378 有序矩陣中第 K 小的元素
如果數(shù)組本身已經(jīng)排序谒养，并且需要找出兩個(gè)數(shù)字，那么可以使用雙指針明郭。
167 兩數(shù)之和 II - 輸入有序數(shù)組
b. 求解過程中存在單調(diào)性
在按照題目的描述一步步求解的過程中买窟，如果發(fā)現(xiàn)搜索目標(biāo)解的過程中，搜索過的值單調(diào)遞增或者遞減达址，可以通過維護(hù)單調(diào)棧來實(shí)現(xiàn)蔑祟。要意識(shí)到這一點(diǎn)需要根據(jù)題目要求，將求解過程模擬出來沉唠。
42 接雨水
給定 n 個(gè)非負(fù)整數(shù)表示每個(gè)寬度為 1 的柱子的高度圖，計(jì)算按此排列的柱子苛败，下雨之后能接多少雨水满葛。
首先思考什么樣的柱子才能接到雨水径簿，必然是一個(gè)“洼地”。假設(shè)對(duì)一片“洼地”從左向右遍歷嘀韧，在到達(dá)最低點(diǎn)前篇亭，柱子的高度一定是遞減的，因此可以使用單調(diào)棧來記錄數(shù)據(jù)锄贷。如果遍歷到的數(shù)字不滿足遞減關(guān)系了译蒂，說明到了“洼地”的另一側(cè)，此時(shí)可以計(jì)算出能接到的雨水的增量谊却。更加詳細(xì)的動(dòng)畫演示可以參考力扣的題解柔昼。
def trap(self, height: List[int]) -> int:
n = len(height)
stack = []
ans = 0
for i in range(n):
curr = height[i]
while stack and curr>height[stack[-1]]:
last = stack.pop()
while stack and height[stack[-1]]==height[last]:
stack.pop()
if stack:
h= min(height[stack[-1]], curr)-height[last]
ans += h*(i-stack[-1]-1)
stack.append(i)
return ans
c. 求解結(jié)果有序
對(duì)于前 k 大或前 k 小這類問題，有一個(gè)通用的解法：優(yōu)先隊(duì)列炎辨。優(yōu)先隊(duì)列可以在O(logn) 的時(shí)間內(nèi)完成插入或刪除元素的操作（其中 n 為優(yōu)先隊(duì)列的大胁锻浮），并可以 O(1)地查詢優(yōu)先隊(duì)列頂端元素碴萧。
215 數(shù)組中的第K個(gè)最大元素
在未排序的數(shù)組中找到第 k 個(gè)最大的元素乙嘀。請(qǐng)注意，你需要找的是數(shù)組排序后的第 k 個(gè)最大的元素破喻，而不是第 k 個(gè)不同的元素虎谢。
使用一個(gè)小根堆，如果小根堆的大小小于K就向里面加數(shù)字曹质，否則就彈出堆頂（K+1個(gè)數(shù)中最小的）嘉冒，最后堆頂就是第K大的元素。
def findKthLargest(self, nums: List[int], k: int) -> int:
n = len(nums)
heap = []
for i in range(n):
heapq.heappush(heap, nums[i])
if len(heap)>k:
heapq.heappop(heap)
return heap[0]
數(shù)組無序
a. 存在對(duì)應(yīng)關(guān)系
如果在數(shù)組中存在對(duì)應(yīng)關(guān)系咆繁，可以通過哈希表存儲(chǔ)關(guān)鍵字讳推，減少計(jì)算，提高代碼效率玩般。這里的對(duì)應(yīng)關(guān)系可以是一個(gè)數(shù)學(xué)關(guān)系银觅，或者是某種映射關(guān)系，比如數(shù)組索引與對(duì)應(yīng)數(shù)字的關(guān)系坏为，與頻數(shù)相關(guān)的題目也經(jīng)常會(huì)用哈希表究驴。
1兩數(shù)之和
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出 和為目標(biāo)值 的那 兩個(gè) 整數(shù)匀伏，并返回它們的數(shù)組下標(biāo)洒忧。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是够颠，數(shù)組中同一個(gè)元素在答案里不能重復(fù)出現(xiàn)熙侍。
數(shù)組中的元素存在著對(duì)應(yīng)關(guān)系：nums[i] = target - nums[j], nums[i] 與索引 i。
可以以nums[i]為key，以索引i為value蛉抓，對(duì)于每一個(gè)值nums[i]庆尘，尋找target - nums[j]是否存在于哈希表內(nèi)。
def twoSum(self, nums: List[int], target: int) -> List[int]:
table = {}
for i in range(len(nums)):
if target-nums[i] in table:
return [table[target-nums[i]],i]
table[nums[i]] = i
return []
454四數(shù)相加II
給定四個(gè)包含整數(shù)的數(shù)組列表 A , B , C , D ,計(jì)算有多少個(gè)元組 (i, j, k, l) 巷送，使得 A[i] + B[j] + C[k] + D[l] = 0驶忌。
可以將這個(gè)四數(shù)相加的問題轉(zhuǎn)化為兩數(shù)相加的問題，將A,B,C,D分為兩組笑跛，分別為A,B相加的所有可能結(jié)果和C,D相加的所有可能結(jié)果付魔，要尋找的是滿足 A[i] + B[j] = - C[k] - D[l]的元組的個(gè)數(shù)。
以A[i] + B[j]的值為key飞蹂，以出現(xiàn)次數(shù)為value建立哈希表几苍，在C,D中尋找滿足A[i] + B[j] = - C[k] - D[l]的索引，并計(jì)算出現(xiàn)次數(shù)晤柄。
def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
n = len(A)
ans = 0
group1 = collections.defaultdict(int)
for i in range(n):
for j in range(n):
group1[A[i]+B[j]]+=1
for i in range(n):
for j in range(n):
tmp = C[i]+D[j]
if -tmp in group1:
ans += group1[-tmp]
return ans
其他用到了哈希表的題目：
30 串聯(lián)所有單詞的子串
138 復(fù)制帶隨機(jī)指針的鏈表
146 LRU緩存機(jī)制
b. 需要同時(shí)維護(hù)兩個(gè)值
如果求解過程中需要同時(shí)維護(hù)兩個(gè)變量擦剑，可以考慮雙指針。如果暴力的解法需要用到多重循環(huán)枚舉芥颈，并且在枚舉時(shí)發(fā)現(xiàn)枚舉元素間保持著某種關(guān)系惠勒，比如隨著第一個(gè)元素增加，第二個(gè)元素是遞減的（三數(shù)之和）爬坑，就可以使用雙指針的方法纠屋，將時(shí)間復(fù)雜度從減少到
。
11 盛最多水的容器
給你 n 個(gè)非負(fù)整數(shù) a1盾计，a2售担，...，an署辉，每個(gè)數(shù)代表坐標(biāo)中的一個(gè)點(diǎn) (i, ai) 族铆。在坐標(biāo)內(nèi)畫 n 條垂直線，垂直線 i 的兩個(gè)端點(diǎn)分別為 (i, ai) 和 (i, 0) 哭尝。找出其中的兩條線哥攘，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。
盛水需要左右兩個(gè)邊同時(shí)存在材鹦，并且左右兩邊中較小的那個(gè)決定了水位的高度逝淹，左右兩邊的間隔決定了容器的長(zhǎng)度，可以使用左右兩個(gè)指針來分別指向左右兩邊桶唐。
尋找盛水最多的容器需要遍歷容器的長(zhǎng)度和水位的高度栅葡，長(zhǎng)度可以通過移動(dòng)左右指針來實(shí)現(xiàn)。水位高度是由最短邊決定的尤泽，因此無論長(zhǎng)邊如何移動(dòng)欣簇，得到的水位高度都會(huì)等于或者小于短邊的高度规脸，因此每一次迭代，需要移動(dòng)短的一邊醉蚁。
def maxArea(self, height: List[int]) -> int:
maxare = 0
left = 0
right = len(height) -1
while left <right:
distance = right-left
maxare = max(maxare, min(height[left],height[right])*(distance))
if height[left] <height[right]:
left += 1
else:
right -=1
return maxare
c. 左右各遍歷一次
比較有技巧性的方法燃辖，從左向右遍歷一次數(shù)組鬼店，再從右向左遍歷一次數(shù)組网棍，應(yīng)用場(chǎng)景與雙指針相似，但是不太容易想到妇智。當(dāng)要求解的是最大最小的問題滥玷，比如距離最近的最大是多少，有可能用到這種技巧巍棱。
581. 最短無序連續(xù)子數(shù)組
給你一個(gè)整數(shù)數(shù)組 nums 惑畴，你需要找出一個(gè) 連續(xù)子數(shù)組 ，如果對(duì)這個(gè)子數(shù)組進(jìn)行升序排序航徙，那么整個(gè)數(shù)組都會(huì)變?yōu)樯蚺判颉?br> 請(qǐng)你找出符合題意的 最短 子數(shù)組如贷，并輸出它的長(zhǎng)度。
根據(jù)題意需要找到的是到踏，數(shù)組中需要排序的最短子數(shù)組的邊界杠袱。對(duì)于一個(gè)已經(jīng)排好序的數(shù)組，從左到右遍歷到的最大值應(yīng)該等于當(dāng)前值窝稿，從右到左遍歷到的最小值楣富，應(yīng)該也是當(dāng)前值；否則就說明當(dāng)前遍歷到的數(shù)字為亂序伴榔。從左到右遍歷和從右到左遍歷分別記錄下需要排序的子數(shù)組的起始和終止位置纹蝴。
def search(arr,n):
if n<2:
return 0
leftMax, leftId = float('-inf'), -1
rightMin, rightId = float('inf'),-1
for i in range(n):
if arr[i]>=leftMax:
leftMax = arr[i]
else:
leftId = i # index of num smaller than the leftMax
if leftId ==-1:
return 0
for i in range(n-1,-1,-1):
if arr[i]<=rightMin:
rightMin = arr[i]
else:
rightId = i
return leftId-rightId+1
網(wǎng)易校招筆試-電影院選座
疫情逐步緩和后，電影院終于開業(yè)了踪少，但是由于當(dāng)前仍處于疫情期間塘安，應(yīng)盡量保持人群不聚集的原則。所以當(dāng)小易來電影院選定一排后援奢，盡量需要選擇一個(gè)遠(yuǎn)離人群的位置兼犯。已知由0和1組成的數(shù)組表示當(dāng)前排的座位情況,其中1表示已被選座，0表示空座請(qǐng)問小易所選座位和最近人的距離座位數(shù)最大是多少萝究？有如下假設(shè)：至少有一個(gè)人已選座免都，至少有一個(gè)空座位，且座位數(shù)限制為[2,1000]帆竹。
從左到右遍歷一次绕娘，從右到左遍歷一次，分別計(jì)算坐在位置i的適合栽连，距離左邊第一個(gè)1的距離和距離右邊第一個(gè)的距離险领，取每個(gè)位置上左右距離中最小的那個(gè)侨舆，然后取其中的最大值。
參考：
Leetbook-2021 春招沖刺攻略
程序員代碼面試指南
