字節跳動—特征提取

文章目錄

• • 字節跳動---特征提取
  • 一、題目描述
  • 二、分析
  • 三、代碼

一、題目描述

小明是一名算法工程師，同時也是一名鏟屎官。某天，他突發奇想，想從貓咪的視頻里挖掘一些貓咪的運動信息。為了提取運動信息，他需要從視頻的每一幀提取“貓咪特征”。一個貓咪特征是一個兩維的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> 所有用例的輸入特征總數和<100000N滿足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

輸出例子1:

3

例子說明1:

特征<1,1>在連續的幀中連續出現3次，相比其他特征連續出現的次數大，所以輸出3

二、分析

• 這道題不難，如果你去暴力遍歷肯定會超時。所以需要選取合適的數據結構快速處理數據
• 特征<a, b>是一個鍵值對的形式，所以需要有一個pair<int,int>的鍵值對數據結構
• 你需要存儲每個鍵值對的出現次數信息，所以你還需要一個map/unordered_map

三、代碼

方法一：

#include <iostream> #include <vector> #include <map> using namespace std;int main() {//代表用例的個數int n;cin >> n;pair<int, int> xy;while (n--){//代表行數int m;cin >> m;//保存結果int count = 0;//存儲上一行鍵值對出現的次數信息map<pair<int, int>, int> preFeaTimes;//存儲本行鍵值對在上一行的基礎上出現的次數信息map<pair<int, int>, int> feaTimes;while (m--){//代表每行鍵值對的個數int len;cin >> len;for (int i = 0; i < len; i++){cin >> xy.first >> xy.second;//判斷如果本次輸入的鍵值對在上一行出現過，那么該鍵值對的次數//等于上一行中記錄的出現次數+1if (preFeaTimes.count(xy))feaTimes[xy] = preFeaTimes[xy] + 1;else//如果該鍵值對沒有出現過或者沒在上一行出現過，說明該鍵值對//要么根本沒出現過要么中間斷了，所以重新置為1feaTimes[xy] = 1;count = max(count,feaTimes[xy]);}//注意注意????，這里的清空和交換非常重要//正式因為有這兩個操作才完成每次記錄的都是本行和上一行鍵值對出現的信息//清理：是因為本行已經遍歷完了，鍵值對的更新信息已經保存在feaTimes中了preFeaTimes.clear();//swap：是因為要繼續判斷下一行的鍵值對信息，下一行是依賴本行的preFeaTimes.swap(feaTimes);//總結：就是通過這兩個操作完成判讀最長連續出現的鍵值對}cout << count << endl;}return 0; }

方法二：

#include<iostream> #include<algorithm> #include<cstring> #include<map> #include<bits/stdc++.h> using namespace std;map< pair<int,int>, set<int> > m1;int main() {int n;cin>>n;while(n--){int m;cin>>m;int maxn = 0,now = 0;int k;int x,y;for(int i = 0;i < m;i++){cin>>k;for(int j = 0;j < k;j++){cin>>x>>y;m1[make_pair(x,y)].insert(i);}}for(map <pair<int,int>, set<int> >::iterator it = m1.begin();it != m1.end();it++){int num = 0;int sum = 1;set<int>::iterator itt = it->second.begin();num = *itt;itt++;for(;itt != it->second.end();itt++){if(*itt == num+1){sum++;num = *itt;}else {num =* itt;maxn = max(maxn,sum);sum = 1;}}if(itt == it->second.end()) maxn = max(maxn,sum);}cout<<max(maxn,now)<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的字节跳动---特征提取的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。