碎碎念:哦哈呦,到第二天也是哦哈哟,,学前缀和差分学了半天!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] += 1
lis[x1][y2+1] -= 1
lis[x2+1][y1] -= 1
lis[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