最近病気でしばらく問題を解いていなかったが、今朝 Leetcode の週次コンテストに参加し、問題解説を書こうと思う。今朝の調子はまあまあだった。ちなみに、今後毎週コンテストに参加し、問題解説を書くつもりだ。
Leetcode 1341. 行列の K 弱い行#
説明：
1（兵士を表す）と 0（市民を表す）からなる m * n の行列 mat が与えられたとき、最も弱い行から最も強い行までの k 弱い行のインデックスを返す。
行 i は行 j よりも弱い場合、行 i の兵士の数が行 j の兵士の数より少ないか、兵士の数が同じで i が j より小さい場合です。兵士は常に行の前線に立っており、つまり常に 1 が最初に現れ、その後に 0 が続きます。
例 1：
入力: mat =
[[1,1,0,0,0],
[1,1,1,1,0],
[1,0,0,0,0],
[1,1,0,0,0],
[1,1,1,1,1]],
k = 3
出力: [2,0,3]
説明:
各行の兵士の数は次のとおりです:
行0 -> 2
行1 -> 4
行2 -> 1
行3 -> 2
行4 -> 5
最も弱い行から最も強い行までの順序は[2,0,3,1,4]です。
問題は非常に簡単で、実際にはこの問題は二進数の処理です。Python では暴力的に解決できます。
from typing import List
class Solution:
def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
if not mat:
return []
number = []
for i in range(len(mat)):
number.append((int("".join([str(x) for x in mat[i]]), 2), i))
number.sort()
return [x for _, x in number[0:k]]
1342. 配列のサイズを半分に減らす#
説明：
配列 arr が与えられます。整数のセットを選択し、配列内のこれらの整数のすべての出現を削除できます。
配列の整数の少なくとも半分が削除されるようにするためのセットの最小サイズを返します。
入力: arr = [3,3,3,3,5,5,5,2,2,7]
出力: 2
説明: {3,7}を選択すると、新しい配列[5,5,5,2,2]が作成され、サイズは5（すなわち古い配列のサイズの半分に等しい）になります。
サイズ2の可能なセットは{3,5},{3,2},{5,2}です。
{2,7}のセットを選択することはできません。なぜなら、新しい配列[3,3,3,3,5,5,5]が作成され、古い配列のサイズの半分を超えるからです。
この問題も非常に簡単です。配列が与えられ、数字のセットを選択して削除し、削除後の配列のサイズが以前の半分以下になるようにし、最小限の数字を選択する必要があります。
ハッシュテーブルを使用した O (N) のアプローチです。
from typing import List
class Solution:
def minSetSize(self, arr: List[int]) -> int:
if not arr:
return 0
counter = {}
for i in arr:
counter[i] = counter.setdefault(i, 0) + 1
counter = {k: v for k, v in sorted(counter.items(), key=lambda item: item[1], reverse=True)}
total_count = 0
result_count = 0
for i, count in counter.items():
total_count += count
result_count += 1
if total_count >= len(arr) / 2:
break
return result_count
1343. 分割された二分木の最大積#
説明：
二分木の root が与えられます。1 つのエッジを削除して二分木を 2 つの部分木に分割し、部分木の合計の積を最大化します。
答えが大きすぎる可能性があるため、10^9 + 7 でモジュロを取ります。
例 1：
入力: root = [1,2,3,4,5,6]
出力: 110
説明: 赤いエッジを削除すると、合計が11と10の2つの二分木が得られます。それらの積は110（11*10）です。
この問題も非常に簡単です。値を持つ二分木が与えられ、特定のエッジを削除して 2 つの新しい二分木に分割し、2 つの二分木の和の積を最大化する必要があります。
最初は多くの人がこの問題に驚かされるかもしれませんが、実際にはこの問題は二分木のトラバーサルです。前順、中順、後順のいずれでも、まず二分木を一度トラバースして、二分木のノード値の合計と各ノードの左部分木の合計 left_sum および右部分木の合計 right_sum を求めます。
その後、再度トラバースして、result=max((total_sum-left_sum)*left_sum),(total_sum-right_sum)*right_sum),result)と暴力的に解決できます。
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def maxProduct(self, root: TreeNode) -> int:
total_sum = self.sum_node(root)
result = 0
stack = []
node = root
while node or stack:
while node:
stack.append(node)
result = max(result, ((total_sum - node.left_sum) * node.left_sum))
result = max(result, ((total_sum - node.right_sum) * node.right_sum))
node = node.left
node = stack.pop()
node = node.right
if node:
result = max(result, ((total_sum - node.right_sum) * node.right_sum))
result = max(result, ((total_sum - node.left_sum) * node.left_sum))
return result % (10 ** 9 + 7)
def sum_node(self, root: TreeNode) -> int:
if not root:
return 0
left_sum = self.sum_node(root.left)
right_sum = self.sum_node(root.right)
root.left_sum = left_sum
root.right_sum = right_sum
return left_sum + right_sum + root.val
ちなみに、このコードの type hint の使用には少し問題があります。コンテストが終わった後に修正しました。
from typing import Optional, Tuple, List
class TreeNode:
val: int
left: Optional["TreeNode"]
right: Optional["TreeNode"]
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class TreeNodeWithSum:
val: int
left: Optional["TreeNodeWithSum"]
right: Optional["TreeNodeWithSum"]
left_sum: int
right_sum: int
def __init__(
self,
x: int,
left: Optional["TreeNodeWithSum"],
right: Optional["TreeNodeWithSum"],
left_sum: int,
right_sum: int,
):
self.val = x
self.left = left
self.right = right
self.left_sum = left_sum
self.right_sum = right_sum
class Solution:
def maxProduct(self, root: TreeNode) -> int:
total_sum,new_root = self.sum_node(root)
result = 0
stack:List[TreeNodeWithSum] = []
node = new_root
while node or stack:
while node:
stack.append(node)
result = max(result, ((total_sum - node.left_sum) * node.left_sum))
result = max(result, ((total_sum - node.right_sum) * node.right_sum))
node = node.left
node = stack.pop()
node = node.right
if node:
result = max(result, ((total_sum - node.right_sum) * node.right_sum))
result = max(result, ((total_sum - node.left_sum) * node.left_sum))
return result % (10 ** 9 + 7)
def sum_node(
self, root: Optional[TreeNode]
) -> Tuple[int, Optional[TreeNodeWithSum]]:
if not root:
return 0, None
left_sum, new_left_node = self.sum_node(root.left)
right_sum, new_right_node = self.sum_node(root.right)
return (
left_sum + right_sum + root.val,
TreeNodeWithSum(
root.val, new_left_node, new_right_node, left_sum, right_sum
),
)
ちなみに、この問題はデータが非常に大きいため、10^9+7 でモジュロを取る必要があります。私はモジュロを取るのを忘れてしまい、2 回 WA を受けてしまいました。罰時間が長くて泣きそうです... 本当に下手です。。
1344. ジャンプゲーム V#
説明：
整数の配列 arr と整数 d が与えられます。1 ステップで、インデックス i からインデックスにジャンプできます：
i + x ただし: i + x < arr.length かつ 0 < x <= d。
i - x ただし: i - x >= 0 かつ 0 < x <= d。
さらに、インデックス i からインデックス j にジャンプできるのは、arr [i] > arr [j] かつ arr [i] > arr [k]（i と j の間のすべてのインデックス k に対して）である場合のみです（より正式には min (i, j) < k < max (i, j)）。
配列の任意のインデックスを選択してジャンプを開始できます。訪れることができるインデックスの最大数を返します。
なお、いつでも配列の外にジャンプすることはできません。
入力: arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
出力: 4
説明: インデックス10から開始できます。10 --> 8 --> 6 --> 7にジャンプできます。
インデックス6から開始すると、インデックス7にしかジャンプできません。インデックス5にはジャンプできません。なぜなら13 > 9だからです。インデックス4にはジャンプできません。なぜならインデックス5がインデックス4と6の間にあり、13 > 9だからです。
同様に、インデックス3からインデックス2またはインデックス1にジャンプすることはできません。
この問題の説明は次のとおりです。配列にはいくつかの値が含まれており、任意の位置からジャンプを開始できます。一度に 1 つだけジャンプでき、ジャンプする際にはルールを満たす必要があります。仮に配列 i の位置からジャンプを開始すると、毎回ジャンプできる範囲は x であり、次の条件を満たす必要があります。
-
i+x < arr.length かつ 0<x<=d
-
i-x >=0 かつ 0<x<=d
さらに、i から j にジャンプする場合、arr [i]>arr [j] かつ i から j の間のすべての要素が arr [j]<x<arr [i] を満たす必要があります。最大で何個の要素をジャンプできるかを求めます。
最初はこの問題が双方向 DP の問題だと思いましたが、書くのが面倒でやめました。しかし、後でコンテストが終わった後に、この問題は実際には単方向 DP で解決できることに気付きました。なぜなら、高いところから低いところにしかジャンプできないからです。したがって、要素をソートして順にトラバースすることで、次の式を得ることができます。dp[i]=max(dp[i]+dp[j]+1) ここで j は i から到達可能なインデックスです。DP 部分の計算量は O (DN) ですが、事前にソートする必要があるため、全体の時間計算量は O (logN+DN) です。
from typing import List
class Solution:
def maxJumps(self, arr: List[int], d: int) -> int:
length = len(arr)
dp = [1] * length
for a, i in sorted([a, i] for i, a in enumerate(arr)):
for di in [-1, 1]:
for j in range(i + di, i + d * di + di, di):
if not (0 <= j < length and arr[j] < arr[i]):
break
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
まとめ#
しばらく問題を解いていなかったので、手が少し鈍っていました。最初の数問で時間をかけてしまい、初歩的なミスも犯しました。これからは問題を解くことを続けなければなりません。ちなみに、今回の週次コンテストの問題はすべて非常に簡単で、漏洩した問題のバックアップのように感じました。それでは、これで終わりにします。私は引き続き病気を養生します。