上岸算法LeetCode Weekly Contest 299解题报告

【NO.1 判断矩阵是否是一个 X 矩阵】

解题思路

遍历矩阵判断即可。

代码展示


【NO.2 统计放置房子的方式数】

解题思路

动态规划。

f[i][0] 表示位置 i 不放房子的方案数

f[i][1] 表示位置 i 的上侧放房子的方案数

f[i][2] 表示位置 i 的下侧放房子的方案数

f[i][3] 表示位置 i 的上下两侧都放房子的方案数

代码展示

【NO.3 拼接数组的最大分数】

解题思路

动态规划。

f[i][0] 表示不交换时,nums1 的最大和,即等价于 presum(nums1, i)

f[i][1] 表示交换 i 时,nums1 的最大和,等于 max(f[i - 1][0], f[i - 1][1]) + nums2[i]

类似地,用 g[i] 表示 nums2 对应的解。

代码展示

【NO.4 从树中删除边的最小分数】

解题思路

建树,求子节点的异或和。枚举删除哪两条边即可。

需要判断的是删除的两条边上的点是否互为祖孙关系,可以用类似 LCA 的倍增数组快速判断。

代码展示