- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
题目地址:https://leetcode.com/problems/maximum-average-subarray-i/description/open in new window
Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.
Example 1:
Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75
Note:
1、 1<=k<=n<=30,000.;
2、 Elementsofthegivenarraywillbeintherange[-10,000,10,000].;
求给定数组中长度为k的切片的最大平均值。
首先需要区分两个概念:子串(子数组)和子序列。
这两个名词经常在题目中出现,非常有必要加以区分。
子串sub-string(子数组 sub-array)是连续的,而子序列 subsequence 可以不连续。
今天题目让求最大平均数,由于 k 是不变的,因此可以先求区间的最大和,然后再除以 k。
上周我在题解中已经说过,求区间的和可以用 preSum。preSum 方法还能快速计算指定区间段 i ~ j 的元素之和。它的计算方法是从左向右遍历数组,当遍历到数组的 i 位置时,preSum表示 i 位置左边的元素之和。
假设数组长度为 N,我们定义一个长度为 N+1 的 preSum 数组,preSum[i] 表示该元素左边所有元素之和(不包含当前元素)。然后遍历一次数组,累加区间 [0, i) 范围内的元素,可以得到 preSum 数组。代码如下:
N = len(nums)
preSum = range(N + 1)
for i in range(N):
preSum[i + 1] = preSum[i] + nums[i]
print(preSum)
1 2 3 4 5
利用preSum 数组,可以在 O(1)
的时间内快速求出 nums
任意区间 [i, j]
(两端都包含) 的各元素之和。
sum(i, j) = preSum[i + 1] - preSum[j]
对于本题,可以先遍历一次,求数组每个位置的 preSum,然后再遍历一次,求长度为 k 的每个区间的最大和。最终除以 k 得到最大平均数。
使用Python2 写的代码如下。
class Solution(object):
def findMaxAverage(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: float
"""
N = len(nums)
preSum = range(N + 1)
for i in range(N):
preSum[i + 1] = preSum[i] + nums[i]
largest = float("-inf")
for i in range(k - 1, N):
largest = max(preSum[i + 1] - preSum[i + 1 - k], res)
return largest / float(k)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
题目也可以抽象成长度固定为 k 的滑动窗口。当每次窗口右移的时候,需要把右边的新位置加到窗口中的和中,把左边被移除的位置从窗口的和中减掉。这样窗口里面所有元素的和是准确的,我们求出最大的和,最终除以 k 得到最大平均数。
这个方法只用遍历一次数组。
需要注意的是,需要根据 i 的位置,计算滑动窗口是否开始、是否要移除最左边元素:
使用Python2 写的代码如下。
class Solution(object):
def findMaxAverage(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: float
"""
sums = 0
largest = float('-inf')
for i, num in enumerate(nums):
sums += num
if i >= k:
sums -= nums[i - k]
if i >= k - 1:
largest = max(sums, largest)
return largest / float(k)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
今天的题目非常好,虽然是个 Easy 题目,但是让我们练习了 preSum 和 滑动窗口 两种方法的最基本用法。
任何组织或个人未经作者授权不得转发
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
考虑一下,我们在具有整数弧容量的有向网络中有一个非整数最大流。 是否有算法可以将这个流量转化为整数最大流量? 它的运行时间是多少? 这不是作业问题。 最佳答案 如果您正在寻找具有积分弧容量的最大 s-
我有一个可以接受 byte[] 的 WCF 服务。我正在使用 HttpClient 创建客户端并收到以下错误。我在网上看到你必须在服务器和客户端上设置 readerQuotas,但是如何在 HttpC
我有一个如下所示的数据框: df = pd.DataFrame({'A':[100,300,500,600], 'B':[100,200,300,400],
我开始使用 cocoapi评估使用 Object Detection API 训练的模型。在阅读了解释平均精度 (mAP) 和召回率的各种来源后,我对 cocoapi 中使用的“最大检测”参数感到困惑
这个问题已经有答案了: 已关闭10 年前。 Possible Duplicate: Size-limited queue that holds last N elements in Java Java
您好,我需要帮助制作以下算法: 假设一个二维空间域,具有 xmax、xmin、ymin、ymax,空间中有“n~10,000”个点。 浏览点位置列表。 当框中的点数达到最大数量(假设为 10 个)时,
我在 Android 应用程序中有一个类,它包含一个字节数组作为纹理的数据源。我使用帧缓冲区将一些东西渲染到该纹理上,然后在屏幕上渲染该纹理。这非常有效。 但是,我只能使用 151 个纹理来执行此操作
系统调用中可以传递多少个参数?我检查了内核文件 /asm/unistd.h,没有看到包含超过 4 个参数的系统调用。 最佳答案 这取决于您使用的架构。对于 i386,系统调用号旁边最多有 6 个参数。
题目地址:https://leetcode-cn.com/problems/maximum-average-subtree/ 题目描述 Given the root of a binary tre
题目地址:https://leetcode.com/problems/sliding-window-maximum/ 题目描述 Given an array nums, there is a sl
题目地址:https://leetcode-cn.com/problems/maximum-distance-in-arrays/ 题目描述 Given m arrays, and each ar
题目地址:https://leetcode.com/problems/maximum-average-subarray-i/description/open in new window 题目描述
题目地址:https://leetcode.com/problems/third-maximum-number/description/ 题目描述 Given a non-empty array
我有一个很难重现的错误。另外,有人告诉我写日志文件是一种安全责任。所以我想在异常中尽可能多地捕捉。 我找不到任何说明 C# 异常的最大长度是多少的地方。 我想粘贴一条 XML 消息(1 或 2K),也
是否可以限制 QML 应用的最大 FPS? 我在低端 iten atom 硬件中获得 60FPS 和 30% 的 CPU 使用率使用 win32 Angle 驱动程序(openGL 软件无法使用),我
我已启用 SeriLog(最新版本)自记录功能,并且看到数百条消息说 Maximum destructuring depth reached 不知道这意味着什么以及这是否是我需要担心的问题。 有谁知道
我有一个具有两个属性的模型(我只显示两个,因为只需要这两列) 我的模型 place_id ---------------------- user_id 1 ----------------------
考虑以下情况:要设置一个群集,其中每台计算机都具有32G GB的RAM。和16个CPU核心 如何根据信息(32G GB RAM和16 CPU CORE)确定以下参数 ) yarn.scheduler.
完成如下函数定义: -- maxi x y returns the maximum of x and y 我应该不使用 Haskell 中的“最大”函数来完成这个任务。 maxi :: Int
Haskell 标准库中是否有与 maximum 等效的安全值? *Main Control.Monad.State Data.List> maximum [] *** Exception: Prel
我是一名优秀的程序员,十分优秀!