一、本周周賽總結

• T1 模擬。
• T2 快速冪模擬。
• T3 滑窗。
• T4 分組線段合并。

100143. 統計已測試設備

100143. 統計已測試設備

1. 題目描述

2. 思路分析

• 用一個d記錄后邊要減去的數量

3. 代碼實現

class Solution:def countTestedDevices(self, batteryPercentages: List[int]) -> int: d = ans = 0for i in range(len(batteryPercentages)):if batteryPercentages[i] - d>0:ans += 1d += 1return ans 

100155. 雙模冪運算

100155. 雙模冪運算

1. 題目描述

2. 思路分析

• 用py自帶快速冪。

3. 代碼實現

class Solution:def getGoodIndices(self, variables: List[List[int]], target: int) -> List[int]:return [i for i,(a,b,c,m) in enumerate(variables) if pow(pow(a,b,10),c,m) == target]

100137. 統計最大元素出現至少 K 次的子數組

100137. 統計最大元素出現至少 K 次的子數組

1. 題目描述

2. 思路分析

• 滑窗，但這題可能把窗口出到空，因此用雙指針寫法比隊列寫法方便一些。
• 對每個右端點，考慮左端點的個數，即左端點向左一下即能出現合法，因此當cnt[mx]>=k即可滑。

3. 代碼實現

class Solution:def countSubarrays(self, nums: List[int], k: int) -> int:mx = max(nums)l = 0cnt = Counter()ans = 0 for i,v in enumerate(nums):cnt[v] += 1while  cnt[mx] >= k:cnt[nums[l]] -= 1l += 1ans += lreturn ans

100136. 統計好分割方案的數目

100136. 統計好分割方案的數目

1. 題目描述

2. 思路分析

• 觀察題意，要求相同數字必須分在同一組，因此可以先按數組分組，求每個數字的左右邊界；
• 這時發現有的數字會有交叉，根據題意他們也應該同組。
• 于是想到線段合并。
• 合并完后，相鄰組可以任意分組或者不分。那么方案數考慮插板，n組中間有n-1個位置，每個位置可以插或不插。

3. 代碼實現

class Solution:def numberOfGoodPartitions(self, nums: List[int]) -> int:g = {}for i,v in enumerate(nums):if v not in g:g[v]= [i,0]g[v][1] = i lr = sorted(g.values())c = 1x,y = lr[0]for l,r in lr:if l > y:x = l c += 1y = max(y, r)return pow(2,c-1,10**9+7)

參考鏈接