蓝桥杯 每日2题 day5
碎碎念：哦哈呦，到第二天也是哦哈哟，，学前缀和差分学了半天！day6堂堂连载！
0.单词分析
14.单词分析 - 蓝桥云课 (lanqiao.cn)
关于这题就差在input前加一个sorted，记录一下下。接下来就是用字典把字母和出现次数绑定，然后用sorted的key lambda排序。感觉写过两次了不再赘述
1.棋盘
15.棋盘 - 蓝桥云课 (lanqiao.cn)
前缀和与差分
焦灼两天~！还是没写出来，，那个边界搞死人，，先差分再求前缀和！！真没招了半懂半不懂的
差分：在数据变化的第一个数+1，在数据变化的下一个-1
前缀和：想一下矩阵图
n,m = map(int, input().split())
lis = [[0]*(n+2) for _ in range(n+2)]
# 构建差分
for t in range(m):x1,y1,x2,y2 = map(int, input().split())lis[x1][y1] += 1lis[x1][y2+1] -= 1lis[x2+1][y1] -= 1lis[x2+1][y2+1] += 1
# 计算差分的前缀和，直接在原数组上计算
for i in range(1,n+1): # 注意边界，前缀和从1开始计算 [1-n]for j in range(1,n+1):lis[i][j] = (lis[i-1][j] + lis[i][j-1] - lis[i-1][j-1] + lis[i][j])%2
# 算一个矩形的加和，翻一次+1，结果为偶数则为白（0），为奇数就是黑（1）print(lis[i][j],end='')print()关于前缀和与差分学习了这篇文章：
Python数据结构与算法篇（二）-- 前缀和与差分数组_python 前缀和数组-CSDN博客
质量真的是高啊，，膜拜，，推荐大家去看
练习1 303. 区域和检索 - 数组不可变 - 力扣（LeetCode）
class NumArray:def __init__(self, nums: List[int]):self.myarray = [0]for i in range(len(nums)):self.myarray.append(self.myarray[i]+nums[i])def sumRange(self, left: int, right: int) -> int:return self.myarray[right+1]-self.myarray[left]练习2 304. 二维区域和检索 - 矩阵不可变 - 力扣（LeetCode）
对什么时候+1什么时候-1要注意：初始化时多建立一行一列是为了处理边界情况。计算矩形数字和时对引用的行和列要+1，是因为前缀和二维表比原始数据二维表多了一行一列，需要加上保证引用对应。
图是灵茶山大佬的。
class NumMatrix:def __init__(self, matrix: List[List[int]]):m, n = len(matrix), len(matrix[0])self.presum = [[0]*(n+1) for i in range(m+1)]for i in range(m):for j in range(n):self.presum[i+1][j+1] = self.presum[i+1][j] + self.presum[i][j+1] - self.presum[i][j] + matrix[i][j]def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:ans = self.presum[row2+1][col2+1] - self.presum[row2+1][col1] - self.presum[row1][col2+1] + self.presum[row1][col1]return ans练习3 1109. 航班预订统计 - 力扣（LeetCode）
差分与前缀和的部分
差分：
- 差分数组
d初始化为长度为n的全0数组，其中n是飞机的座位数。- 对于每一条预订信息
bookings[i]，在bookings[i][0] - 1的位置（注意要减1，因为数组是从0开始索引的）加上预订的座位数bookings[i][2]，在bookings[i][1]的位置减去预订的座位数。这样，d数组就表示了每一天座位数的变化量。- 为什么要这么做呢？因为对于每一段连续的预订，我们只需要在起始和结束位置进行标记，而不需要对中间的每一天都进行遍历。这样可以大大减少计算量。
前缀和：
- 计算出差分数组
d后，我们需要求出每一天结束时的实际座位数。这可以通过计算前缀和来实现。- 遍历
d数组，从第二个元素开始（索引为1），每一个元素都加上前一个元素的值。这样，d[i]就表示了第i天结束时的剩余座位数。边界的设置
在代码中，边界的设置主要体现在差分数组
d的初始化以及差分操作的细节上。
初始化：
d数组被初始化为长度为n的全0数组。这是因为一开始每个座位都是空的，所以初始剩余座位数都是0。差分操作：
- 在
bookings[i][0] - 1的位置加上预订的座位数时，没有特别的边界检查，因为题目保证bookings[i][0]是在有效范围内的（即1 <= bookings[i][0] <= n）。- 在
bookings[i][1]的位置减去预订的座位数时，有一个边界检查if bookings[i][1] < n:。这是因为如果bookings[i][1]等于n，实际上是不需要进行减法的，因为第n天之后没有更多的天了。bookings[i][1]的位置不需要再减1，是因为它代表的是预订的结束位置（座位号），而不是数组的索引。当我们在差分数组d中进行减法操作时，我们实际上是在标记结束位置之后的第一天，将预订的座位数减去。这样做是因为我们想要保持结束位置当天（即bookings[i][1]）的座位数不变，因为预订在当天结束时仍然有效。
class Solution:def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:lis = [0]*n for i in range(len(bookings)): # 计算差分数组lis[bookings[i][0]-1] += bookings[i][2] if bookings[i][1] < n: # 判断边界lis[bookings[i][1]] -= bookings[i][2]for i in range(1,n): # lis[0]是初始值lis[i] += lis[i-1]return lis