python3-算法刷题-数组-记录累加和差值-更新中

参考：https://labuladong.github.io/algo/2/20/25/

累加和

适合原数组不变的情况下，频繁查询某段的和。如果不记录累加和，则需要每次都循环，太耗时了。

【简单】303. 区域和检索 - 数组不可变

https://leetcode.cn/problems/range-sum-query-immutable/

思路：设立新数组，计算累加和，避免多次调用sumRange循环计算。

class NumArray:
    def __init__(self, nums: List[int]):
        self.preSum = [0]  # 第一个位置置0
        for i in range(len(nums)):
            self.preSum.append(self.preSum[i] + nums[i])

    def sumRange(self, left: int, right: int) -> int: # 闭区间
        return self.preSum[right + 1] - self.preSum[left]
1
2
3
4
5
6
7
8

【中等】304. 二维区域和检索 - 矩阵不可变

https://leetcode.cn/problems/range-sum-query-2d-immutable/

思路：每个矩形区域的面积可以通过三个矩形的加减得出。假设整个区域的和为S，那么 S = A + B + C - D

因此用一个矩阵preSum记录每个矩形的累加和。

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        r = len(matrix)
        c = len(matrix[0])
        # preSum[i][j]是左上角(0, 0)到右下角(i-1, j-1)的和
        self.preSum = [[0 for j in range(c + 1)] for i in range(r + 1)]
        for i in range(1, r+1):
            for j in range(1, c + 1):
                self.preSum[i][j] = self.preSum[i-1][j] + self.preSum[i][j-1] + matrix[i-1][j-1] - self.preSum[i-1][j-1]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return self.preSum[row2+1][col2+1] - self.preSum[row2+1][col1] - self.preSum[row1][col2+1] \
                + self.preSum[row1][col1]
1
2
3
4
5
6
7
8
9
10
11
12
13

差分和

适合对原数组某段频繁增减的情况。比如对nums[1:4]逐个+1，再对nums[2:8]逐个-3。每次都循环肯定耗时，所以准备一个数组，其中diff[i]=nums[i]-nums[i-1]。此时再对整段进行加减时，举例：nums[2:8]（闭区间）整段+1，则对于i=2，它与前一个的差值增加了1；对于i=8，它与后一个位置的差值减少了1；对于2-8中间的，因为整体增减，实际差值不会变化。这样的差分数组也可以很快恢复为原值。

实现：

class Difference:
    def __init__(self, nums:list):
        self.diff = [nums[0]]
        for i in range(1, len(nums)):
            self.diff.append(nums[i] - nums[i - 1])
            
    # 闭区间。val是实数
    def increment(self, i:int, j:int, val:int):
        self.diff[i] += val
        if (j + 1) < len(self.diff):
            self.diff[j + 1] -= val
            
    def result(self) -> list:
        ans = [self.diff[0]]
        for i in range(1, len(self.diff)):
            ans.append(ans[i-1] + self.diff[i])
        return ans

a = [1,4,5,2,6]
d = Difference(a)
d.increment(1, 2, -1)
print(d.result()) # [1, 3, 4, 2, 6]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

【中等】370. 区间加法

https://leetcode.cn/problems/range-addition/
假设你有一个长度为 n 的数组，初始情况下所有的数字均为 0，你将会被给出 k​​​​​​​ 个更新的操作。
其中，每个操作会被表示为一个三元组：[startIndex, endIndex, inc]，你需要将子数组 A[startIndex … endIndex]（包括 startIndex 和 endIndex）增加 inc。请你返回 k 次操作后的数组。
示例:
输入: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
输出: [-2,0,3,5,3]

思路：直接改上面的函数。

class Solution:
    def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
        # 初始化数组
        diff = [0] * length
        for u in updates:
        	# 更新值
            diff[u[0]] += u[2]
            if u[1] + 1 < length:
                diff[u[1] + 1] -= u[2]
        # 恢复原数组
        ans = [diff[0]]
        for i in range(1, length):
            ans.append(ans[i-1] + diff[i])
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14

【中等】1109. 航班预订统计

https://leetcode.cn/problems/corporate-flight-bookings
这里有 n 个航班，它们分别从 1 到 n 进行编号。
有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seats[i] 个座位。请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

思路：跟370. 区间加法完全一样！！！！！代码不写了。

【中等】1094. 拼车

https://leetcode.cn/problems/car-pooling
车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）
给定整数 capacity 和一个数组 trips , trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。
当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。

示例 1：
输入：trips = [[2,1,5],[3,3,7]], capacity = 4
输出：false
示例 2：
输入：trips = [[2,1,5],[3,3,7]], capacity = 5
输出：true

思路：还是基本复用代码啊。不一样的就是：toi那里是下车，所以那里是不需要加值的，要提前处理

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        # 初始化数组
        diff = [0] * 1001
        # length记录边界值，即最大里程
        length = 0
        for u in trips:
        	# 更新值
            diff[u[1]] += u[0]
            diff[u[2]] -= u[0]
            if u[2] > length: length = u[2]
        # 恢复原数组
        if diff[0] > capacity: return False
        # 不要数组了，就要一个变量记录即可
        ans = diff[0]
        for i in range(1, length+1):
            if ans + diff[i] > capacity: return False
            ans += diff[i]
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19