7.1題目 241. 為運算表達式設(shè)計優(yōu)先級

【分治】x op y (op為運算符),它的結(jié)果取決于x和y的結(jié)果組合數(shù)，該問題子問題就是x op y中的x和y：以運算符分割的左右側(cè)算式解，分治算法三步走:分解成左右兩部分分別求解，遞歸求子問題的解，合并左右兩部分的解得出最后解。

7.2題目 871. 最低加油次數(shù)

【貪心】1.計算當(dāng)前位置與上一個位置的距離之差，根據(jù)該距離之差得到從上一個位置行駛到當(dāng)前位置需要使用的汽油量，將使用的汽油量從剩余的汽油量中減去。2.剩余油量小于0說明無法從上一個位置行駛到當(dāng)前位置，取出優(yōu)先隊列中的最大元素加到剩余的汽油量，并將加油次數(shù)加 1，重復(fù)該操作直到剩余的汽油量大于等于 0 或優(yōu)先隊列變?yōu)榭铡?.如果優(yōu)先隊列變?yōu)榭諘r，剩余的汽油量仍小于 0，則表示在所有經(jīng)過的加油站加油之后仍然無法到達當(dāng)前位置，返回 -1。4.如果當(dāng)前位置是加油站，則將當(dāng)前加油站的加油量添加到優(yōu)先隊列中，并使用當(dāng)前位置更新上一個位置。

7.3題目 556. 下一個更大元素 III

【數(shù)學(xué)】從n開始，不斷比較其最低位數(shù)字和次地位數(shù)字的大小，如果次地位數(shù)字不低于最低位數(shù)字，則一處最低位數(shù)字，繼續(xù)循環(huán)，循環(huán)結(jié)束后的n就對應(yīng)方法以的下標(biāo)i，即nums的前i + 1個字符。

7.4題目 1200. 最小絕對差

【排序 + 一次遍歷】對arr升序排序，最小絕對差只能由有序數(shù)組相鄰的兩個元素構(gòu)成。用一個delta變量存遇到的最小差。

7.5題目 729. 我的日程安排表 I

【遍歷】區(qū)間如果沒有交集，說明s1 > e2 or s2 > e1。

【二分】起點≥end的第一個區(qū)間[l1,r1)，和前一個區(qū)間[l2, r2)，如果r2 ≤ start < end < l1則可以預(yù)定。

【線段樹】預(yù)定的區(qū)間中每個元素標(biāo)記為1，每次調(diào)用book時，需檢測區(qū)間內(nèi)元素是否標(biāo)記位1，不必世紀(jì)開辟10**9的數(shù)組，可以用動態(tài)線段樹，懶標(biāo)記lazy標(biāo)記[l,r]已經(jīng)被預(yù)定。

7.6題目 736. Lisp 語法解析

【遞歸解析】遞歸解析表達式——下一個字符!='('，去掉左括號后下一個字符是'|'、'a'、'm'。

7.7題目 648. 單詞替換

【哈希集合】將dic所有詞放入哈希集合中，對于每個單詞，從短至長遍歷它所有前綴，如果這個前綴出現(xiàn)在哈希集合中，則找到了當(dāng)前最短詞根，可以用這個詞根替換原來的單詞，最后返回拼接的句子。

7.8題目 1217. 玩籌碼

【貪心】移動到偶數(shù)位置的最小開銷就是初始奇數(shù)位置籌碼數(shù)量，移動到奇數(shù)位置的最小開銷就是初始偶數(shù)位置籌碼數(shù)量。

7.9題目 873. 最長的斐波那契子序列的長度

【暴力】每次從arr中找前兩個數(shù)，然后查看后續(xù)符合斐波那契的數(shù)在arr中有沒有。

7.10題目 741. 摘櫻桃

【DP】假設(shè)兩人同時出發(fā)，且速度相同，設(shè)兩人的坐標(biāo)為（x1，1）和（x2，2），則x1+1=x2+2=k。那么當(dāng)x1=x2時，必然有y1=y2，即兩個人到達了同一個格子。枚舉A和B上一步的走法，來計算f[k] [x1] [x2]，有四種情況。

7.11題目 676. 實現(xiàn)一個魔法字典

【枚舉】把字典中的所有字符串存儲在數(shù)組中，而當(dāng)進行search 操作時，我們將待查詢的字符串和數(shù)組中的字符串依次進行比較。

【字典樹】我們也可以使用字典樹代替數(shù)組，將所有字符串進行存儲。這一部分需要的時間是相同的。在查詢時，我們可以使用遞歸+回潮的方法，使用遞歸函數(shù)dfs(ode, pos, modified).

7.12題目 1252. 奇數(shù)值單元格的數(shù)目

【模擬】用n×m的矩陣存操作結(jié)果，對每一對[r_i,c_i]模擬。

【模擬空間優(yōu)化】用rows和cols記錄每一行和每一列被增加的次數(shù)。出位置（x，y）位置的計數(shù)即為rows[x] + cols[y]。

【計數(shù)優(yōu)化】矩陣中位于（x，y）位置的數(shù)為奇數(shù)，當(dāng)且僅當(dāng)rows[z和cols劃中恰好有一個為奇數(shù)，一個為偶數(shù)。設(shè)rows有odd個奇數(shù)，cols有odd個奇數(shù)。綜上我們可以得到奇數(shù)的數(shù)目為odd×（n-odd）+（m-odd）x oddy.

7.13題目 735. 行星碰撞

【棧模擬】st模擬行星，alive記錄是否還存在，只判斷一個方向：默認把向右的全入棧（向右的無需判斷)，向左的需要判斷是否爆炸，不爆炸就入棧。(alive = st[-1] < -a 省了if判斷)

7.14題目 745. 前綴和后綴搜索

【遍歷 + 哈希表】預(yù)先計算出每個單詞的組合可能性，用特殊符號連接。

7.15題目 558. 四叉樹交集

【分治】假設(shè)當(dāng)前操作的兩個節(jié)點分別為node1和node2，node1為葉子節(jié)點時，如果node1的值為1，那么node1 | node2 = node1，否則node1 | node2=node2。node2為葉子節(jié)點與之相反。兩者都不是葉子節(jié)點時：那么分別對兩者的四個子節(jié)點來進行對應(yīng)的分治處理一分別進行合并操作。

7.16題目 劍指 Offer II 041. 滑動窗口的平均值

【列表】按題意模擬。

【隊列】隊列中數(shù)字=滑動窗口的大小，移除隊首的數(shù)字 就 將滑動窗口的數(shù)字之和中減去。計算滑動窗口的數(shù)字之和與隊列中的數(shù)字個數(shù)之商。

7.17題目 565. 數(shù)組嵌套

【圖】遍歷數(shù)組，從i向nums連邊，可以得到一張有向圖。由于題目保證nums中不含有重復(fù)的元素，因此有向圖中每個點的出度和入度均為1。在這種情況下，有向圖必然由一個或多個環(huán)組成。我們可以遍歷nums，找到節(jié)點個數(shù)最大的環(huán)。代碼實現(xiàn)時需要用一個vis數(shù)組來標(biāo)記訪問過的節(jié)點。

【原地標(biāo)記】可證一定有環(huán)，找最大的環(huán)，優(yōu)化:省掉vis數(shù)組，放置n作為標(biāo)記點，當(dāng) nums[i] == n時，說明到環(huán)起點了。

7.18題目 749. 隔離病毒

【BFS】遍歷到is Infected中的一個1時，就從這個1對應(yīng)的位置開始進行廣度優(yōu)先搜索，這樣就可以得到連續(xù)的一塊被病毒感染的區(qū)域.如果當(dāng)前是第idx（idx≥1）塊被病毒感染的區(qū)域，我們就把這些1都賦值成-idx，這樣就可以防止重復(fù)搜索.

7.19題目 731. 我的日程安排表 II

【遍歷】檢查區(qū)間有沒有交集。

【差分?jǐn)?shù)組】需要用到python的Map/TreeMap 數(shù)據(jù)結(jié)構(gòu)，sortedcontainers庫。

【線段樹】區(qū)間更新 + 動態(tài)線段樹懶標(biāo)記。

7.20題目 1260. 二維網(wǎng)格遷移

【一維展開】每次遷移操作都相當(dāng)于將該一維數(shù)組向右循環(huán)移動一次，那么k次遷移操作之后，grid[x] [y]的下標(biāo)idx = (index + k) mod (m × n)。

7.21題目 814. 二叉樹剪枝

【遞歸】后序遍歷的時候，遞歸地pruneTree。

7.22題目 757. 設(shè)置交集大小至少為2

【貪心】從該區(qū)間左邊界開始往后添加不在交集集合中的元素，并往前進行更新需要更新的區(qū)間，重復(fù)該過程直至該區(qū)間與交集元素集合有m個元素相交。右端點從小到大，保證貪心處理邊緣點的正確性，同時右端點一樣的時候優(yōu)先處理長度最短的區(qū)間，因為該區(qū)間可選點最少同時會覆蓋其他區(qū)間，由于我們是單調(diào)遞增添加元素，維護當(dāng)前集合前二大的元素即可判斷是否需要添加新的，如果區(qū)間左端點也在當(dāng)前最大元素的右邊，說明需要從該區(qū)間添加兩個新點(可以理解為遞歸，前面的不再起作用)，貪心取最大的兩個點。

7.23題目 劍指 Offer II 115. 重建序列

【拓撲排序】根據(jù)有向邊計算每個結(jié)點的入度，然后將所有入度為0的結(jié)點添加到隊列中，進行拓撲排序。如果隊列中的元素個數(shù)大于1，則超序列的下一個數(shù)字不唯一，因此nums不是唯一的最短超序列，返回false；如果隊列中的元素個數(shù)等于1，則超序列的下一個數(shù)字是隊列中唯一的數(shù)字。將該數(shù)字從隊列中取出，將該數(shù)字指向的每個數(shù)字的入度減1，并將入度變成0的數(shù)字添加到隊列中。

7.24題目 1184. 公交站間的距離

【一次遍歷】distance = min(start to distance, start to 0)。

7.25題目 919. 完全二叉樹插入器

【隊列】可以使用一個隊列存儲上述提到的這些可以添加子節(jié)點的節(jié)點。隊列中的存儲順序為：首先從左往右存儲倒數(shù)第二層最右側(cè)的節(jié)點，再「從左往右」存儲最后一層的全部節(jié)點。

7.26題目 1206. 設(shè)計跳表

【直接構(gòu)造】search、add、erase.

7.27題目 592. 分?jǐn)?shù)加減運算

【調(diào)庫】 fractions模塊提供了處理分?jǐn)?shù)的方法。

7.28題目 1331. 數(shù)組序號轉(zhuǎn)換

【排序 + 哈希表】首先用一個數(shù)組保存排序完的原數(shù)組，然后用一個哈希表保存各元素的序號，最后將原屬組的元素替換為序號后返回。

7.29題目 593. 有效的正方形

【數(shù)學(xué)】正方形判定定理.

7.30題目 952. 按公因數(shù)計算最大組件大小

【并查集】可以使用并查集實現(xiàn)組件的計算。初始時，每個數(shù)分別屬于不同的組件。如果兩個正整數(shù)滿足其中一個正整數(shù)是另一個正整數(shù)的因數(shù)，則這兩個正整數(shù)屬于同一個組件，將這兩個正整數(shù)的組件合并。

7.31題目 1161. 最大層內(nèi)元素和

【BFS】我的層序遍歷模板。