5.1題目 1305. 兩棵二叉搜索樹中的所有元素

【中序遍歷 + 歸并】中序遍歷這兩棵二叉搜索樹，可以得到兩個有序數(shù)組。然后可以使用雙指針方法來合并這兩個有序數(shù)組.

5.2題目 591. 標(biāo)簽驗證器

【棧 + 字符串遍歷】一次遍歷，判斷是否合法。

5.3題目 937. 重新排列日志文件

【自定義排序】定義比較函數(shù)logCompare時，有兩個輸入log1和log2。當(dāng)相等時，返回0；當(dāng)log1大時，返回正數(shù)；當(dāng)log2大時，返回負數(shù)。

5.4題目 1823. 找出游戲的獲勝者

【隊列】按題意模擬。

5.5題目 713. 乘積小于 K 的子數(shù)組

【滑動窗口】枚舉子數(shù)組右端點j，左端點從i = 0開始用prod記錄子數(shù)字[i,j]的元素乘積。

5.6題目 933. 最近的請求次數(shù)

【隊列】用一個隊列維護發(fā)生請求的時間，當(dāng)在時間t收到請求時，將時間t入隊。

5.7題目 433. 最小基因變化

【BFS】嘗試所有合法的基因變化，并找到最小的變換次數(shù)即可.

5.8題目 442. 數(shù)組中重復(fù)的數(shù)據(jù)

【一次遍歷】用正負號作為標(biāo)記，正數(shù)說明沒出現(xiàn)過，加上負號，負數(shù)說明已經(jīng)出現(xiàn)過，加入答案。

5.9題目 942. 增減字符串匹配

【貪心】每次都選擇的是最小數(shù)和最大數(shù)，可以用兩個變量o和hi表示當(dāng)前剩余數(shù)字中的最小數(shù)和最大數(shù)。

5.10題目 1728. 貓和老鼠 II

【拓撲排序】極大極小博弈，老鼠盡量找自己獲勝的，其次接受平局 貓盡量找自己獲勝的，其次接受平局，param m: 老鼠的位置，param c: 貓的位置，param i: 回合。

5.11題目 449. 序列化和反序列化二叉搜索樹

【后序遍歷】序列化時，只需要對二叉搜索樹進行后序遍歷，再將數(shù)組編碼成字符串即可。

5.12題目 944. 刪列造序

【遍歷】逐列訪問字符串?dāng)?shù)組，統(tǒng)計不是按字典序升序排列的列。

5.13題目 面試題 01.05. 一次編輯

【分類討論】如果frst和second需要一次編輯，則可能有三種情況：往frst中插入一個字符得到second，此時n-m=1，second比irst多一個字符，其余字符都相同；從first中刪除一個字符得到second，此時m-n=1，first比second多一個字符，其余字符都相同；將first中的一個字符替換成不同的字符得到second，此時m=n，first和second恰好有一個字符不同。

5.14題目 691. 貼紙拼詞

【記憶化搜索 + 狀態(tài)壓縮】定義函數(shù)dp(mask)來求解不同狀態(tài)的最小貼紙數(shù)，輸入是某個子序列mask，輸出是拼出該子序列的最小貼紙數(shù)。

5.15題目 812. 最大三角形面積

【枚舉】三角形面積公式。

5.16題目 面試題 04.06. 后繼者

【中序遍歷】由于只需要找到節(jié)點p的后繼節(jié)點，因此不需要維護完整的中序遍歷序列，只需要在中序遍歷的過程中維護上一個訪問的節(jié)點和當(dāng)前訪問的節(jié)點。如果上一個訪問的節(jié)點是節(jié)點p，則當(dāng)前訪問的節(jié)點即為節(jié)點p的后繼節(jié)點。

5.17題目 953. 驗證外星語詞典

【遍歷】依次檢測strs中的字符串前一個字符串和后一個字符串在給定的字母表下的字典序即可。

5.18題目 668. 乘法表中第k小的數(shù)

【二分】求第幾小等價于求有多少數(shù)字不超過x，可以遍歷乘法表的每一行。

5.19題目 462. 最小操作次數(shù)使數(shù)組元素相等 II

【排序】所有元素都變成nums?len(nums) / 2?時，移動次數(shù)最少。

5.20題目 436. 尋找右區(qū)間

【二分】對區(qū)間ntervals的起始位置進行排序，并將每個起始位置intervals[i][0]對應(yīng)的索引i存儲在數(shù)組startIntervals中，然后枚舉每個區(qū)間i的右端點intervals[i[1]，利用二分查找來找到大于等于intervals[[1]的最小值val即可，此時區(qū)間i對應(yīng)的右側(cè)區(qū)間即為右端點val對應(yīng)的索引。

5.21題目 961. 在長度 2N 的數(shù)組中找出重復(fù) N 次的元素

【數(shù)學(xué)】如果相鄰的x之間至少都隔了2個位置，那么數(shù)組的總長度至少為：n+2（n-1）=3n-2，只需要遍歷所有間隔2個位置及以內(nèi)的下標(biāo)對，判斷對應(yīng)的元素是否相等即可。

5.22題目 464. 我能贏嗎

【記憶化搜索 + 狀態(tài)壓縮】考慮邊界情況，當(dāng)所有數(shù)字選完仍無法到達desiredTotal時，兩人都無法獲勝，返回false。當(dāng)所有數(shù)字的和大于等于desiredTotal時，其中一方能獲得勝利，需要通過搜索來判斷獲勝方。

5.23題目 675. 為高爾夫比賽砍樹

【BFS】對矩陣中的樹按照樹的高度進行排序，依次求出相鄰的樹之間的最短距離。利用廣度優(yōu)先搜索，按照層次遍歷，處理隊列中的節(jié)點（網(wǎng)格位置）。visited記錄在某個時間點已經(jīng)添加到隊列中的節(jié)點，這些節(jié)點已被處理或在等待處理的隊列中。對于下一個要處理的每個節(jié)點，查看他們的四個方向上相鄰的點，如果相鄰的點沒有被遍歷過且不是障礙，將其加入到隊列中，直到找到終點為止，返回當(dāng)前的步數(shù)即可。最終返回所有的步數(shù)之和即為最終結(jié)果。

5.24題目 965. 單值二叉樹

【DFS】一棵樹的所有節(jié)點都有相同的值，當(dāng)且僅當(dāng)對于樹上的每一條邊的兩個端點，它們都有相同的值（這樣根據(jù)傳遞性，所有節(jié)點都有相同的值）。因此，我們可以對樹進行一次深度優(yōu)先搜索。當(dāng)搜索到節(jié)點x時，我們檢查x與x的每一個子節(jié)點之間的邊是否滿足要求。例如對于左子節(jié)點而言，如果其存在并且值與x相同，那么我們繼續(xù)向下搜索該左子節(jié)點；如果值與x不同，那么我們直接返回False。.

5.25題目 467. 環(huán)繞字符串中唯一的子字符串

【DP】定義dp[α]為p中以字符a結(jié)尾且在s中的子串的最長長度。

5.26題目 699. 掉落的方塊

【暴力枚舉】用數(shù)組heights記錄各個方塊掉落后的高度。

5.27題目 面試題 17.11. 單詞距離

【一次遍歷】從左到右遍歷數(shù)組vords，當(dāng)遍歷到word1時，如果已經(jīng)遍歷的單詞中存在word，為了計算最短距離，應(yīng)該取最后一個已經(jīng)遍歷到的wor所在的下標(biāo)，計算和當(dāng)前下標(biāo)的距離。同理，當(dāng)遍歷到word時，應(yīng)該取最后一個已經(jīng)遍歷到的word所在的下標(biāo)，計算和當(dāng)前下標(biāo)的距離。

5.28題目 1021. 刪除最外層的括號

【?！勘闅vs，并用一個棧來表示括號的深度。遇到‘（則將字符入棧，遇到）'則將棧頂字符出棧。

5.29題目 468. 驗證IP地址

【依次判斷】ipv4和ipv6分別判斷，長度、if包含數(shù)字、值范圍，是否含前導(dǎo)零…

5.30題目 1022. 從根到葉的二進制數(shù)之和

【遞歸】如果節(jié)點是葉子節(jié)點，返回它對應(yīng)的數(shù)字val；如果節(jié)點是非葉子節(jié)點，返回它的左子樹和右子樹對應(yīng)的結(jié)果之和。

5.31題目 劍指 Offer II 114. 外星文字典

【拓撲排序 + DFS】對于一個特定節(jié)點，如果該節(jié)點的所有相鄰節(jié)點都已經(jīng)搜索完成，則該節(jié)點也會變成已經(jīng)搜索完成的節(jié)點，在拓撲排序中，該節(jié)點位于其所有相鄰節(jié)點的前面。一個節(jié)點的相鄰節(jié)點指的是從該節(jié)點出發(fā)通過一條有向邊可以到達的節(jié)點。