问题描述：【Sort】406. Queue Reconstruction by Height
解题思路：
这道题是假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对 (h, k) 表示，其中 h 是这个人的身高，k 是排在这个人前面且身高大于或等于 h 的人数。编写一个算法来重建这个队列。
这道题很明显先要进行排序，关键是按照 h 还是 k 来排序呢？
- 先考虑一种简单的情况：队列中没有身高相同的人，如 people = [[6,1], [7,0], [5,2]]，很容易看出按照身高 h 降序排列，而 k 表示的就是人所在队列的位置，即重构后的队列为 [[7,0], [6,1], [5,2]]。
- 再考虑可能有身高相同的情况，如 people = [[6,1], [7,0], [5,2], [7,1]]，我们按照上述思路先对身高 h 降序排列，相同的身高按照 k 进行升序排列（因为不难看出相同身高，k 小的肯定排在前面），得到 [[7,0], [7,1], [6,1], [5,2]]，还是按照上述思路，我们依次将 h 插入到 k 位置：7 插入到位置 0 得到 [[7,0]]；7 插入到位置 1 得到 [[7,0], [7,1]]；6 插入到位置 1 得到 [[7,0], [6,1], [7,1]]（可以发现 [6,1] 的插入不会对 [7,1] 造成影响，因为 6 本来就比 7 小，前面放一个小的数字不影响 [7,1] 中的 k 值）；5 插入到位置 2 即可得到重构后的队列为 [[7,0], [6,1], [5,2], [7,1]]（同理，5 的插入不会对后面的 6 和 7 的 k 造成影响）。
- 最后考虑例子中的 people = [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]，按照 h 升序 k 降序，得到 [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]，依次将 h 插入到 k 位置上，即可得到重构后的队列为 [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]，理由同上。
总之，一句话，就是先按照身高 h 降序排列，如果有相同身高，按照 k 值升序排列。然后，对于排列后的每一个 (hi, ki)，依次把 (hi, ki) 插入到 ki 位置上就是最后的答案。用 Python 可以一句代码实现排序任务：
people.sort(key=lambda x: (-x[0], x[1])) # 按照第一维降序，第一维相同按第二维升序
这是一种贪婪的策略，即先考虑高个子，身高相同的考虑位置在前的。时间复杂度来自于排序的开销 O(n*logn)。
Python3 实现：
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
people.sort(key=lambda x: (-x[0], x[1])) # 按照第一维降序，第一维相同按第二维升序
ans = []
for p in people:
ans.insert(p[1], p) # 将(hi,ki)插入到ki位置上
return ans
问题描述：【Greedy】763. Partition Labels
解题思路：
这道题是给一个字符串，把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。
这道题其实可以从给的例子中就能发现解题技巧。S = "ababcbacadefegdehijhklij" 最终划分成三段，"ababcbaca", "defegde", "hijhklij"，可以发现每个字母处于哪一段取决于它最后一个相同字母的位置。如字母 'a' 的最后一个字母在 S[8] 处，'e' 的最后一个字母在 S[15] 处等等。
- 因此，我们先对 S 进行遍历，得到每一个字母的最后一个位置，并把它保存到字典中。
- 然后，我们遍历 S 中的每一个字母。第一段 "ababcbaca"，保存 a 的最后一个位置 pos，b 和 c 的最后一个位置都没有超过 pos 且遍历到了 a 的最后一个位置 pos，那么就划分出了一个段；第二段 "defegde"，保存 d 的最后一个位置 pos，e 的最后一个位置超过了 d，就更新 pos 为 e 的最后一个位置；后面的 f、g 没有超过 pos 且遍历到 e 的最后一个位置，那么就划分出了一个段；第三段 "hijhklij"，保存 h 的最后一个位置 pos，i 的最后一个位置超过 pos，就更新 pos 为 i 的最后一个位置；j 的最后一个位置也超过 pos，就更新 pos 为 j 的最后一个位置；后面的 k、l 没有超过 pos 且遍历到了最后 j 的最后一个位置，那么就划分出了一个段。
这是一种贪婪的策略，每次考虑最后一个字符所在的位置。时间复杂度为 O(n)，空间复杂度为 O(26)，即保存 26 个字符所用的空间。
Python3 实现：
class Solution:
def partitionLabels(self, S: str) -> List[int]:
dic = dict()
for i in range(len(S)):
dic[S[i]] = i
ans = []
ch, pos, cnt = "", -1, 0
for i in range(len(S)):
cnt += 1
if ch != S[i] and dic[S[i]] > pos: # 更新最后一个字符的位置 pos
ch, pos = S[i], dic[S[i]]
if i == pos: # 遍历到最后一个字符，划分出一个段
ans.append(cnt)
ch, pos, cnt = "", -1, 0
return ans
问题描述：【Greedy】861. Score After Flipping Matrix
解题思路：
这道题是给一个 m*n 的01矩阵，通过多次翻转行或列（0变成1、1变成0），最后将该矩阵的每一行都按照二进制数来解释，矩阵的得分就是这些数字的总和，返回尽可能高的分数。
方法1（时间复杂度 O((mn)^2)）:
很明显，我们要获得尽可能高的分数，第一列要保证全 1。所以，先通过行变换把第一列为 0 的那一行进行翻转。因为保证了第一列全为 1，后面就不能进行行变换了，不然第一列有 1 又会变成 0，所以之后只能进行列变换。
对于第二列之后的每一列 j，有翻转 j 和不翻转 j 两种情况，分别计算两种情况下的分数，并更新最大分数。这样时间复杂度为 O((mn)^4)，由于 n <= 20，是可以 AC 的。
Python3 实现：
class Solution:
def matrixScore(self, A: List[List[int]]) -> int:
def calculate(): # 计算得分
score = 0
for p in range(m):
base = 1
for q in range(n-1, -1, -1):
score += A[p][q] * base
base *= 2
return score
m = len(A)
n = len(A[0])
for i in range(m): # 将第一列改为全1
if A[i][0] == 0:
for j in range(n):
if A[i][j] == 0: A[i][j] = 1
else: A[i][j] = 0
max_score = calculate() # 初始分数
for j in range(1, n): # 翻转第j列
for i in range(m):
if A[i][j] == 0: A[i][j] = 1
else: A[i][j] = 0
change_score = calculate() # 计算翻转第j列的得分
if change_score > max_score:
max_score = change_score
else: # 不翻转第j列，还原
for i in range(m):
if A[i][j] == 0: A[i][j] = 1
else: A[i][j] = 0
return max_score
方法2（时间复杂度 O(n^2)）:
实际上，我们对于第二列之后的每一列 j，没必要计算翻转 j 和不翻转 j 的得分，而是只需要统计第 j 列中 0 与 1 的个数即可。如果 0 的个数超过 1，就进行翻转，这样的话最后的分数肯定比不翻转要高。如果 0 和 1 的个数相同，那么翻不翻转得分是一样的（因为第 j 列中 1 对结果的贡献是 m*(2^(n-j-1))，翻转后 1 变成 0，但 0 也变成了 1，对结果的贡献还是那么多）。
这样，我们只需要统计第二列后的每一列 0 与 1 的个数，累加该列对总和的贡献 max(cnt0, cnt1)*(2^(n-j-1))，除了第一列其他列不用真正地翻转，时间复杂度就可以降为 O(mn)。
Python3 实现：
class Solution:
def matrixScore(self, A: List[List[int]]) -> int:
m = len(A)
n = len(A[0])
for i in range(m): # 将第一列改为全1
if A[i][0] == 0:
for j in range(n):
if A[i][j] == 0: A[i][j] = 1
else: A[i][j] = 0
score = m * (2 ** (n-1)) # 第一列对该位的贡献
for j in range(1, n): # 统计每一列0和1的个数
cnt = [0, 0]
for i in range(m):
if A[i][j] == 0: cnt[0] += 1
else: cnt[1] += 1
score += (max(cnt) * (2 ** (n - j - 1))) # 最多的0/1对该位的贡献
return score
问题描述：【Greedy、DP、DP2】1094. Car Pooling
解题思路：
拼车问题。给一个数组和容量，数组每一项包括人数、上车时间、下车时间，判断是否可以在不超过容量的情况下顺利接送所有乘客（乘客遵循先下后上的原则）。
方法1（Greedy，时间复杂度 O(n^2)）：
这道题有点像课程表安排，首先先按照上车时间对数组从小到大排序，并用一个变量 cur 记录当前车上的人数。然后对数组的每一项 trips[i]，依循先下后上原则，先判断 trips[i] 的上车时间是否大于等于之前项的下车时间，如果是，标记之前的项为已经结束，同时减少 cur；都判断完成后，再把 trips[i] 的人数加到 cur 上，并和 capacity 比较。
由于对于每一个 trips[i]，还要和前面的 i 项比较，这样时间复杂度为 O(n^2)。
Python3 实现：
class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
trips.sort(key=lambda x: x[1]) # 按照上车时间从小到大排序
end = [False] * len(trips) # 标记哪个时间段已经结束
cur = 0
for i in range(len(trips)):
for j in range(i): # 先下
if end[j] == False and trips[i][1] >= trips[j][2]: # 当前上车时间大于等于前面的下车时间
end[j] = True
cur -= trips[j][0] # 减去人数
cur += trips[i][0] # 后上
if cur > capacity:
return False
return True
print(Solution().carPooling([[8,2,3],[4,1,3],[1,3,6],[8,4,6],[4,4,8]], 12)) # False
方法2（DP，时间复杂度 O(n^2)）：
因为发现 0 <= trips[i][1] < trips[i][2] <= 1000，所以可以使用动态规划的思想，建立一个 dp[1001] 的数组，其中 dp[i] 表示 i 时刻车上的人数。因此我们对于每一个时间段 [begin, end]，让 dp[i] 累加每个时刻上的人数。最后，dp 中的最大值不大于 capacity，即满足。
因为对于每一项 [cnt, begin, end]，dp[i] 都要累加 [begin, cnt] 中每一时刻的 cnt，如果 begin 和 end 间隔很大，这样时间复杂度最坏还是 O(n^2)。
Python3 实现：
class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
dp = [0] * 1001
for (cnt, begin, end) in trips:
for i in range(begin, end):
dp[i] += cnt
return max(dp) <= capacity
方法3（DP2，时间复杂度 O(n)）：
当然方法 2 可以进一步优化，我们可以对每个区间的两个端点标记，左边端点使用加法（表示有人上车），右边端点使用减法（表示有人下车）。最后遍历标记后的数组，遍历的过程中累加标记值，如果超过了capacity，那么就表示不满足。
Python3 实现：
class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
dp = [0] * 1001
for (cnt, begin, end) in trips:
dp[begin] += cnt
dp[end] -= cnt
cur = 0
for t in dp:
cur += t
if cur > capacity:
return False
return True
拓展：
如果起始时刻和终止时刻无限大，大到无法用上述方法 2 和方法 3 中的 dp 存储，怎么做呢？实际上，这种情况就和 Leetcode 253：Meeting Rooms II（超详细的解法！！！） 类似了，仿照其直接可以写出如下代码：
class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
time_people = sorted(x for (n, start, end) in trips for x in [[start, n], [end, -n]]) # 上车时间为正人数，下车时间为负人数，然后从小到大排序
cnt = 0
for tp in time_people:
cnt += tp[1]
if cnt > capacity:
return False
return True
网友评论