首页 > 试题广场 >

特征提取

[编程题]特征提取

热度指数：12654 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小明是一名算法工程师，同时也是一名铲屎官。某天，他突发奇想，想从猫咪的视频里挖掘一些猫咪的运动信息。为了提取运动信息，他需要从视频的每一帧提取“猫咪特征”。一个猫咪特征是一个两维的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。

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

输入描述:

第一行包含一个正整数N，代表测试用例的个数。

每个测试用例的第一行包含一个正整数M，代表视频的帧数。

接下来的M行，每行代表一帧。其中，第一个数字是该帧的特征个数，接下来的数字是在特征的取值；比如样例输入第三行里，2代表该帧有两个猫咪特征，<1，1>和<2，2>
所有用例的输入特征总数和<100000

N满足1≤N≤100000，M满足1≤M≤10000，一帧的特征个数满足 ≤ 10000。
特征取值均为非负整数。

输出描述:

对每一个测试用例，输出特征运动的长度作为一行

示例1

输入

输出

说明

特征<1,1>在连续的帧中连续出现3次，相比其他特征连续出现的次数大，所以输出3

备注:

如没有长度大于2的特征运动，返回1

算法知识视频讲解

踩着光登月

发表于 2019-08-09 22:25:38

题目：https://www.nowcoder.com/ta/2019test?page=10题解：使用 map<int, pair<int, int>> mp; // 特征，特征起点帧的序号，特征计数遍历每个帧，加入新特征或者更新已存在特征的帧起点，特征计数1、如果该展开全文

多给生活加点糖

发表于 2020-05-16 10:53:17

import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); 展开全文

laglangyue

发表于 2020-06-12 22:34:40

参考抄袭大佬思路：双map当作两个相邻帧，开始还想着字符串匹配，kmp，dp之类的。 import java.util.ArrayList; import java.util.HashMap; import java.util.Map; import java.util.Scanner; publ 展开全文

白伟仝

发表于 2020-04-29 13:36:41

import java.util.*; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.ne 展开全文

大厂算法岗必拿下

发表于 2021-09-20 05:05:14

双字典论滚解决 #include<bits/stdc++.h> using namespace std; int main(){ int N,m; cin>>N; while(N--){ cin>>m; 展开全文

马老师的金轮

发表于 2022-02-12 20:11:50

import java.util.*; public class Main{ public static void main(String[] args){ Scanner scanner = new Scanner(System.in); int times 展开全文

17c89

发表于 2023-12-19 14:05:54

import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Scanner; public class Main { public static void mai 展开全文

honeyyy

发表于 2021-02-21 16:45:35

时间复杂度：O(NML)空间复杂度：O(L)维护一个buff字典 buff = {} maxlen = 0 n = int(input()) for _ in range(n): m = int(input()) for _ in range(m): line = i 展开全文

ZX2021

发表于 2021-07-31 00:22:58

该题读取特征时需要每次都读入x,y两个数字，两个数字组成二元组。每一帧的第一个数字代表有多少个这样的二元组，遍历即可。一行代表一帧，如果上一行的二元组在当前行也出现则为连续帧。用一个map来存储连续的次数，键为二元组，值为次数。如果为连续帧则次数加1，否则次数变为1。 #include <st 展开全文

小牛冲冲冲jiang

发表于 2021-09-20 06:38:56

字节题是真顶没办法把数组作为key就把数组转换成String import java.util.Scanner; import java.util.*; public class Main{ public static void main(String[] args) { 展开全文

问题信息

C++工程师 iOS工程师安卓工程师数组运维工程师算法工程师测试工程师 PHP工程师哈希查找模拟字节跳动 2019 Java工程师

上传者：小小

难度：

85条回答 338收藏 21349浏览

通过挑战的用户

查看代码

牛客23066...

2023-03-09 21:47:41
z84112938

2023-02-13 17:17:47
spmomo

2023-02-11 20:17:37
Elizabe...

2022-12-05 14:04:45
爱如覆水难收

2022-12-04 15:42:13

特征提取

输入描述:

输出描述:

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题