首先是 605. Can Place Flowers (easy)
https://leetcode.com/problems/can-place-flowers/

練習slide的基本題，種花的隔壁都不能有花。

想法：
1.前後加兩個0花壇方便處理，但跑判斷時不跑
2.直接運用[0,0,0]進行slide判斷

class Solution:
    #slide
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        flowerbed = [0] + flowerbed + [0]
        for i in range(2,len(flowerbed)):
            if flowerbed[i-2:i+1] == [0,0,0]:
                flowerbed[i-1] = 1
                n-=1
            if n <= 0:
                return 1
        return 0

再來是 628. Maximum Product of Three Numbers (easy)
https://leetcode.com/problems/maximum-product-of-three-numbers/
在串列中找出三個數字令最後乘積最大。

想法，找最大的三個數字，或找最大的一個乘最小兩個

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        nums.sort()
        return max(nums[0]*nums[1]*nums[-1],nums[-1]*nums[-2]*nums[-3])

再來是 643. Maximum Average Subarray I (easy)
https://leetcode.com/problems/maximum-average-subarray-i/

給一個數列，按照順序把k個數字加起來，找出最大的可能性

想法暴力解or前綴和or slide

class Solution:
    #TLE
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        maxNum = []
        for i in range(k,len(nums)+1):
            maxNum.append(sum(nums[i-k:i]))
        return max(maxNum)/k
    
    #前墜和算法prefix sums
    #首先先得到一個串列 S 專門記錄nums在前i個總和
    #由於要計算第i個到第i-k個的總和為多少，那就會是s[i] - s[i-k]
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        S = [0]
        for i in nums:
            S.append(S[-1]+i)
        maxNum = -float("inf")
        for i in range(k,len(S)):
            maxNum = max(maxNum,S[i] - S[i-k])
        return maxNum/k
    
    #Slide較優版本
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        total = 0
        for i in range(k):
            total += nums[i]
        maxNum = total
        for i in range(k,len(nums)):
            total += nums[i] - nums[i-k]
            maxNum = max(maxNum,total)
        return maxNum/k

以上為今天的練習，感謝大家