LeetCode Weekly Contest 174 题解
这是LeetCode 上的第 173 场周赛（链接）。
1341. 方阵中战斗力最弱的 K 行（The K Weakest Rows in a Matrix）
给定一个只包含 0 和 1 的二维数组，输出包含 1 数量最少的前 k 行。写这题的时候总有一种 Python 用了这么多语法糖会不会太投机取巧的担忧。。
class Solution:
def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
s = [[i, sum(mat[i])] for i in range(len(mat))]
s.sort(key=lambda x: x[1])
return [x[0] for x in s[:k]]
1342. 数组大小减半（Reduce Array Size to The Half）
给定一个数组，一次可以删除所有的某个数字，求将数组长度缩减到至少一半的最小删除次数。
思路是现将所有数字按照出现的次数从大到小排序，然后遍历累加这个频次数组，一旦累加的和（即长度）超过原数组一半就输出累加次数。
class Solution:
def minSetSize(self, arr: List[int]) -> int:
dic = dict()
for i in arr:
if i not in dic:
dic[i] = 1
else:
dic[i] += 1
v = list(dic.values())
v.sort(reverse=True)
count = 0
ans = 0
for i in v:
count += i
ans += 1
if count*2 >= len(arr):
return ans
1339. 分裂二叉树的最大乘积（Maximum Product of Splitted Binary Tree）
给定一棵二叉树，去掉一条边变成两树二叉树。找到这两棵子树和的乘积的最大值。由于这个值很大，所以输出还要模 1e9+7。
这其实是一道基础的题，关键在于对二叉树这个数据结构的理解。参考了 这位dalao 的思路。
- 对整棵树后序遍历，得到以各个节点为根的子树总和。
- 去掉一条边，两棵子树的乘积 = 子树总和 * （总和 - 子树总和），遍历取最大值。
- 最后进行取模操作。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def maxProduct(self, root: TreeNode) -> int:
sums = []
def postOrder(root: TreeNode):
if not root:
return 0
res = root.val + postOrder(root.left) + postOrder(root.right)
sums.append(res)
return res
s = postOrder(root)
ans = -1
for i in sums:
ans = max(ans, i * (s - i))
return int(ans % (1e9 + 7))
1344. 跳跃游戏 V（Jump Game V）
动态规划。使用 dp[i] 表示下标 i 最多能跳的次数，max(dp) 就是我们想要的结果。
关键在于，如何计算 dp[i]。
-
我们可以通过下标 i 的左右可跳范围去计算 dp[i]，状态转移方程是：
\[dp[i] = max(dp[j] + 1)\]上式中，j 为在 i 的可跳范围内的下标，即 i-d..i+d（或 0..i+d、i-d..len(arr)-1、0..len(arr)-1，视是否到边界的情况而定）。
-
初始条件：所有 dp[i] 一开始初始化为 1，即一开始我们认为每个地方都只能跳自己一次。
-
最后，按照高度从低到高的顺序遍历下标，在可跳范围内，按照状态转移方程更新 dp[i] 的值即可。
class Solution:
def maxJumps(self, arr: List[int], d: int) -> int:
l = len(arr)
A = [[i, arr[i]] for i in range(l)]
A.sort(key=lambda x:x[1])
dp = [1 for _ in range(l)]
for index, height in A:
cur = 1
# 向左找
for i in range(index-1, max(index-d, 0)-1, -1):
if arr[i] >= height:
break
cur = max(cur, dp[i]+1)
# 向右找
for i in range(index+1, min(index+d, l-1)+1):
if arr[i] >= height:
break
cur = max(cur, dp[i]+1)
dp[index] = max(dp[index], cur)
return max(dp)
动态规划真是巧妙呀！
有什么想法，留个评论吧：