那些论坛网站做的比较好,wordpress4.8主题,东莞网站建设硅胶,书吧网站设计论文思路
把问题拆解成三步#xff1a;入-更新-出。
入#xff1a;下标为 i 的元素进入窗口#xff0c;更新相关统计量。如果 ik−1 则重复第一步。更新#xff1a;更新答案。一般是更新最大值/最小值。出#xff1a;下标为 i−(k-1) 的元素离开窗口#xff0c;更新相关…思路
把问题拆解成三步入-更新-出。
入下标为 i 的元素进入窗口更新相关统计量。如果 ik−1 则重复第一步。更新更新答案。一般是更新最大值/最小值。出下标为 i−(k-1) 的元素离开窗口更新相关统计量。
题单链接
1456. 定长子串中元音的最大数目
题目
给你字符串 s 和整数 k 请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。
英文中的 元音字母 为a, e, i, o, u。
示例 1 输入s “abciiidef”, k 3 输出3 解释子字符串 “iii” 包含 3 个元音字母。
示例 2 输入s “aeiou”, k 2 输出2 解释任意长度为 2 的子字符串都包含 2 个元音字母。
示例 3 输入s “leetcode”, k 3 输出2 解释“lee”、“eet” 和 “ode” 都包含 2 个元音字母。
示例 4 输入s “rhythms”, k 4 输出0 解释字符串 s 中不含任何元音字母。
示例 5 输入s “tryhard”, k 4 输出1
提示
1 s.length 1 0 5 10^5 105s 由小写英文字母组成1 k s.length
题目链接
题解
class Solution:def maxVowels(self, s: str, k: int) - int:res vowel 0for i, c in enumerate(s):if c in aeiou:vowel 1print(i,c,vowel)# 1. 入if i k-1: # 先统计前 k−1 个字母的元音个数print(-)continue# 2. 更新res max(res,vowel)# 3. 出if s[i-(k-1)] in aeiou:vowel -1return res
643. 子数组最大平均数 I
题目
给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 请你找出平均数最大且 长度为 k 的连续子数组并输出该最大平均数。
任何误差小于 10-5 的答案都将被视为正确答案。
示例 1 输入nums [1,12,-5,-6,50,3], k 4 输出12.75 解释最大平均数 (12-5-650)/4 51/4 12.75
示例 2 输入nums [5], k 1 输出5.00000
提示
n nums.length1 k n 1 0 5 10^5 105 − 1 0 4 -10^4 −104 nums[i] 1 0 4 10^4 104
题目链接
题解
class Solution:def findMaxAverage(self, nums: List[int], k: int) - float:res float(-inf) #为什么-10**4不行sum_n 0for i,num in enumerate(nums):#1.入sum_n numif i k-1:continue #2.更新res max(res,sum_n)#3.出 sum_n - nums[i-(k-1)]return res/k
1343. 大小为 K 且平均值大于等于阈值的子数组数目
题目
给你一个整数数组 arr 和两个整数 k 和 threshold 。
请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。
示例 1 输入arr [2,2,2,2,5,5,5,8], k 3, threshold 4 输出3 解释子数组 [2,5,5],[5,5,5] 和 [5,5,8] 的平均值分别为 45 和 6 。其他长度为 3 的子数组的平均值都小于 4 threshold 的值)
示例 2 输入arr [11,13,17,23,29,31,7,5,2,3], k 3, threshold 5 输出6 解释前 6 个长度为 3 的子数组平均值都大于 5 。注意平均值不是整数。
提示
1 arr.length 1 0 5 10^5 1051 arr[i] 1 0 4 10^4 1041 k arr.length0 threshold 1 0 4 10^4 104
题目链接
题解
class Solution:def numOfSubarrays(self, arr: List[int], k: int, threshold: int) - int:res 0sum_n 0for i,num in enumerate(arr):sum_n num# 入if i k-1:continue# 更新 if sum_n/k threshold:res 1# 出 sum_n -arr[i-(k-1)]return res
2090. 半径为 k 的子数组平均值
题目
给你一个下标从 0 开始的数组 nums 数组中有 n 个整数另给你一个整数 k 。
半径为 k 的子数组平均值 是指nums 中一个以下标 i 为 中心 且 半径 为 k 的子数组中所有元素的平均值即下标在 i - k 和 i k 范围含 i - k 和 i k内所有元素的平均值。如果在下标 i 前或后不足 k 个元素那么 半径为 k 的子数组平均值 是 -1 。
构建并返回一个长度为 n 的数组 avgs 其中 avgs[i] 是以下标 i 为中心的子数组的 半径为 k 的子数组平均值 。
x 个元素的 平均值 是 x 个元素相加之和除以 x 此时使用截断式 整数除法 即需要去掉结果的小数部分。
例如四个元素 2、3、1 和 5 的平均值是 (2 3 1 5) / 4 11 / 4 2.75截断后得到 2 。
示例 1
输入nums [7,4,3,9,1,8,5,2,6], k 3 输出[-1,-1,-1,5,4,4,-1,-1,-1] 解释
avg[0]、avg[1] 和 avg[2] 是 -1 因为在这几个下标前的元素数量都不足 k 个。中心为下标 3 且半径为 3 的子数组的元素总和是7 4 3 9 1 8 5 37 。 使用截断式 整数除法avg[3] 37 / 7 5 。中心为下标 4 的子数组avg[4] (4 3 9 1 8 5 2) / 7 4 。中心为下标 5 的子数组avg[5] (3 9 1 8 5 2 6) / 7 4 。avg[6]、avg[7] 和 avg[8] 是 -1 因为在这几个下标后的元素数量都不足 k 个。
示例 2 输入nums [100000], k 0 输出[100000] 解释
中心为下标 0 且半径 0 的子数组的元素总和是100000 。 avg[0] 100000 / 1 100000 。
示例 3 输入nums [8], k 100000 输出[-1] 解释
avg[0] 是 -1 因为在下标 0 前后的元素数量均不足 k 。
提示
n nums.length1 n 1050 nums[i], k 105
题目链接
题解
思路如下图所示
class Solution:def getAverages(self, nums: List[int], k: int) - List[int]:if k0: return numsres [-1]*len(nums)sum_n 0for i, num in enumerate(nums):sum_nnumif i 2*k:continueres[i-k] sum_n//(2*k1)sum_n - nums[i-2*k]return res
2379. 得到 K 个黑块的最少涂色次数
题目
给你一个长度为 n 下标从 0 开始的字符串 blocks blocks[i] 要么是 ‘W’ 要么是 ‘B’ 表示第 i 块的颜色。字符 ‘W’ 和 ‘B’ 分别表示白色和黑色。
给你一个整数 k 表示想要 连续 黑色块的数目。
每一次操作中你可以选择一个白色块将它 涂成 黑色块。
请你返回至少出现 一次 连续 k 个黑色块的 最少 操作次数。
示例 1 输入blocks “WBBWWBBWBW”, k 7 输出3 解释 一种得到 7 个连续黑色块的方法是把第 0 3 和 4 个块涂成黑色。 得到 blocks “BBBBBBBWBW” 。 可以证明无法用少于 3 次操作得到 7 个连续的黑块。 所以我们返回 3 。
示例 2 输入blocks “WBWBBBW”, k 2 输出0 解释 不需要任何操作因为已经有 2 个连续的黑块。 所以我们返回 0 。
提示
n blocks.length1 n 100blocks[i] 要么是 ‘W’ 要么是 ‘B’ 。1 k n
题目链接
题解
求出现一次连续 k 个黑色块的最少操作次数问题可以转化成求连续 k 个块中白色块最少的个数
class Solution:def minimumRecolors(self, blocks: str, k: int) - int:res float(inf)w_num 0for i, block in enumerate(blocks):if block W:w_num 1if ik-1:continueres min(res, w_num)if blocks[i-(k-1)] W:w_num -1return res
QA 子数组最大平均数 I题目中为什么res float(-inf)而-10**4不行 res float(-inf) 表示将 res 初始化为一个非常小的负数其目的是确保在后续的比较中任何子数组的平均数都会大于这个初始值因为子数组的平均数不可能是负无穷大。而 -10**4 这样的值虽然在大多数情况下也可以作为初始值但是它存在问题 范围限制题目中提到 − 1 0 4 -10^4 −104 nums[i] 1 0 4 10^4 104这意味着数组中的元素值是有限制的。如果有 k 个元素都是 − 1 0 4 -10^4 −104那么它们的和就是 − 1 0 4 ∗ k -10^4 * k −104∗k此时res大于sum_n导致结果错误。精度问题浮点数在计算机中是有精度限制的。使用一个非常大的负数作为初始值可能会导致精度损失尤其是在进行减法和除法操作时。 因此使用 float(“-inf”) 作为初始值是一个更安全、更稳定的做法它可以确保在所有情况下都能正确地找到最大平均数而不会因为数值范围或者精度问题导致错误的结果。
