欢迎光临散文网 会员登陆 & 注册

复盘|第291场周赛

2022-11-23 20:30 作者:UCLmsc  | 我要投稿

移除指定数字得到的最大结果

【枚举】遍历nums寻找所有可移除的下标,用ans记录能得到的最大结果,每当找到nums[i] == digit的下标i就移除。数值大小和字符串字典序大小保持一致,所以不用转int。

【贪心】从左到右遍历nums,如果nums[i] == digit and nums[i] < nums[i + 1]就删除该字符,如果遍历完成仍不满足,就删除digit出现的最后一个下标,这样能保证删除后的结果最大。

必须拿起的最小连续卡牌数

【贪心 + 哈希表】用d存每个元素最近一次的下标,每次更新最小距离。

含最多 K 个可整除元素的子数组

【枚举 + 哈希集合去重】通过枚举左右边界来遍历nums的所有子数组,并检查它们是否至多包含k个可被p整除的元素,若cnt>k就可以停止枚举这个左边界情况下的右边界了。用哈希集合来去重。

字符串的总引力

【DP】将所有字串按照其末尾字符下标分组,考虑两组相邻的字串:以s[i - 1]结尾的字串、以s[i]结尾的字串,以s[i]结尾的字串,可以看作以s[i - 1]结尾的字串,在末尾加上s[i]。从左往右遍历s,考虑将s[i]添加到以s[i - 1]结尾的字串的末尾,添加后,这些以s[i - 1]结尾的字串的引力增加值分类讨论:s[i]之前没遇到,这些字串引力值+1,字串引力值之和增加i,再加上1即s[i]单独组成的字串的引力值。如果s[i]之前遇到过,设上次出现的下标为j,字串s[j + 1, .. i + 1],s[j + 2..i - 1]...不包含s[i]的字串的引力值都+1,再加上1,即s[i]单独组成的字串的引力值。


复盘|第291场周赛的评论 (共 条)

分享到微博请遵守国家法律