leetcode–差分数组

全栈程序员站长

发布于 2022-06-27 09:45:51

4750

发布于 2022-06-27 09:45:51

文章被收录于专栏：全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

0. 差分数组的概念：

常用于某个区间值都需加/减去a的问题。

1. 1094拼车

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        max_val = 0
        for i in range(len(trips)):
            max_val = max(max_val, trips[i][2])
        diff = [0]*(max_val+2)
        for i in range(len(trips)):
            diff[trips[i][1]] += trips[i][0]
            diff[trips[i][2]] -= trips[i][0]
        sum_val = 0   
        flag = True 
        for i in range(len(diff)):
            sum_val +=diff[i]
            if sum_val > capacity:
                flag = False
                break 
        return flag

2. 1109航班预定统计

class Solution:
    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:
        diff = [0]*(n+2)
        res = [0]*n
        sum_val = 0 
        for i in range(len(bookings)):
            diff[bookings[i][0]] += bookings[i][2]
            diff[bookings[i][1]+1] -= bookings[i][2]
        for i in range(1,n+1):
            sum_val+= diff[i]
            res[i-1] = sum_val
        return res

1674. 使数组互补的最少操作数

class Solution:
    def minMoves(self, nums: List[int], limit: int) -> int:
        diff = [0 for i in range(2*limit +2)]
        n = len(nums)
        for i in range(n//2):
            A = nums[i]
            B = nums[n-1-i]
            l = 2
            r = 2*limit
            diff [l] +=2
            diff[r+1] -=2
            l = 1 + min(A,B)
            r = limit + max(A,B)
            diff [l] -=1
            diff [r+1] +=1
            diff [A+B] -=1
            diff[A+B+1] +=1
        print(diff)    
        res = n    
        sum_val = 0
        for j in range(2,2+limit+1):
            sum_val += diff[j]
            res = min(res, sum_val)
        return res