leetcode 第 310 场算法比赛

零、背景

这次比赛题目有点意思，我感觉做题速度还可以，结果依旧没进前百名。

不知是大家变强了，还是我变弱了。

一、出现最频繁的偶数元素

题目：给一个数组，统计出现次数最高的偶数数字是哪个。

思路：map 统计偶数，遍历寻找最大频次即可。

小技巧：一种不需要空间的方法是原地排序，然后连续出现的数字就是这个数字的频次。

二、子字符串的最优划分

题意：给一个字符串，问最少可以划分多少了没有交集的子字符串，使得每个子字符串中没有重复字母。

思路：贪心。

边遍历边统计每个字母出现的次数，一旦重复就是分割线，统计器重置为0。

三、将区间分为最少组数

题意：给一些左右封闭区间，问最少可以划分多少个区间集合，使得集合内的区间没有交集。

思路：贪心。

每轮选择最小的左区间，然后选择下个没有交集的最小的左区间，直到找不到，则形成一个集合。

不断的重复上面的操作，最终统计的集合个数就是答案。

四、最长递增子序列 II

题意：给一个数组，求 LIS，即最长递增子序列。
要求：子序列相邻元素的差值不超过 k。

思路：n log(n)的经典动态规划我不知道能不能做这道题。

我是使用最原生的方法来做这道题的。

当前值 v 为结尾的最优值，要么不变，要么是[v-k, v-1] 结尾的最优值再加1。

所以我们需要一个数据结构，能够快速查询区间[v-k, v-1]的最优值，并且能更新当前点的最优值。

这就是典型的线段树。

PS：比赛的时候，我脑子短路，误认为区间内值不为0的都还需要加1，浪费不少时间在改线段树模板。

五、最后

这次比赛中间两题都是贪心，最后一题线段树，挺有意思的。

只可惜我想错了，浪费不少时间，没能进去前百名。

加油，算法人。

《完》

-EOF-

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