leetcode 第 305 场算法比赛

零、背景

题目进一步简单，都不出 Hard 了，拼手速拼不动了。

一、算术三元组的数目

题目：给一个数组，求三元组的个数。
三元组：三个不同位置的值呈等差数列，且差值等于输入的值。

思路：数组转集合，枚举第一个位置的值，查找后两个位置的值是否存在即可。

二、受限条件下可到达节点的数目

题目：给一个无向树，以及一些不可访问节点。
问从节点 0 可以到达哪些节点。

思路1：建图，Dfs 遍历的时候，遇到不可访问节点不访问即可。

思路2：建图的时候，对于不可访问节点不创建边，然后 dfs 遍历整个图即可。

三、检查数组是否存在有效划分

题目：给一个数组，问是否可以按规则划分出子数组。

规则1：子数组长度为 2，元素都相等。
规则2：子数组长度为 3，元素都相等。
规则3：子数组长度为 3，元素连续递增，差值都为 1。

思路：简单 DP。

状态定义：dp(i) 前 i 个元素是否可以划分。

转移方程就是题目对应的三个规则。

四、最长理想子序列

题意：给一个字符串，求最长的符合规则的子系列。

规则：相邻两个字符值之差的绝对值不大于 K。

思路：简单 DP。

状态定义：dp(i, c) 前 i 个字符中，以字符 c 为后缀的符合规则的最长子序列。

状态转移方程：

dp(i, c) = max(i-1, v) + 1
c-k <= v <= c+k

小技巧：由于状态转移方程只与上一个位置有关系，可以使用一维数组即可。

五、最后

这次比赛比较简单，一个递归题，两个动态规划题。

加油，算法人。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code