LeetCode冲刺：Day40

发布于 2022-12-17  1065 次阅读

差分数组

类比导数的概念，对差分数组进行累加，可以得到原数组。当要对数组下标 l 到 r 的元素加 k 时，只要在差分数组下标 l 和 r + 1 上加 k ，而其他位不变。

当题目中遇到对某一区间进行多次统一操作时，要想到用差分数组解。

此外，应当注意到，有时我们在end的下一位置恢复差分值，而有时在end上恢复差分值，要注意判断。

1. 花期内花的数目

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

从题目设定来看，其实就是在花期开始时差分数组对应位置加一，结束时下一位置减一，累加即可得到每个时间的开花数目。

但应当注意到如果只是单纯从头到尾累加差分数组，那么其实跟纯粹的遍历每一个区间结点来获得开花数组是一样的，就失去了使用差分数组的意义。

除了花期的起止时间节点，其他的位置都是0，累加这些位置是没有意义的。所以应当在计算完差分数组后（实际上可以用字典，只记录有变化的时间节点，对persons进行排序，然后从小到大遍历其的过程中去累加差分数组的时间节点，得出答案。

代码

# 我的解法，超时
class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], persons: List[int]) -> List[int]:
        n = max(max(interval[1] for interval in flowers), max(persons)) + 2
        diff = [0 for i in range(n)]
        date = [0 for i in range(n)]
        ans = [0 for i in range(len(persons))]
        for interval in flowers:
            diff[interval[0]] += 1
            diff[interval[1] + 1] -= 1
        for i in range(1, n):
            date[i] = date[i - 1] + diff[i]
        for i in range(len(persons)):
            ans[i] = date[persons[i]]
        return ans
# 正解
class Solution:
    def fullBloomFlowers(self, flowers: List[List[int]], persons: List[int]) -> List[int]:
        # 用字典存储差分数组
        diff = defaultdict(int)
        for interval in flowers:
            diff[interval[0]] += 1
            diff[interval[1] + 1] -= 1
        # 获取排序后的时间节点
        times = sorted(diff.keys())
        i = sum = 0
        n = len(persons)
        ans = [0 for i in range(n)]
        # 将persons排序，遍历其值和对应下标，累加其之前的时间节点的差分
        for p, id in sorted(zip(persons, range(n))):
            while i < len(times) and times[i] <= p:
                sum += diff[times[i]]
                i += 1
            ans[id] = sum
        return ans

2. 航班预订统计

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

代码

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        diff = [0 for i in range(n + 2)]
        for book in bookings:
            diff[book[0]] += book[2]
            diff[book[1] + 1] -= book[2]
        ans = [0 for i in range(n)] # 也可以复用 diff 数组算前缀和然后返回
        sum = 0
        for i in range(n):
            sum += diff[i + 1]
            ans[i] = sum
        return ans

3. 得分最高的最小轮调

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

初看题目实在想不到这跟差分数组有什么关系。

从解法上来看，首先考虑暴力做法，枚举所有可能的k，范围是0到n-1，计算每个元素调整后的下标，是 (i - k + n) % n ，然后统计分数。显然会超时。

现在考虑另一种思路，不是从k出发，而是从每个元素出发。当初始元素和其下标固定时，我们应当可以算出当k在什么范围时，这一元素可以贡献1分。则用一个数组 points 记录每一个k可以获得的分数，那么可以在每个元素可贡献一分的范围上加一，这就转换成了一个差分数组可以解决的问题。在推导范围时还是需要一些灵感的。

代码

class Solution:
    def bestRotation(self, nums: List[int]) -> int:
        n = len(nums)
        points = [0 for i in range(n)]
        for i in range(n):
            points[(i + 1) % n] += 1
            points[(n + i - nums[i] + 1) % n] -= 1
        maxScore = points[0]
        k = 0
        for i in range(1, n):
            points[i] += points[i - 1]
            if points[i] > maxScore:
                maxScore = points[i]
                k = i
        return k

4. 拼车

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

比较标准的可以用差分数组解决的问题。要注意的有两点，一是差分值不是1而是当前乘客数量；二是乘客下车是即时发生的，因此不是在end的下一个位置才加回来，而是在end上就加回来。

代码

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        diff = defaultdict(int)
        for trip in trips:
            diff[trip[1]] -= trip[0]
            diff[trip[2]] += trip[0] # 注意这里不是下一个位置，在当前位置就直接下车了
        milestones = sorted(diff.keys())
        for milestone in milestones:
            capacity += diff[milestone]
            if capacity < 0: return False
        return True

5. 人口最多的年份

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

与拼车类似，也是在end上就加减差分值。同样利用到 defaultdict() 。

代码

class Solution:
    def maximumPopulation(self, logs: List[List[int]]) -> int:
        diff = defaultdict(int)
        for log in logs:
            diff[log[0]] += 1
            diff[log[1]] -= 1
        times = sorted(diff.keys())
        maxNum = ans = sum = 0
        for time in times:
            sum += diff[time]
            if sum > maxNum:
                maxNum = sum
                ans = time
        return ans

6. 省份数量

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

标准的并查集问题，代码中的 UF 是并查集类。

代码

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        uf = UF(n)
        for i in range(n):
            for j in range(n): 
                if isConnected[i][j] == 1:
                    uf.union(i, j)
        return uf.getCount()

7. 岛屿的最大面积

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

给 UF 类额外加了一个查询所在连通分量大小的方法。

代码

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m , n = len(grid), len(grid[0])
        ans = 0
        uf = UF(m * n)
        dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    for dir in dirs:
                        newI = i + dir[0]
                        newJ = j + dir[1]
                        if (newI >= 0 and newI < m) and (newJ >= 0 and newJ < n) and grid[newI][newJ] == 1:
                            uf.union(i * n + j, newI * n + newJ)
                    islandSize = uf.getSize(i * n + j)
                    ans = ans if ans > islandSize else islandSize
        return ans

8. 判断二分图

难度

  • Easy
  • Medium
  • Hard

完成情况

  • 独立完成
  • 参考思路
  • 参考答案

思路

开始有点误解，前面将每个顶点所连接的顶点集合并是没问题的，但判断是否构成二分图上，我一开始想从集合数量来判断，即集合数量减掉无连接顶点数目是否是偶数。

但实际上，只要在每次合并完顶点所连接的顶点集后，判断一下该顶点是否与顶点集在同一个并查集中即可。若在，返回否。最后能跑完循环的话，就返回是。

代码

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        uf = UF(n)
        for i in range(n):
            m = len(graph[i])
            if m == 0:
                continue
            for j in range(1, m):
                uf.union(graph[i][0], graph[i][j])
                if uf.isConnected(i, graph[i][0]):
                    return False
        return True