例行 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 を引き、ゼロに到達するために必要なステップ数を求めます。
暴力的に書く
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 と 2 つの整数 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. 時計の針の間の角度#
題面：
2 つの数字、hour と minutes が与えられます。時針と分針の間に形成される小さい角度（性別単位）を返します。
示例：
Input: hour = 12, minutes = 30
Output: 165
ある時刻における時針と分針の間の角度を求めます、、、ああ、私の神よ、一度小学校に戻ったような気分です。。。数学の問題です。まず、次の知識を普及させましょう。
-
普通の時計は円に相当し、時針または分針が一周することは 360° の角度を移動することに相当します。
-
時計の各大格（時針の 1 時間または分針の 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 が与えられ、最初のインデックスに初期配置されています。
1 ステップで、インデックス 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 まで 3 回のジャンプが必要です。インデックス 9 は配列の最後のインデックスです。
また格子を飛び越えます。配列が与えられ、その中に具体的な値が含まれています。現在、インデックス = 0 からジャンプを開始し、ジャンプのルールは次のとおりです。
-
i+1 または i-1 が配列の範囲内であること。
-
index=j かつ arr [i]==arr [j] かつ i!=j の場合、i から j に直接ジャンプできます。
インデックス = 0 からインデックス = arr.length-1 までの最小のジャンプ回数を求めます。
この題はまだ A していません。後で考えたところ、これは探索の問題です。
-
辞書を構築し、値をキー、インデックスを値にします（同じ値の間で直接ジャンプできます）。
-
ジャンプした点を保存するために set を使用します。
-
インデックス = 0 から BFS を開始し、各点が 1 ステップ内でどの点にジャンプできるかを求め、終点に到達するまで 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 の第三の問題の題面は、心のバランスを崩すものでした、、、明日、題解を書きます。
さて、寝る時間です。