2.1題目?2325. 解密消息

【哈希表】用哈希表存對照表，遍歷每個字符，替換為對應(yīng)字符。

2.2題目?1129. 顏色交替的最短路徑

【BFS】最短路問題，先對所有邊進行預(yù)處理，將所有邊按照顏色分類，存儲到多維數(shù)組g中，g[0]存紅色邊，g[1]存藍色邊。q存搜索到的節(jié)點和當前邊的顏色，vis存已經(jīng)搜索過的節(jié)點和當前邊的顏色，d存搜索層數(shù)即節(jié)點到起點的距離，ans存每個節(jié)點到起點的最短距離。先將起點0和起點邊顏色0或1入堆，表示從起點出發(fā)且當時是紅色或藍色邊，開始BFS，每次取出一個節(jié)點(i,c)，當前節(jié)點答案未更新就將當前節(jié)點的答案更新為當前層數(shù)d，然后將顏色c取反。

2.3題目?1145. 二叉樹著色游戲

【DFS】貪心，哪顆子樹最大，二號玩家就選哪顆，設(shè)n2為二號玩家最多可以染的節(jié)點個數(shù)，左子樹大小為l_size，右子樹大小為r_size。父節(jié)點子樹大小為n-1-l_size-r_size，n2 = max(l_size, r_size, n-1-l_size-r_size)。

2.4題目?1798. 你能構(gòu)造出連續(xù)值的最大數(shù)目

【排序+貪心】先排序，遍歷數(shù)組，對于當前遍歷到的元素v，如果v>ans，說明無法構(gòu)造出ans+1個連續(xù)的整數(shù)，直接跳出循環(huán)，否則說明可以構(gòu)造出ans+v個連續(xù)整數(shù)。

2.5題目?1210. 穿過迷宮的最少移動次數(shù)

【BFS】相當于網(wǎng)格圖上求起點到重點的最短路長度，但多一個水平/垂直條件，可以添加一個維度解決，用（x,y,s）表示蛇尾在第x行y列，s=0表示水平狀態(tài)，s=1表示垂直狀態(tài)，則初始位置為(0, 0, 0)， 最終位置為(n - 1, n - 2, 0)。用三元組表示(x,y,s)的變化量，狀態(tài)變換可以用異或運算解決。最后需要判斷：移動后蛇身不能出界，移動后蛇身不能在障礙物上，旋轉(zhuǎn)需要保證(x+1, y + 1)沒有障礙物。蛇尾在(x,y)，如果s=0，則蛇頭在(x, y + 1)，如果s = 1， 蛇頭在(x + 1, y)，合并成一個公式表示蛇頭：(x+s, y + s ⊕ 1)。

2.6題目?2331. 計算布爾二叉樹的值

【遞歸】要計算當前節(jié)點node的值，首先需計算出兩個葉子節(jié)點組成的子樹的值，再計算出當前節(jié)點組成的子樹的值。

2.7題目?1604. 警告一小時內(nèi)使用相同員工卡大于等于三次的人

【哈希表 + 排序】同一個員工使用卡的時間順序是按照h和min遞增的，遍歷數(shù)組keyname和keytime，哈希表記錄事件列表。

2.8題目?1233. 刪除子文件夾

【排序】將folder按照字典序排序，遍歷數(shù)組，對于當前遍歷到的文件夾f，如果長度大于等于最后一個文件夾的長度，并且它的前綴包含答案數(shù)組的最后一個文件夾再加上一個“/”，說明f是答案數(shù)組中最后一個文件夾的子文件夾。

2.9題目?1797. 設(shè)計一個驗證系統(tǒng)

【哈希表】維護一個哈希表，鍵是tokenId，值是過期時間，generate操作時，將tokenId作為鍵，currentTime + timeToLive作為值存入哈希表中；renew操作時，如果tokenId不在哈希表中，或者currentTime≥d[tokenId]，則忽略當前操作否則更新為currentTime + timeToLive，countUnexpiredTokens操作時，遍歷哈希表統(tǒng)計未過期的tokenId個數(shù)。

2.10題目?1223. 擲骰子模擬

【DP】定義f[i] [j] [x]為投擲前i次骰子，且第i次投擲的點數(shù)為j，連續(xù)投擲點數(shù)j的次數(shù)為x的方案數(shù)，初始時f[1] [j] [1] = 1，(1≤j≤6)，答案是ΣΣf[n] [j] [x]。

2.11題目?2335. 裝滿杯子需要的最短總時長

【貪心 + 分類討論】設(shè)a b c為數(shù)組amount中的三個數(shù)，有以下兩種情況：如果a+b≤c，只需要c次操作可將所有數(shù)變?yōu)?，答案為c；如果a+b>c，每次操作都可以將其中兩個數(shù)減1，最后會剩下一個數(shù)（取決與總和是偶數(shù)還是奇數(shù)），ans = ?(a+b+c+1)/2?

2.12題目?1138. 字母板上的路徑

【模擬】從起點(0,0)出發(fā)，模擬每一步的移動，將每一步的移動結(jié)果拼接到答案中，移動方向遵循左上右下的順序。

2.13題目?1234. 替換子串得到平衡字符串

【同向雙指針】如果待替換字串之外任意字符出現(xiàn)次數(shù)都>n/4，那么無論怎么替換都無法使這個字符的出現(xiàn)次數(shù)=n/4。如果待替換字串之外任意字符出現(xiàn)次數(shù)都不超過n/4，那么可以通過替換把s變成平衡字符串。用雙指針，設(shè)字串左右端點為l和r，枚舉r，如果字串外任意字符出現(xiàn)次數(shù)都不超過n/4，則說明l到r這段字串可以是待替換字串，用其長度r-l+1更新答案的最小值。

2.14題目?1124. 表現(xiàn)良好的最長時間段

【前綴和 + 哈希表】維護一個變量s，表示從下標0到當前下標的這一段，勞累天數(shù)與不勞累天數(shù)的差值，如果s>0，說明從下標到當前下標這一段滿足“表現(xiàn)良好”。用pos記錄每個s第一次出現(xiàn)的下標。遍歷hours，對于每個i，如果hous[i]>8，就讓s+1，否則-1。如果s>0，說明從下標0到當前下標這一段滿足“表現(xiàn)良好”，否則，如果s-1在哈希表中，記j=pos[s-1]，說明從下標j+1到當前下標i這一段，滿足“表現(xiàn)良好”，更新ans，如果s不在哈希表中，記錄pos[s] = i。

2.15題目?1250. 檢查「好數(shù)組」

【數(shù)學】數(shù)論中的“裴蜀定理”——對于不全為0的任意整數(shù)a和b，記g=gcd(a,b)，則對于任意整數(shù)x和y都滿足ax+by是g的倍數(shù)，特別地，存在整數(shù)x和y滿足ax+by=g。也可以推廣到多個整數(shù)的情況，對于不全為0的任意n個整數(shù)a1,a2,...an，記n個數(shù)的gcd為g，則對于任意n個整數(shù)x1,x2,...xn，都滿足求和ai×xi是g的倍數(shù)。正整數(shù)a1-an的最大公約數(shù)是1的充分必要條件是存在n個整數(shù)x1-xn滿足求和ai×xi = 1。由裴蜀定理，題目等價于求nums中全部數(shù)字的最大公約數(shù)是否是1.

2.16題目?2341. 數(shù)組能形成多少數(shù)對

【哈希表】統(tǒng)計數(shù)組nums中每個數(shù)字x出現(xiàn)的次數(shù)，記錄在哈希表或數(shù)組cnt中，遍歷cnt，對于每個數(shù)字x，如果x出現(xiàn)的次數(shù)v>1，則可以從數(shù)組選中兩個x形成一個數(shù)對，將v除以2向下取整，可得到當前數(shù)字x可以形成的數(shù)對數(shù)目，最后剩余的個數(shù)為nums的長度減去可以形成的數(shù)對數(shù)目×2。

2.17題目?1139. 最大的以 1 為邊界的正方形

【前綴和 + 枚舉】枚舉正方形邊長d和左上角坐標(i,j)，四條邊全為1等價于1的個數(shù)都等于d，用前綴和快速計算1的數(shù)量。

2.18題目?1237. 找出給定方程的正整數(shù)解

【相向雙指針】由于f是單調(diào)遞增函數(shù)，可以從x=1，y=1000開始，表示在橫坐標為x，1000以及縱坐標為[1，y]矩形范圍內(nèi)搜索答案。分類討論：1.如果f（x，y）2，那對于任意x>x，都有f（x'，y)>f（x，y）>z，這說明固定y枚舉其余x無法找到答案，那么將劉減一，縮小搜索范圍。3.如果f（x，y）=z，那么記錄答案，同情況1一樣，將x加一。由于f（x+1，y）>f（x，y）=z，根據(jù)情況2，可以同時將y減一。不斷循環(huán)直到x>1000或y<1為止，此時搜索范圍為空。

2.19題目?1792. 最大平均通過率

【優(yōu)先隊列（增量大根堆）】假設(shè)一個班級當前通過率為a/b，將一個聰明學生安排到此班級后，班級通過率變成(a+1)/(b+1)，通過率增量為(a+1)/(b+1) - a/b。維護一個大根堆（優(yōu)先選擇通過率增加量最大的班級），堆中存儲每個班級的通過率增量，進行extraStudents次操作，每次從堆頂取出一個班級，將這個班級的人數(shù)和通過人數(shù)都+1，然后將這個班級通過率增量重新計算并放回堆中，重復(fù)這個過程直到所有學生都分配完畢，最后將所有班級的通過率求和，然后除以班級數(shù)目即為答案。

2.20題目?2347. 最好的撲克手牌

【哈希表 + 計數(shù)】按題意求解。

2.21題目?1326. 灌溉花園的最少水龍頭數(shù)目

【貪心】對于能覆蓋某個左端點的水龍頭，選擇能覆蓋最遠右端點的水龍頭是最優(yōu)的，所以，先預(yù)處理數(shù)組ranges，對于第i個水龍頭，它能覆蓋的左端點l=max(0, i - ranges[i])，右端點r = i + ranges[i]，算出所有能覆蓋左端點l的水龍頭中，右端點最大的那個位置，記錄在數(shù)組last[i]中。定義mx為當前能覆蓋的最遠右端點，pre為上一個水龍頭覆蓋的最遠右端點。在[0,....,n-1]范圍內(nèi)遍歷所有位置，對于當前位置i，用last[i]更新mx，即mx=max(mx, last[i])，如果mx<i，說明無法覆蓋下一個位置，返回-1；如果pre=i，說明需要使用一個新的子區(qū)間，更新pre=mx。

2.22題目?1140. 石子游戲 II

【DP + 后綴和】定義f[i] [m]表示從piles[i]開始拿石子，可得到的最大石子數(shù)。定義后綴和s[i] = Σpiles[j]，有f[i] = s[i] - min(f[i + x], max(m, x))，ans= f[0] [1]。

2.23題目?1238. 循環(huán)碼排列

【位運算】“在一組數(shù)的編碼中，若任意兩個相鄰（包括首尾）的代碼只有一位二進制數(shù)不同，則稱這種編碼為格雷碼（Gray Code）”。二進制碼轉(zhuǎn)換成二進制格雷碼，其法則是保留二進制碼，其法是保留二進制碼的最高位作為格雷碼的最高位，次高位格雷碼為二進制碼的高位和次高位相異或，格雷碼其余各位與次高位的求法類似。對整數(shù)x，x ^ (x >> 1)可以得到其格雷碼。gray(0) = 0，那么gray(0) ⊕ start = start，gray(i)與gray(i - 1)只有一個二進制位不同，所以gray(i) ⊕ start 與 gray(i - 1) ⊕ start也只有一個二進制位不同，所以可以直接將[]0,...,2^n-1]這些整數(shù)轉(zhuǎn)換成對應(yīng)的gray(i) ⊕ start，可以得到首項位start的格雷碼排列。

2.24題目?2357. 使數(shù)組中所有元素都等于零

【哈希集合】貪心策略，觀察可知，操作數(shù)數(shù)組中不同非零元素個數(shù)。

2.25題目?1247. 交換字符使得字符串相同

【哈希表 + 貪心】s1[i] = s2[i]的位置不用處理，s1[i]!=s2[i]的個數(shù)記作d，d為奇數(shù) 奇數(shù)不能均分所以不可能，d為偶數(shù)，則不同的情況為s1[i] = 'x'，s2[i] = 'y'或s1[i] = 'y'，s2[i] = 'x',通過一次交換最多使d-2（貪心），如果不同的x個數(shù)為偶數(shù)，則每次都d-2，總次數(shù)d/2，不同的x為奇數(shù)，則每次d-2，最后還剩一對不同要通過兩次交換，所以是(d - 2)/2 + 2即d/2 + 1

2.26題目?1255. 得分最高的單詞集合

【二進制枚舉】由于數(shù)據(jù)范圍不大可以二進制枚舉出所有的單詞組合，判斷每個單詞組合是否滿足要求，滿足則積分，然后取得分最大的單詞組合，首先用哈希表或數(shù)組cnt記錄字母表letters中每個字母出現(xiàn)次數(shù)，然后枚舉所有單詞組合，二進制的每一位表示單詞表中每一個單詞是否被選中，第i位為1表示選中，然后統(tǒng)計當前單詞組合中每個字母出現(xiàn)的次數(shù)，記錄在哈希表中，如果每個字母出現(xiàn)次數(shù)都不大于cnt中對應(yīng)字母出現(xiàn)次數(shù)，說明滿足要求。

2.27題目?1144. 遞減元素使數(shù)組呈鋸齒狀

【枚舉 + 貪心】為了使操作次數(shù)盡量少，nums[i]需要不斷減小到比左右相鄰數(shù)字都小，就立刻停止，所以nums[i]修改成m = min(nums[i-1], nums[i + 1]) - 1，修改次數(shù)為max(nums[i] - m, 0)，如果i-1或i+1的下標越界，則對應(yīng)的數(shù)字為無窮大，最后把奇偶下標對應(yīng)的修改次數(shù)分別累加，結(jié)果為min(奇修改次數(shù)，偶修改次數(shù))。

2.28題目?2363. 合并相似的物品

【哈希表】用哈希表統(tǒng)計items1和items2的總重量然后從小到大遍歷即可。（注意：itertools.chain是合并兩個可迭代對象，比items1+items2的性能更好——items1+items2是用一個新建的list對象作為中間變量，時空間有額外的開銷，chain知識把兩個迭代器合成了，計算過程是lazy的，不存儲中間變量，這樣除了構(gòu)建管道的成本和捕獲異常的成本之外不會有額外的時空開銷，在兩個大items的情景下性能會更好）