114 Gas Station 加油站

沿着一条圆形路线有 n 个加油站。你会得到两个整数阵列的gas和cost，其中：

• gas[i] 是第 i 个站点的 gas 量。
• cost[i] 是从第 i 个加油站到第 （i + 1） 个加油站所需的汽油量。（最后一个站连接到第一个站）

您有一辆可以储存无限量汽油的汽车，但您在其中一个加油站以空油箱开始旅程。
返回起始加油站的索引，以便您可以按顺时针方向绕电路行驶一次。如果不可能，则返回 -1。
可以保证最多存在一个解决方案。

示例1：
Input: gas = [1,2,3,4], cost = [2,2,4,1]
Output: 3
说明：从第 3 站（索引 3）开始，加注 4 个单位的汽油。您的水箱 = 0 + 4 = 4
前往 0 号站。您的水箱 = 4 - 1 + 1 = 3
前往 1 号站。您的水箱 = 3 - 2 + 2 = 3
前往 2 号站。您的水箱 = 3 - 2 + 3 = 4
前往 3 号站。您的水箱 = 2 - 4 + 4 = 2示例2：
gas = [1,2,3], cost = [2,3,2]
Output: -1
说明：您不能从 0 或 1 号站开始，因为没有足够的汽油前往下一个站。
如果您从工号 2 开始，您可以移动到工号 0，然后移动到工号 1。
在站点 1，您的水箱 = 0 + 3 - 2 + 1 - 2 = 0。
您被困在第 1 站，因此无法绕着电路行驶。

解题1： 贪婪

这里用diff数组来存储油的加入和消耗之差，来判断是否可以从该位置出发。

class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:# 首先要保证汽油之和要大于消耗if sum(gas) < sum(cost):return -1total = 0res = 0for i in range(len(gas)):total += (gas[i] - cost[i])if total < 0:total = 0res = i + 1return res

时间复杂度: $O(n)$
空间复杂度: $O(1)$

115 Hand of Straights 顺子之手

您将得到一个整数数组hand和一个整数 groupSize，其中 hand [i] 是写在第i张卡片上的值。
您需要将卡片重新排列成组，以便每个组的卡片数量为 groupSize，并且卡片值连续增加 1。
如果可以通过这种方式重新排列卡片，则返回 true ，否则返回 false 。

示例1：
Input: hand = [1,2,4,2,3,5,3,4], groupSize = 4
Output: true
说明：卡片可以重新排列为 [1,2,3,4] 和 [2,3,4,5] 。示例2：
Input: hand = [1,2,3,3,4,5,6,7], groupSize = 4
Output: false
解释：我们能得到的最接近的是 [1,2,3,4] 和 [3,5,6,7] ，但第二组中的牌不是连续的。

解题1： 堆

我们首先用HashMap来存储每个数字的个数，每使用一个就把其对应的个数减一。同时用MinHeap来弹出最小值，同时当某个数在HashMap中的个数减少为0的时候，也将该数从最小堆中弹出。

class Solution:def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:# 首先判断是否可以整除groupSizeif len(hand) % groupSize:return Falsecount = {}for n in hand:count[n] = 1 + count.get(n, 0)minH = list(count.keys())heapq.heapify(minH)while minH:first = minH[0]for i in range(first, first + groupSize):if i not in count:return Falsecount[i] -= 1if count[i] == 0:if i != minH[0]:return Falseheapq.heappop(minH)return True

时间复杂度: $O(n)$
空间复杂度: $O(1)$

116 Merge Triplets to Form Target 将 Triplelet 合并到 Form Target

你得到一个整数 triplelets 的二维数组，其中三元组[i] = [ai， bi， ci] 表示第 i 个三元组。你还会得到一个整数数组 target = [x， y， z]，这是我们想要得到的三元组。
要获取 target，您可以对 triplelets 零次或多次应用以下作用：
选择两个不同的三元组 triplets[i] 和 triplets[j]，并将 triplets[j] 更新为 [max(ai, aj), max(bi, bj), max(ci, cj)] 。
例如，如果三元组[i] = [1， 3， 1] 且三元组[j] = [2， 1， 2]，则三元组[j]将更新为 [max(1, 2), max(3, 1), max(1, 2)] = [2, 3, 2] 。
如果可以将 target 作为三元组的元素获取，则返回 true，否则返回 false。

示例1：
Input: triplets = [[1,2,3],[7,1,1]], target = [7,2,3]
Output: true
解释：选择第一个和第二个三元组，将第二个三元组更新为 [max（1， 7）， max（2， 1）， max（3， 1）] = [7， 2， 3]。示例2：
Input: triplets = [[2,5,6],[1,4,4],[5,7,5]], target = [5,4,6]
Output: false
解释：

解题1： 贪婪

class Solution:def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:good = set()for t in triplets:if t[0] > target[0] or t[1] > target[1] or t[2] > target[2]:continuefor i, v in enumerate(t):if v == target[i]:good.add(i)return len(good) == 3

时间复杂度: $O(n^2)$
空间复杂度: $O(1)$

117 Partition Labels 分区标签

你被给了一个由小写英文字母组成的字符串 s 。
我们希望尽可能地将字符串分割成多个子字符串，同时确保每个字母最多只出现在一个子字符串中。
返回一个表示这些子字符串大小的整数列表，按其在字符串中出现的顺序排列。

示例1：
Input: s = "xyxxyzbzbbisl"
Output: [5, 5, 1, 1, 1]
解释：字符串可以被分割为 ["xyxxy", "zbzbb", "i", "s", "l"] 。示例2：
Input: s = "abcabc"
Output: [6]

解题1： 双指针（贪心）

这里设置一个HashMap来映射每个字母最后出现的位置索引。
size用来记录substring的长度，同时用来检查改位置的字母最后一次出现的索引是不是小于end，如果不是需要修改end的值。

class Solution:def partitionLabels(self, s: str) -> List[int]:lastIndex = {} # char -> last index in sfor i, c in enumerate(s):lastIndex[c] = ires = []size, end = 0, 0for i, c in enumerate(s):size += 1end = max(end, lastIndex[c])if i == end:res.append(size)size = 0return res

时间复杂度: $O(n)$
空间复杂度: $O(m)$
n 是字符串 s 的长度，而 m 是字符串 s 中唯一字符的数量。

118 Valid Parenthesis String 有效的括号字符串

您被给定一个字符串 s ，它只包含三种类型的字符： ‘(’ 、 ‘)’ 和 ‘*’ 。
返回 true 如果 s 有效，否则返回 false 。
一个字符串如果遵循以下所有规则，则是有效的：

• 每个左括号 ‘(’ 都必须有一个相应的右括号 ‘)’ 。
• 每个右括号 ‘)’ 都必须有一个对应的左括号 ‘(’ 。
• 左括号 ‘(’ 必须在相应的右括号 ‘)’ 之前。
• 一个 ‘*’ 可以被当作一个右括号 ‘)’ 字符或一个左括号 ‘(’ 字符，或者作为一个空字符串 “” 。

示例1：
Input: s = "((**)"
Output: true
解释：其中一个 '*' 可能是一个 ')' ，另一个可能是空字符串。示例2：
Input: s = "(((*)"
Output: false
说明：字符串无效，因为开头多了一个 '(' ，不管多出来的 '*' 。

解题1： 贪心算法

class Solution:def checkValidString(self, s: str) -> bool:leftMin, leftMax = 0, 0for c in s:if c == "(":leftMin, leftMax = leftMin + 1, leftMax + 1elif c == ")":leftMin, leftMax = leftMin - 1, leftMax - 1else:leftMin, leftMax = leftMin - 1, leftMax + 1if leftMax < 0:return Falseif leftMin < 0: # s = ( * ) (leftMin = 0return leftMin == 0

时间复杂度: $O(n)$
空间复杂度: $O(1)$

119 Insert Interval 插入间隔

您被给定一个非重叠区间数组 intervals ，其中 intervals[i] = [start_i, end_i] 表示 ith 区间的开始和结束时间。 intervals 最初按 start_i 升序排序。
您被赋予另一个区间 newInterval = [start, end] 。
将 newInterval 插入到 intervals 中，使得 intervals 仍然按 start_i 升序排列，并且 intervals 仍然没有重叠的区间。如果需要，可以合并重叠的区间。
返回 intervals 后添加 newInterval 。
注意：如果区间没有公共点，则它们是非重叠的。例如，[1,2] 和 [3,4] 是非重叠的，但 [1,2] 和 [2,3] 是重叠的。

示例1：
Input: intervals = [[1,3],[4,6]], newInterval = [2,5]
Output: [[1,6]]示例2：
Input: intervals = [[1,2],[3,5],[9,10]], newInterval = [6,7]
Output: [[1,2],[3,5],[6,7],[9,10]]

解题1： 贪心算法

class Solution:def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:res = []for i in range(len(intervals)):if newInterval[1] < intervals[i][0]:res.append(newInterval)return res + intervals[i:]elif newInterval[0] > intervals[i][1]:res.append(intervals[i])else:newInterval = [min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])]res.append(newInterval)return res

时间复杂度: $O(n)$
空间复杂度: $O(1)$

120 Merge Intervals 合并区间

给定一个数组 intervals ，其中 intervals[i] = [start_i, end_i] ，合并所有重叠的区间，并返回覆盖输入中所有区间的非重叠区间数组。
您可以将答案以任何顺序返回。
注意：如果区间没有公共点，则它们是非重叠的。例如， [1, 2] 和 [3, 4] 是非重叠的，但 [1, 2] 和 [2, 3] 是重叠的。

示例1：
Input: intervals = [[1,3],[1,5],[6,7]]
Output: [[1,5],[6,7]]示例2：
Input: intervals = [[1,2],[2,3]]
Output: [[1,3]]

解题1： 排序

class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:# O(nlogn) 首先需要从小到大进行排序intervals.sort(key = lambda i : i[0])output = [intervals[0]]for start, end in intervals[1:]:lastEnd = output[-1][1]# 判断是否有重叠if start <= lastEnd:output[-1][1] = max(lastEnd, end)else:output.append([start, end])return output

时间复杂度: $O(nlogn)$
空间复杂度: $O(n)$

121 Non-overlapping Intervals 非重叠区间

给定一个区间数组 intervals ，其中 intervals[i] = [start_i, end_i] ，返回你需要移除的最小区间数，以使得剩余的区间不重叠。
注意：即使有共同点，区间也不会重叠。例如， [1, 3] 和 [2, 4] 是重叠的，但 [1, 2] 和 [2, 3] 是非重叠的。

示例1：
Input: intervals = [[1,2],[2,4],[1,4]]
Output: 1
解释：移除[1,4]之后，其余的区间都是非重叠的。示例2：
Input: intervals = [[1,2],[2,4]]
Output: 0

解题1： 贪心（按起始时间排序）

class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:intervals.sort()res = 0prevEnd = intervals[0][1]for start, end in intervals[1:]:# 如果没有重叠if start >= prevEnd:prevEnd = endelse:res += 1prevEnd = min(end, prevEnd)return res

时间复杂度: $O(nlogn)$
空间复杂度: $O(1)或O(n)$，取决于排序算法。

122 Meeting Rooms II 会议室 II

给定一个包含会议时间间隔对象的数组，这些对象包括开始和结束时间，求在不发生任何冲突的情况下安排所有会议所需的最少天数。

示例1：
Input: intervals = [(0,40),(5,10),(15,20)]
Output: 2
解释：
day1: (0,40)
day2: (5,10),(15,20)示例2：
Input: intervals = [(4,9)]
Output: 1

解题1： 双指针

当我们进行遍历时，首先0开始，然后时5。当遍历到5的时候，发现0-30这个会议还没有结束。所以count+1。

当我们继续，到10的时候，一个会议结束，count-1。再继续，到15的时候，因为0-30这个还没有结束，所以count+1。

用双指针，每次比较start和end中的值，取小的那个，如果小的在start，那么count+1，否则count-1。
当都遇到10的时候，因为要一个会议结束，另一个才能开始。所以这里，end中的指针要+1，count要-1。

"""
Definition of Interval:
class Interval(object):def __init__(self, start, end):self.start = startself.end = end
"""class Solution:def minMeetingRooms(self, intervals: List[Interval]) -> int:start = sorted([i.start for i in intervals])end = sorted([i.end for i in intervals])res, count = 0, 0s, e = 0, 0# 只要遍历完satrt就可以停止while s < len(intervals):if start[s] < end[e]:s += 1count += 1else:e += 1count -= 1res = max(res, count)return res

时间复杂度: $O(nlogn)$
空间复杂度: $O(n)$

123 Rotate Image 旋转图片

给定一个整数矩阵 n x n ，将其顺时针旋转 90 度。
您必须在原地旋转矩阵。不要分配另一个二维矩阵进行旋转。

示例1：
Input: matrix = [[1,2],[3,4]
]Output: [[3,1],[4,2]
]

示例2：
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]
]
Output: [[7,4,1],[8,5,2],[9,6,3]
]

解题1： 旋转四格

从上图可以看出，一个n×n的矩阵，最外层旋转的次数不是n，而是n-1。

已经知道移动的步骤了，为了减少操作次数，我们可以先用一个临时变量来存储左上角的数，然后顺时针移动数字。

class Solution:def rotate(self, matrix: List[List[int]]) -> None:l, r = 0, len(matrix) - 1while l < r:for i in range(r - l):top, bottom = l, r# 保存左上角topLeft = matrix[top][l + i]# 左下移动到左上matrix[top][l + i] = matrix[bottom - i][l]# 右下到左下matrix[bottom - i][l] = matrix[bottom][r - i]# 右上到右下matrix[bottom][r - i] = matrix[top + i][r]# 左上到右上matrix[top + i][r] = topLeftr -= 1l += 1

时间复杂度: $O(n^2)$
空间复杂度: $O(1)$