9.1題目 1475. 商品折扣后的最終價格

【單調(diào)?！繂握{(diào)棧預(yù)處理prices，使得查詢prices中每個元素對應(yīng)位置右邊的第一個更小的元素值時不需要再遍歷price。在每個位置維護一個其右邊更小的元素列表。

9.2題目 687. 最長同值路徑?

【DFS】類似求二叉樹最大深度。

9.3題目 646. 最長數(shù)對鏈

【貪心】pre記錄上一個pair[1]，下一個pair[0]得大于上一個pair[1]。

9.4題目 1582. 二進制矩陣中的特殊位置

【模擬】枚舉每個位置判斷是否滿足，可以用原始矩陣的第一行來存減少空間消耗。

9.5題目 652. 尋找重復(fù)的子樹

【使用序列化表示】用哈希表存子樹，如果一局出現(xiàn)就把子樹放進哈希表中。

9.6題目 828. 統(tǒng)計子串中的唯一字符

【一次遍歷】從左向右遍歷s的同時，對每個字母s[i]記錄上一次出現(xiàn)的下標(biāo)last_0[s[i]]和上上次出現(xiàn)的下標(biāo)last_1[s[i]]，可以算出以s[i-1]結(jié)尾的字串到以s[i]結(jié)尾的字串，countUniqueChars值的變化量為i - 2last_0[s[i]] + last_1[s[i]]。

9.7題目 1592. 重新排列單詞間的空格

【模擬】首先按照空格分割text，得到單詞集合，并統(tǒng)計空格數(shù)。如果單詞數(shù)為 1，則將全部空格拼接到這個單詞后面，否則先計算出單詞間的間隔，按照單詞及間隔來進行拼接，若拼接后仍有多余的空格，則將剩下的空格拼接在末尾即可。

9.8題目 667. 優(yōu)美的排列 II

【思維題】k=1時，1~n按照[1,2,…,n]的順序排列，相鄰的差均為1，滿足k=1的要求。k = n -1時，將1~n按照[1,n,2,n-1,3,…]的順序排列，相鄰的差從n-1開始，依次減1，這樣所有1到n-1的差值均出現(xiàn)一次，滿足k=n-1。其他一般情況，將這兩種情況合并，前半部分相鄰差為1，后半部分相鄰差從k開始遞減到1，這樣1到k的差值均出現(xiàn)一次，對應(yīng)列表[1,2,…,n-k,n,n-k+1,n-1,n-k+2,..]

9.9題目 1598. 文件夾操作日志搜集器

【模擬】用depth記錄當(dāng)前目錄的深度，../如果depth > 0則減1，./則depth不變，x/則depth加1.

9.10題目 669. 修剪二叉搜索樹

【遞歸】一個節(jié)點的值如果沒有落在[lo, hi]內(nèi)，如果root.val < lo，則root和root的左子樹都小于lo，都需要被剪掉；如果root.val > hi，則root和root的右子樹都大于hi，都需要被剪掉。

9.11題目 857. 雇傭 K 名工人的最低成本

【貪心 + 最大堆】在最優(yōu)發(fā)工資方案下，至少有一名工人，發(fā)給他的工資恰好等于他的最低期望工資。剩余工人可以按每單位工作質(zhì)量的工資即r_i = wage_i / quality_i 升序排序，k名工人quality之和為sumQ，發(fā)工資總額為sumQ × r_i，所以sumQ越小發(fā)的工資總額就越小，所以需要從小到大枚舉r_i。維護當(dāng)前最小的k個quality值。代碼中，可以用最大堆（優(yōu)先隊列）來維護，按照r_i從小到大的順序遍歷，當(dāng)堆中有k個元素時，如果quality_i比堆頂小，可以彈出堆頂，將quality_i入堆，從而得到一個更小的sumQ，此時有可能找到一個更優(yōu)解sumQ×r_i。

9.12題目 1608. 特殊數(shù)組的特征值

【降序排序 + 一次遍歷】特征值x是在[1,n]范圍內(nèi)的一個整數(shù)，其中n是數(shù)組nums的長度，因此可以遍歷[1,n]判斷某個整數(shù)i是否是特征值，若i是特征值，那么nums中恰好有i個元素大于等于i，由于數(shù)組降序排序，說明nums[i - 1]必須大于等于i，nums[i]如果存在必須小于i。

9.13題目 670. 最大交換

【貪心】右邊越大的數(shù)字與左邊較小的數(shù)字進行交換，這樣產(chǎn)生的整數(shù)才能保證越大。

9.14題目 1619. 刪除某些元素后的數(shù)組均值

【排序】排序后，區(qū)間[n / 20, 19n/20)內(nèi)的元素求和即為未刪除元素，再除以0.9n即為均值。

9.15題目 672. 燈泡開關(guān) Ⅱ

【二進制枚舉】找規(guī)律，位置i與i + 6的燈泡的開關(guān)狀態(tài)始終一致，所以只需考慮前n=6個燈泡的開關(guān)狀態(tài)。對于每個按鈕，若操作偶數(shù)次，相當(dāng)于沒執(zhí)行，若操作奇數(shù)次，相當(dāng)于操作1次，不同按鈕操作的先后順序不影響結(jié)果。共4個按鈕，每個按鈕有“操作偶數(shù)次”和“操作奇數(shù)次”兩種狀態(tài)，共有2^4種按鈕狀態(tài)，可以二進制枚舉按鈕的狀態(tài)mask，若當(dāng)前狀態(tài)滿足題目presses的限制，可以xor模擬，最終得到的狀態(tài)t去重后即為答案。

9.16題目 850. 矩形面積 II

【離散化 + 線段樹 + 掃描線】先將所有矩形的左右邊界按照橫坐標(biāo)排序，確定掃描線掃描順序，隨后遍歷左右邊界，一次性處理掉一批橫坐標(biāo)相同的左右邊界，對應(yīng)增加或減少覆蓋的長度，下一個沒遍歷到的左右邊界橫坐標(biāo)就是掃描新水平方向移動過的距離，而覆蓋的線段長度可以離散化。

9.17題目 1624. 兩個相同字符之間的最長子字符串

【哈希表】類似兩數(shù)之和的解法。

9.18題目 827. 最大人工島

【DFS】統(tǒng)一島嶼中所有點都屬于同一個集合，可用不同的mark值標(biāo)識不同的島嶼，用p記錄每個grid[i] [j]對應(yīng)的mark值，用cnt記錄每個島嶼的面積，遍歷grid，對于每個0，統(tǒng)計相鄰四個點中1所在的島嶼。

9.19題目 1636. 按照頻率將數(shù)組升序排序

【哈希表】先算出數(shù)組nums中各元素的頻率，然后按照元素頻率和數(shù)值對數(shù)組進行排序即可。

9.20題目 698. 劃分為k個相等的子集

【DFS + 剪枝】首先sum(nums)如果不能被k整除則肯定無法劃分為k個子集，如果能被k整除，將每個子集的期望和記為s，創(chuàng)建長度為k的數(shù)組cur表示每個子集的和，對nums降序排序，嘗試將每個元素加入cur的子集，如果子集的和超過s，則可以跳過，如果cur[j] == cur[j - 1]說明在之前已經(jīng)完成搜索也可以跳過，如果所有元素都能加入cur中，則可以劃分為k個子集。

9.21題目 854. 相似度為 K 的字符串

【DFS】每次碰到不同的s1[i] != s2[i]時，從s1[i + 1,…]中選擇處于不同位置的字符s1[j] = s2[j]，將其與s1[i]進行交換，然后保持當(dāng)前子狀態(tài)，搜索下一個位置i+1，直到素有字符串s1全部與s2匹配完成，當(dāng)前子狀態(tài)搜索完成后，回復(fù)字符串，繼續(xù)搜索下一個與s2[i]相等的字符，并進行替換。長度為n的兩個相似字符串，n為偶數(shù)時，至少交換n/2次，n為奇數(shù)，至少交換(n+1)/2次。

9.22題目 1640. 能否連接形成數(shù)組

【哈希表】用一個哈希表記錄pieces哥哥數(shù)組的首元素與下標(biāo)的對應(yīng)關(guān)系，將piece[j]與arr[i]及之后的整數(shù)進行比較，都相等就往后移直到所有pieces都匹配成功。

9.23題目 707. 設(shè)計鏈表

【指針引用實現(xiàn)單鏈表】單向鏈表的每個節(jié)點僅存儲本身的值和后繼節(jié)點，還需要一個哨兵節(jié)點作為頭節(jié)點。

【靜態(tài)數(shù)組實現(xiàn)單鏈表】指針引用每次動態(tài)創(chuàng)建一個鏈表節(jié)點，頻繁new操作會增加耗時，可以使用靜態(tài)數(shù)組來實現(xiàn)，預(yù)先申請一塊略大于數(shù)據(jù)范圍的內(nèi)存空間，每次插入節(jié)點時，從數(shù)組中取出一個空閑的位置，將新節(jié)點插入到該位置，同時更新該位置的前驅(qū)和后繼節(jié)點的指針引用。

9.24題目 1652. 拆炸彈

【前綴和】若 k 為 0，直接返回[0] * n。若 k為正數(shù)，那么 i 位置的值為 i 位置后 kk 個位置的值之和，若 k 為負(fù)數(shù)，那么 i 位置的值為 i ?位置前 |k| 個位置的值之和。

9.25題目 788. 旋轉(zhuǎn)數(shù)字

【枚舉】按題意，2，5，6，9是合法的旋轉(zhuǎn)后不同的數(shù)字，3，4，7是不合法的數(shù)字，0，1，8是合法的但旋轉(zhuǎn)后相同的數(shù)字。所以該數(shù)字的數(shù)位中必須至少出現(xiàn)2，5，6，9中的一個，且不能出現(xiàn)3，4，7，而0，1，8出現(xiàn)與否都無所謂。用一個check數(shù)組存一下，依次判斷。

9.26題目 面試題 17.19. 消失的兩個數(shù)字

【位運算】xor初始化為0，缺兩個數(shù)的[1,N] xor 完整[1,N]，xor的結(jié)果是缺的兩個數(shù)的異或和。已知lowbit算法x & (-x)可以保留x最右邊的1，其余位置置0。運用lowbit算法找到xor的最右邊的1，表示在這一個二進制位上缺失的兩個數(shù)一個是0一個是1，把該位當(dāng)成mask過濾兩遍（按0按1都行）得到其中一個數(shù)，用xor異或上這個數(shù)得到另一個數(shù)。(a ^ b ^ a = b)

9.27題目 面試題 01.02. 判定是否互為字符重排

【哈希表】用哈希表統(tǒng)計兩個字符串每個字符出現(xiàn)次數(shù)，相等就行。

9.28題目 面試題 17.09. 第 k 個數(shù)

【平衡樹/最小堆】每次把最小的3x,5x,7x存進去，第k次取到的數(shù)即為第k小的數(shù)。

【多路歸并】第k位數(shù)可以由3x、5x、7x三種序列歸并而來，用三個指針指向當(dāng)前最小的那個數(shù)。

9.29題目 面試題 01.09. 字符串輪轉(zhuǎn)

【模擬】需要滿足長度相等，且把s2拼起來，s1一定在其中。

9.30題目 面試題 01.08. 零矩陣

【使用標(biāo)記數(shù)組】遍歷每一行每一列，如果有0，將整行置0.

【使用單個標(biāo)記變量】先用一個遍歷存第一列是否存在0，存在flag變量里，之后用第一行存每一列是否包含0，用第一列存每一行是否包含0，可以節(jié)約空間。倒序遍歷是為了留著第一列最后再用flag變量更新。