小明是一名算法工程师，同时也是一名铲屎官。某天，他突发奇想，想从猫咪的视频里挖掘一些猫咪的运动信息。为了提取运动信息，他需要从视频的每一帧提取“猫咪特征”。一个猫咪特征是一个两维的vector<x, y>。如果x_1=x_2 and y_1=y_2，那么这俩是同一个特征。
因此，如果喵咪特征连续一致，可以认为喵咪在运动。也就是说，如果特征<a, b>在持续帧里出现，那么它将构成特征运动。比如，特征<a, b>在第2/3/4/7/8帧出现，那么该特征将形成两个特征运动2-3-4 和7-8。
现在，给定每一帧的特征，特征的数量可能不一样。小明期望能找到最长的特征运动。
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32M，其他语言64M
输入描述：
第一行包含一个正整数N，代表测试用例的个数。 每个测试用例的第一行包含一个正整数M，代表视频的帧数。 接下来的M行，每行代表一帧。其中，第一个数字是该帧的特征个数，接下来的数字是在特征的取值；比如样例输入第三行里，2代表该帧有两个猫咪特征，<1，1>和<2，2> 所有用例的输入特征总数和<100000 N满足1≤N≤100000，M满足1≤M≤10000，一帧的特征个数满足 ≤ 10000。 特征取值均为非负整数。
输出描述：
对每一个测试用例，输出特征运动的长度作为一行
示例1
输入例子：
1 8 2 1 1 2 2 2 1 1 1 4 2 1 1 2 2 2 2 2 1 4 0 0 1 1 1 1 1 1
输出例子：
3
例子说明：
特征<1,1>在连续的帧中连续出现3次，相比其他特征连续出现的次数大，所以输出3。
说白了，就是找一个数组，在每一行连续出现的最大次数。
这里我借助了一个辅助类。文章来源：https://www.toymoban.com/news/detail-468546.html
static class Node{
//数组第一个元素
int value1;
//数组第二个元素
int value2;
//连续出现的最大累加次数
int max;
//这是一个临时计数变量，当数组出现的行数，不是紧挨着上一次出现的行数时
//暂时用这个变量计数，当再次出现不连续时，比较maxTemp和max，更新max
//maxTemp重置为1
int maxTemp;
//最后出现的索引，就是行数，从0开始
int lastIndex;
public Node(int v1,int v2,int index){
value1 = v1;
value2 = v2;
max = 1;
lastIndex = index;
}
}整体代码如下：文章来源地址https://www.toymoban.com/news/detail-468546.html
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNext()) { // 注意 while 处理多个 case
List<Node> list = new ArrayList<>();
//取用例个数
int count = in.nextInt();
for (int i = 0; i < count; i++) {
//取行数（视频帧数）
int n = in.nextInt();
for (int j = 0; j < n; j++) {
//取每行的特征数量
int m = in.nextInt();
//依次取出数组，每个数组两个元素
for (int k = 0; k < m * 2; k += 2) {
int[] arr = new int[]{in.nextInt(), in.nextInt()};
//先查找列表中是否存在元素值一样的对象
int index = findItem(list,arr);
//没有，直接添加
if (index == -1)
list.add(new Node(arr[0],arr[1],j));
else {
//如果找到了
Node node = list.get(index);
//判断当前行是否和之前存在的连续
if (j == node.lastIndex + 1){
//如果连续，判断maxTemp是否计数过，并更新max值
if (node.maxTemp > 0){
node.maxTemp++;
if (node.maxTemp > node.max){
node.max = node.maxTemp;
}
}
//否则，max+1
else
node.max++;
}
//如果不连续
else {
//更新max值
if (node.maxTemp > node.max){
node.max = node.maxTemp;
}
//maxTemp重置为1，开始下一轮计数
node.maxTemp = 1;
}
//更新最后出现行数索引
node.lastIndex = j;
}
}
}
int max = 0;
//遍历取出最大值
for(Node node : list){
max = Math.max(max,node.max);
}
//打印
System.out.println(max);
}
}
}
private static int findItem(List<Node> list,int[] item){
for(int i=0;i<list.size();i++){
Node node = list.get(i);
if (node.value1 == item[0] && node.value2 == item[1]){
return i;
}
}
return -1;
}
static class Node{
//数组第一个元素
int value1;
//数组第二个元素
int value2;
//连续出现的最大累加次数
int max;
//这是一个临时计数变量，当数组出现的行数，不是紧挨着上一次出现的行数时
//暂时用这个变量计数，当再次出现不连续时，比较maxTemp和max，更新max
//maxTemp重置为1
int maxTemp;
//最后出现的索引，就是行数，从0开始
int lastIndex;
public Node(int v1,int v2,int index){
value1 = v1;
value2 = v2;
max = 1;
lastIndex = index;
}
}
}到了这里，关于字节跳动春招——特征提取的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
