复盘|第305场周赛
算术三元组的数目
【哈希表】用哈希表记录每个元素,然后遍历nums,看nums[j]-diff和nums[j]+diff是否都在哈希表中。遍历nums[k],加入哈希表的同时可以顺带求出算术三元组,从而做到一次遍历。
【三指针】nums严格递增的,遍历nums[k]时,i和j只增不减,可以用三个指针来实现判断逻辑。
受限条件下可到达节点的数目
【DFS + 哈希表】用哈希表记录哪些节点是受限的,建图的时候只有当两个节点都不是受限的才连边。然后DFS这棵树,统计从0出发能访问到的节点数,即为答案。
检查数组是否存在有效划分
【DP】定义f[i+1]表示从nums[0]到nums[i]的这些元素能否有效划分。
最长理想子序列
【DP】定义f[i] [c]表示s的前i个字母中的以c结尾的理想字符串的最长长度。