例行 Leetcode 周賽，這周雙周賽，兩場賽打下來，有點酸爽，先寫個 BiWeekly 19 Contest 的題解吧
1342. 將一個數字減至零的步數#
題面：
給定一個非負整數 num，返回將其減至零的步數。如果當前數字是偶數，則必須將其除以 2，否則，必須從中減去 1。
示例：
Input: num = 14
Output: 6
Explanation:
Step 1) 14 是偶數；除以 2 得到 7。
Step 2) 7 是奇數；減去 1 得到 6。
Step 3) 6 是偶數；除以 2 得到 3。
Step 4) 3 是奇數；減去 1 得到 2。
Step 5) 2 是偶數；除以 2 得到 1。
Step 6) 1 是奇數；減去 1 得到 0。
這個題題面很簡單，一個非負整數，偶數除 2，奇數減 1，求需要多少步到 0
暴力寫
class Solution:
def numberOfSteps(self, num: int) -> int:
count = 0
if num == 0:
return count
result = num
while result > 1:
if result % 2 == 0:
result = int(result / 2)
else:
result -= 1
count += 1
return count + 1
大小為 K 且平均數大於或等於閾值的子數組的數量#
題面：
給定一個整數數組 arr 和兩個整數 k 和 threshold。
返回大小為 k 且平均數大於或等於閾值的子數組的數量。
示例：
Input: arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
Output: 3
Explanation: 子數組 [2,5,5],[5,5,5] 和 [5,5,8] 的平均數分別為 4, 5 和 6。所有其他大小為 3 的子數組的平均數均小於 4（閾值）
給定一個數組和一個長度 k，和一個閾值 threshold ，求這個數組中的所有長度為 K 且平均數大於等於閾值的子數組的個數。這個題，暴力寫很簡單，一個簡單的數組的拆分，sum(arr[i:i+k])/k >= threshold 即可，但是這裡有個問題，如果實時求和，那麼時間複雜度為 O (M*K) M 為數組的長度，這個時候暴力會 T
因此需要做個小技巧的優化。可以考慮這樣這樣一個做法，假設當前 i 及其後 k 個數的和為 sum [i]，那麼有這樣一個公式，sum [i]=sum [i-1]-arr [i]+arr [i+k-1]，這樣每次計算和都是 O (1) 的複雜度，那麼整體就是一個 O (N) 的做法
好了，暴力開寫
from typing import List
class Solution:
def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
if not arr:
return 0
length = len(arr)
sum_threshold = [0.0] * length
count = 0
last_index = length
for i in range(length - k, -1, -1):
if i == length - k:
total_sum = sum(arr[i:i + k])
else:
total_sum = sum_threshold[i + 1] - arr[last_index] + arr[i]
sum_threshold[i] = total_sum
if total_sum / k >= threshold:
count += 1
last_index -= 1
return count
1344. 鐘表指針之間的角度#
題面：
給定兩個數字，hour 和 minutes。返回時針和分針之間形成的較小角度（以度為單位）。
示例：
Input: hour = 12, minutes = 30
Output: 165
求某個時刻，時針與分針的夾角，，，啊，，我的上帝呀，一度夢回小升初。。。一個數學題，首先科普如下知識
-
普通鐘表相當於圓，其時針或分針走一圈均相當於走過 360° 角；
-
鐘表上的每一個大格（時針的一小時或分針的 5 分鐘）對應的角度是：360°/12=30°；
-
時針每走過 1 分鐘對應的角度應為：360°/(12*60)=0.5°；
-
分針每走過 1 分鐘對應的角度應為：360°/60=6°。
好了，那麼就暴力做吧
class Solution:
def angleClock(self, hour: int, minutes: int) -> float:
hour %= 12
result = abs((minutes * 6) - (hour * 30 + minutes * 0.5))
return result if result < 360 else 360 - result
1345. 跳躍遊戲 IV#
題面：
給定一個整數數組 arr，你最初位於數組的第一個索引。
在一步中，你可以從索引 i 跳到索引：
- i + 1 其中：i + 1 < arr.length。
- i - 1 其中：i - 1 >= 0。
- j 其中：arr [i] == arr [j] 且 i != j。
返回到達數組最後一個索引的最小步數。
注意，你不能在任何時候跳出數組。
示例：
Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: 你需要三次跳躍從索引 0 --> 4 --> 3 --> 9。注意索引 9 是數組的最後一個索引。
還是跳格子，給定一個數組，裡面會有一些具體的值，現在從 index = 0 的地方起跳，跳躍規則如下：
-
在 i+1 或 i-1 都在數組的範圍內
-
如果存在 index=j 且 arr [i]==arr [j] 且 i!=j 的時候，可以直接從 i 跳到 j
求從 index=0 跳到 index=arr.length-1 最小的次數
這題我還是沒 A，後面琢磨了下，一個搜索的題目
-
構建一個字典，值為 key，index 為 value（相同的值之間可以直接跳）
-
利用一個 set 來保存跳過的點
-
從 index = 0 開始進行 BFS ，求每個點在一步之內可以跳到哪個點，然後不斷的 BFS 直到到達終點
-
更新被訪問過的點
emmmm，好吧 BFS ，開寫吧
from typing import List, Set
import collections
class Solution:
def minJumps(self, arr: List[int]) -> int:
length = len(arr)
if not arr or length == 1:
return 0
value_index = collections.defaultdict(list)
for index, value in enumerate(arr):
value_index[value].append(index)
visited: Set[int] = set()
traversal_queue = collections.deque([(0, 0)])
result = 0
while traversal_queue:
next_step_queue = collections.deque()
for _ in range(len(traversal_queue)):
cur_index, cur_step = traversal_queue.popleft()
cur_value = arr[cur_index]
visited.add(cur_index)
for next_index in [cur_index + 1, cur_index - 1] + value_index[
cur_value
]:
if (length > next_index >= 0) and (next_index not in visited):
if next_index == length - 2:
return cur_step + 2
if next_index == length - 1:
return cur_step + 1
next_step_queue.append((next_index, cur_step + 1))
del value_index[cur_value]
traversal_queue = next_step_queue
return result
總結#
這周的題，還是簡單，但是需要小心，比如第二題我太大意直接暴力吃了一發 T，然後第三題沒仔細讀題（求最小的度數）吃了一發 WA，不過和第二天周賽比起來，真的是幸福，175 第三題的題面直接讓心態崩了，，明天寫題解。
好了，滾去睡覺