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

备注:
如没有长度大于2的特征运动,返回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
使用map记录动作上一次出现的帧数和当前连续帧数,同时记录下当前连续的最长帧数res。
第一组数:(1,1)-> (0,1)    ,    (2,2) -> (0,1)      res = 1;
即代表(1,1)上次出现在0时刻,当前连续动作为1;(2,2)上次出现在0时刻,当前连续动作为1
第二组数:(1,1)-> (1,2)    ,    (1,4) -> (1,1)      res = 2;
即代表(1,1)上次出现在1时刻,当前连续动作为2;(1,4)上次出现在1时刻,当前连续动作为1
第三组数:(1,1)-> (2,3)    ,    (2,2) -> (2,1)      res = 3;
即代表(1,1)上次出现在2时刻,当前连续动作为3;(2,2)上次出现在2时刻,当前连续动作为1
第四组数:(2,2)-> (3,2)    ,    (1,4) -> (3,1)      res = 3;

代码如下:(实际上需要写个while(N--),但是好像测试用例都是1组,就懒得改了)
#include<iostream>
#include<map>
#include<algorithm>
using namespace std;

int main() {
    int N; cin >> N; //测试用例数
    int M; cin >> M; //帧数
    map<pair<int, int>, pair<int, int> > record;

    int amounts, x, y;
    int res = 1;
    for (int i = 0; i < M; i++) {//每一组测试用例
        cin >> amounts;
        for (int j = 0; j < amounts; j++) { //每一组特征
            cin >> x >> y;
            if (record.find(make_pair(x, y)) == record.end()) {
                record.insert(make_pair(make_pair(x, y), make_pair(i, 1)));
            }
            else {
                auto iter = record.find(make_pair(x, y));
                if (i - iter->second.first == 1) {//连续出现
                    iter->second.first = i; iter->second.second += 1;
                    res = max(res, iter->second.second);
                }
                else { //没有连续出现
                    iter->second.first = i;
                    iter->second.second = 1;
                }
            }
        }
    }
    cout << res << endl;
    return 0;
}



编辑于 2019-08-08 09:43:24 回复(0)
从头到尾遍历
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for (int i=0;i<n;i++){
            int m = in.nextInt();
            Pair[][] pairs = new Pair[m][];
            for (int j=0;j<m;j++){
                int t = in.nextInt();
                pairs[j] = new Pair[t];
                for (int k=0;k<t;k++){
                    pairs[j][k] = new Pair(in.nextInt(),in.nextInt());
                }
            }
            int max = Integer.MIN_VALUE;
            for (int j=0;j<m;j++){          //遍历每一帧
                for (int k=0;k<pairs[j].length;k++){         //遍历每一特征
                    if (pairs[j][k] != null){         //如果特征不为null
                        int c = 1;          //特征初始次数为1
                        int temp = c;
                        for (int t=j+1;t<m;t++){         //遍历当前帧以下的所有帧
                            for (int s = 0;s<pairs[t].length;s++){      //遍历每一特征
                                if (pairs[t][s] != null && pairs[j][k].first == pairs[t][s].first
                                        && pairs[j][k].second == pairs[t][s].second){     //若特征不为null,且相等
                                    pairs[t][s] = null;         //将其标志为null,防止后序重复遍历
                                    c++;      //特帧数加1
                                }
                            }
                            if (temp == c){    //遍历一个帧后,特征数不变,说明其已不连续了,此时退出
                                break;
                            }else {
                                temp = c;
                            }
                        }//还有一种退出情况,即循环到尾部,自动退出了
                        if (c > max)
                            max = c;    //记录最大特帧数
                    }
                }
            }
            System.out.println(max);
        }
    }

    private static class Pair{
        int first;
        int second;
        Pair(int first,int second){
            this.first = first;
            this.second = second;
        }
    }
}


编辑于 2019-08-18 16:04:57 回复(0)
#把特征出现的帧记录在字典中,并取最长连续帧
n =int(input())
for i in range(n):
    m =int(input())
    #保存不同的帧出现的像素
    num =0
    index =0
    #保存不同特征出现的位置
    dic ={}
    while index < m:
        line =[int(x) forx in input().strip().split()]
        num_pixel =line[0]
        num +=num_pixel
        p =[]
        for j in range(num_pixel):
            term =(line[2*j+1],line[2*j+2])
            if term not in dic:
                dic[term] =[]
                dic[term].append(index)
            else:
                dic[term].append(index)
        index +=1
    #最大连续序列
    max1 =0#全局最大长度
    for key indic:
        sequence =dic[key]
        max2 =1#至少有一个
        s =0
        while s +1< len(sequence):
            if sequence[s+1] ==sequence[s] +1:
                max2 +=1
            else:
                #连续断了,新断归0
                max2 =1
            if max2 > max1:
                max1 =max2
            s +=1
        if max2 > max1:
            max1 =max2
    print(max1)

发表于 2019-08-11 11:01:34 回复(0)
我想知道有什么方法能让一个数组中的数的组合成为map的键值。做题的时候没想到,只能把数组转换程字符串作为map的键值了。很难受
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        for(int i = 0; i < N; ++i){
            HashMap<String, Integer> mem = new HashMap<>();
            HashMap<String, Integer> temp_mem = new HashMap<>();
            int M = sc.nextInt();
            int max = 1;
            for(int j = 0; j < M; ++j){
                temp_mem.clear();
                int n = sc.nextInt();
                for(int k = 0; k < n; ++k){
                    int x = sc.nextInt();
                    int y = sc.nextInt();
                    String key = String.valueOf(x) + " " + String.valueOf(y);
                    temp_mem.put(key, mem.getOrDefault(key, 0) + 1);
                    max = Math.max(temp_mem.get(key), max);
                }
                mem.clear();
                mem.putAll(temp_mem);
            }
            if(max <= 1){
                System.out.println(1);
            }else{
                System.out.println(max);
            }
        }

    }
}




发表于 2019-08-09 21:45:28 回复(0)
#include<iostream>
#include<vector>
#include<map>
#include<set>
using namespace std;

int main(){
    int N; cin>>N;
    for(int i=0; i<N; i++){
        int M; cin>>M;
        
        int ans = 0;
        map<pair<int,int>, int> pairMap;
        
        vector<set<pair<int,int>>> nums(M);
        for(int i=0; i<M; i++){
            set<pair<int,int>> one;
            int len; cin>>len;
            int x, y;
            for(int j=0; j<len; j++){
                cin>>x>>y; one.insert(make_pair(x,y));
                if(i-1>=0 && nums[i-1].find(make_pair(x,y))!=nums[i-1].end()){
                    pairMap[make_pair(x,y)]++;
                }else{
                    pairMap[make_pair(x,y)] = 1;
                }
                ans = max(ans, pairMap[make_pair(x,y)]);
            }
            nums[i] = one;
        }
        cout<<ans<<endl;
    }
    return 0;
}

发表于 2019-07-07 18:30:34 回复(1)

貌似没啥好说的额,用一个字典记录上一帧最大连续特征就行

n = int(input())

while n > 0:
    m = int(input())
    res = 1
    d = {}
    for i in range(m):
        l = list(map(int , input().split()))
        k = l[0]
        tmp_d = {}
        for j in range(k):
            index = l[2 * j + 1] * 1000000000 + l[2 * j + 2]
            if index in d:
                tmp_d[index] = d[index] + 1
                res = max(res, tmp_d[index])
            else:
                tmp_d[index] = 1
        d = tmp_d
    print(res)
    n -= 1
发表于 2019-05-28 20:45:48 回复(0)
请各位大神看一下到底哪里出错了
N=int(input())
M=int(input())
for i in range(N):
    if M<=2:
        print(1)
        continue
    else:
        d={}
        for i in range(M):
            cu=list(map(int,input().strip().split(' ')))
            fnum=cu[0]
            if fnum!=0:
                for i in range(1,2*fnum,2):
                    term=(cu[i],cu[i+1])
                    if term not in d:
                        d[term]=[]
                        d[term].append(i+1)
                    else:
                        d[term].append(i+1)
            else:
                continue
        max_length=0
        for feature,num in d.items():
            max0=1
            for index in range(len(num)-1):
                if  num[index+1]==num[index]+1:
                    max0+=1
                else :
                    break
            max_lenght=max(max0,max_length)
        print(max_length)


发表于 2019-08-11 15:53:55 回复(1)
#include <bits/stdc++.h>
using namespace std;

typedef struct {
    int i;
    int len;
} node;

map<pair<int, int>, node> m;

int main(){
    int N, M;
    ios::sync_with_stdio(false);

    cin >> N;
    for(int t = 0; t < N; t++){
        cin >> M;
        int max = 0;
        // 帧
        for(int i = 0; i < M; i++){
            int F;
            cin >> F;
            // 特征
            for(int j = 0; j < F; j++){
                pair <int, int> p;
                cin >> p.first >> p.second;
                m[p] = node{i, m[p].len+1};
                if(m[p].len > max){
                    max = m[p].len;
                }
            }
            for(auto key : m){
                if(key.second.i != i){
                    m[key.first] = node{0, 0};
                }
            }
        }
        cout << max << endl;
    }
}

发表于 2019-08-09 13:26:44 回复(0)
map套set 存进去之后找连续的
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<bits/stdc++.h>
using namespace std;
map< pair<int,int>, set<int> > m1;
int main()
{
  //  freopen("in","r",stdin);
    int n,m;
    cin>>n;
    while(n--){
        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++;
           // maxn=max(max)
            for(;itt!=it->second.end();itt++){
         //       cout<<it->first.first<<' '<<it->first.second<<' '<<*itt<<endl;
                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;
}
编辑于 2019-06-22 18:40:02 回复(0)