4.1題目 954. 二倍數(shù)對數(shù)組

【哈希表 + 排序】用一個哈希表來統(tǒng)計ct，并將其鍵值按絕對值從小到大排序，然后模擬上述操作，去掉元素的操作可以改為從cnt中減去對應(yīng)值。

4.2題目 420. 強密碼檢驗器

【分類討論】根據(jù)k mod 3 = 0/1/2分類討論。

4.3題目 744. 尋找比目標字母大的最小字母

【線性查找】如果目標字母小于列表中的最后一個字母，則一定可以在列表中找到比目標字母大的最小字母。如果目標字母大于或等于列表中的最后一個字母，則列表中不存在比目標字母大的字母，根據(jù)循環(huán)出現(xiàn)的順序，列表的首個字母是比目標字母大的最小字母。

4.4題目 307. 區(qū)域和檢索 - 數(shù)組可修改

【分塊處理】設(shè)數(shù)組大小為n，我們將數(shù)組nums分成多個塊，每個塊大小sze，最后一個塊的大小為剩余的不超過sze的元素數(shù)目，那么塊的總數(shù)為?n/size?，用一個數(shù)組sm保存每個塊的元素和。

4.5題目 762. 二進制表示中質(zhì)數(shù)個計算置位

【數(shù)學(xué) + 位運算】枚舉[left，right]范圍內(nèi)的每個整數(shù)，挨個判斷是否滿足題目要求。

4.6題目 310. 最小高度樹

【BFS】只需要求出路徑最長的兩個葉子節(jié)點即可，并求出其路徑的最中間的節(jié)點即為最小高度樹的根節(jié)點。

4.7題目 796. 旋轉(zhuǎn)字符串

【模擬】首先，如果s和goal的長度不一樣，那么無論怎么旋轉(zhuǎn)，s都不能得到goal，返回flse在長度一樣（都為n）的前提下，假設(shè)s旋轉(zhuǎn)i位，則與goal中的某一位字符goalj對應(yīng)的原s中的字符應(yīng)該為s[(i+j) mod n]。在固定i的情況下，遍歷所有j，若對應(yīng)字符都相同，則返回tru。否則，繼續(xù)遍歷其他候選的i。若所有的i都不能使s變成goal，則返回false。

4.8題目 429. N 叉樹的層序遍歷

【BFS】先把根節(jié)點oot放入隊列中，隨后在廣度優(yōu)先搜索的每一輪中，我們首先記錄下當前隊列中包含的節(jié)點個數(shù)（記為c），即表示上一層的節(jié)點個數(shù)。在這之后，我們從隊列中依次取出節(jié)點，直到取出了上一層的全部ct個節(jié)點為止。當取出節(jié)點cur時，我們將cur的值放入一個臨時列表，再將cur的所有子節(jié)點全部放入隊列中。

4.9題目 780. 到達終點

【反向計算】可以從(tx, ty)開始反向計算，判斷是否可以到達狀態(tài)(sx,sy)。

4.10題目 804. 唯一摩爾斯密碼詞

【哈希表】我們將數(shù)組words中的每個單詞按照莫爾斯密碼表轉(zhuǎn)換為摩爾斯碼，并加入哈希集合中，最終的答案即為哈希集合中元素的個數(shù)。

4.11題目 357. 統(tǒng)計各位數(shù)字都不同的數(shù)字個數(shù)

【排列組合】考慮n = 0/1/2的情況，組合數(shù)學(xué)計算。

4.12題目 806. 寫字符串需要的行數(shù)

【直接遍歷】width + widths[c] ≤ 100更新時不變，width + ?widths[c] > 100.

4.13題目 380. O(1) 時間插入、刪除和獲取隨機元素

【變長數(shù)組 + 哈希表】插入操作時，首先判斷val是否在哈希表中，如果已經(jīng)存在則返回false，如果不存在則插入val，刪除操作時，首先判斷val是否在哈希表中，如果不存在則返回false，如果存在則刪除val.

4.14題目 1672. 最富有客戶的資產(chǎn)總量

【遍歷】分別計算每位客戶在各家銀行托管的資產(chǎn)數(shù)量之和，返回這些資產(chǎn)總量的最大值。

4.15題目 385. 迷你語法分析器

【DFS】從左至右遍歷s，如果第一位是‘[’字符，則表示待解析的是一個列表，從‘[’后面的字符開始又是一個新的NestedInteger實例，仍調(diào)用解析函數(shù)來解析列表的元素，調(diào)用結(jié)束后如果遇到的是，字符，表示列表仍有其他元素，需要繼續(xù)調(diào)用。如果是‘]’字符，表示這個列表已經(jīng)解析完畢，可以返回NestedInteger實例。否則，則表示待解析的NestedInteger只包含一個整數(shù)。我們可以從左至右解析這個整數(shù)，并注意是否是負數(shù)，直到遍歷完或者遇到非數(shù)字字符（']’或‘，'），并返回NestedInteger實例。

4.16題目 479. 最大回文數(shù)乘積

【枚舉】可以從大到小枚舉回文數(shù)，由于確定了回文數(shù)的左半部分，其右半部分也就確定了，因此我們只需要枚舉左半部分。

4.17題目 819. 最常見的單詞

【哈希表 + 計數(shù)】遍歷段落paragraph，得到段落中的所有單詞，并對每個單詞計數(shù)，使用哈希表記錄每個單詞的計數(shù)。由于每個單詞由連續(xù)的字母組成，因此當遇到一個非字母的字符且該字符的前一個字符是字母時，即為一個單詞的結(jié)束，如果該單詞不是禁用單詞，則將該單詞的計數(shù)加1。如果段落的最后一個字符是字母，則當遍歷結(jié)束時需要對段落中的最后一個單詞判斷是否為禁用單詞，如果不是禁用單詞則將次數(shù)加1。

4.18題目 386. 字典序排數(shù)

【DFS】嘗試在number后面附加一個零，即number×10，如果number×10≤n，那么說明number×10是下一個字典序整數(shù)；如果number mod 10 = 9或number+1>n，那么說明未尾的數(shù)位已經(jīng)搜索完成，退回上一位，即number = ?number / ?10?然后繼續(xù)判斷直到number mod10≠9且number+1≤n為止，那么number+1是下一個字典序整數(shù)。

4.19題目 821. 字符的最短距離

【兩次遍歷】問題可以轉(zhuǎn)換成，對s的每個下標i，求min(s[到其左側(cè)最近的字符c的距離, s[到其右側(cè)最近的字符c的距離)

4.20題目 388. 文件的最長絕對路徑

【?！课募到y(tǒng)中文件絕對路徑的最大長度，可用棧保存當前已遍歷路徑的長度，棧中元素的個數(shù)即為當前路徑的深度，棧頂元素即為當前路徑的長度。

4.21題目 824. 山羊拉丁文

【模擬】一次遍歷，按題意模擬。

4.22題目 396. 旋轉(zhuǎn)函數(shù)

【迭代】F(k)=F(k-1)+numSum - n x nums[n - k] - k ?(1 ≤ k < n)

4.23題目 587. 安裝柵欄

【Jarvis 算法】經(jīng)典求凸包。

4.24題目 868. 二進制間距

【位運算】我們可以使用一個循環(huán)從n二進制表示的低位開始進行遍歷，并找出所有的1。我們用一個變量last記錄上一個找到的1的位置。如果當前在第i位找到了1，那么就用i-last更新答案，再將last更新為i即可。

4.25題目 398. 隨機數(shù)索引

【水塘采樣】遍歷nums，當我們第i次遇到值為target的元素時，隨機選擇區(qū)間「0，i）內(nèi)的一個整數(shù)，如果其等于0，則將返回值置為該元素的下標，否則返回值不變。設(shè)nums中有k個值為target的元素，該算法會保證這k個元素的下標成為最終返回值的概率均為1/k。

4.26題目 883. 三維形體投影面積

【數(shù)學(xué)】根據(jù)題意，x軸對應(yīng)行，y軸對應(yīng)列，z軸對應(yīng)網(wǎng)格的數(shù)值。xy平面的投影面積等于網(wǎng)格上非零數(shù)值的數(shù)目；yz平面的投影面積等于網(wǎng)格上每一列最大數(shù)值之和；zx平面的投影面積等于網(wǎng)格上每一行最大數(shù)值之和。

4.27題目 417. 太平洋大西洋水流問題

【DFS】使用深度優(yōu)先搜索實現(xiàn)反向搜索，搜索過程中需要記錄每個單元格是否可以從太平洋反向到達以及是否可以從大西洋反向到達。反向搜索結(jié)束之后，遍歷每個網(wǎng)格，如果一個網(wǎng)格既可以從太平洋反向到達也可以從大西洋反向到達，則該網(wǎng)格滿足太平洋和大西洋都可以到達，將該網(wǎng)格添加到答案中。

4.28題目 905. 按奇偶排序數(shù)組

【原地交換】記數(shù)組nums的長度為n。先從nums左側(cè)開始遍歷，如果遇到的是偶數(shù)，就表示這個元素已經(jīng)排好序了，繼續(xù)從左往右遍歷，直到遇到一個奇數(shù)。然后從nums右側(cè)開始遍歷，如果遇到的是奇數(shù)，就表示這個元素已經(jīng)排好序了，繼續(xù)從右往左遍歷，直到遇到一個偶數(shù)。交換這個奇數(shù)和偶數(shù)的位置，并且重復(fù)兩邊的遍歷，直到在中間相遇，nums排序完畢。

4.29題目 427. 建立四叉樹

【遞歸 + 二維前綴和優(yōu)化】X可以與處理出數(shù)組gd的二維前綴和，這樣一來，當我們需要判定某一部分是否均為0或1時，可以在O（1）的時間內(nèi)得到這一部分的和，從而快速地進行判斷。

4.30題目 908. 最小差值 I

【數(shù)學(xué)】更改后的整數(shù)數(shù)組nums的最低分數(shù)為maxNum-minNum-2k。