这是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 的思路。

  1. 对整棵树后序遍历，得到以各个节点为根的子树总和。
  2. 去掉一条边，两棵子树的乘积 = 子树总和 * （总和 - 子树总和），遍历取最大值。
  3. 最后进行取模操作。
# 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)

动态规划真是巧妙呀！