Leetcode【78、90、289、621、718】
Leetcode【78、90、289、621、718】
问题描述：【BFS、Bit】78. Subsets
解题思路：
方法1（回溯法）：
这道题是给一个数组，返回所有的子集。
首先可以想到用回溯法 BFS 求解，如 nums = [0,2,5]，使用回溯法可以依次得到 [0]、[0,2]、[0,2,5]、[0,5]、[2]、[2,5]、[5]
注意：（1）把空集 [] 也加进去；（2）集合的子集是组合数，因此可以把 nums 的索引也当作参数传入，防止出现排列数。
Python3 实现：
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
def search(d, ind, path): # d为深度，ind保证组合数，path保存结果
for i in range(ind, N):
path.append(nums[i])
ans.append(path[:]) # 防止传引用调用
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) 个，由此可以想到每一个子集对应一个 len(nums) 位的二进制数。如果二进制数某一位为 '1'，那么就代表该位置有 nums[i]。如 nums = [0,2,5]，len(nums) = 3，有 2^3 = 8 个子集，那么二进制数 000、001、010、011、100、101、110、111 分别对应 []、[5]、[2]、[2,5]、[0]、[0,5]、[0,2]、[0,2,5]。
Python3 实现：
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
解题思路：
这道题是给一个数组，数组中的数字可能有重复，返回所有可能的子集。
相比于上面的 Leetcode 78，这道题只是数字可能有重复而已，我们同样可以使用回溯法 BFS 和位操作 Bit 来求解。
先把结果保存在集合中，这样如果后面有重复的项，判断是否在集合中的时间复杂度为 O(1)。还要注意，要先对 nums 进行排序。为什么呢？
比如 nums = [2,1,2]，无论采取 BFS 还是 Bit 方法，会出现 [2,1] 和 [1,2] 两种情况，集合视它们是不同的。但是如果先排序，nums = [1,2,2]，只会有 [1,2] 这种情况出现，因此先要对 nums 进行排序。
最后还要注意一点：因为 list 是不可哈希的类型（unhashable type），如果进行诸如 list in set 的判断会出错。可以将每次的结果转化为 tuple，因为 tuple 是可以哈希的，因此就不会报错。
除此之外，求解过程和 Leetcode 78 几乎相同。
Python3 实现（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)) # 将结果转化为可哈希的tuple再存入集合中
if d < N:
search(d+1, i+1, path)
path.pop()
N = len(nums)
nums.sort() # 先对nums排序，因为有重复的数字
ans = set()
ans.add(tuple([]))
search(1, 0, [])
return list(ans)Python3 实现（Bit）：
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
N = len(nums)
nums.sort() # 先对nums排序，因为有重复的数字
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)) # 将结果转化为可哈希的tuple再存入集合中
return list(ans)问题描述：【Array】289. Game of Life
解题思路：
这道题是给一个 01 矩阵，每个位置看成一个细胞。1 为活细胞，0 为死细胞。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞遵循四条生存定律，求根据当前 01 矩阵状态计算下一个 01 矩阵状态。
这道题需要注意的有两点：（1）所有细胞改变改变是同时发生的；（2）要在原矩阵上修改，不能创建额外的空间。
第一点好办，对于每个位置的活细胞或死细胞，统计周围八个位置的活细胞的数量，按照生存定律改变状态。
但是考虑到第二点，只能在原数组上修改状态，如果 1 修改成 0 或者 0 改成 1，就会影响后面的细胞的判断。所以就不能将 1 先改成 0，也不能将 0 先改成 1。我们可以先把 1 改成 -1，后面的细胞每次判断加一个 abs，-1 的绝对值还是 1，就不影响；而对于 0 而言，因为不可能改成 -0，所以先随便改一个，如 float("inf")（反正不是 1 和 -1 就行，不然影响后面判断）。等所有的细胞状态改完之后，再遍历一遍矩阵，把所有的 -1 改成 0，把所有的 float("inf") 改成 1 即可。
Python3 实现：
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 # 活细胞的数量
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 任务分配，给一个数组 tasks 存储 A 到 Z，表示不同的任务，任务可以以不同顺序进行。每个任务可以在一个时间间隔中完成。对于一个时间间隔，CPU 可以执行一个任务或者是闲置。但是，两个同样的任务之间至少需要有 n 个冷却时间，也就是说假如 A 执行后，那么未来 n 个时间间隔内，A 是不允许再执行的。
这道题我刚开始的想法也是用贪婪算法求解。
- 先对 tasks 按任务出现的次数从大到小排序。假设有 k 个任务都是出现了最多的次数，为 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"。
- 对于次数小于 x 的任务，假设为 C，可以发现，如果有空闲单元，这样的插入也是满足要求的。如 task = ['A','A','A','B','B','B','C', 'D']，如果 n=2，那么 ans = 2*3+2 = 8，即这样安排 "ABCABDAB"。
- 但是，如果任务多的话，有些任务就插不进去了，如 task = ['A','A','A','B','B','B','C','D','E']，如果 n=2，那么按照公式 ans = 8，但实际上 'E' 无法插进去，答案应该是 9。因此，卡到了这一步，没有思路嘤嘤嘤...
实际上，再想一下，答案就出来了。即我们可以在原来的基础上这样插 "ABC(E)ABDAB"，可以发现，按照公式计算出来的 ans = 8 小于数组长度（9），我们直接返回数组长度即可。再举一个例子，tasks = ['A','A','A','B','B','B','C', 'C', 'D', 'D', 'E']，可以这样插 "ABCDEABCDAB"，ans = 8 < len(tasks) = 11，直接返回数组长度 11 即可。
这是一种贪心的策略，即 A 一定能够符合距离下一个 A 的冷却时间为 n，那么跟在 A 后面的也一定符合。只要保证 A 符合就行了，其他任务的的符合要求都可以由 A 的符合推导出来。
时间复杂度为 O(N)，即统计各个任务次数的花销；空间复杂度为 O(26)，保存最多 26 个任务出现的次数。
Python3 实现：
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
dic = collections.Counter(tasks)
x = max(dic.values()) # 出现最多次数
k = 0 # 出现最多次数的任务有几个
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
解题思路：
这道题是给两个数组，求最长公共子数组。
同最长公共字串问题 常考的经典算法--最长公共子序列（LCS）与最长公共子串(DP)，用动态规划求解即可。
Python3 实现：
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_