12.1題目?1779. 找到最近的有相同 X 或 Y 坐標(biāo)的點(diǎn)

【枚舉】直接枚舉所有點(diǎn)。

12.2題目?1769. 移動(dòng)所有球到每個(gè)盒子所需的最小操作數(shù)

【預(yù)處理 + 枚舉】根據(jù)前一個(gè)盒子的操作數(shù)得到下一個(gè)盒子的操作數(shù)。預(yù)處理出每個(gè)位置i左邊的小球移動(dòng)到i的操作數(shù)left[i]，每個(gè)位置i右邊的小球移動(dòng)到i的操作數(shù)right[i]，ans[i] = left[i] + right[i]。

12.3題目?1796. 字符串中第二大的數(shù)字

【直接遍歷】記錄第一大和第二大，只對s[i]為數(shù)字生效。

【位運(yùn)算】整數(shù)mask標(biāo)識(shí)字符串中出現(xiàn)的數(shù)字，從高位到低位遍歷mask，找到第二個(gè)為1的二進(jìn)制位，其對應(yīng)的數(shù)字即為第二大數(shù)字。

12.4題目?1774. 最接近目標(biāo)價(jià)格的甜點(diǎn)成本

【回溯】回溯過程中總開銷不增不減，當(dāng)總開銷大于target時(shí)，停止搜索。

【DP】某一個(gè)開銷是否存在甜品制作方案，問題轉(zhuǎn)化為01背包問題，設(shè)最小基料開銷x，x≥target直接返回最小基料開銷，x<target對超過target的保存一份最小的方案。

【枚舉子集和 + 排序 + 二分查找】復(fù)制一份配料，dfs枚舉子集和，代碼中可以枚舉一半配料的所有子集和，在另一半配料中，二分最接近的配料。

12.5題目?1687. 從倉庫到碼頭運(yùn)輸箱子

【動(dòng)態(tài)規(guī)劃 + 單調(diào)隊(duì)列】定義f[i]表示把前i個(gè)箱子從倉庫運(yùn)送到相應(yīng)碼頭的最少行程數(shù)，ans = f[n]。從f[j]轉(zhuǎn)移過來的時(shí)候，卡車上的箱子數(shù)量不能超過maxBoxes從；從f[j]轉(zhuǎn)移過來的時(shí)候，卡車上的箱子總重量不能超過maxWeight?？梢酝ㄟ^前綴和，計(jì)算出碼頭之間的行程數(shù)，再加上首尾兩趟行程。實(shí)際上我們是要在[i-max Boxes，，…i-1]這個(gè)窗口內(nèi)找到一個(gè)j，使得f[j]-cs[j]的值最小，求滑動(dòng)窗口的最小值，一般用單調(diào)隊(duì)列。

12.6題目?1805. 字符串中不同整數(shù)的數(shù)目

【雙指針 + 模擬】找到每個(gè)整數(shù)的起始位置和結(jié)束位置，截取出這一個(gè)字串，存入哈希表，最后返回哈希表大小。

【正則】

12.7題目?1775. 通過最少操作次數(shù)使數(shù)組的和相等

【貪心 + 哈希表】設(shè)d = sum(nums2) - sum(nums1)，對于每個(gè)i，nums1[i]的最大變化量為6 - nums[i]，nums2[i]的最小變化量為nums2[i] - 1。統(tǒng)計(jì)變化量的個(gè)數(shù)，記到長為6的cnt數(shù)組中，有cnt[i]個(gè)數(shù)可以使d減少i，從大到小枚舉i = 5,4,3,2,1。如果d > i?cnt[i]，那么應(yīng)該把這cnt[i]個(gè)數(shù)的變化量拉滿，并更新d為d - i?cnt[i]，否則通過修改?d/i?個(gè)數(shù)，使d恰好為0，退出循環(huán)，ans = Σ（需要修改的數(shù)的個(gè)數(shù)）。可以優(yōu)化，如何把nums1全改成6仍小于nums2全改成1（互換同理），那么無法相等。

12.8題目?1812. 判斷國際象棋棋盤中一個(gè)格子的顏色

【找規(guī)律】顏色相同的兩個(gè)格子（x1,y1）和（x2,y2）滿足x1+y1和x2+y2同奇偶，奇白偶黑。

12.9題目?1780. 判斷一個(gè)數(shù)字是否可以表示成三的冪的和

【進(jìn)制轉(zhuǎn)換】一個(gè)數(shù)n可以表示位若干個(gè)不同的三的冪之和，那么n的三進(jìn)制表示中，每一位的數(shù)字只能是0或1，將n轉(zhuǎn)換為三進(jìn)制判斷。

12.10題目?1691. 堆疊長方體的最大高度

【排序 + 動(dòng)態(tài)規(guī)劃】把所有長方體的邊長進(jìn)行排序，使每個(gè)長方體滿足 長 <= 寬 <= 高，定義f[i]表示以長方體i位最底部長方體時(shí)的最大高度，枚舉每個(gè)長方體i的上方的長方體j，其中0≤j<i，j可以放在i上方時(shí)，有f[i] = max(f[j] + h[i])。h[i]是長方體i的高度，ans = max(f[i])。

12.11題目?1827. 最少操作使數(shù)組遞增

【遍歷】用變量mx記錄當(dāng)前嚴(yán)格遞增數(shù)組的最大值，每個(gè)遍歷到的元素給他set到至少mx+1，統(tǒng)計(jì)ans。

12.12題目?1781. 所有子字符串美麗值之和

【枚舉】O(n^2)枚舉每個(gè)字串的起始位置i，找到以該起點(diǎn)位置的字符為左端點(diǎn)的所有字串，計(jì)算每個(gè)子串的美麗值，累加到答案中。

12.13題目?1832. 判斷句子是否為全字母句

【位運(yùn)算】用一個(gè)整數(shù)mask記錄出現(xiàn)過的字母，其中mask的第i位表示第i個(gè)字母是否出現(xiàn)過，最后判斷mask的二進(jìn)制表示中是否有26個(gè)1，即mask 是否等于2^26-1.

12.14題目?1697. 檢查邊長度限制的路徑是否存在

【離線查詢 + 并查集】給定一個(gè)查詢時(shí)，遍歷edgeList里的所有邊，依次將長度小于limit的邊加入并查集，使用并查集查詢p和q是否屬于同一個(gè)集合，如果p和q屬于同一個(gè)集合，說明存在p到q的路徑，且這條路徑上每一條邊的長度都嚴(yán)格小于limit，查詢返回true，否則false。如果queries的limit是非遞減的，說明上一次查詢的并查集里的邊都滿足當(dāng)前查詢的limit要求，只需將剩余的長度小于limit的邊加入并查集中。首先將edgeList按邊長度從小到大排序，將queries按limit從小到大排序，用k指向上一次查詢中不滿足limit的長度最小的邊。依次遍歷queries，k指向的邊的長度小于對應(yīng)查詢的limit，則將該邊加入并查集中，然后將k加1，直到k指向的邊不滿足要求，最后根據(jù)并查集查詢p和q是否屬于同一集合。

12.15題目?1945. 字符串轉(zhuǎn)化后的各位數(shù)字之和

【模擬】按題意模擬。

12.16題目?1785. 構(gòu)成特定和需要添加的最少元素

【數(shù)學(xué)】需要使用多少個(gè)不超過limit的數(shù)組湊齊abs(sum-goal)，limit整除diff，答案就是?diff/limit?，若limit不整除，答案是?diff/limit? + 1，以上兩種情況可以統(tǒng)一為?(diff+limit?1)/limit?。

12.17題目?1764. 通過連接另一個(gè)數(shù)組的子數(shù)組得到一個(gè)數(shù)組

【雙指針】變量i指向group[i]。遍歷第k個(gè)元素，最后都找到了i=n就true。

12.18題目?1703. 得到連續(xù) K 個(gè) 1 的最少相鄰交換次數(shù)

【貪心 + 前綴和】可證明移動(dòng)到x（x為qi-i的中位數(shù)p?k/2?是最優(yōu)的），枚舉第i個(gè)1是連續(xù)1的最左邊的，前綴和求。

12.19題目?1971. 尋找圖中是否存在路徑

【DFS】建圖，dfs圖，用vis數(shù)組記錄vistied的頂點(diǎn)，判斷是否存在從source到destination的路徑。

【并查集】構(gòu)建并查集，將每條邊的兩個(gè)節(jié)點(diǎn)合并，最后查詢source和destination的祖先節(jié)點(diǎn)是否相同，相同則說明兩個(gè)節(jié)點(diǎn)連通。

12.20題目?1760. 袋子里最少數(shù)目的球

【二分】題目轉(zhuǎn)換為對于某個(gè)開銷值看它能否在maxOperations次操作內(nèi)得到，二分枚舉開銷。假設(shè)最大值不超過y，二分查找到 y時(shí)，對于第 i 個(gè)袋子，其中有 nums[i] 個(gè)球，那么需要的操作次數(shù)為?(nums[i] - 1)/y??？偛僮鲾?shù)P= Σ?(nums[i] - 1)/y?，P≤maxOperations時(shí)，調(diào)整二分上界，否則調(diào)整二分下界。

12.21題目?1753. 移除石子的最大得分

【模擬 + 貪心】每次從最大的兩堆石頭里取石頭，直到至少兩堆石頭為空。

【數(shù)學(xué)】設(shè)a≤b≤c，那么當(dāng)a+b≤c時(shí)，先從a,c兩堆中取石頭得分x，再從b,c兩堆中取石頭得分y，總分?jǐn)?shù)x+y。a+b>c時(shí)，從c及a和b中較大的那一堆取石頭，最終將c取空。

12.22題目?1799. N 次操作后的最大分?jǐn)?shù)和

【狀壓DP】預(yù)處理Nums中任意兩個(gè)數(shù)的最大公約數(shù)，其中 g[i]表示 nums[i]和nums[j] 的最大公約數(shù)，從小到大枚舉狀態(tài)。

12.23題目?2011. 執(zhí)行操作后的變量值

【模擬】注意到每個(gè)字符串的第二個(gè)位置一定是符號(hào)。

12.24題目?1754. 構(gòu)造字典序最大的合并字符串

【貪心 + 雙指針】對于word1[i]和word2[j]，誰字典序大添加誰。word1[i] = word2[j]時(shí)，看word1[i:]和word[j:]的字典序大?。ê缶Y字典序），自身字典序和后綴字典序均相等則任選一個(gè)即可。

本題也可以用后綴數(shù)組來做。

12.25題目?1739. 放置盒子

【數(shù)學(xué)】接觸地面的盒子 = 1 + 2 + ... + i = i(i + 1) / 2，對應(yīng)盒子上限maxN = 1 + (1 + 2) + (1 + 2 + 3) + ... + i(i + 1)/ 2 = i(i + 1)(i + 2)/6，在i(i + 1)(i + 2)/6的基礎(chǔ)上，接觸地面的盒子再增加j個(gè)，盒子上限增加1+2+..+j = j(j+1)/2。

12.26題目?1759. 統(tǒng)計(jì)同構(gòu)子字符串的數(shù)目

【數(shù)學(xué)】同構(gòu)子字符串為一個(gè)連續(xù)的字符序列且需要序列中的字符都相同，首先按照連續(xù)相同的字符來對字符串s進(jìn)行分組，對于一個(gè)組中字符串的任意子字符串都為同構(gòu)子字符串，而一個(gè)長度為m的字符串的子字符串的數(shù)目為m(m+1)/2。對于每一個(gè)組來統(tǒng)計(jì)其貢獻(xiàn)的同構(gòu)子字符串?dāng)?shù)目并求和即可。

12.27題目?2027. 轉(zhuǎn)換字符串的最少操作次數(shù)

【貪心】遍歷字符串 s，只要遇到 X，指針i就往后移動(dòng)三格，并且答案加 1；否則指針 i往后移動(dòng)一格。

12.28題目?1750. 刪除字符串兩端相同字符后的最短長度

【雙指針】定義兩個(gè)指針i和j指向字符串s的頭部和尾部，然后相中間移動(dòng)，直至i和j指向的字符不相等。

12.29題目?2032. 至少在兩個(gè)數(shù)組中出現(xiàn)的值

【數(shù)組 + 枚舉】將每個(gè)數(shù)組中的元素放入對應(yīng)的數(shù)組（或哈希表）中，然后枚舉1到100中的每個(gè)數(shù)i，判斷i是否在至少兩個(gè)數(shù)組中出現(xiàn)過。若是，則將加入答案數(shù)組中。

12.30題目?855. 考場就座

【有序集合 + 哈希表】假設(shè)兩個(gè)人位置分別為l和r，區(qū)間[l, r]表示之間的空閑作為區(qū)間，選中點(diǎn)m = l + ?(r-l) / 2?能使距離最大化。題意需要實(shí)時(shí)維護(hù)這些區(qū)間順序關(guān)系，并實(shí)時(shí)獲取這些區(qū)間中的最優(yōu)區(qū)間?？梢杂糜行蚣媳４孀粎^(qū)間，有序集合的每個(gè)元素為一個(gè)二元組(l, r)，表示(l, r)能坐學(xué)生，用left,right兩個(gè)哈希表維護(hù)每個(gè)學(xué)生左右鄰居。

12.31題目?2037. 使每位學(xué)生都有座位的最少移動(dòng)次數(shù)

【排序】將兩個(gè)數(shù)組分別排序，然后遍歷兩個(gè)數(shù)組，計(jì)算每個(gè)學(xué)生的座位與其實(shí)際座位的距離，將所有距離相加即為答案。