最近因為生病好久沒刷題，今早開始打了一場 Leetcode 的周賽，來寫個題解，今早狀態還行，，BTW 以後每週都會打周賽，爭取寫題解
Leetcode 1341. 矩陣中 K 個最弱的行#
描述：
給定一個 m * n 的矩陣 mat，矩陣中有 1（代表士兵）和 0（代表平民），返回矩陣中 k 個最弱的行的索引，按從弱到強的順序排列。
行 i 比行 j 弱，如果行 i 中的士兵數量少於行 j 中的士兵數量，或者它們的士兵數量相同但 i 小於 j。士兵總是站在行的前沿，也就是說，總是 1 可能先出現然後是 0。
範例 1：
Input: 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
Output: [2,0,3]
解釋:
每行的士兵數量為:
row 0 -> 2
row 1 -> 4
row 2 -> 1
row 3 -> 2
row 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。你可以選擇一組整數並移除數組中這些整數的所有出現。
返回最小的集合大小，以便至少移除數組中的一半整數。
Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 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. 分割二叉樹的最大乘積#
描述：
給定一個二叉樹的根節點。通過移除 1 條邊將二叉樹分割成兩個子樹，使得子樹的和的乘積最大化。
由於答案可能太大，請返回它對 10^9 + 7 取模。
範例 1：
Input: root = [1,2,3,4,5,6]
Output: 110
解釋: 移除紅色邊並得到兩棵二叉樹，和分別為 11 和 10。它們的乘積為 110 (11*10)
這個題的題面也很簡單，給定一個帶值的二叉樹，移除某個二叉樹的邊，使之分割成為兩個新的二叉樹，求兩個二叉樹和的乘積最大
最開始很多人會被這道題唬到，但是實際上這道題就是一個二叉樹的遍歷，無論前中後序遍歷，先遍歷一次二叉樹，求出二叉樹節點值的總和，以及每個節點的左子樹的和 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
BTW 這段代碼的 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
),
)
BTW，這道題因為數據太大，需要對 10^9+7 取模，我智障的忘了取模，WA 了兩次，罰時罰哭。。。我真的太菜了。。
1344. 跳躍遊戲 V#
描述：
給定一個整數數組 arr 和一個整數 d。在一步中，你可以從索引 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] 對於所有索引 k 在 i 和 j 之間（更正式地說 min (i, j) < k < max (i, j)）。
你可以選擇數組中的任何索引開始跳躍。返回你可以訪問的最大索引數量。
注意，你不能在任何時候跳出數組。
Input: arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
Output: 4
解釋: 你可以從索引 10 開始。你可以跳 10 --> 8 --> 6 --> 7，如圖所示。
注意，如果你從索引 6 開始，你只能跳到索引 7。你不能跳到索引 5，因為 13 > 9。你不能跳到索引 4，因為索引 5 在索引 4 和 6 之間且 13 > 9。
同樣，你不能從索引 3 跳到索引 2 或索引 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)
總結#
很久沒刷題了，手還是有點生，在前面幾個簽到題上花了時間，，而且犯了低級錯誤，，所以以後一定要堅持刷題了。。BTW 這次的周賽題感覺都很簡單，感覺像是被洩題後找的 Backup，好了就先這樣吧，我繼續臥床養病了。。