問題描述：【BFS排嫌、Bit】78. Subsets
解題思路：
方法1（回溯法）：
這道題是給一個數(shù)組，返回所有的子集缰犁。
首先可以想到用回溯法 BFS 求解淳地，如 nums = [0,2,5]怖糊，使用回溯法可以依次得到 [0]、[0,2]薇芝、[0,2,5]蓬抄、[0,5]、[2]夯到、[2,5]、[5]
注意：（1）把空集 [] 也加進去饮亏；（2）集合的子集是組合數(shù)耍贾，因此可以把 nums 的索引也當(dāng)作參數(shù)傳入，防止出現(xiàn)排列數(shù)路幸。
Python3 實現(xiàn)：
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
def search(d, ind, path): # d為深度荐开，ind保證組合數(shù)，path保存結(jié)果
for i in range(ind, N):
path.append(nums[i])
ans.append(path[:]) # 防止傳引用調(diào)用
if d < N:
search(d+1, i+1, path)
path.pop() # 回溯一步
ans = [[]]
N = len(nums)
search(1, 0, [])
return ans
方法2（位操作）：
因為長度為 len(nums) 的子集有 2^len(nums) 個简肴，由此可以想到每一個子集對應(yīng)一個 len(nums) 位的二進制數(shù)晃听。如果二進制數(shù)某一位為 '1'，那么就代表該位置有 nums[i]砰识。如 nums = [0,2,5]能扒，len(nums) = 3，有 2^3 = 8 個子集辫狼，那么二進制數(shù) 000初斑、001、010膨处、011见秤、100、101真椿、110鹃答、111 分別對應(yīng) []、[5]突硝、[2]测摔、[2,5]、[0]狞换、[0,5]避咆、[0,2]、[0,2,5]修噪。
Python3 實現(xiàn)：
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
N = len(nums)
ans = []
for i in range(1 << len(nums)):
bin_s = bin(i)[2:].zfill(N) # 前面補0到長度N
path = []
for i in range(len(bin_s)):
if bin_s[i] == '1': # 如果某位為'1'
path.append(nums[i])
ans.append(path)
return ans
問題描述：【BFS查库、Bit】90. Subsets II
解題思路：
這道題是給一個數(shù)組，數(shù)組中的數(shù)字可能有重復(fù)黄琼，返回所有可能的子集樊销。
相比于上面的 Leetcode 78整慎，這道題只是數(shù)字可能有重復(fù)而已，我們同樣可以使用回溯法 BFS 和位操作 Bit 來求解围苫。
先把結(jié)果保存在集合中裤园，這樣如果后面有重復(fù)的項，判斷是否在集合中的時間復(fù)雜度為 O(1)剂府。還要注意拧揽，要先對 nums 進行排序。為什么呢腺占？
比如 nums = [2,1,2]淤袜，無論采取 BFS 還是 Bit 方法，會出現(xiàn) [2,1] 和 [1,2] 兩種情況衰伯，集合視它們是不同的铡羡。但是如果先排序，nums = [1,2,2]意鲸，只會有 [1,2] 這種情況出現(xiàn)烦周，因此先要對 nums 進行排序。
最后還要注意一點：因為 list 是不可哈希的類型（unhashable type）怎顾，如果進行諸如 list in set 的判斷會出錯读慎。可以將每次的結(jié)果轉(zhuǎn)化為 tuple杆勇，因為 tuple 是可以哈希的贪壳，因此就不會報錯。
除此之外蚜退，求解過程和 Leetcode 78 幾乎相同闰靴。
Python3 實現(xiàn)（BFS）：
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
def search(d, ind, path):
for i in range(ind, N):
path.append(nums[i])
if tuple(path) not in ans:
ans.add(tuple(path)) # 將結(jié)果轉(zhuǎn)化為可哈希的tuple再存入集合中
if d < N:
search(d+1, i+1, path)
path.pop()
N = len(nums)
nums.sort() # 先對nums排序，因為有重復(fù)的數(shù)字
ans = set()
ans.add(tuple([]))
search(1, 0, [])
return list(ans)
Python3 實現(xiàn)（Bit）：
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
N = len(nums)
nums.sort() # 先對nums排序钻注，因為有重復(fù)的數(shù)字
ans = []
for i in range(1 << len(nums)):
bin_s = bin(i)[2:].zfill(N)
path = []
for i in range(len(bin_s)):
if bin_s[i] == '1':
path.append(nums[i])
if tuple(path) not in ans:
ans.append(tuple(path)) # 將結(jié)果轉(zhuǎn)化為可哈希的tuple再存入集合中
return list(ans)
問題描述：【Array】289. Game of Life
解題思路：
這道題是給一個 01 矩陣蚂且，每個位置看成一個細胞。1 為活細胞幅恋，0 為死細胞杏死。每個細胞與其八個相鄰位置（水平，垂直捆交，對角線）的細胞遵循四條生存定律淑翼，求根據(jù)當(dāng)前 01 矩陣狀態(tài)計算下一個 01 矩陣狀態(tài)。
這道題需要注意的有兩點：（1）所有細胞改變改變是同時發(fā)生的品追；（2）要在原矩陣上修改玄括，不能創(chuàng)建額外的空間。
第一點好辦肉瓦，對于每個位置的活細胞或死細胞遭京，統(tǒng)計周圍八個位置的活細胞的數(shù)量胃惜，按照生存定律改變狀態(tài)。
但是考慮到第二點哪雕，只能在原數(shù)組上修改狀態(tài)船殉，如果 1 修改成 0 或者 0 改成 1，就會影響后面的細胞的判斷斯嚎。所以就不能將 1 先改成 0利虫，也不能將 0 先改成 1。我們可以先把 1 改成 -1堡僻，后面的細胞每次判斷加一個 abs列吼，-1 的絕對值還是 1，就不影響苦始；而對于 0 而言，因為不可能改成 -0慌申，所以先隨便改一個陌选，如 float("inf")（反正不是 1 和 -1 就行，不然影響后面判斷）蹄溉。等所有的細胞狀態(tài)改完之后咨油，再遍歷一遍矩陣，把所有的 -1 改成 0柒爵，把所有的 float("inf") 改成 1 即可役电。
Python3 實現(xiàn)：
class Solution:
def gameOfLife(self, board: List[List[int]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
pos = [[-1,0], [1,0], [0,-1], [0,1], [-1,-1], [-1,1], [1,-1], [1,1]] # 周圍8個位置
m = len(board)
n = len(board[0])
for i in range(m):
for j in range(n):
live = 0 # 活細胞的數(shù)量
if board[i][j] == 0:
for p in pos:
if 0 <= i+p[0] < m and 0 <= j+p[1] < n and abs(board[i+p[0]][j+p[1]]) == 1:
live += 1
if live == 3:
board[i][j] = float("inf") # 先把0改成float("inf")
elif board[i][j] == 1:
for p in pos:
if 0 <= i+p[0] < m and 0 <= j+p[1] < n and abs(board[i+p[0]][j+p[1]]) == 1:
live += 1
if live < 2 or live > 3:
board[i][j] = -1 # 先把1改成-1
for i in range(m): # 把所有float("inf")改成1，把所有-1改成0
for j in range(n):
if board[i][j] == float("inf"):
board[i][j] = 1
elif board[i][j] == -1:
board[i][j] = 0
問題描述：【Greedy】621. Task Scheduler
解題思路：
這道題是模擬 CPU 任務(wù)分配棉胀，給一個數(shù)組 tasks 存儲 A 到 Z法瑟，表示不同的任務(wù)，任務(wù)可以以不同順序進行唁奢。每個任務(wù)可以在一個時間間隔中完成霎挟。對于一個時間間隔，CPU 可以執(zhí)行一個任務(wù)或者是閑置麻掸。但是酥夭，兩個同樣的任務(wù)之間至少需要有 n 個冷卻時間，也就是說假如 A 執(zhí)行后脊奋，那么未來 n 個時間間隔內(nèi)熬北，A 是不允許再執(zhí)行的。
這道題我剛開始的想法也是用貪婪算法求解诚隙。
- 先對 tasks 按任務(wù)出現(xiàn)的次數(shù)從大到小排序讶隐。假設(shè)有 k 個任務(wù)都是出現(xiàn)了最多的次數(shù)，為 x 次最楷，那么時間至少為 ans = (x-1)*(n+1)+k整份。如 task = ['A','A','A','B','B','B']待错，如果 n=2，那么 ans = 2*3+2 = 8烈评，即這樣安排 "AB(idle)AB(idle)AB"火俄。
- 對于次數(shù)小于 x 的任務(wù)，假設(shè)為 C讲冠，可以發(fā)現(xiàn)瓜客，如果有空閑單元，這樣的插入也是滿足要求的竿开。如 task = ['A','A','A','B','B','B','C', 'D']谱仪，如果 n=2，那么 ans = 2*3+2 = 8否彩，即這樣安排 "ABCABDAB"疯攒。
- 但是，如果任務(wù)多的話列荔，有些任務(wù)就插不進去了敬尺，如 task = ['A','A','A','B','B','B','C','D','E']，如果 n=2贴浙，那么按照公式 ans = 8砂吞，但實際上 'E' 無法插進去，答案應(yīng)該是 9崎溃。因此蜻直，卡到了這一步，沒有思路嚶嚶嚶...
實際上袁串，再想一下概而，答案就出來了。即我們可以在原來的基礎(chǔ)上這樣插 "ABC(E)ABDAB"般婆，可以發(fā)現(xiàn)到腥，按照公式計算出來的 ans = 8 小于數(shù)組長度（9），我們直接返回數(shù)組長度即可蔚袍。再舉一個例子乡范，tasks = ['A','A','A','B','B','B','C', 'C', 'D', 'D', 'E']，可以這樣插 "ABCDEABCDAB"啤咽，ans = 8 < len(tasks) = 11晋辆，直接返回數(shù)組長度 11 即可。
這是一種貪心的策略宇整，即 A 一定能夠符合距離下一個 A 的冷卻時間為 n瓶佳，那么跟在 A 后面的也一定符合。只要保證 A 符合就行了鳞青，其他任務(wù)的的符合要求都可以由 A 的符合推導(dǎo)出來霸饲。
時間復(fù)雜度為 O(N)为朋，即統(tǒng)計各個任務(wù)次數(shù)的花銷；空間復(fù)雜度為 O(26)厚脉，保存最多 26 個任務(wù)出現(xiàn)的次數(shù)。
Python3 實現(xiàn)：
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
dic = collections.Counter(tasks)
x = max(dic.values()) # 出現(xiàn)最多次數(shù)
k = 0 # 出現(xiàn)最多次數(shù)的任務(wù)有幾個
for v in dic.values():
if v == x:
k += 1
return max((n+1)*(x-1)+k, len(tasks)) # 按照公式算出來的值可能比tasks長度小
問題描述：【DP】718. Maximum Length of Repeated Subarray
解題思路：
這道題是給兩個數(shù)組傻工，求最長公共子數(shù)組。
同最長公共字串問題 逞炱ィ考的經(jīng)典算法--最長公共子序列（LCS）與最長公共子串(DP)，用動態(tài)規(guī)劃求解即可泄伪。
Python3 實現(xiàn)：
class Solution:
def findLength(self, A: List[int], B: List[int]) -> int:
dp = [[0] * (len(B) + 1) for _ in range(len(A) + 1)]
max_ = 0
for i in range(1, len(A) + 1):
for j in range(1, len(B) + 1):
if A[i-1] == B[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
max_ = max(max_, dp[i][j])
return max_
