927，三等分
核心方法：贪心
class Solution:
def threeEqualParts(self, arr: List[int]) -> List[int]:
IMP = [-1, -1]
# 能够等分需要保证1的数量能被3整除
S = sum(arr)
if S % 3:
return IMP
# 还需要保证每个区间内1的数量相等
T = S / 3
if T == 0:
# 如果区间内没有1，说明arr中没有1，只有0，那么就可以随便分了
return [0, len(arr)-1]
# 记录每个区间的边界，共有三个区间，6个边界
breaks = list()
su = 0
for i, v in enumerate(arr):
if v:
su += v
if su in {1, T+1, 2*T+1}:
breaks.append(i)
if su in {T, 2*T, 3*T}:
breaks.append(i)
i1, j1, i2, j2, i3, j3 = breaks
# 需要保证边界都为1的三个区间是一摸一样的，否则不存在等分的情况
if not (arr[i1: j1+1] == arr[i2: j2+1] == arr[i3: j3+1]):
return IMP
# 检查后缀0
x = i2 - j1 - 1 # 区间1和区间2之间的0
y = i3 - j2 - 1 # 区间2和区间3之间的0
z = len(arr) - j3 - 1 # 区间3后面的后缀0
# 需要保证区间1和区间2之间的0的数量和区间2和区间3之间0的数量要大于等于区间3后面的0的数量
# 如果x比小z，x还面临着被拆分为区间1和区间2，每个区间内1后面0的个数不一样，一定不能三等分
if x < z or y < z:
return IMP
# 说明区间1，区间2的后缀0数量和区间3点的必须相等，所以边界需要加上这个数量
j1 += z
j2 += z
return [j1, j2+1]55，跳跃游戏，中等
核心方法：贪心
遍历到每个位置，去检查当前位置加上能够跳跃的步数，也就是维护最远可以达到的位置，是否能够达到数组的末尾。如果能到达就返回True，所有位置全部遍历完毕后，就返回False
时间复杂度：O(n)
空间复杂度：O(1)
class Solution:
def canJump(self, nums: List[int]) -> bool:
n, rightmost = len(nums), 0
for i in range(n):
# 维护最远距离，当前遍历位置不能超过最远距离
if i <= rightmost:
rightmost = max(rightmost, nums[i]+i)
if rightmost >= n-1:
return True
return False48，旋转图像，中等
核心方法：找规律
对于矩阵中第 i 行的第 j 个元素，在旋转后，出现在倒数第 i 列的第 j 个位置，也就是matrix[r][c] -> matrix[c][n-r-1]。需要一个额外的数组来存储转换后的结果
时间复杂度：$O(n^2)$
空间复杂度：$O(n^2)$
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
new = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
new[j][n-1-i] = matrix[i][j]
matrix[:] = new核心方法：直接使用位置替换
根据上面的推导公式，可以验证，以下四个点之间的位置轮转是交替的。
matrix[i][j] -> matrix[j][n-i-1] -> matrix[n-i-1][n-j-1] -> matrix[n-j-1][i] -> matrix[i][j]
对于遍历的位置，如果n是偶数，那么需要取到n // 2；如果n是偶数，那么需要取到(n+1) // 2
时间复杂度：$O(n^2)$
空间复杂度：O(1)
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
for i in range(n//2):
for j in range((n+1) // 2):
matrix[i][j], matrix[n-j-1][i], matrix[n - i - 1][n - j - 1], matrix[j][n-i-1] \
= matrix[n-j-1][i], matrix[n - i - 1][n - j - 1], matrix[j][n-i-1], matrix[i][j]核心方法：直接翻转
使用平轴翻转，matrix[r][c] = matrix[n-r-1][c]，再使用matrix[r][c] = matrix[c][r]，将这两个式子联立就得到了最上面公式
时间复杂度：O(n^2)
空间复杂度：O(1)
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
# 水平翻转，注意i，j的边界
for i in range(n//2):
for j in range(n):
matrix[n-i-1][j], matrix[i][j] = matrix[i][j], matrix[n-i-1][j]
# 主对角线翻转，注意i，j的边界
for i in range(n):
for j in range(i):
matrix[j][i], matrix[i][j] = matrix[i][j], matrix[j][i]621，任务调度器，中等
核心方法：模拟
如果当前有多种任务不在冷却中，我们应该选择剩余执行任务次数最多的那个任务，将每种任务的剩余执行次数尽可能平均，使得CPU处理待命状态的时间尽可能少。
因此我们可以使用二元组
我们用
剪枝：
- 时间复杂度：O(∣tasks∣⋅∣Σ∣)，其中 ∣Σ∣ 是数组 task 中出现任务的种类，在本题中任务用大写字母表示，因此 ∣Σ∣ 不会超过 26。
- 空间复杂度：O(∣Σ∣)。我们需要使用哈希表统计每种任务出现的次数，以及使用数组 nextValid 和 test 帮助我们进行遍历得到结果，这些数据结构的空间复杂度均为 O(∣Σ∣)
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
# 统计每个任务的个数
freq = collections.Counter(tasks)
m = len(freq) # 任务类型总数
nextValid = [1] * m # 初始化每个任务的最早执行时间
rest = list(freq.values()) # 每个任务的剩余次数
time = 0 # 初始化起始时间
for i in range(len(tasks)):
time += 1
# 获取剩余任务中最早可以执行的执行时间
minNextValid = min(nextValid[j] for j in range(m) if rest[j] > 0)
# 更新time为所有nextValid的最大值，起到剪枝的作用
time = max(time, minNextValid)
best = -1
# 执行剩余次数最大的任务
for j in range(m):
if rest[j] and nextValid[j] <= time:
# 保证剩余次数大于零，且下一个最早执行时间要小于time
# 这里同样也保证了，上一次已经执行过的任务不会再执行了，因为其最早执行时间一定比当前time大
if best == -1 or rest[j] > rest[best]:
# 这里取剩余次数大的索引
best = j
# 这里表示当前执行best索引对应的任务，更新其下一次时间，并且剩余数量减1
nextValid[best] = time + n + 1
rest[best] -= 1
return time构造：
- 我们首先考虑所有任务种类中执行次数最多的那一种，记它为 A，的执行次数为 maxExec。
- 我们使用一个宽为 n+1 的矩阵可视化地展现执行 A 的时间点。其中任务以行优先的顺序执行，没有任务的格子对应 CPU 的待命状态。由于冷却时间为 n，因此我们将所有的 A 排布在矩阵的第一列，可以保证满足题目要求，并且容易看出这是可以使得总时间最小的排布方法，对应的总时间为：(maxExec-1)(n+1)+1
- 如果需要执行 maxExec 次的任务的数量为
$maxCount$ ，那么类似地可以得到对应的总时间为：$(maxExec-1)(n+1)+maxCount$，$|\textit{task}|$ 任务总数。 - 如果我们没有填「超出」了 n+1 列，那么图中存在 0 个或多个位置没有放入任务，由于位置数量为
$(maxExec−1)(n+1)+maxCount$ ，因此有：$|\textit{task}| < (\textit{maxExec} - 1)(n + 1) + \textit{maxCount}$ - 如果我们填「超出」了 n+1 列，那么同理有：$|\textit{task}| > (\textit{maxExec} - 1)(n + 1) + \textit{maxCount}$
时间复杂度：O(∣task∣+∣Σ∣)，其中 ∣Σ∣ 是数组 task 中出现任务的种类，在本题中任务用大写字母表示，因此 ∣Σ∣ 不会超过 26。
空间复杂度：O(∣Σ∣)。
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
freq = collections.Counter(tasks)
# 最多的执行次数
maxExec = max(freq.values())
# 具有最多执行次数的任务数量
maxCount = sum(1 for v in freq.values() if v == maxExec)
return max((maxExec - 1) * (n + 1) + maxCount, len(tasks))406，根据身高重建队列，中等
核心方法：从低到高排序
一个重要的观点就是，第
具体做法：首先将people数组按照身高生序，人数降序进行排序；然后每次获取一个人，并同时计算其前面应该预留的位置的数量。然后遍历结果列表，从第一个空位开始向后找，直到找到对应着当前人位置的空位将他放下，然后可以直接break终止内层循环。
时间复杂度：O(n^2)
空间复杂度：O(logn)，排序使用的栈空间。
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
# 首先对数组进行排序，按照h_i升序，k_i降序的标准
people.sort(key=lambda x: (x[0], -x[1]))
n = len(people)
# 初始化结果列表
ans = [[] for _ in range(n)]
for person in people:
# 每次获取一个人，在第一个空位置开始的第k_i + 1个空位置放入这个人
space = person[1] + 1
for i in range(n):
if not ans[i]:
# 从第一个空位置开始，数到第space个空位置
# 将space每次减1，等于0时就可以放入
space -= 1
if space == 0:
ans[i] = person
break
return ans核心方法：从高到低
也可以将每个人按照身高从大到小进行排序，处理身高相同的人使用的方法类似，即：按照
我们可以发现，后面的人既然不会对第
时间复杂度：O(n^2)
空间复杂度：O(logn)，排序使用的栈空间。
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
# 首先对数组进行排序，按照h_i升序，k_i降序的标准
people.sort(key=lambda x: (-x[0], x[1]))
n = len(people)
# 初始化结果列表
ans = list()
for person in people:
ans[person[1]:person[1]] = [person]
return ans990，等式方程的可满足性，中等
核心方法：并查集
所有包含等号的式子中涉及的变量都是相等，所以可以将所有等式中变量作为一个集合。首先遍历所有的等式，构造并查集。同一个等式中的两个变量属于同一个连通分量，因此将两个变量进行合并。
然后遍历所有的不等式。同一个不等式中的两个变量不能属于同一个连通分量，因此对两个变量分别查找其所在的连通分量，如果两个变量在同一个连通分量中，则产生矛盾，返回 false；如果遍历完所有的不等式没有发现矛盾，则返回 true。
具体实现方面，使用一个数组 parent 存储每个变量的连通分量信息，其中的每个元素表示当前变量所在的连通分量的父节点信息，如果父节点是自身，说明该变量为所在的连通分量的根节点。一开始所有变量的父节点都是它们自身。对于合并操作，我们将第一个变量的根节点的父节点指向第二个变量的根节点；对于查找操作，我们沿着当前变量的父节点一路向上查找，直到找到根节点。
注意这里可以简单的理解为：根节点，也就是第一个等式中的第一个变量，其索引对应的值将会被修改到所有与第一个变量相等的其他变量（当然这是来自所有等式的）索引对应的值上。
- 时间复杂度；$O(n+ClogC)$，其中 n 是 equations 中的方程数量，C 是变量的总数，在本题中变量都是小写字母，即
$C≤26$ 。上面的并查集代码中使用了路径压缩优化，对于每个方程的合并和查找的均摊时间复杂度都是$O(logC)$ 。由于需要遍历每个方程，因此总时间复杂度是$O(n+ClogC)$ 。 - 时间复杂度：O(n)，创建一个数组
parent存储每个变量的连通分量信息，由于变量都是小写字母，因此parent是长度为 C。
class Solution:
class unionFind():
def __init__(self):
self.parent = list(range(26))
def find(self, index):
if index == self.parent[index]:
return index
# 向上一个节点继续查找
self.parent[index] = self.find(self.parent[index])
return self.parent[index]
def union(self, index1, index2):
self.parent[self.find(index1)] = self.find(index2)
def equationsPossible(self, equations: List[str]) -> bool:
uf = Solution.unionFind()
for st in equations:
if st[1] == '=':
index1 = ord(st[0]) - ord('a')
index2 = ord(st[3]) - ord('a')
uf.union(index1, index2)
for st in equations:
if st[1] == '!':
index1 = ord(st[0]) - ord('a')
index2 = ord(st[3]) - ord('a')
if uf.find(index1) == uf.find(index2):
# 相当于找到两个index所在的集合中的根节点是否相等
return False
return True399，除法求值，中等
核心方法：并查集
这个题与上面的区别在于，在两个变量之间加入了一个倍数，这个倍数在建图的过程中会被转化为一个权值。具体表现在如下几个方面：
-
在初始化图时，同时初始化权值关系，每个位置上都为1
-
在进行查找时，当前变量对应的权值要向上连乘前面节点的权值，直到根节点，得到的结果就是当前变量指向根节点的权重
-
两个不同集合进行合并时，如果计算b到c的权重，已知a到b，和a到d，d到c的权值，那么 ab权值 * bc权值 = ad权值 * dc权值
-
计算queries中的变量比值时，只要两个变量同属于一个根节点，那么两个变量之间的比值就是其权重的比值；否则这个比值等于-1
-
时间复杂度：O((N+Q)logA)，
- 构建并查集 O(NlogA) ，这里 N 为输入方程 equations 的长度，每一次执行合并操作的时间复杂度是 O(logA)，这里 A 是 equations 里不同字符的个数；
- 查询并查集 O(QlogA)，这里 Q 为查询数组 queries 的长度，每一次查询时执行「路径压缩」的时间复杂度是 O(logA)。
-
空间复杂度：O(A)：创建字符与 id 的对应关系 hashMap 长度为 A，并查集底层使用的两个数组 parent 和 weight 存储每个变量的连通分量信息，parent 和 weight 的长度均为 A。
class Solution:
class UnionFind:
def __init__(self, equations):
# 初始化并查集和权重集
self.parent, self.weight = dict(), dict()
for nodes in equations:
for x in nodes:
if x not in self.parent:
self.parent[x], self.weight[x] = x, 1
def find(self, x):
if self.parent[x] != x:
parent = self.parent[x]
self.parent[x] = self.find(parent)
# 向上查找的时候，权重要进行连乘
self.weight[x] *= self.weight[parent]
return self.parent[x]
def union(self, x, y, value):
rootX = self.find(x)
rootY = self.find(y)
if rootX != rootY:
# 如果两个变量不在一个图中，则两个变量所在的集合要进行合并
self.parent[rootX] = rootY
# 如果计算b到c的权重，已知a到b，和a到d，d到c的权值
# 那么 ab权值*bc权值 = ad权值*dc权值
self.weight[rootX] = self.weight[y] * value / self.weight[x]
def isConnected(self, x, y):
if x in self.parent and y in self.parent:
rootX, rootY = self.find(x), self.find(y)
if rootX == rootY:
# 如果两个节点根节点相同，那么直接比较权重，就能得到结果
return self.weight[x] / self.weight[y]
# 否则返回-1
return -1
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
uf, n, ans = self.UnionFind(equations), len(equations), list()
# 将equations中的所有表达式进行合并
for i in range(n):
uf.union(equations[i][0], equations[i][1], values[i])
# 计算query中的结果
for x, y in queries:
ans.append(uf.isConnected(x, y))
return ans