本文主要是介绍leetcode-2846、560、239、76，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
2846. 边权重均等查询 - 力扣（LeetCode）
解题思路
LCA看不懂
算法详解之最近公共祖先(LCA) - hulean - 博客园 (cnblogs.com)
leetcode-hot100
和为K的子数组
题目链接
560. 和为 K 的子数组 - 力扣（LeetCode）
解题思路
1、暴力破解
class Solution:def subarraySum(self, nums: List[int], k: int) -> int:n = len(nums)result = 0for i in range(n):for j in range(i, n):temp = nums[i:j+1]#print(temp)sum_ = sum(temp)if sum_ == k:result += 1return result超出时间限制
加入改进通过使用一个数组记录前n个数的和，降低时间复杂度。
滑动窗口最大值
题目链接
239. 滑动窗口最大值 - 力扣（LeetCode）
暴力破解
超出时间限制
class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:left = 0right = k - 1n = len(nums)result = []while right < n:minstr = nums[left:right+ 1]result.append(max(minstr))right += 1left += 1return result优先队列：
对于最大值，我们可以想到一种非常合适的数据结构，那就是优先队列，其中的大根堆可以帮助我们实时维护一系列元素的最大值。
对于本题而言，初始时，我们将数组nums的前k个元素放入优先队列中。每当我们向右移动窗口时，我们就把一个新的元素放入优先队列中。此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中，在这种情况下，这个值在数组nums中的位置出现在滑动窗口左边界的左侧1.因此，当我们后续继续向右移动窗口时，这个值就永远不可能出现在滑动窗口中，我们可以将其永久的从优先队列中移除。
我们不断移除堆定的元素，直到其确实出现在滑动窗口中。此时，堆顶元素就是滑动窗口中的最大值。为了方便判断堆顶元素与滑动窗口的位置关系，我们可以在优先队列中存储二元组，表示元素num在数组中的下标位index。
class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:n = len(nums)#注意python默认的优先队列时小根堆q = [(-nums[i], i) for i in range(k)]heapq.heapify(q)ans = [-q[0][0]]for i in range(k,n):heapq.heappush(q,(-nums[i],i))while q[0][1] <= i - k:heapq.heappop(q)ans.append(-q[0][0])return ans这篇关于leetcode-2846、560、239、76的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
