java基础第二弹

大家好，我是讯享网，很高兴认识大家。

大家好，我们继续来看字节跳动的招聘真题。题目同样源于牛客网，感兴趣的同学记得去亲自做一做练习哦。

这是七道题中的第四题，难度适中，我个人感觉是LeetCode Medium-的水平。对于算法的要求不高，主要考察的是候选人的思维以及代码能力。

题目链接：https://www.nowcoder.com/question/next?pid=&qid=&tid=

废话不多说了，我们来看题。

题意

小明是一名算法工程师，同时也是一名铲屎官。某天，他突发奇想，想从猫咪的视频里挖掘一些猫咪的运动信息。为了提取运动信息，他需要从视频的每一帧提取“猫咪特征”。一个猫咪特征是一个两维的vector<x, y>。如果x_1=x_2 and y_1=y_2，那么这俩是同一个特征。

因此，如果喵咪特征连续一致，可以认为喵咪在运动。也就是说，如果特征<a, b>在持java基础第二弹续帧里出现，那么它将构成特征运动。比如，特征<a, b>在第2/3/4/7/8帧出现，那么该特征将形成两个特征运动2-3-4 和7-8。

现在，给定每一帧的特征，特征的数量可能不一样。小明期望能找到最长的特征运动。

输入描述:

讯享网

输出描述:

讯享网

输入例子1:

输出例子1:

讯享网

例子说明1:

题解

题目的题意还是比较清楚的，即找出最长连续出现的特征数量。

首先，对于题目当中的特征是用两个int的pair对代表的，相同的pair被视为是同样的特征。特征必须要连续出现才算，中间中断则重新计算。

比较容易想到，我们可以使用map来存储所有的特征以及它当前出现的最多次数。这样我们虽然搞定了存储问题，但还需要解决另外两个问题。第一个问题是两个int构成的特征如何作为map的key，第二个问题是，有一些pair在之前的帧中出现过，但是中途中断了，我们如何快速清除？

使用pair

这两个问题我们一个一个来看，先看第一个问题。这个问题很好解决，在C++当中有一个数据结构叫做Pair，它是两个不同类型变量打包成的简单结构体，它可以作为map的key。

具体的用法非常简单，我们用pair<int, int>来声明两个int组成的特征，这里的类型可以根据自己的需要进行修改。当我们需要在map当中使用的时候，我们采用同样的方式来声明map即可。比如可以写成这样：map<pair<int, int>, int>，由于这样书写比较麻烦，一般acmer会使用define宏定义将它进行简化。比如pair<int, int>通常会简化成pii，表示两个int的pair。

这样的话，我们声明和使用pair就会简单得多。

临时map

第二个问题稍稍麻烦一些，对于一些之前出现的pair，我们需要实时清除。但是我们的map当中只会存储特征连续出现的次数，并没有办法判断每一个特征有没有中断过。

对于这个问题，我们有一个很好的办法，就是使用两个map。第一个map存储的是历史上一直连续出现至今的特征，我们叫它老map。第二个map是临时map，用来储存当前帧加入之后依然持续出现的特征。这样我们只需要在当前帧处理结束之后，用临时的map去更新老map，这样就完成了map中内容的更新。

我这么说可能有一点抽象，大家可以参考一下代码以及注释，会好理解一些。这个技巧也是比赛当中非常常用的技巧，这样通过两个map的来回迭代，就省去了对key的清理工作，这样节省了大量时间。

最后，我们来看下代码。

从代码来看，这道题其实是不难的，也没用到什么高深的算法和数据结构。但是对于新手来说还是很有挑战的，主要是pair的应用很多人不熟悉，然后对于临时map这样的技巧可能也不一定能想得到。更何况这个还是笔试题，真正能在笔试的时候能写上来的就更加困难了，很需要代码能力。

建议大家最好能自己亲手写一下遇到问题之后再看标程，这样的提升最明显。

相关推荐