10.1題目 1694. 重新格式化電話號(hào)碼

【模擬】按題意模擬即可。

10.2題目 777. 在LR字符串中交換相鄰字符

【雙指針】思路：X是空地，L是向左移，L是向右移，L不能穿過(guò)R，R不能穿過(guò)X。代碼：首先start和end里L(fēng)和R的相對(duì)順序必須一致（因?yàn)長(zhǎng)R不能互相穿越），雙指針遍歷start和end，如果當(dāng)前字符是L，但i<j 由于L無(wú)法向右移 false，R i>j false。

10.3題目 1784. 檢查二進(jìn)制字符串字段

【模擬】由于沒(méi)有前導(dǎo)零，避免01串就行。

10.4題目 921. 使括號(hào)有效的最少添加

【貪心】left、right分別記錄左右括號(hào)需求，碰到一個(gè)左括號(hào)說(shuō)明需求一個(gè)右括號(hào)，碰到一個(gè)右括號(hào)，右括號(hào)需求減一，如果右括號(hào)又缺一個(gè)，左括號(hào)需求加一。

10.5題目 811. 子域名訪問(wèn)計(jì)數(shù)

【哈希表】用哈希表記錄每個(gè)子域名的訪問(wèn)次數(shù)（為了避免子域名重復(fù)），最后將計(jì)數(shù)和子域名拼接。

10.6題目 927. 三等分

【三指針】首先，需要能夠三等分，數(shù)組中1的數(shù)量必須是3的倍數(shù)。其次，由于第三組0的數(shù)量是確定的，用第三組的大小去確定前兩組（find函數(shù)找到每組的第一個(gè)1來(lái)劃分組）。滿足三組每組1的數(shù)量相同后，從前往后檢查每組的二進(jìn)制值是否相等。

10.7題目 1800. 最大升序子數(shù)組和

【模擬】按題意模擬，用sm記錄升序子數(shù)組的和，ans記錄其中最大值。

10.8題目 870. 優(yōu)勢(shì)洗牌

思路：田忌賽馬，打得過(guò)直接打，打不過(guò)派最爛的打。

【有序數(shù) + 二分】用比nums2[i]稍大的去打nums2[i]，要是nums1里最大的都打不過(guò)就用num1最小的打。

【排序 + 雙指針】對(duì)于增序的兩個(gè)數(shù)組nums1和nums2，如果nums1[i] ≤ nums2[i]，說(shuō)明nums[i] ≤ nums2的任意元素，剩著最后再匹配。（此題可以用nums2原地排序節(jié)約ans的空間）

10.9題目 856. 括號(hào)的分?jǐn)?shù)

題意：( ) 1分.（ () () () ）2×(1+1+1)分

【字符串處理】按題意，()一分，左括號(hào)加，右括號(hào)結(jié)算兩倍分?jǐn)?shù)。

【計(jì)數(shù)】記（的個(gè)數(shù)為exp，每多一個(gè)得分倍數(shù)×2，每次碰到右括號(hào)結(jié)算得分2^exp。

10.10題目 801. 使序列遞增的最小交換次數(shù)

【dp】用一個(gè)維度的狀態(tài)表示交換與否，設(shè)dp[i] [0]表示到位置i為止nums1和nums2都嚴(yán)格遞增所需的最小操作數(shù)且不對(duì)位置i進(jìn)行交換，dp[i] [1]就是滿足遞增但對(duì)位置i進(jìn)行交換。記a1 = nums1[i - 1], a2 = nums1[i], b1 = nums2[i - 1], b2 = nums2[i], 若a1 < a2且b1 < b2時(shí)，位置i可換可不換，有dp[i] [0] = dp[i - 1] [0]；dp[i] [1] = dp[i - 1] [1] +1；若a2 > b1且 b2 > a1，可以交換a2和b2 或a1和b1（選次數(shù)少的換），有dp[i] [0] = min(dp[i] [0], dp[i - 1] [1])，dp[i] [1] = min(dp[i] [1], dp[i - 1] [0] + 1)。

10.11題目 1790. 僅執(zhí)行一次字符串交換能否使兩個(gè)字符串相等

【計(jì)數(shù)】?jī)蓚€(gè)字符串至多只存在兩個(gè)位置i,j處字符不相等，交換i,j處字符即可。如果s1==s2不需要交換，若s1!=s2，必須要滿足s1[i] = s2[j],s1[j] = s2[i]，兩個(gè)字符中只存在1個(gè)或大于2個(gè)位置的字符不相等，則無(wú)法通過(guò)一次交換使之相等。

10.12題目 817. 鏈表組件

【模擬】題意是找“一維連通塊”的數(shù)量，即以head中節(jié)點(diǎn)值不在nums的節(jié)點(diǎn)作為分割，能分割出來(lái)子鏈數(shù)量。

10.13題目 769. 最多能完成排序的塊

【貪心】arr是[0~n-1]的排列，記一個(gè)塊[0,i]內(nèi)最大值為mx，如果mx>i，則在[i+1,n-1]區(qū)間內(nèi)必定存在一個(gè)值小于mx，這個(gè)值必然屬于前一個(gè)塊（否則塊分別排序完這個(gè)值將在mx之后），所以可知對(duì)于每個(gè)i==mx為塊的分割點(diǎn)。

10.14題目 940. 不同的子序列 II

【DP】定義dp[i]為以s[i]結(jié)尾的不同子序列的個(gè)數(shù)，遍歷字符串s，更新dp[i] = Σdp[j] + 1。（Σdp[j]是之前求的不同子序列的個(gè)數(shù)，+1是指s[i]本身作為一個(gè)子序列）

10.15題目 1441. 用棧操作構(gòu)建數(shù)組

【模擬】cur對(duì)應(yīng)從list里取的1~n，遍歷target的每個(gè)num，如果cur < num，說(shuō)明應(yīng)該先push再pop cur這個(gè)數(shù)，直到cur = num那么只push不pop。

10.16題目 886. 可能的二分法

【DFS】染色法判定二分圖模板題，先把題中給的邊數(shù)組改成鄰接表，然后判斷是否為二分圖。兩種染色標(biāo)記為1和-1。遍歷每個(gè)節(jié)點(diǎn)，把該點(diǎn)染成c，然后遍歷這個(gè)點(diǎn)的鄰近節(jié)點(diǎn)，不能出現(xiàn)顏色同樣為c，也不能出現(xiàn)沒(méi)染過(guò)色但是染-c失敗的點(diǎn)。(color[x] = 0表示未訪問(wèn)節(jié)點(diǎn))

【BFS】上述操作也用隊(duì)列來(lái)實(shí)現(xiàn).(q就是visited)

【并查集】遍歷每個(gè)人，這個(gè)人和他討厭的人不該在同一個(gè)集合中。

10.17題目 904. 水果成籃

【滑動(dòng)窗口 + 哈希表】題意是求找到一段區(qū)間內(nèi)不超過(guò)兩種類型的最長(zhǎng)子數(shù)組的長(zhǎng)度。右邊界每次都右移，用哈希表統(tǒng)計(jì)滑動(dòng)窗口內(nèi)的種類數(shù)，如果超過(guò)2種就需要將左邊界右移，每次遍歷更新一次答案。

10.18題目 902. 最大為 N 的數(shù)字組合

【記憶化搜索】題意是求給定區(qū)間內(nèi)，由digits中數(shù)字構(gòu)成的正整數(shù)個(gè)數(shù)，可以用記憶化搜索來(lái)實(shí)現(xiàn)數(shù)位 DP，定義dfs(i, is_limit, is_num)，i表示數(shù)字位數(shù)，is_num表示第i位前是否填了數(shù)字，is_limit表示可填數(shù)字是否有限制。

10.19題目 1700. 無(wú)法吃午餐的學(xué)生數(shù)量

【模擬】遍歷每個(gè)三明治，如果某個(gè)三明治所有學(xué)生都不喜歡，那么這個(gè)三明治及之后的都無(wú)法被拿走了，返回剩余學(xué)生數(shù)量。

10.20題目 779. 第K個(gè)語(yǔ)法符號(hào)

【位運(yùn)算 + 遞歸】寫幾行找規(guī)律，可以發(fā)現(xiàn)每一層的前半部分和上一層完全一致，后半部分是上一層的01反轉(zhuǎn)。那么如果k在前半部分，第k個(gè)字符就是上一層的第k個(gè)字符，遞歸kthGrammar(n -1 ,k)，若k在后半部分，k就是上一層第k - 2^n - 2個(gè)字符的01反轉(zhuǎn)，即kthGrammar(n -1 , k - 2^n - 2) xor 1。

【位運(yùn)算 + 找規(guī)律】找規(guī)律，反轉(zhuǎn)奇數(shù)次，相當(dāng)于反轉(zhuǎn)1次，反轉(zhuǎn)偶數(shù)次，字符不變，所以只需要看k整個(gè)數(shù)字的累計(jì)反轉(zhuǎn)次數(shù)，等價(jià)于求 k的二進(jìn)制表示中，有多少位是 1。

10.21題目 901. 股票價(jià)格跨度

【單調(diào)?！拷?jīng)典單調(diào)棧模型，找出左側(cè)第一個(gè)比當(dāng)前元素大的元素。從當(dāng)天price往前找到第一個(gè)比該price大的價(jià)格，兩個(gè)元素的下標(biāo)之差即為跨度。需要維護(hù)一個(gè)棧底島棧頂單調(diào)遞減的棧，棧中每個(gè)元素存放(price, idx)數(shù)據(jù)對(duì)。

10.22題目 1235. 規(guī)劃兼職工作

【dp + 二分】先按結(jié)束時(shí)間排序，定義dp[i]為前i個(gè)工作的最大報(bào)酬，對(duì)于第i個(gè)工作要么選要么不選，dp[i] = max(dp[i - 1], dp[j] + profit[j])，j是最大的滿足endtime[j] ≤ starttime[i]的j，不存在時(shí)為-1，為了避免處理-1，可以改為dp[i + 1] = max(dp[i], dp[j] + profit[i])，初始f[0] = 0, ans = f[n]。由于結(jié)束時(shí)間有序，j可以用二分查找到。

【記憶化搜索 + 二分】定義dfs(i)為從第i份工作開(kāi)始,可獲最大報(bào)酬,ans = dfs(0). dfs(i) = max(dfs(i + 1), dfs(j) + profit[i]).

10.23題目 1768. 交替合并字符串

【雙指針】按題意模擬，使用兩個(gè)指針i 、j，分別指向兩個(gè)字符串的起始，如果i沒(méi)超過(guò)范圍就加入word[i]，j同理，i、j都超出范圍就return.

【調(diào)庫(kù)】itertools.zip_longest和zip的區(qū)別——zip匹配短的那個(gè)，zip_longest匹配長(zhǎng)的那個(gè)。

10.24題目 915. 分割數(shù)組

【一次遍歷】left中每個(gè)元素都≤right中的每個(gè)元素，等價(jià)于left中最大值≤right中的最小值。從左向右遍歷，left_max記錄left數(shù)組最大值，如過(guò)有效，則右側(cè)從partition + 1開(kāi)始的每個(gè)元素值都應(yīng)該大于left_max，如果右側(cè)找到一個(gè)left_max小的元素，合并到左側(cè)區(qū)間，否則記錄一個(gè)cur_max，一旦右側(cè)數(shù)組再次比left_max小，left_max = cur_max。

10.25題目 934. 最短的橋

【DFS + BFS】求最小反轉(zhuǎn)次數(shù)使得兩個(gè)島嶼連接，實(shí)際上是求連個(gè)島嶼之間的最短距離，可以用DFS將其實(shí)一個(gè)島嶼的所有點(diǎn)都找出來(lái)放到隊(duì)列里，然后通過(guò)BFS一層層向外擴(kuò)展，直至碰到另一個(gè)島嶼，當(dāng)前擴(kuò)展層數(shù)即為答案。搜索過(guò)程中，可以將已訪問(wèn)過(guò)的點(diǎn)標(biāo)記為-1避免重復(fù)訪問(wèn)。

10.26題目 862. 和至少為 K 的最短子數(shù)組

【前綴和 + 單調(diào)隊(duì)列】子數(shù)組的和可以轉(zhuǎn)換為2個(gè)前綴和的差，可以暴力枚舉所有i > j且presum[i] - presum[j] ≥ k的子數(shù)組[j, i)，找到最小的i-j就是答案。也可以用單調(diào)隊(duì)列維護(hù)遍歷過(guò)的presum[i]，如果presum[i] - presum[j] ≥ k，可以把presum[j]彈出，如果presum[i] < presum[j]，后續(xù)有presum[u]使得presum[u] - presum[i] ?≥ k,也可以彈出presum[j]，保證presum[j]單調(diào)遞增。優(yōu)化：可以在計(jì)算前綴和的同時(shí)計(jì)算答案。

10.27題目 1822. 數(shù)組元素積的符號(hào)

【遍歷】元素值乘積的正負(fù)與正負(fù)元素的數(shù)量奇偶有關(guān)，初始sign = 1，碰到整數(shù)sign不變，如果碰到負(fù)數(shù)符號(hào)反轉(zhuǎn)。

10.28題目 907. 子數(shù)組的最小值之和

【單調(diào)棧】對(duì)每個(gè)數(shù)，算出它是哪些子數(shù)組的最小值，可以用單調(diào)棧維護(hù)arr[i]的左右邊界，可以直接在出棧的時(shí)候計(jì)算貢獻(xiàn)。

10.29題目 1773. 統(tǒng)計(jì)匹配檢索規(guī)則的物品數(shù)量

【模擬】用哈希表把輸入key轉(zhuǎn)為value下標(biāo)，再遍歷統(tǒng)計(jì)value相等的數(shù)量。

10.30題目 784. 字母大小寫全排列

【暴搜】依次遍歷s的每個(gè)字母，將其轉(zhuǎn)換為小寫和大寫兩種字母。

【BFS】遍歷下一個(gè)字符c，如果是數(shù)字，將所有序列的末尾都加上c，如果是字母，加上c和swapcase(c)，放入隊(duì)列，隊(duì)列長(zhǎng)度==長(zhǎng)度則說(shuō)明搜索完成。

【回溯】搜索到字符串s的第i個(gè)字符c時(shí)，若c為數(shù)字繼續(xù)檢測(cè)下一個(gè)字符，若c為字母，swapcase之后繼續(xù)搜索，搜索完后恢復(fù)c繼續(xù)搜索。

【位掩碼】字符串s有m個(gè)字母，全排列有2^m個(gè)字符串序列，用bits唯一地表示一個(gè)字符串，bits的第i為0表示s從左往右第i個(gè)字母為小寫，1為大寫。位掩碼計(jì)算字母，數(shù)字就跳過(guò)，依次檢測(cè)字符串第i個(gè)字符串c，c為數(shù)字直接添加，c為字母，根據(jù)掩碼bits判斷添加大小寫。

10.31題目 481. 神奇字符串

【構(gòu)造】1、2交替出現(xiàn)，根據(jù)現(xiàn)在的數(shù)字確定接下來(lái)生成幾個(gè)1or2。1和2的轉(zhuǎn)換可以用3 - cur 或 xor3（1^3=2, 2^3=1）。也可以提前構(gòu)造好數(shù)組，直接查詢。