开源镜像网站开发,装修公司加盟十大品牌排行榜,邯郸信息港二手房出售,微信公众平台小程序怎么发布碎碎念#xff1a;哦哈呦#xff0c;到第二天也是哦哈哟#xff0c;#xff0c;学前缀和差分学了半天#xff01;day6堂堂连载#xff01;
0.单词分析
14.单词分析 - 蓝桥云课 (lanqiao.cn)
关于这题就差在input前加一个sorted#xff0c;记录一下下。接下来就是用字…碎碎念哦哈呦到第二天也是哦哈哟学前缀和差分学了半天day6堂堂连载
0.单词分析
14.单词分析 - 蓝桥云课 (lanqiao.cn)
关于这题就差在input前加一个sorted记录一下下。接下来就是用字典把字母和出现次数绑定然后用sorted的key lambda排序。感觉写过两次了不再赘述 1.棋盘
15.棋盘 - 蓝桥云课 (lanqiao.cn)
前缀和与差分
焦灼两天~还是没写出来那个边界搞死人先差分再求前缀和真没招了半懂半不懂的
差分在数据变化的第一个数1在数据变化的下一个-1
前缀和想一下矩阵图
n,m map(int, input().split())
lis [[0]*(n2) for _ in range(n2)]
# 构建差分
for t in range(m):x1,y1,x2,y2 map(int, input().split())lis[x1][y1] 1lis[x1][y21] - 1lis[x21][y1] - 1lis[x21][y21] 1
# 计算差分的前缀和直接在原数组上计算
for i in range(1,n1): # 注意边界前缀和从1开始计算 [1-n]for j in range(1,n1):lis[i][j] (lis[i-1][j] lis[i][j-1] - lis[i-1][j-1] lis[i][j])%2
# 算一个矩形的加和翻一次1结果为偶数则为白0为奇数就是黑1print(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[right1]-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]*(n1) for i in range(m1)]for i in range(m):for j in range(n):self.presum[i1][j1] self.presum[i1][j] self.presum[i][j1] - self.presum[i][j] matrix[i][j]def sumRegion(self, row1: int, col1: int, row2: int, col2: int) - int:ans self.presum[row21][col21] - self.presum[row21][col1] - self.presum[row1][col21] 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
