6.1題目?2517. 禮盒的最大甜蜜度

【貪心 + 二分】由于隨著甜蜜度的增大，能選擇的糖果數(shù)量變小，有單調(diào)性，所以可以用二分答案來做。對price從小到大排序，二分答案d。最小的數(shù)x可以選，下一個(gè)可以選的數(shù)是第一個(gè)≥x+d的數(shù)，依此類推。如果可以選的數(shù)<k，說明d取大了，否則說明d取小了，根據(jù)這一點(diǎn)來二分。二分上界可以取(price[-1] - price[0]) // (k - 1) + 1（即?(max(price) - min(price)) / (k - 1)?）。

6.2題目?2559. 統(tǒng)計(jì)范圍內(nèi)的元音字符串?dāng)?shù)

【前綴和】創(chuàng)建一個(gè)長度為n+1的前綴和數(shù)組s，s[i]表示數(shù)組words的前i個(gè)字符串中以元音開頭和結(jié)尾的字符串的數(shù)目。遍歷words，如果當(dāng)前字符串以元音開頭和結(jié)尾，s[i+1] = s[i] + 1，否則s[i+1] = s[i]。

6.3題目?1156. 單字符重復(fù)子串的最大長度

【雙指針】用哈希表統(tǒng)計(jì)字符串text每個(gè)字符出現(xiàn)的次數(shù)。定義一個(gè)指針i，每次將指針j指向i，并不斷向右移動(dòng)j，直到j(luò)指向的字符與i指向的字符不同，此時(shí)得到一個(gè)長度為l=j-i的字串text[i:j-1]，其余字符都相同。然后跳過指針j指向的字符，用指針k繼續(xù)向右移動(dòng)，知道k指向的字符與i指向的字符不同，此時(shí)得到一個(gè)長度為r = k - j - 1的字串text[j+1:k-1]，其中所有字符都相同，最多通過一次交換，可得最長單字符重復(fù)字串長度為min(l+r+1,cnt[text[i]])，接下來將指針i移動(dòng)到j(luò)繼續(xù)尋找下一個(gè)字串。

6.4題目?2465. 不同的平均值數(shù)目

【排序】排序后每次取數(shù)組守衛(wèi)元素計(jì)算它們的和，用哈希表記錄每個(gè)和出現(xiàn)的次數(shù)。

6.5題目?2460. 對數(shù)組執(zhí)行操作

【模擬】遍歷nums，對于任意相鄰的兩個(gè)元素nums[i]和nums[i+1]，如果nums[i]=nums[i+1]，那么將nums[i]的值變?yōu)樵瓉淼?倍，同時(shí)將nums[i+1]的值變?yōu)?。創(chuàng)建一個(gè)長度為n的答案數(shù)組ans，并將nums中所有非零元素按序放入ans中。

6.6題目?2352. 相等行列對

【模擬】將矩陣每一行和每一列進(jìn)行比較，如果相等那么就是一對相等行列對。

6.7題目?2611. 老鼠和奶酪

【貪心 + 排序】將第i塊奶酪從第二只老鼠分給第一只老鼠，得分的變化量為reward1[i] - reward2[i]，希望這個(gè)變化量盡可能大，才能使總得分最大。因此將奶酪按照reward1[i] - reward2[i]從大到小排序，前k塊奶酪由第一只老鼠吃掉，剩下奶酪由第二只老鼠吃掉。

6.8題目?1240. 鋪瓷磚

【遞歸回溯 + 狀態(tài)壓縮】按位置進(jìn)行遞歸回溯，過程中我們用一個(gè)變量t記錄當(dāng)前使用的瓷磚數(shù)。如果j=m，第i行已經(jīng)被完全填充，則遞歸到下一行，即(i+1,0)；如果i=n，則表示所有位置都已被填充，應(yīng)該更新答案并返回；如果當(dāng)前(i,j)已經(jīng)被填充，遞歸到下一個(gè)位置(i,j+1)。否則枚舉當(dāng)前位置(i,j)可以填充的最大正方形邊長w，并將當(dāng)前位置(i,j)到(i+w-1,j+w-1)的位置全部填充，然后遞歸到下一個(gè)位置(i,j+w)?；厮輹r(shí)，要將當(dāng)前位置(i,j)到(i+w-1,j+w-1)的位置全部清空。由于每個(gè)位置只有兩種狀態(tài)：填充或者未填充，因此我們可以使用一個(gè)整數(shù)來表示當(dāng)前位置的狀態(tài)。我們使用一個(gè)長度為n的整數(shù)數(shù)組filled，其中filled[1]表示第i行的狀態(tài)。如果filled[i]的第j位為1，則表示第i行第j列已經(jīng)被填充，否則表示未填充。

6.9題目?2699. 修改圖中的邊權(quán)

【兩次Dijkstra】先把-1都修改成1，然后跑第一遍Dijkstra，設(shè)從source到點(diǎn)i的最短路長度為d_i，0。如果從起點(diǎn)到終點(diǎn)的最短路長度不超過target（否則無解，返回空數(shù)組），那我們就來嘗試修改某些邊權(quán)，使得從起點(diǎn)到終點(diǎn)的最短路長度恰好等于target。不妨再跑一遍Dijkstra，由于Dijkstra算法保證每次拿到的點(diǎn)的最短路就是最終的最短路，所以按照Dijkstra算法遍歷點(diǎn)/邊的順序去修改，就不會(huì)對已確定的最短路產(chǎn)生影響。對于第二遍Dijkstra，設(shè)從source到點(diǎn)i的最短路長度為d_i，1。對于一條可以修改的邊x-y，假設(shè)要把它的邊權(quán)改為w，那么source-x-y-destination這條路徑由三部分組成： 1.從source到x的最短路，這是第二遍Dijkstra算出來的，即d_x，1。 2.從x到y(tǒng)，即w。 3.從y到destination的最短路，由于后面的邊還沒有修改，這個(gè)最短路是第一遍Dijkstra算出來的，即d_destination，0-d_y，0。注意這個(gè)式子僅當(dāng)y在從source到destination的最短路上才成立。不過，如果y不在最短路上，修改x-y并不會(huì)對最短路產(chǎn)生影響，所以代碼中并沒有判斷y是否在最短路上。這三部分之和需要等于target，所以有dx，1+w+d_destination，0-d_y，0=target。解得w=target-d_destination，0+dy，0-d_x，1。如果第二遍Dijkstra跑完后，從起點(diǎn)到終點(diǎn)的最短路仍然小于target，那么就說明無法修改，返回空數(shù)組。否則，答案就是我們在第二遍Dijkstra中作出的修改。注意第二遍Dijkstra跑完后可能還有些邊是-1（因?yàn)樵趙=1的時(shí)候沒有修改，或者有些邊不影響最短路），把這些邊都改成1就行。代碼實(shí)現(xiàn)時(shí)，為了修改邊權(quán)，需要在鄰接表中額外記錄邊的編號(hào)。此外，由于輸入最壞是稠密圖，可以用樸素版的Dijkstra算法。

6.10題目?1170. 比較字符串最小字母出現(xiàn)頻次

【排序 + 二分】首先根據(jù)題目描述實(shí)現(xiàn)函數(shù)f——返回字典序最小的字母的出現(xiàn)次數(shù)。接下來將words中每個(gè)字符串w都計(jì)算出f(w)并排序。然后遍歷queries，對于每個(gè)字符串q，在ws數(shù)組中二分查找第一個(gè)大于f(q)的位置i，則ws中下標(biāo)i及后面的元素都滿足f(q) < f(W)，當(dāng)前查詢答案就是n-i。

6.11題目?1171. 從鏈表中刪去總和值為零的連續(xù)節(jié)點(diǎn)

【前綴和 + 哈希表】若鏈表節(jié)點(diǎn)的兩個(gè)前綴和相等，說明兩個(gè)前綴和之間的連續(xù)節(jié)點(diǎn)序列的和為0，可以消去這部分連續(xù)節(jié)點(diǎn)。第一次遍歷鏈表，用哈希表last記錄前綴和及對應(yīng)鏈表節(jié)點(diǎn)，對于同一前綴和sm，后面出現(xiàn)的節(jié)點(diǎn)覆蓋前面的節(jié)點(diǎn)。接下來遍歷鏈表，若當(dāng)前節(jié)點(diǎn)cur的前綴和sm在last中出現(xiàn)，說明cur與last[s]之間的所有節(jié)點(diǎn)和為0，我們直接修改cur的指向，即cur.next=last[s].next，這樣就刪去了這部分和為0的連續(xù)節(jié)點(diǎn)。繼續(xù)往后遍歷，刪除所有和為0的連續(xù)節(jié)點(diǎn)。

6.12題目?1483. 樹節(jié)點(diǎn)的第 K 個(gè)祖先

【樹上倍增】預(yù)處理出每個(gè)節(jié)點(diǎn)的第2^i個(gè)祖先節(jié)點(diǎn)，由于任意k可以分解為不同的2的冪，如13=8+4+1。先枚舉i，再枚舉x，計(jì)算出所有爺爺節(jié)點(diǎn)，再算出所有爺爺?shù)臓敔敼?jié)點(diǎn)，pa[x] [0] = parent[x]，即父節(jié)點(diǎn)。pa[x] [1] = pa[pa[x]][0][0]，即爺爺節(jié)點(diǎn)。一般地，pa[x] [i+1] = pa[pa[x][i][i]][i]，如果pa[x] [i] == -1則pa[x] [i+1] = -1。需要找到k的二進(jìn)制表示中的所有1，可以從小到大枚舉i，如果k右移i位后的最低位為1，就說明k的二進(jìn)制從低到高第i位是1。

6.13題目?2475. 數(shù)組中不等三元組的數(shù)目

【哈希表】用 Counter 統(tǒng)計(jì)每個(gè)數(shù)字出現(xiàn)的次數(shù)，然后依次遍歷每個(gè)數(shù)字的出現(xiàn)次數(shù)，假設(shè)當(dāng)前遍歷到的數(shù)字為 x，出現(xiàn)次數(shù)為 c，那么在已經(jīng)選擇了 x 作為其中一個(gè)數(shù)字的情況下，剩下可以選擇的數(shù)字個(gè)數(shù)為 n-c，而在選擇 x 之前可以選擇的數(shù)字個(gè)數(shù)為 a，因此選擇 x 作為第二個(gè)數(shù)字的方案數(shù)為 a?c，同時(shí)在已經(jīng)選擇了 x 和另外一個(gè)數(shù)字作為三元組的前兩個(gè)數(shù)字的情況下，還需要選擇一個(gè)與它們都不同的數(shù)字作為第三個(gè)數(shù)字，剩下可以選擇的數(shù)字個(gè)數(shù)為 n-a-c，因此總的方案數(shù)為 a?c * (n-a-c)，這些方案數(shù)累加起來就是最終的結(jié)果。

6.14題目?1375. 二進(jìn)制字符串前綴一致的次數(shù)

【遍歷】只有當(dāng)前面所有的位都已經(jīng)被翻轉(zhuǎn)時(shí)，后面的位才可能成為前綴一致的一部分。在翻轉(zhuǎn)過程中，mx 記錄了當(dāng)前已經(jīng)翻轉(zhuǎn)過的位中最大的位置，如果 mx 等于當(dāng)前的下標(biāo) i，說明前 i 個(gè)位都已經(jīng)被翻轉(zhuǎn)，因此可以將答案加 1。

6.15題目?1177. 構(gòu)建回文串檢測

【前綴和】考慮一個(gè)字串能否在經(jīng)過最多k次替換后變回回文串，需要統(tǒng)計(jì)字串中每個(gè)字符出現(xiàn)的次數(shù)，可以通過前綴和。對于出現(xiàn)偶數(shù)次數(shù)的字符，不需要替換，對于出現(xiàn)奇數(shù)次的字符，需要進(jìn)行替換，替換次數(shù)為?x/2?，x為出現(xiàn)奇數(shù)次的字符個(gè)數(shù)，如果?x/2? < k，可以變成回文串。預(yù)處理長為i的前綴中，每種字符各出現(xiàn)多少次，用n*26的二維數(shù)組sm存前綴和，其中sm[i + 1] [j]表示sm[0] 到sm[i]中，字母表的第j個(gè)小寫字母的出現(xiàn)次數(shù)。對于queries[i]，利用前綴和計(jì)算每種字母出現(xiàn)次數(shù)，統(tǒng)計(jì)多少種字母出現(xiàn)奇數(shù)次，設(shè)為m，如果?m/2? <= k，那么ans[i]為真。

6.16題目?1494. 并行課程 II

【子集狀壓 DP】將所有的課程抽象成一個(gè)有向無環(huán)圖（DAG），其中每個(gè)節(jié)點(diǎn)表示一門課程，每條邊表示一個(gè)先修課程的關(guān)系。用二進(jìn)制數(shù)來表示當(dāng)前已經(jīng)選修的課程，其中二進(jìn)制數(shù)的第 i 位為 1 表示已經(jīng)選修第 i 門課程，為 0 則表示還未選修。用 f[S] 表示已經(jīng)選修了集合 S 中的所有課程所需要的最少學(xué)期數(shù)。因?yàn)橐还灿?2^n 種選課狀態(tài)，所以我們需要使用狀態(tài)壓縮的方式來存儲(chǔ)和轉(zhuǎn)移狀態(tài)。枚舉當(dāng)前學(xué)期選修的課程集合 T，并將其與當(dāng)前已經(jīng)選修的課程集合 S 進(jìn)行合并，得到一個(gè)新的選課狀態(tài) S' = S ∪ T。由于我們需要在當(dāng)前學(xué)期內(nèi)最多選修 k 門課程，因此 T 的大小不能超過 k。另外，為了保證先修課程的關(guān)系不被違反，我們需要保證 T 中的每個(gè)課程的先修課程都已經(jīng)在 S 中選修過了。用一個(gè)二進(jìn)制數(shù) pre[i] 來表示第 i 門課程的先修課程集合。具體來說，pre[i] 的第 j 位為 1 表示第 j 門課程是第 i 門課程的先修課程。然后，我們可以使用位運(yùn)算來判斷 T 中的所有課程的先修課程是否都已經(jīng)在 S 中選修過了。在枚舉 T 的過程中，我們需要對所有合法的 T 進(jìn)行轉(zhuǎn)移。具體來說，我們可以將 f[S'] 更新為 f[S ? (S' \ T)] + 1，其中 S ? (S' \ T) 表示從 S 中去掉所有在 S' \ T 中的課程，即已經(jīng)選修過但不在 T 中的課程。這個(gè)轉(zhuǎn)移的含義是，我們先選修 S 中除了 T 中的課程之外的所有課程，然后在當(dāng)前學(xué)期選擇 T 中的課程。

6.17題目?2481. 分割圓的最少切割次數(shù)

【分類討論】當(dāng)n=1時(shí)無需切割；n為奇數(shù)時(shí)，不存在共線的情況，最少需要n次切割；n為偶數(shù)時(shí)，可以兩兩共線，最少需要n/2次切割。

6.18題目?1254. 統(tǒng)計(jì)封閉島嶼的數(shù)目

【DFS】從網(wǎng)格圖的第一行、最后一行、第一列和最后一列的所有0出發(fā)，DFS訪問四方向的0，并把這些0標(biāo)記成訪問過。代碼實(shí)現(xiàn)時(shí)可以直接把0修改成1。然后從剩下的0出發(fā)，按照同樣的方式DFS訪問四方向的0，同時(shí)把0改成1。每次從一個(gè)新的0出發(fā)（起點(diǎn)），就意味著找到了一個(gè)新的封閉島嶼，答案加一。

6.19題目?1262. 可被三整除的最大和

【DP】定義dfs(i,j)為nums[0]到nums[i]中選數(shù)，后續(xù)還需選的數(shù)字之和sm滿足sm mod 3 = j的前提下下，sm的最大值，設(shè)x = nums[i]：如果不選x，問題變成從nums[0]到nums[i-1]中選數(shù)，所選數(shù)字之和sm，滿足sm mod 3 = j的前提下，sm的最大值，即dfs(i,j) = dfs(i-1,j)。如果選x，問題變成從nums[0]到nums[i-1]中選數(shù)，所選數(shù)字之和sm滿足(sm + x) mod 3 = j，即sm mod 3 = (j - x) mod 3的前提下，sm的最大值，即dfs(i,j) = dfs(i - 1, (j - x) mod 3) + x。兩種情況取最大值，有dfs(i,j) = max(dfs(i - 1, (j - x) mod 3) + x, dfs(i-1,j))，轉(zhuǎn)換成f[i] [j] = max(f[i-1] [j], f[i-1] [(j+x) mod 3] + x)，最后用滾動(dòng)數(shù)組優(yōu)化。

6.20題目?1595. 連通兩組點(diǎn)的最小成本

【狀壓DP】定義dfs(i,j)為第一組0~i和第二組0~m-1相連且第二組的集合j未被連接時(shí)，最小成本是多少。枚舉第一組的點(diǎn)i和第二組的0~m-1其中一個(gè)點(diǎn)相連，取最小值，即dfs(i,j) = min(dfs(i-1, j \ {k}) + cost[i] [k])，改成遞推，即f[i] [j] = min(f[i-1] [j \ {k}] + cost[i] [k])。

6.21題目?LCP 41. 黑白翻轉(zhuǎn)棋

【BFS】題目中棋盤的大小最大為8×8，因此可以嘗試枚舉所有的空余位置作為下一步放置黑棋的位置，然后使用廣度優(yōu)先搜索的方法計(jì)算在該位置下可以翻轉(zhuǎn)的白棋的數(shù)量，找出最大值即可。我們定義一個(gè)函數(shù)bfs(i,j)，表示在棋盤上放置黑棋在s(i,j)位置后，可以翻轉(zhuǎn)的白棋的數(shù)量。在函數(shù)中，我們使用隊(duì)列來進(jìn)行廣度優(yōu)先搜索，初始時(shí)將s(i,j)放入隊(duì)列中，然后不斷取出隊(duì)首位置，遍歷棋盤的八個(gè)方向，如果該方向上是一段連續(xù)的白棋，且在末尾是黑棋，則將該黑棋之前的所有白棋都可以翻轉(zhuǎn)，將這些白棋的位置放入隊(duì)列中，繼續(xù)進(jìn)行廣度優(yōu)先搜索。最后，我們返回可以翻轉(zhuǎn)的白棋的數(shù)量。

6.22題目?面試題 16.19. 水域大小

【DFS】從網(wǎng)格圖的0出發(fā)，DFS訪問八方向的0，并把這些0標(biāo)記成“訪問過”。代碼實(shí)現(xiàn)時(shí)可以直接把0修改成1。DFS過程中，統(tǒng)計(jì)每個(gè)方向訪問到的格子個(gè)數(shù)，累加個(gè)數(shù)得到池塘大小cnt。每次從一個(gè)新的0出發(fā)（起點(diǎn)），就意味著找到了一個(gè)新的池塘，把DFS得到的池塘大小加入答案。把答案排序后返回。

6.23題目?2496. 數(shù)組中字符串的最大值

【模擬】定義一個(gè)函數(shù)f(s)用于計(jì)算字符串s的值，如果s只包含數(shù)字，那么f(s)就是s在十進(jìn)制下的值，否則f（s)就是s的長度，答案為max(f(s))。

6.24題目?1659. 最大化網(wǎng)格幸福感

【狀壓dp】每個(gè)網(wǎng)格只有三種狀態(tài)：不分配人員、分配內(nèi)向的人、分配外向的人，用012表示三種狀態(tài)。定義dfs(i,pre,ic,ec)表示從第i行開始，且上一行的狀態(tài)為pre，內(nèi)向的人還剩ic個(gè)，外向的人還剩ec個(gè)，網(wǎng)格的最大幸福感。答案是dfs(0,0,introvertsCount,extrovertsCount)。如果i=m表示已經(jīng)處理完了所有行返回0，如果ic=ec=0表示所有人已經(jīng)分配玩了返回0，否則枚舉當(dāng)前行的狀態(tài)cur，計(jì)算當(dāng)前行的幸福感f[cur]，以及上一行的狀態(tài)pre之間對幸福感的共線g[pre] [cu]，并遞歸計(jì)算dfs(i+1, cur, ic-ix[cur], ec-ex[cur])，最后dfs(i,pre,ic,ec) = max(f[cur] + g[pre] [cur] + dfs(i+1, cur, ic-ix[cur], ec-ex[cur]))。

6.25題目?1401. 圓和矩形是否有重疊

【數(shù)學(xué)】 (x,y)小于圓半徑就在圓內(nèi)，矩形內(nèi)說明x1<=x<=x2，y1<=y<=y2，?和舉行重疊相當(dāng)于在舉行內(nèi)找到一個(gè)(x,y)使得a = |x-xCenter| 和b=|y-yCenter|都取到最小值，此時(shí)若a^2+b^2<=radius^2說明有重疊。對于x∈[x1,x2]和y∈[y1,y2]統(tǒng)一用f函數(shù)處理。

6.26題目?2485. 找出中樞整數(shù)

【公式】 (1+x)?x = (x+n)?(n - x + 1)，變形：n?(n - 1) = 2?x^2，x = 根號(hào)(n * (n + 1) / 2)。

6.27題目?1186. 刪除一次得到子數(shù)組最大和

【dp】定義f[i] [j]為子數(shù)組右端點(diǎn)是arr[i]，不能/必須刪除數(shù)字的情況下，子數(shù)組元素和的最大值。f[i] [0] = max(f[i - 1] [0], 0) + arr[i]，f[i] [1] = max(f[i - 1] [1] + arr[i], f[i - 1] [0]) ，空間優(yōu)化，在計(jì)算f[i+1]時(shí)，不會(huì)用到x下標(biāo)<i的狀態(tài)，狀態(tài)轉(zhuǎn)移方程改為f[1] = max(f[1] + arr[i], f[0]), f[0] = max(f[0], 0) + arr[i]。

6.28題目?1681. 最小不兼容性

【預(yù)處理 + 狀壓DP】設(shè)劃分后每個(gè)子集大小為m，m=n/k，n為數(shù)組長度。枚舉所有子集i（i∈[0,2^n]），如果子集i的二進(jìn)制表示中有m個(gè)1，并且子集i中的元素沒有重復(fù)，就可以計(jì)算出子集i的不兼容性，記為g[i]，即g[i] = max(min{num[j]})。定義f[i]為當(dāng)前已經(jīng)劃分的子集狀態(tài)為i時(shí)，子集的不兼容性和的最小值，對于狀態(tài)i，找出所有未被劃分且不重復(fù)的元素，用狀態(tài)mask表示，如果狀態(tài)mask中元素個(gè)數(shù)大于等于m，就枚舉mask的所有子集j，f[i ∪ j] = min{f[i ∪ j], f[i] + g[j]}。

6.29題目?1253. 重構(gòu) 2 行二進(jìn)制矩陣

【貪心】創(chuàng)建ans[0]和ans[1]分別表示矩陣的第一和第二行，從左到右遍歷數(shù)組colsum，對于遍歷到的元素colsum[j]。如果colsum[j] = 2，將ans[0] [j] 和 ans[1] [j]都置為1，如果colsum[j] = 1，將ans[0] [j] 或 ans[1] [j]置為1，如果upper > lower，優(yōu)先將ans[0] [j]置為1，否則優(yōu)先將ans[1] [j]置為1，此時(shí)upper或lower減去1。如果colsum[j] = 0，將ans[0] [j] 和ans[1] [j]都置為0。如果upper<0或lower<0，說明無法構(gòu)造出滿足要求的矩陣，返回一個(gè)空數(shù)組，遍歷結(jié)束，如果upper和lower都為0則返回ans，否則返回一個(gè)空數(shù)組。

6.30題目?2490. 回環(huán)句

【模擬】判斷字符串的第一個(gè)字符和最后一個(gè)字符是否相等，如果不相等則返回false，否則遍歷字符串，如果當(dāng)前字符是空格，則判斷前一個(gè)字符和后一個(gè)字符是否相等，如果不相等則返回false，否則遍歷完所有字符后返回true。