7.1題目?1. 兩數(shù)之和

【哈希表】變形：nums[j] = tarhet - nums[i]，一邊枚舉j，一邊把nums[j]和j加到哈希表中。

7.2題目?2. 兩數(shù)相加

【遞歸】每次把兩個節(jié)點值l1.val，l2.val和進位值carry相加，除以10的余數(shù)即為當前節(jié)點需要保存的數(shù)位，除以10的商即為新的進位值。技巧：如果發(fā)現(xiàn)l2比l1場可以交換l1和l2，保證l1不是空節(jié)點從而簡化代碼邏輯。

【迭代】初始化答案為一個空鏈表，每次循環(huán)向該鏈表末尾添加一個節(jié)點，循環(huán)即遍歷鏈表l1和l2，每次把兩個節(jié)點值l1.val，l2.val與進位值carry相加，除以10的玉樹即為當前節(jié)點需要保存的數(shù)位，除以10的上即為新的進位制。在第一次循環(huán)時無法往一個空節(jié)點末尾添加節(jié)點，所以要創(chuàng)建一個哨兵節(jié)點當成初始的空鏈表，循環(huán)結(jié)束后哨兵節(jié)點下一個節(jié)點就是要返回的鏈表頭節(jié)點。

7.3題目?445. 兩數(shù)相加 II

【遞歸】反轉(zhuǎn)鏈表l1和l2，調(diào)用兩數(shù)相加的代碼，得到鏈表l3，最后返回反轉(zhuǎn)后的l3。

【迭代】

7.4題目?2679. 矩陣中的和

【排序】對每行排序，轉(zhuǎn)置后，遍歷每一列，找到每一列的最大值并相加。

7.5題目?2600. K 件物品的最大和

【貪心】按照1,0,-1的順序選，先選1，如果k≤numOnes那么答案就是k。再選0，如果k≤numOnes+numZeros那么答案為numOnes。最后選-1（題目要求恰好選k個），那么剩余必須選k-numOnes-numZeros個一1，答案為numOnes+(k-numOnes-numZeros).(-1)=numOnes.2+numZeros-k。

7.6題目?2178. 拆分成最多數(shù)目的正偶數(shù)之和

【貪心】finalSum分解成偶數(shù)之和，而偶數(shù)+偶數(shù)=偶數(shù)，所以finalSum必須是偶數(shù)，既然要盡可能多的分解且分解出的偶數(shù)各不相同，可以按照2468的順序分解，減小finalSum，直到finalSum小于要分解出的數(shù)為止，最后把剩余的finalSum加到最后一個分解出的偶數(shù)上。

7.7題目?2532. 過橋的時間

【模擬】建立4個堆，每個堆都記錄工人下標和完成時間（到達橋的時間），這4個堆從左到右分別表示：workL：新倉庫正在放箱的工人；waitL：左邊等待過橋的工人；waitR：右邊等待過橋的工人；workR；舊倉庫正在搬箱的工人。記錄當前時間cur，不斷循環(huán)直到所有箱子被搬完，每次循環(huán)： ①把完成時間不超過cur的workL彈出，放入waitL中；②把完成時間不超過cur的vorkR彈出，放入waitR中；③如果watR不為空，出堆，過橋，更新cur為過完橋的時間，然后把這個工人放入workL中（記錄完成時間）；④否則如果watL不為空，出堆，過橋，更新c2ur為過完橋的時間，然后把這個工人放入workR中（記錄完成時間），同時把n減一；⑤否則說明cur過小，找個最小的放箱/搬箱完成時間來更新cur。循環(huán)結(jié)束后，不斷彈出wokR，過橋，最后一個工人過完橋的時間即為答案。

7.8題目?167. 兩數(shù)之和 II - 輸入有序數(shù)組

【雙指針】定義兩個指針i和j，分別指向數(shù)組的第一個和最后一個元素，每次計算nums[i]+nums[j]如果等于target就返回[i+1,j+1]即可，如果和小于目標值，將i右移一位，如果和大于目標值，將j左移一位。

7.9題目?15. 三數(shù)之和

【排序 + 雙指針】不用按照順序返回三元組，所以可以對數(shù)組進行排序，能跳過重復元素，枚舉三元組第一個元素nums[i]，對于每個i，維護兩個指針j=i+1和k=n-1，找到滿足nums[i] + nums[j] + nums[k] = 0的j和k，在枚舉的過程中，需要跳過重復的元素，避免出現(xiàn)重復的三元組。具體判斷邏輯如下：如果i>0且nums[i]=nums[i-1]說明枚舉的元素與上一個元素相同直接跳過，如果nums[i]>0，說明當前枚舉的元素>0，三數(shù)之和必然無法等于0，結(jié)束枚舉。否則令左指針J=i+1，右指針k = n -1，當j0，說明nums[k]太大，需要將k左移一位。否則，說明我們找到一個合法的三元組，將其加入答案并將j右移一位，k左移一位，同時跳過所有重復的元素，繼續(xù)尋找下一個合法的三元組。

7.10題目?16. 最接近的三數(shù)之和

【雙指針】排序后枚舉nums[i]作為第一個數(shù)，找另外兩個數(shù)使得三個數(shù)和與target最接近。設(shè)s為三數(shù)之和，mindiff維護|s-target|的最小值。如果s=target，那么答案就是s，直接返回s；如果s>target，那么如果s-target<min Diff，說明找到了一個與target更近的數(shù)，更新minDiff為s-target，更新答案為s。然后和三數(shù)之和一樣，把k減一；否則s<target，那么如果target-s<min Diff，說明找到了一個與target更近的數(shù)，更新minDiff為target-s，更新答案為s。然后和三數(shù)之和一樣，把j加一。

7.11題目?1911. 最大子序列交替和

【DP】定義f[i]為從前i個元素中選出的子序列，且最后一個元素為奇數(shù)下標時的最大交替和，g[i]為從前i個元素中選出的子序列，且最后一個元素為偶數(shù)下標時的最大交替和，初始f[0] = g[0] = 0，答案為max(f[n], g[n])。考慮第i個元素nums[i-1]，如果選取該元素為奇數(shù)下標，上一個元素必須為偶數(shù)下標，只能從前i-1個元素中選取，因此f[i] = g[i-1]- nums[i -1]，如果不選取，f[i] = f[i- 1]。如果選取該元素并且該元素為偶數(shù)下標，那么上一個元素必須為奇數(shù)下標，只能從前i-1元素選取，因此g[i] = f[i-1]+nums[i-1]，不選取該元素那么g[i] = g[i-1]，狀態(tài)轉(zhuǎn)移方程f[i] = max(g[i - 1] - nums[i -1], f[i - 1])，g[i] = max(f[i - 1] - nums[i -1], g[i - 1])。最終答案為max(f[n], g[n])。

7.12題目 2544. 交替數(shù)字和

【模擬】從最低位開始，通過n mod 10得到個位數(shù)，再把n除以10，重復前面過程，得到十位數(shù)、百位數(shù)，最后得到最高位，如果它取負號則把答案取反。

7.13題目?931. 下降路徑最小和

【DP】定義f[r] [c]為從matrix[r] [c]出發(fā)向上走到第一排的路徑最小和，f[r] [c] = min(f[r - 1] [c - 1], f[r- 1] [c], f[r- 1] [c + 1]) + matrix[r] [c]。修改邊界+類似01背包空間優(yōu)化→f[c + 1] = min(f[c], f[c+1], f[c+2]) + matrix[r] [c]。

7.14題目?979. 在二叉樹中分配硬幣

【DFS】定義d = coins - nodes，計數(shù)器的值就是|d|，d = d_left + d_right + node.val - 1。

7.15題目?18. 四數(shù)之和

【排序 + 雙指針】設(shè)s = nums[a] + nums[a + 1] + nums[a + 2] + nums[a + 3]，如果s > target，由于數(shù)組已經(jīng)排序，后面無論怎么選，選出四個數(shù)的和不會比s還小，后面不會找到等于target的四數(shù)之和了，只要s>target，break；設(shè)s = nums[a] + nums[n - 3] + nums[n - 2] + nums[n - 1]。如果s0且nums[a] = nums[a - 1]，那么nums[a]和后面數(shù)字相加的結(jié)果，必然在之前算出過，所以無需執(zhí)行后續(xù)代碼，直接continue外才能循環(huán)。對于nums[b]的枚舉，也有類似優(yōu)化：設(shè)s = nums[a] + nums[b] + nums[b - 1] + nums[b + 2]。如果s >target，由于數(shù)組已經(jīng)排序，選出的四個數(shù)的和不會比s還小，后面不會找到等于target的四叔之和了，所以s>target，直接break。設(shè)s = nums[a] + nums[b] + nums[n - 1]+ nums[n -1 ]，如果sa+1且nums[b] = nums[b - 1]那么nums[b]和后面數(shù)字相加的結(jié)果，必然在之前算出過，所以無需執(zhí)行后續(xù)代碼，直接contitnue，注意這里b>a+1的判斷是必須的，如果不判斷，示例2這樣的數(shù)據(jù)會直接continue。

7.16題目?834. 樹中距離之和

【換根DP】從0出發(fā)DFS，累加0到每個點的距離，得到ans[0]。DFS的同時，計算出每棵子樹的大小size[i]。然后從0出發(fā)再次DFS，設(shè)y是x的兒子，那么：ans[y] = ans[x] + n-2.size[y]。利用該公式可以自頂向下遞推得到每個αns[i]。

7.17題目?415. 字符串相加

【雙指針】我們用兩個指針i和j分別指向兩個字符串的末尾，從末尾開始逐位相加。每次取出對應(yīng)位的數(shù)字a和b，計算它們的和a+b+c，其中c表示上一次相加的進位，最后將a+b+c的個位數(shù)添加到追加到答案字符串的末尾，然后將α+b+c的十位數(shù)作為進位c的值，循環(huán)此過程直至兩個字符串的指針都已經(jīng)指向了字符串的開頭并且進位c的值為0。最后將答案字符串反轉(zhuǎn)并返回即可。

7.18題目 1851. 包含每個查詢的最小區(qū)間

【排序 + 離線查詢 + 優(yōu)先隊列（小根堆）】注意到查詢的順序不會影響答案，并且涉及到的區(qū)間也不會發(fā)生變化，因此考慮將所有查詢按照從小到大的順序排序，同時將所有區(qū)間按照左斷電從小到大的順序進行排序。用一個優(yōu)先隊列pq維護當前所有的區(qū)間，隊列每個元素是一個二元組(v,r)，表示區(qū)間長度為v，右端點為r的區(qū)間。初始時，優(yōu)先隊列為空，另外定義一個指針i指向當前遍歷到的區(qū)間，初始時i=0，按照從小到大的順序一次遍歷每個查詢(i,j)，并進行如下操作：如果指針i尚未遍歷完所有區(qū)間，并且當前遍歷到的區(qū)間[a,b]的左端點小于等于x，那么將該區(qū)間加入優(yōu)先隊列中，并將指針i后裔一位，循環(huán)此過程；如果優(yōu)先隊列不為空，且對頂元素區(qū)間右端點小于x，將對頂元素彈出，循環(huán)此過程；如果優(yōu)先隊列不為空，對頂元素就是包含x的最小區(qū)間，將其長度v加入答案數(shù)組ans中。

7.19題目?874. 模擬行走機器人

【哈希表 + 模擬】定義一個長度為5的方向數(shù)組dirs=[0,1,0,-1,0]，數(shù)組中2個相鄰元素表示一個方向，即(dirs[0], dirs[1])表示向北，而(dirs[1], dirs[2])表示向東。用哈希表s存所有障礙物的下標，另外用兩個變量x和y表示機器人當前所在坐標，k表示機器人當前的方向，答案變量ans表示機器人距離遠點的最大歐式距離的平方，接下來遍歷commands的每個元素c，c=-1則左轉(zhuǎn)90°即k = (k + 3) mod 4；c= -1表示機器人向右轉(zhuǎn)90°，k = (k + 1) mod 4; 否則向前移動c個單位長度。

7.20題目?918. 環(huán)形子數(shù)組的最大和

【DP】計算最大非空子數(shù)組和macS以及最小子數(shù)組和mimS。（注意最小子數(shù)組可以是空的，但不能是整個數(shù)組。）如果mimS=sum（nums），返?macS，否則返?max{macS，sum（nums）-mimS}。

7.21題目 1499. 滿足不等式的最大值

【單調(diào)隊列】yi+yj=|xi-xj| = yi+yj+xj-xi = (xi+yj) + (yi-xi)，枚舉j，問題變成計算yi-xi的最大值，其中i<j且xi>xj-k。用單調(diào)隊列優(yōu)化：單調(diào)隊列存儲二元組(xi,yi-xi)，首先把隊首的超出范圍的數(shù)據(jù)出隊，即xi<xj-k的數(shù)據(jù)，然后把(xj,yj-xj)入隊，入隊前如果發(fā)現(xiàn)yj-xj不低于隊尾的數(shù)據(jù)，直接彈出隊尾，這樣維護后，單調(diào)隊列的yi-xi從隊首到隊尾是嚴格遞減的，yi-xi的最大值即為隊首的最大值。

7.22題目 860. 檸檬水找零

【分類討論】5美元能用于10美元和20美元的詔令，所以5比10更通用，所以優(yōu)先用10，用完了再用5。設(shè)當前有five張5美元鈔票，ten張10美元鈔票。設(shè)b=bills[i]分類討論。

7.23題目 42. 接雨水

【DP】定義left[i]表示下標i位置及其左邊的最高柱子的高度，定義right[i]表示下標i位置及其右邊最高柱子的高度，下標i位置能接的雨水量是min(left[i], right[i]) - height[i]，遍歷數(shù)組，計算出Left[i]和right[i]，最后答案為Σmin(left[i], right[i]) - height[i]。

7.24題目 771. 寶石與石頭

【數(shù)組】用一個數(shù)組s記錄所有寶石的類型，遍歷所有石頭統(tǒng)計答案。

7.25題目 2208. 將數(shù)組和減半的最少操作次數(shù)

【優(yōu)先隊列（大根堆）】每次取數(shù)組當前最大值進行減半，減半后的數(shù)重新放回大根堆里。

7.26題目 2569. 更新數(shù)組后處理求和查詢

【Lazy 線段樹】假設(shè)nums1中總共有c個1，那么操作2相當于把nums2的元素和增加了c·p。所以只需要維護nums1中1的個數(shù)。如何實現(xiàn)操作1？用Lazy線段樹維護區(qū)間內(nèi)1的個數(shù)cnt，以及整個區(qū)間是否需要反轉(zhuǎn)的Lazy標記p。

7.27題目 2500. 刪除每行中的最大值

【排序】每一次操作是從每一行刪除最大值，然后取最大值加到答案中，因此可以先對每一行進行排序，接下來遍歷每一列取每一列的最大值，然后加到答案中。

7.28題目 2050. 并行課程 III

【拓撲排序 + DP】定義f[i]為完成第i門課需要花費的最少月份數(shù)，根據(jù)題意，只有當i的所有先修課都完成時，才能開始學習第i門課，并且可以立即開始，所以f[i] = time[i] + max(f[j])，j是i的先修課。由于題目保證圖是一個有向無環(huán)圖，所以一定存在拓撲序，可以在計算拓撲序的同時計算狀態(tài)轉(zhuǎn)移。設(shè)當前節(jié)點為x，可以在計算出f[x]后，更新y的所有秀安修課耗時的最大值，x是y的先修課，答案是所有f[i]的最大值。

7.29題目 141. 環(huán)形鏈表

【快慢指針】定義快慢指針fast和slow，初始時均指向head，快指針每次走兩步，慢指針每次走一步，不斷循環(huán)，當快慢指針相遇時說明鏈表存在環(huán)。

7.30題目 142. 環(huán)形鏈表 II

【快慢指針】先用快慢指針判斷鏈表是否有環(huán)，如果有環(huán)，再定義一個答案指針ans指向鏈表頭部，讓ans和慢指針一起走，每次走一步，直到ans和慢指針相遇，相遇的節(jié)點為環(huán)的入口節(jié)點。

7.31題目 143. 重排鏈表

【快慢指針 + 反轉(zhuǎn)鏈表 + 合并鏈表】先用快慢指針找到鏈表的中點，然后將鏈表后半部分反轉(zhuǎn)，最后將左右兩個鏈表合并。