5972. 统计隐藏数组数目
?先求出来这条线，然后统一往上走直到upper，往下走直到lower。这个上下能波动几次，就是最终返回值
?其实就是在算这个曲线的高低差是多少
class Solution:
def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
value=0
min_val=0
max_val=0
for i in range(len(differences)):
value=value+differences[i]
min_val=min(min_val,value)
max_val=max(max_val,value)
if upper-lower-(max_val-min_val)+1>0:
return upper-lower-(max_val-min_val)+1
return 05955 摘水果
前缀和
class Solution(object):
def maxTotalFruits(self, fruits, startPos, k):
"""
:type fruits: List[List[int]]
:type startPos: int
:type k: int
:rtype: int
"""
n = len(fruits)
postions = [fruit[0] for fruit in fruits]
amounts = [fruit[1] for fruit in fruits]
# 前缀和便于统计不同区间范围总和
preSum = [0] * (n + 1)
for i in range(1, n + 1):
preSum[i] = preSum[i - 1] + amounts[i - 1]
ret = float('-inf')
for x in range(k + 1):
y = k - 2*x
# 往左 x 步， 往右 y 步
left, right = startPos - x, startPos + y
# 确定区间边界
leftIdx, rightIdx = bisect_left(postions, left), bisect_right(postions, right)
ret = max(ret, preSum[rightIdx] - preSum[leftIdx])
# 往左 y 步， 往右 x 步
left, right = startPos - y, startPos + x
leftIdx, rightIdx = bisect_left(postions, left), bisect_right(postions, right)
ret = max(ret, preSum[rightIdx] - preSum[leftIdx])
return ret
上面那个代码应该有点问题，在确定左边界之后，右边界应该是k-2*左边届。
724. 寻找数组的中心下标
2163?删除元素后和的最小差值
前缀和+后缀和+堆
class Solution:
def minimumDifference(self, nums: List[int]) -> int:
m = len(nums)
n = m // 3
min_pq = nums[m - n:]
heapify(min_pq)
suf_max = [0] * (m - n + 1) # 后缀最大和
suf_max[-1] = s = sum(min_pq)
for i in range(m - n - 1, n - 1, -1):
s += nums[i] - heappushpop(min_pq, nums[i])
suf_max[i] = s
max_pq = [-v for v in nums[:n]] # 所有元素取反当最大堆
heapify(max_pq)
pre_min = -sum(max_pq) # 前缀最小和
ans = pre_min - suf_max[n]
for i in range(n, m - n):
pre_min += nums[i] + heappushpop(max_pq, -nums[i])
ans = min(ans, pre_min - suf_max[i + 1])
return ans
作者：endlesscheng
链接：https://leetcode-cn.com/problems/minimum-difference-in-sums-after-removal-of-elements/solution/qian-zhui-zui-xiao-he-hou-zhui-zui-da-he-yz3d/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。class Solution {
public long minimumDifference(int[] nums) {
int n = nums.length / 3;
// min[i] 表示 nums[0] ~ nums[i] 个元素中选择 n 个元素和最小
long[] min = new long[3 * n];
// max[i] 表示 nums[i] ~ nums[3*n-1] 个元素中选择 n 个元素和最大
long[] max = new long[3 * n];
// 升序队列、 降序队列
PriorityQueue<Integer> asc = new PriorityQueue<>();
PriorityQueue<Integer> desc = new PriorityQueue<>((a, b) -> b - a);
long sum_first = 0, sum_second = 0;
for (int i = 0; i < 3 * n; i++) {
int l = i, r = 3 * n - 1 - i;
int left = nums[l], right = nums[r];
sum_first += left;
desc.add(left);
sum_second += right;
asc.add(right);
if (i >= n) {
sum_first -= desc.poll();
sum_second -= asc.poll();
}
min[l] = sum_first;
max[r] = sum_second;
}
// 遍历所有情况找到最小差值
long minAns = Long.MAX_VALUE;
for (int i = n - 1; i < 2 * n; i++) {
minAns = Math.min(minAns, min[i] - max[i + 1]);
}
return minAns;
}
}
?795. 区间子数组个数
?暴力双指针，超时
class Solution:
def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
#从i到j的子数组是否满足条件
#这么写有一个错误:当前index不满足时，还可以往后遍历
cnt=0
index1=0
while index1<len(nums):
index2=index1
max_val=nums[index2]
while max_val<left:
index2=index2+1
if index2 < len(nums):
max_val= max(max_val, nums[index2])
else:
break
while max_val>=left and max_val<=right:
cnt+=1
index2=index2+1
if index2 < len(nums):
max_val = max(max_val, nums[index2])
else:
break
index1+=1
return cnt前缀和mostk
class Solution:
def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
#前缀和,拆分成小于right的子数组和小于left的子数组
def mostk(k):
#以右端点为基准
ans=0
pre=0
for i in range(len(nums)):
if nums[i]<=k:
pre=pre+1
else:
pre=0
ans=ans+pre
return ans
return mostk(right)-mostk(left-1)1109. 航班预订统计
?
class Solution(object):
def corpFlightBookings(self, bookings, n):
"""
:type bookings: List[List[int]]
:type n: int
:rtype: List[int]
"""
#转化为上车下车问题
res=[0 for _ in range(n)]
for i in range(len(bookings)):
cur_first=bookings[i][0]
cur_last=bookings[i][1]
res[cur_first-1]+=bookings[i][2]
if cur_last<n:
res[cur_last]-=bookings[i][2]
for i in range(1,n):
res[i]=res[i-1]+res[i]
return res
# for i in range(len(bookings)):
# cur=bookings[i]
# cur_first=cur[0]
# cur_last=cur[1]
# for i in range(cur_first,cur_last+1):
# res[i-1]+=cur[2]
return res560. 和为 K 的子数组
?前缀和+哈希表
暴力
?前缀和
?前缀和+哈希表
注意：实现的时候要先判断差值是否在哈希表中?，然后再把当前值加入哈希表。先都加入哈希表，再判断差值是否在哈希表中，有case无法通过，如：。因为无法判断减去的值是不是当前自身值
class Solution(object):
def subarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
# 前缀和
presum = [0 for _ in range(len(nums))]
maps={}
presum[0] = nums[0]
maps[presum[0]]=1
for i in range(1, len(nums)):
presum[i] = presum[i - 1] + nums[i]
if presum[i] in maps:
maps[presum[i]]+=1
else:
maps[presum[i]]=1
count = 0
for i in range(len(nums)):
if presum[i]==k:
count+=1
if presum[i]-k in maps:
count+=maps[presum[i]-k]
return count
# count=0
# for i in range(len(nums)):
# for j in range(i+1,len(nums)+1):
# cur=nums[i:j]
# if sum(cur)==k:
# count+=1
return count