8.1題目 1374. 生成每種字符都是奇數(shù)個(gè)的字符串

【分類討論】n為奇數(shù)，返回n個(gè)'a'，n為偶數(shù)，返回n-1個(gè)'a'和一個(gè)'b'.

8.2題目 622. 設(shè)計(jì)循環(huán)隊(duì)列

【數(shù)組】設(shè)置一個(gè)隊(duì)尾rear，一個(gè)隊(duì)首front，隊(duì)列的長(zhǎng)度為(rear - front + capacity) mod capacity。

8.3題目 899. 有序隊(duì)列

【分類討論】k!=1時(shí)，可以將字符串打亂成任意順序，等價(jià)于尋找全排列中字典序最小排列，直接sort。k==1時(shí)，可以將字符串復(fù)制一份到自己身后，遍歷從0~n-1開(kāi)始的長(zhǎng)度為n的n個(gè)字串，n個(gè)字串就是k=1的所有合法排列。

8.4題目 1582. 二進(jìn)制矩陣中的特殊位置

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

8.5題目 623. 在二叉樹(shù)中增加一行

【BFS】層序遍歷，每個(gè)node都新增left和right兩個(gè)節(jié)點(diǎn)，并把原子節(jié)點(diǎn)作為left的左子節(jié)點(diǎn)，把原右子節(jié)點(diǎn)作為right的右子節(jié)點(diǎn)。

8.6題目 1408. 數(shù)組中的字符串匹配

【枚舉】枚舉每個(gè)子字符串判斷是否是其他字符串的子字符串。

8.7題目 636. 函數(shù)的獨(dú)占時(shí)間

【?！坑脳ＤM函數(shù)調(diào)用過(guò)程，函數(shù)調(diào)用開(kāi)始時(shí)，如果當(dāng)前有函數(shù)正在運(yùn)行，則當(dāng)前正在運(yùn)行函數(shù)應(yīng)當(dāng)停止，此時(shí)計(jì)算其的執(zhí)行時(shí)間，然后將調(diào)用函數(shù)入棧。
當(dāng)函數(shù)調(diào)用結(jié)束時(shí)，將棧頂元素彈出，并計(jì)算相應(yīng)的執(zhí)行時(shí)間，如果此時(shí)棧頂有被暫停的函數(shù)，則開(kāi)始運(yùn)行該函數(shù)。

8.8題目 761. 特殊的二進(jìn)制序列

【分治】對(duì)于一個(gè)特殊序列而言，它一定以 1開(kāi)始，以 0結(jié)束?？梢园咽孜?11 和末位 00 直接移除，進(jìn)一步考慮剩余的字符串?？梢赃f歸地考慮每個(gè)特殊系列，遞歸返回后可以合并，按照字典序降序排序再拼接。

8.9題目 1413. 逐步求和得到正數(shù)的最小值

【前綴和】只需保證累加和的最小值accSumMin滿足accSumMin + startValue ≥ 1，最小值可取-accSumMin + 1。

8.10題目 640. 求解方程

【模擬】sign記錄符號(hào)，num記錄數(shù)字，valid記錄num是否有效，factor表示系數(shù)，val表示常量值，方程有解時(shí)，整數(shù)解x = -val/factor。

8.11題目 1417. 重新格式化字符串

【雙指針】sum_digit為字符串中數(shù)字個(gè)數(shù)，sum_alpha為字符串中字母?jìng)€(gè)數(shù)，格式化字符串的充要條件為|sum_digit - sum_alpha| ≤ 1.

8.12題目 1282. 用戶分組

【哈希表】對(duì)于每個(gè)元素x，x出現(xiàn)y次時(shí)，y一定能被x整除，且大小為x的組有y/x個(gè)。

8.13題目 768. 最多能完成排序的塊 II

【單調(diào)?！繌淖蟮接颐總€(gè)分塊都有一個(gè)最大值，這些分塊最大值單調(diào)遞增，可用棧存最大值。

8.14題目 1422. 分割字符串的最大得分

【枚舉】枚舉每個(gè)下標(biāo)i作為分割點(diǎn)，分別計(jì)算s[0:i-1]中0的個(gè)數(shù)和s[i,n-1]中1的個(gè)數(shù)。

【前綴和】分別統(tǒng)計(jì)左邊0和右邊1，設(shè)所有0總數(shù)total_presum，左側(cè)0個(gè)數(shù)presum，右側(cè)1個(gè)數(shù)為(n - i) - (total_presum - presum)。

8.15題目 641. 設(shè)計(jì)循環(huán)雙端隊(duì)列

【數(shù)組】此題可以用數(shù)組或鏈表實(shí)現(xiàn)，類似設(shè)計(jì)循環(huán)隊(duì)列，隊(duì)列判滿條件是front = (1 + rear) mod capacity，隊(duì)列長(zhǎng)度 = (rear - front + capacity) mod capacity。

8.16題目 1656. 設(shè)計(jì)有序流

【哈希表】按題意模擬。

8.17題目 1302. 層數(shù)最深葉子節(jié)點(diǎn)的和

【DFS】遍歷時(shí)候維護(hù)層數(shù)，如果當(dāng)前節(jié)點(diǎn)層數(shù)大于最大層數(shù)，更新最大層數(shù)，最深節(jié)點(diǎn)更新為當(dāng)前值，如果當(dāng)前節(jié)點(diǎn)層數(shù)等于最大層數(shù)，將當(dāng)前節(jié)點(diǎn)值加到最深節(jié)點(diǎn)之和。

【BFS】層序遍歷標(biāo)準(zhǔn)寫(xiě)法。

【BFS】層序遍歷我的模板。

8.18題目 1224. 最大相等頻率

【哈希表】分類討論，四種情況：12345/11111/1112223334/1112223334444。count記錄x出現(xiàn)的次數(shù),freq記錄出現(xiàn)次數(shù)f的次數(shù)。其中if cnt[num]: freq[cnt[num]] -= 1 這一步是為了給freq“去重”，因?yàn)樗谐霈F(xiàn)次數(shù)≥2的數(shù)都出現(xiàn)了1次。

8.19題目 1450. 在既定時(shí)間做作業(yè)的學(xué)生人數(shù)

【枚舉】按題意模擬，starttime到endtime之間的人數(shù)。

【二分】starttime ≤ querytime的人數(shù) 減去 結(jié)束時(shí)間＜querytime的人數(shù)，就是ans。

【差分?jǐn)?shù)組】對(duì)差分?jǐn)?shù)組求前綴和，可以統(tǒng)計(jì)出t時(shí)刻正在做作業(yè)的人數(shù)，querytime時(shí)刻正在做作業(yè)的人數(shù)是Σcnt[j]。

8.20題目 654. 最大二叉樹(shù)

【遞歸】按題意模擬，區(qū)間最大值右側(cè)構(gòu)建右子樹(shù)，左側(cè)構(gòu)建左子樹(shù)。

【單調(diào)棧（笛卡爾樹(shù)）】對(duì)于nums[i]，假設(shè)nums[0]到num[i-1]已經(jīng)構(gòu)建了一顆笛卡爾樹(shù)，現(xiàn)在需要插入nums[i]。為了保證整顆樹(shù)的中序遍歷是原序列，所以nums[i]是當(dāng)前最后一個(gè)數(shù)（中序遍歷的最后一個(gè)樹(shù)），即建完樹(shù)（插入num[i]后），nums[i]是右鏈的最后一個(gè)。情況1：nums[i] > max(nums[:i])，nums[i]作為根節(jié)點(diǎn)，num[:i]作為nums[i]的左兒子；情況2：nums[i] < max(nums[:i])，此時(shí)右鏈滿足堆的性質(zhì)（單調(diào)遞減，越往下越?。?。而插入nums[i]之后仍然需要滿足堆的性質(zhì)，那么應(yīng)該在右鏈從上往下找，找到第一個(gè)小于nums[i]的數(shù)。此時(shí)，既要滿足大根堆從上到下遞減的性質(zhì)，也要滿足中序遍歷為原序列的性質(zhì)，要把nums[i]插到最近的>nums[i]的那個(gè)數(shù)和<nums[i]那個(gè)數(shù)之間，并把<nums[i]這個(gè)數(shù)為根節(jié)點(diǎn)的整顆子樹(shù)作為nums[i]的左兒子。寫(xiě)代碼時(shí)：對(duì)于情況2，可以將nums[:i]這顆樹(shù)右鏈上的點(diǎn)都存在棧里，枚舉時(shí)每次比較棧頂元素是否小于nums[i]，如果是，繼續(xù)往上走。

代碼中，用st存右鏈上所有點(diǎn)，從上往下一直刪比nums[i]小的數(shù)，直到找到比nums[i]大的數(shù)，把第一個(gè)比nums[i]大的數(shù)的右兒子設(shè)成nums[i]。

8.21題目 1455. 檢查單詞是否為句中其他單詞的前綴

【模擬】遍歷，判斷是否以serachword開(kāi)頭。

切片版

re版

8.22題目 655. 輸出二叉樹(shù)

【DFS】行數(shù)m = height + 1，列數(shù)n = 2^(height+1) -1。根節(jié)點(diǎn)所在的行與列會(huì)將剩余空間劃分為兩部分（左下部分和右下部分），遞歸地將左子樹(shù)輸出在左下部分空間，右子樹(shù)輸出在右下部分空間即可。

8.23題目 782. 變?yōu)槠灞P

【分維度計(jì)算】要達(dá)成最終的棋盤實(shí)際上等價(jià)于將矩陣的行表示成 0,1相互交替的狀態(tài)，如果一個(gè)行無(wú)法變?yōu)?0,1交替的狀態(tài)，則我們認(rèn)為矩陣不存在可行的變換。首先要檢測(cè)矩陣合法性，檢測(cè)每一行和每一列的狀態(tài)是否合法，檢測(cè)每一行和每一列中含有的數(shù)字是否合法，檢測(cè)不同狀態(tài)的行數(shù)和列數(shù)是否合法.然后分類討論,n是偶數(shù)和奇數(shù). 可以用32位整數(shù)(位掩碼)表示每一行或者每一列.

8.24題目 1460. 通過(guò)翻轉(zhuǎn)子數(shù)組使兩個(gè)數(shù)組相等

【排序】分別排序.

【哈希表】數(shù)組元素都一樣.

8.25題目 658. 找到 K 個(gè)最接近的元素

【自定義排序】按照"更接近"來(lái)排序,a比b更接近,a將排在b前.

【二分】[0, left]都<x,后一部分[right, n -1]都≥x.left right都能二分得到.

8.26題目 1464. 數(shù)組中兩元素的最大乘積

【排序】按題意模擬.

【大根堆】heapq.nlargest

【一次遍歷】遍歷過(guò)程中用ab兩個(gè)變量維護(hù)最大值和次大值.

8.27題目 662. 二叉樹(shù)最大寬度

【BFS】簡(jiǎn)單思路是求出每一層的寬度，然后求出最大值，每層最大寬度是每層節(jié)點(diǎn)的最大編號(hào)減最小id編號(hào) + 1.。對(duì)節(jié)點(diǎn)進(jìn)行編號(hào)，編號(hào)為index的左子節(jié)點(diǎn)編號(hào)為2×index，右子節(jié)點(diǎn)為2×index+1，每層最大編號(hào)減最小編號(hào) + 1 即為每層寬度.

【DFS】先訪問(wèn)左子節(jié)點(diǎn)，再訪問(wèn)右子節(jié)點(diǎn)，每一層先訪問(wèn)到最左邊的節(jié)點(diǎn)即每層的最小編號(hào)。

8.28題目 793. 階乘函數(shù)后 K 個(gè)零

【二分】令zeta(x)為x!末尾0的個(gè)數(shù)，zeta(x) = Σ1~∞(x/5^k)下取整。

8.29題目 1470. 重新排列數(shù)組

【一次遍歷】前半和后半，重排列。

切片

zip

chain

sum

8.30題目 998. 最大二叉樹(shù) II

【遞歸】在數(shù)組末尾添加新val，如果>根節(jié)點(diǎn)，則val是新根，若<根節(jié)點(diǎn)，val遞歸添加在原根右節(jié)點(diǎn)中，合并兩種情況。

8.31題目 946. 驗(yàn)證棧序列

【棧模擬】pushed是push的順序，popped是pop的順序。按順序執(zhí)行pushed里的每一步 + 按順序執(zhí)行popped里的每一步，最后能夠得到一個(gè)空棧。最后的目的是得到一個(gè)空棧。