Python算法练习 9.12

leetcode 643 子数组最大平均数

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。

请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。

任何误差小于 10-5 的答案都将被视为正确答案

输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

class Solution(object):def findMaxAverage(self, nums, k):""":type nums: List[int]:type k: int:rtype: float"""left = 0right = left + k - 1i = 0windowSum = 0while i < k:windowSum += nums[i]i += 1maxAvg = windowSum / float(k)while right + 1 < len(nums):windowSum = windowSum - nums[left] + nums[right+1]maxAvg = max(maxAvg, windowSum / float(k))left += 1right += 1return maxAvg

k不变，可以先求区间最大和，最后再除

leetcode 1456 定长子串中元音的最大数目

给你字符串 s 和整数 k 。

请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

英文中的 元音字母 为（a, e, i, o, u）。

分析：

先计算初始窗口元音的个数

窗口移动，1 右端进入元音左边退出非元音最大个数+1

2 右端进入元音左边退出元音最大个数不变

3 右边进入非元音无论左边退出什么最大个数不变

s所以仅在情况1时重新计算窗口中的元音个数，然后与maxCount比较

（附自己的代码，超时了。。）

class Solution(object):def maxVowels(self, s, k):""":type s: str:type k: int:rtype: int"""yuanyin = ['a', 'e', 'i', 'o', 'u']left = 0right = left + k - 1maxCount = 0i = 0while i <= right:if s[i] in yuanyin:maxCount += 1i += 1while right + 1 < len(s):currentCount = 0if s[right+1] in yuanyin and s[left] not in yuanyin:i = left + 1while i <= right + 1:if s[i] in yuanyin:currentCount += 1i += 1maxCount = max(currentCount, maxCount)left += 1right += 1return maxCount

修改版：勉强通过，去掉了双重循环，每次记录窗口的元音个数

class Solution(object):def maxVowels(self, s, k):""":type s: str:type k: int:rtype: int"""yuanyin = ['a', 'e', 'i', 'o', 'u']left = 0right = left + k - 1maxCount = 0i = 0while i <= right:if s[i] in yuanyin:maxCount += 1i += 1currentCount = maxCountwhile right + 1 < len(s):if s[right+1] in yuanyin and s[left] not in yuanyin:currentCount += 1if s[right+1] not in yuanyin and s[left] in yuanyin:currentCount -= 1maxCount = max(currentCount, maxCount)left += 1right += 1return maxCount

leetcode 1004 最大连续1的个数III

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

没思路直接看题解

分析：

先问题转换：滑动窗口解法，right所在位置的前缀中0的个数减去left所在位置前缀和中0的个数小于等于k，如果要right-left+1最大，那么就中间0的个数都等于k，一旦它们之间0的个数多于k，再让left往右赶

class Solution(object):def longestOnes(self, nums, k):""":type nums: List[int]:type k: int:rtype: int"""n = len(nums)# lnum 窗口左侧位置的前缀0总数# rnum 窗口右侧位置的前缀0总数lnum = rnum = left = 0maxlen = 0for right in range(n):rnum += 1 - nums[right]while lnum < rnum - k:lnum += 1 - nums[left] left += 1maxlen = max(maxlen, right - left + 1)return maxlen