总结第210场周赛。
1617. 统计子树中城市之间最大距离
题目的难点我觉着有两个,一个是如何找到不一样的子树,一个是如何计算子树的距离。
对于子树中任意两个点的距离,可以考虑flody算法,实现三重循环的方法实现。这里需要特别注意,因为涉及到加法,因此我们不能把最大值设为MAX_VALUE
这样在加法中会爆整数。
其次对于寻找不一样的子树,其实子树就是把不同的节点组织在一起的。看到数据不是很大,其实可以想到用状态压缩DP的思路解决问题。定义dp[i]
表示i的二进制其实是对应节点组成的树的距离。需要考虑,dp的初始其实就是实际连接的两个节点组成的子树。这个子树肯定是连通的。同时我们注意在每次枚举中,子树的大小是只增加不减小的。
1 | class Solution { |
1616. 分割两个字符串得到回文串
字符串问题,还是很难的。这里涉及到了如何低复杂度实现回文串的问题。之前我想到的思路是与回文串添加链接描述的题目类似的,利用集合实现降低复杂度的操作。但是这个题目的特点在,前后拼接是有要求的,也就是其实我们知道最后的长度。
因此操作思路是,首先从中间开始匹配,要求是回文串,在两个字串中都进行这个操作,找到一个最大长度的回文串就可以。当出现不匹配之后,可以有一个容错,跨字符串进行匹配。如果可以完全的匹配,最后left = -1
.
1 | class Solution { |