例行 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 と二つの整数 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 が与えられます。時針と分針の間に形成される小さい角度（60 進法単位）を返します。
示例：
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 が与えられ、最初のインデックスに初期配置されています。
一歩で、インデックス 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 までの最小のジャンプ回数を求めます。
この問題はまだ解けていませんが、後で考えた結果、探索の問題です。
-
辞書を構築し、値をキー、インデックスを値にします（同じ値の間で直接ジャンプできます）。
-
ジャンプした点を保存するためにセットを利用します。
-
インデックス = 0 から BFS を開始し、各点が一歩でどの点にジャンプできるかを求め、終点に到達するまで BFS を続けます。
-
訪問済みの点を更新します。
ええと、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 の三つ目の問題の題面は直接心を崩壊させました、、、明日、題解を書きます。
さて、寝る時間です。