3.1題目?2373. 矩陣中的局部最大值

【枚舉】枚舉每個3×3的矩陣，求出最大值，可以原地修改放入原矩陣中。

3.2題目?面試題 05.02. 二進制數(shù)轉(zhuǎn)字符串

【模擬】十進制小數(shù)轉(zhuǎn)二進制的方法是乘二取整，由于輸入小數(shù)位數(shù)最多只有6位，可證其二進制小數(shù)位數(shù)至多，可優(yōu)化最多循環(huán)6次。證明：num如果看表示為有限位二進制小數(shù)，那么可以表示為一個b/2^k的最簡分數(shù)，b是整數(shù)且與2^k互質(zhì)，num在(0,1)內(nèi)時，k≥1，b與2^k互質(zhì)，如0.625 = 5/8 = 5 / 2^3，對于一個十進制小數(shù)位最多6位的數(shù)num，可以表示為a/(2^5 × 2^6) = b/2^k，都×2^k得a·2^(k-6)/5^6 = b。b和2互質(zhì)，等號左邊不能有因子2，所以k≤6.代碼中不斷乘2減去b1,循環(huán)k次。

3.3題目?1487. 保證文件名唯一

【哈希表】用哈希表d記錄每個文件夾的最小可用編號，其中d[name] = k表示文件夾name的最小可用編號為k，d中沒有任何文件夾，d為空。遍歷文件夾數(shù)組，對于每個文件名name，如果name在d中，不斷嘗試Name(k)，直到找到新文件夾名,將d[name]更新為k+1，如果不在d中，直接將name加入d，將d[name]更新為1。

3.4題目?982. 按位與為零的三元組

【枚舉 + 常數(shù)優(yōu)化】暴力三重循環(huán)枚舉i,j,k的時間復雜度是O(n^3)，應該優(yōu)化。對于nums[k]來說，只需要知道其and一個數(shù)的結(jié)果是否等于0，這個數(shù)具體是哪些nums[i] and nums[j]得到的不重要，所以可以寫一個O(n^2)的枚舉，預處理所有nums[i] and nums[j]的出現(xiàn)次數(shù)，存在一個哈希表或數(shù)組中，然后枚舉Nums[k]和x，如果nums[k] and x = 0 就把cnt[x]加到答案中，用哈希表實現(xiàn)的枚舉所有key，用數(shù)組實現(xiàn)的要枚舉區(qū)間[0, 2^16]內(nèi)的所有數(shù)。繼續(xù)優(yōu)化，如果吧二進制堪稱集合，二進制從低到高第i位為1表示i在集合中，為0表示i不在集合中，如{0,2,3}可以表示為1101，a AND b相當于集合a和集合b沒有交集，也相當于b是C_u A的子集，U = {0,1,...,15}，對應0xffff，一個數(shù)異或0xffff就得到這個數(shù)的補集，可以優(yōu)化成枚舉nums[k] ⊕ 0xffff的子集，可以從m不斷減1，直到0，如果s and m = s就表示s是m的子集，也可以直接跳到下一個子集，即s更新為(s-1) and m，最后s=0時，(s-1) and m = m，繼續(xù)優(yōu)化，預處理每個Nums[k]的補集出現(xiàn)次數(shù)，最后累加cnt[nums[i] AND?nums[j]]，繼續(xù)優(yōu)化，仔細計算cnt的大小u，相應的全集是u-1。

3.5題目?1599. 經(jīng)營摩天輪的最大利潤

【模擬】模擬摩天輪輪轉(zhuǎn)過程，每次輪轉(zhuǎn)時，累加等待的游客及新到達的游客，然后最多4個人上傳，更新等待的游客數(shù)和利潤，記錄最大利潤與其對應的輪轉(zhuǎn)次數(shù)。

3.6題目?1653. 使字符串平衡的最少刪除次數(shù)

【前后綴分解】平衡字符串的a和b之間有分割線，分割線之前要刪b，分割線之后要刪a，枚舉所有分割線，計算刪除次數(shù)的最小值。

【動態(tài)規(guī)劃】s的最后一個字母如果是'b'，則無需刪除，問題變?yōu)槭箂前n-1個字母平衡的最小刪除次數(shù)，如果是'a'，有刪和不刪的選擇，刪問題變?yōu)槭箂前n-1個字母平衡的最小刪除次數(shù) + 1, 不刪則前面所有b都得刪。設(shè)cnt_b為前i個字母中'b'的個數(shù)，定義f[i]表示使s前i個字母平衡的最少刪除次數(shù)，如果第i個字母是'b'，則f[i] = f[i - 1]，如果第i個字母是'a'，則f[i] =min(f[i - 1], cnt_b)，代碼實現(xiàn)時只需要f一個變量。

3.7題目?1096. 花括號展開 II

【遞歸】用dfs(exp)處理表達式exp，將結(jié)果存入集合s中，首先找到第一個右花括號的位置j，如果找不到說明exp中沒有右花括號，即exp為單一元素，直接將exp加入集合s中即可。否則，從位置j開始往左找到第一個左花括號位置i，此時exp[:i]和exp[j+1:]分別為exp的前后綴，而exp[i+!:j]為exp中花括號內(nèi)的部分，即exp的子表達式，將其按逗號分割成多個字符串，將其和前后綴拼起來，遞歸調(diào)用即可，最后將集合s中的元素按字典序排序。

3.8題目?劍指 Offer 47. 禮物的最大價值

【DP】定義f[i] [j]為從棋盤左上角走到右下角 的禮物最大累計價值，f[i] [j] =max(f[i - 1] [j], f[i] [j - 1]) + grid[i - 1] [j - 1]，由于f[i + 1]只依賴于f[i]，那么考研只用兩個滾動數(shù)組，而且f[1] [1]會用到f[0] [1]，直接把f[1] [1]填入f[0] [1]中，所以只需一個長為n+1的一維數(shù)組即可，再優(yōu)化：直接用grid[0]當f數(shù)組，做到O(1)空間。

3.9題目?2379. 得到 K 個黑塊的最少涂色次數(shù)

【滑動窗口】固定大小為k的滑動窗口，在向右移動過程中維護窗口中白色快數(shù)目，返回白色快數(shù)目最小值即需要至少出現(xiàn)一次連續(xù)k個黑色塊最小操作次數(shù)。

3.10題目?1590. 使數(shù)組和能被 P 整除

【前綴和+哈希表】同余：如果(x - y) mod p = 0，則稱x與y對模p同余，記作x ≡ y (mod p)，為了避免判斷是否負數(shù)，可以寫為(x mod p + p) mod p = y mod p （python會保證取模運算的結(jié)果非負）。舉例，設(shè)總和為x，子數(shù)組和為y，去掉y后，x mod p = y mod p，等價于y ≡x (mod p)。通過前綴和，題目轉(zhuǎn)化為：在前綴和數(shù)組sm上找到兩個數(shù)sm[l]和sm[r]，滿足r-l最小，且sm[r] - sm[l] = x (mod p)，移項的sm[r] - x = sm[l] (mod p)，變形為((sm[r] - x) mod p + p) mod p = sm[l] mod p，即(sm[r] mod p - x mod p + p) mod p = sm[l] mod p。遍歷sm的同時，用哈希表記錄sm[i] mod p最近一次出現(xiàn)的下標，如果哈希表中包含(sm[i] mod p - x mod p) mod p，設(shè)其下標為j，那么[j,i)是一個符合要求的子數(shù)組，枚舉所有i計算所有符合要求的子數(shù)組長度的最小值。代碼實現(xiàn)時，可以邊遍歷nums邊計算前綴和。

3.11題目?面試題 17.05. 字母與數(shù)字

【前綴和+哈希表】字母和數(shù)字個數(shù)相同等價于字母的個數(shù)減去數(shù)字的個數(shù)等于0，可以把字母看作1，數(shù)字看作-1，即找到一個最長子數(shù)組其元素和等于0，用前綴和處理，元素和等于0等價于兩個前綴和之差等于0，等于兩個前綴和相同，即從前綴和中找到兩個相同的sm[r]和sm[l]，計算r-l的最大值，遍歷前綴和sm的同時，用一個數(shù)組或哈希表first記錄sm[i]首次出現(xiàn)下標，計算i-first[sm[i]]的最大值。

3.12題目?1617. 統(tǒng)計子樹中城市之間最大距離

【DFS+乘法原理】暴力枚舉i和1作為直徑的兩個端點，那么從到j(luò)的這條簡單路徑是直徑，這上面的每個點都必須選。設(shè)dis[i] [j]為i到j(luò)的距離，為了計算樹上任意兩點的距離ds，枚舉i作為樹的根，計算i到其余點的距離。通過n次DFS，就可以得到樹上任意兩點的距離了。

3.13題目?2383. 贏得比賽需要的最少訓練時長

【貪心 + 模擬】開始時把精力補充到足夠擊敗這n個對手，接下來考慮經(jīng)驗值，遍歷n個對手，若經(jīng)驗不足以超過對手，就把經(jīng)驗補到剛好能超過該對手，擊敗對手后把對方的經(jīng)驗值加到自己身上，遍歷結(jié)束后返回訓練的小時數(shù)。

3.14題目?1605. 給定行和列的和求可行矩陣

【貪心 + 構(gòu)造】以rowSum = [5,7,10], colSum = [8,6,8]為例，單獨看左上角的格子，最小可以填0，最大可以填min(5,8)，按順序給每個格子填最大值，取min的兩個值哪個小，改行/該列剩下就全填0了?？梢杂^察到需要填的格子（非零格）組成了一條向下或向右的路徑，至多要填m+n-1個格子，其余格子全為0。

3.15題目?1615. 最大網(wǎng)絡(luò)秩

【枚舉 + 計數(shù)】用一維數(shù)組cnt記錄每個城市的度，用二維數(shù)組g記錄每對城市之間是否有道路相連，如果a和b之間有道路相連則g[a] [b]= 1，否則g[a] [b] = g[b] [a] = 1，枚舉每對城市(a,b)，計算網(wǎng)絡(luò)秩即cnt[a] + cnt[b] - g[a] [b]（減掉兩者相連即中間重復計算的），其中最大值為答案。

3.16題目?2488. 統(tǒng)計中位數(shù)為 K 的子數(shù)組

【遍歷 + 計數(shù)】前綴和思想，定義一個計數(shù)器 cnt，用于統(tǒng)計當前遍歷過的數(shù)組中，「比 k大的元素的個數(shù)」與「比 k小的元素的個數(shù)」的差值的個數(shù)。由于nums中的整數(shù)互不相同，k是長為奇數(shù)的子數(shù)組的中位數(shù)等價于子數(shù)組中大于k的數(shù)的個數(shù)=小于k的數(shù)的個數(shù)。「左側(cè)小于+右側(cè)小于」 = 「左側(cè)大于+右側(cè)大于」，移項得左側(cè)小于-左側(cè)大于=右側(cè)大于-右側(cè)小于。把比k大的數(shù)視為1，比k小的數(shù)視為-1，k視為0。倒序枚舉子數(shù)組左端點，計算「左側(cè)小于 - 左側(cè)大于」的值 x，然后正序枚舉子數(shù)組右端點，計算「右側(cè)大于 ? 右側(cè)小于」的值x，對每個右端點的x，看有多少個一樣的左端點的x，子數(shù)組長為奇數(shù)時，子數(shù)組個數(shù)為cnt[0] + cnt[1] = 2，子數(shù)組長為偶數(shù)時，「左側(cè)小于-左側(cè)大于」= 「右側(cè)大于 -右側(cè)小于 - 1」，cnt[x-1]是該右端點對應的符合要求的長為偶數(shù)的子數(shù)組個數(shù)，累加這些cnt[x-1]就是子數(shù)組長為偶數(shù)時的答案，奇數(shù)和偶數(shù)個數(shù)相加就是答案。代碼中，x的范圍在[-(n-1), n -1]之間，所以可以用數(shù)組代替哈希表，考慮到要訪問cnt[x-1]，實際范圍是[-n,n-1]，需要一個長為2n的數(shù)組。

3.17題目?2389. 和有限的最長子序列

【排序 + 前綴和 + 二分】對于每個queries[i]，對在前綴和二分找到元素和不超過queries[i]的最小下標j。

3.18題目?1616. 分割兩個字符串得到回文串

【雙指針】a的前綴和b后綴匹配的字母越多，中間需要判斷的回文串越短，a_prefix+b_suffix越可能構(gòu)成回文串(b_prefix+a_suffix同理)。代碼中，check函數(shù)：如果 a_prefix + b_suffix 可以構(gòu)成回文串則返回 True，否則返回 False；相向雙指針，如果兩個指針指向字符相等就同時王中間移動，直到遇到不同的字母或兩指針交叉。如果交叉，說明已經(jīng)得到回文串，否則需要判斷中間剩余字串是否是回文串。沒交叉，則交換a和b重復一遍。

3.19題目?1625. 執(zhí)行操作后字典序最小的字符串

【枚舉】數(shù)據(jù)范圍較小，可以枚舉所有字符串狀態(tài)，取字典序最小的狀態(tài)。可以觀察到，對于累加操作，數(shù)字最多累加10次就會回到原來的狀態(tài)，對于輪轉(zhuǎn)操作，字符串最多輪轉(zhuǎn)n次，就會回到原來的狀態(tài)，所以輪轉(zhuǎn)操作最多產(chǎn)生n種狀態(tài)，如果輪轉(zhuǎn)位數(shù)b是偶數(shù)，累加操作只會對奇數(shù)位數(shù)字產(chǎn)生影響，共n×10種狀態(tài)；如果輪轉(zhuǎn)位數(shù)b是奇數(shù)，累加操作會對奇數(shù)位和偶數(shù)位數(shù)字都產(chǎn)生影響，共n×10×10種狀態(tài).

3.20題目?1012. 至少有 1 位重復的數(shù)字

【數(shù)位 DP】前置知識(位運算和集合論)：集合可以用二進制表示，二進制從低到高第i位為1表示i在集合中，為0表示i不在集合中。例如集合{0,2,3}對應的二進制數(shù)為1101(2)。設(shè)集合對應的二進制數(shù)為x。本題需要用到兩個位運算操作：1.判斷元素d是否在集合中：x>d&1可以取出x的第d個比特位，如果是1就說明d在集合中。2.把元素d添加到集合中：將x更新為x | (1<d)。思路：正難則反，轉(zhuǎn)換成求無重復數(shù)字的個數(shù)。將n轉(zhuǎn)換成字符串s，定義f(i, mask, isLimit, isNum)表示構(gòu)造從高到低第i位及其之后數(shù)位的合法方案數(shù)，其余參數(shù)的含義為：·mask表示前面選過的數(shù)字集合，換句話說，第i位要選的數(shù)字不能在mask中。·isLimit表示當前是否受到了n的約束。若為真，則第i位填入的數(shù)字至多為s[i]，否則可以是9。如果在受到約束的情況下填了s[i]，那么后續(xù)填入的數(shù)字仍會受到的約束?！sNum表示i前面的數(shù)位是否填了數(shù)字。若為假，則當前位可以跳過（不填數(shù)字），或者要填入的數(shù)字至少為1；若為真，則要填入的數(shù)字可以從0開始。代碼中，遞歸入口：f(0,0,true,false)表示：從s[0]開始枚舉：一開始集合中沒有數(shù)字；一開始要受到n的約束（否則就可以隨意填了，這肯定不行）；一開始沒有填數(shù)字。遞歸中：如果isNum為假，說明前面沒有填數(shù)字，那么當前也可以不填數(shù)字。一旦從這里遞歸下去，isLimit就可以置為fa1se了，這是因為s[0]必然是大于0的，后面就不受到n的約束了?；蛘哒f，最高位不填數(shù)字，后面無論怎么填都比n小。如果isNum為真，那么當前必須填一個數(shù)字。枚舉填入的數(shù)字，根據(jù)isNum和isLimit來決定填入數(shù)字的范圍。遞歸終點：當i等于s長度時，如果isNum為真，則表示得到了一個合法數(shù)字（因為不合法的不會繼續(xù)遞歸下去），返回1，否則返回0。

3.21題目?2469. 溫度轉(zhuǎn)換

【模擬】按題意模擬。

3.22題目?1626. 無矛盾的最佳球隊

【排序 + DP】將球員按照分數(shù)從小到大排序，如果分數(shù)相同則按照年齡從小到大排序，定義f[i]為排序后第i個球員的最大得分，枚舉0≤j<i，如果第i個球員年齡大于等于第j個球員年齡，則f[i]可以由f[j]轉(zhuǎn)移來，f[i] = max(f[i], f[j])。

3.23題目?1630. 等差子數(shù)組

【模擬 + 數(shù)學】定義一個check函數(shù)用于判斷子數(shù)組是否能重排成等差數(shù)列，首先子數(shù)組長度n = r - l -1，并將子數(shù)組中元素放入集合st中，獲取子數(shù)組中最大值an和最小值a1，如果an-a1不能被n-1整除，那么不能形成等差數(shù)列，否則計算公差d = (an-a1)/(n-1)，從a1開始依次計算第i項元素，如果第i項元素a1+(i-1)×d不在集合st中，那么不可能形成等差數(shù)列，否則遍歷完所有元素。遍歷所有查詢，對每個查詢調(diào)用check判斷，將結(jié)果存入答案數(shù)組中。

3.24題目?1032. 字符流

【前綴樹】根據(jù)初始化時的字符串數(shù)組words構(gòu)建前綴樹，前綴樹的每個節(jié)點包含兩個屬性：children——指向26個字母的指針數(shù)組，用于存儲當前節(jié)點的子節(jié)點，is_end——標記當前節(jié)點是否為某個字符串的結(jié)尾。構(gòu)造函數(shù)中，遍歷字符串數(shù)組words，對于每個字符串w，將其反轉(zhuǎn)后逐個插入到前綴樹中，插入結(jié)束后，將當前節(jié)點的is_end標記為true。在query函數(shù)中，將當前字符c加入到字符流中，從后往前遍歷字符流，對于每個字符c，在前綴樹中查找是否存在以c為結(jié)尾的字符串，如果存在返回true，否則返回false。

3.25題目?1574. 刪除最短的子數(shù)組使剩余數(shù)組有序

【雙指針】要找出數(shù)組的最長非遞減前綴和最長非遞減后綴，如果i≥j，說明數(shù)組本身就是非遞減的，否則可以刪右側(cè)后綴或左側(cè)前綴。枚舉左側(cè)前綴的最右端點l，對于每個l，直接用雙指針找到第一個大于等于nums[l]的位置，記為r，此時可以刪出nums[l+1,...r-1]，并更新答案，繼續(xù)枚舉l。

3.26題目?2395. 和相等的子數(shù)組

【哈希表】遍歷數(shù)組，用哈希表記錄兩個相鄰元素和，如果已經(jīng)出現(xiàn)過返回true，否則將和加入哈希表。

3.27題目?1638. 統(tǒng)計只差一個字符的子串數(shù)目

【枚舉】記k1為上一個不同字符的位置，記k0為上上一個不同字符的位置，枚舉i，維護k0和k1，累加k1-k0到答案中由于一開始k0和k1不存在，對于j≠i的情況，枚舉它倆的差值d=i-j，例如d=2時，枚舉的是s[i]和t[i-2此時k0和k1應初始化為的初始值減一。

3.28題目?1092. 最短公共超序列

【DP】先用dp求出兩個字符串的最長公共子序列，然后根據(jù)最長公共子序列構(gòu)造出最短公共超序列，定義f[i] [j]為字符串str1的前i個字符和字符串str2的前j個字符的最長公共子序列的長度，狀態(tài)轉(zhuǎn)移方程是{f[i] [j] = 0; f[i - 1] [j - 1] + 1; max(f[i - 1] [j], f[i] [j -1])}。用雙指針ij分別指向str1和str2的末尾，從后往前遍歷，每次比較str1[i]和str2[j]，相等則將任意一個字符加入到答案序列，ij同時減一，不等則將f[i] [j]和f[i -1] [j]和f[i] [j -1]的最大值進行比較，如果f[i] [j] = f[i - 1] [j]則將str1[i]加入答案序列，i--，f[i] [j] = f[i] [j -1]則將str2[j]加入答案序列，j--。直到i = 0 或 j = 0，然后將剩余字符串加入到答案序列，最后將答案反轉(zhuǎn)。

3.29題目?1641. 統(tǒng)計字典序元音字符串的數(shù)目

【數(shù)學】問題轉(zhuǎn)化為n 個字符分配給五個元音所代表的盒子，盒子可以為空，一共有多少種方法。盒子不為空的情況：把 n 個小球分成了 m，放隔板的位置有 n - 1 個，我們要放 m - 1 個隔板。答案為 C(n - 1, m - 1)；盒子可以為空的情況：想成先把 n + m 個小球放到 m 個盒子里，盒子不能為空，然后再在每個盒子里拿走 1 個小球，總共拿走了 m 個小球，得到的結(jié)果，就是把 n 個小球放到 m 個盒子里，盒子可以為空的解，即C(n + m - 1, m - 1)。代入m=5，ans=C(n + 5 - 1, 5 - 1) = C(n + 4, 4)

3.30題目?1637. 兩點之間不包含任何點的最寬垂直區(qū)域

【排序】對數(shù)組points按照x升序排序，獲取相鄰點之間x的差值的最大值。

3.31題目?2367. 算術(shù)三元組的數(shù)目

【三指針】由于nums是嚴格遞增的，遍歷k時，i和j只增不減，因此可以用類似同向雙指針的做法來移動指針：枚舉x=nums[i]；移動j直到nums[j]+diff≥x，如果nums[j]+d時=x，則移動i直到nums[i]+2·diff時≥x；如果nums[2+2·df=x，則找到了一對等差三元組。無需判斷j<k和i<j，因為一旦j=k，numsj]+df≥x必然成立，所以萬<k無需判斷，i也同理。