分割數(shù)組中數(shù)字的數(shù)位

【模擬】翻轉(zhuǎn)新插入的數(shù)字，用到額外空間。

【模擬】可以做到 O(1) 額外空間（忽略切片開銷，其實(shí)可以手動反轉(zhuǎn)）。

從一個范圍內(nèi)選擇最多整數(shù) I

【貪心】優(yōu)先選小的。把list轉(zhuǎn)成哈希表，判斷數(shù)是否在banned里能做到O(1)。

兩個線段獲得的最多獎品

【雙指針】用雙指針處理第二條線段，強(qiáng)制讓線段右端點(diǎn)恰好落在獎品上，設(shè)第二條線段右端點(diǎn)在p[right]時(shí)，左端點(diǎn)最遠(yuǎn)覆蓋了p[left]，需要知道在p[left]左側(cè)第一條線段最多可以覆蓋多少獎品。一條線段時(shí)，線段右端點(diǎn)在p[right]時(shí)，左端點(diǎn)最遠(yuǎn)覆蓋了p[left]，覆蓋獎品個數(shù)為right - left + 1。用一個數(shù)組pre[right + 1]記錄右端點(diǎn)不超過p[right]時(shí)最多可以覆蓋多少個獎品，初始pre[0] = 0，有pre[right + 1] = max(pre[right], right - left + 1)，第二條線段最多可以覆蓋right - left + 1 + pre[left]塊獎牌。(p指prizePositions)

二進(jìn)制矩陣中翻轉(zhuǎn)最多一次使路徑不連通

【DFS】把所有從起點(diǎn)到終點(diǎn)走通的路徑做標(biāo)記，可以得到一個”輪廓”，如果可以使矩陣不連通，翻轉(zhuǎn)一個格子必然使得整個輪廓都不連通。如何找到輪廓——考慮找到下輪廓和上輪廓，從起點(diǎn)出發(fā)優(yōu)先向下走，其次向右走，得到下輪廓；向右走，其次向下走，得到上輪廓。如果兩個輪廓有交集（除了起點(diǎn)終點(diǎn)），那么翻轉(zhuǎn)交集中任意一個格子，都可以使矩陣不連通。代碼中可以直接把下輪廓的格子值改成0，如果第二次從(0,0)出發(fā)無法到達(dá)重點(diǎn)說明可以使得矩陣不連通。說明得到下輪廓后，只需看(0,0)和重點(diǎn)間是否有通路。