? ? ? ?小明是一名算法工程師，同時也是一名鏟屎官。某天，他突發(fā)奇想，想從貓咪的視頻里挖掘一些貓咪的運動信息。為了提取運動信息，他需要從視頻的每一幀提取“貓咪特征”。一個貓咪特征是一個兩維的vector<x, y>。如果x_1=x_2?and y_1=y_2，那么這倆是同一個特征。

? ? ? ?因此，如果喵咪特征連續(xù)一致，可以認為喵咪在運動。也就是說，如果特征<a, b>在持續(xù)幀里出現(xiàn)，那么它將構(gòu)成特征運動。比如，特征<a, b>在第2/3/4/7/8幀出現(xiàn)，那么該特征將形成兩個特征運動2-3-4 和7-8。

現(xiàn)在，給定每一幀的特征，特征的數(shù)量可能不一樣。小明期望能找到最長的特征運動。

時間限制：C/C++ 1秒，其他語言2秒

空間限制：C/C++ 32M，其他語言64M

輸入描述：

第一行包含一個正整數(shù)N，代表測試用例的個數(shù)。

每個測試用例的第一行包含一個正整數(shù)M，代表視頻的幀數(shù)。

接下來的M行，每行代表一幀。其中，第一個數(shù)字是該幀的特征個數(shù)，接下來的數(shù)字是在特征的取值；比如樣例輸入第三行里，2代表該幀有兩個貓咪特征，<1，1>和<2，2>
所有用例的輸入特征總數(shù)和<100000

N滿足1≤N≤100000，M滿足1≤M≤10000，一幀的特征個數(shù)滿足 ≤ 10000。
特征取值均為非負整數(shù)。

輸出描述：

對每一個測試用例，輸出特征運動的長度作為一行

示例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>在連續(xù)的幀中連續(xù)出現(xiàn)3次，相比其他特征連續(xù)出現(xiàn)的次數(shù)大，所以輸出3。

說白了，就是找一個數(shù)組，在每一行連續(xù)出現(xiàn)的最大次數(shù)。

這里我借助了一個輔助類。

static class Node{
    //數(shù)組第一個元素
    int value1;
    //數(shù)組第二個元素
    int value2;
    //連續(xù)出現(xiàn)的最大累加次數(shù)
    int max;
    //這是一個臨時計數(shù)變量，當數(shù)組出現(xiàn)的行數(shù)，不是緊挨著上一次出現(xiàn)的行數(shù)時
    //暫時用這個變量計數(shù)，當再次出現(xiàn)不連續(xù)時，比較maxTemp和max，更新max
    //maxTemp重置為1
    int maxTemp;
    //最后出現(xiàn)的索引，就是行數(shù)，從0開始
    int lastIndex;
    public Node(int v1,int v2,int index){
        value1 = v1;
        value2 = v2;
        max = 1;
        lastIndex = index;
    }
}

整體代碼如下：文章來源地址http://www.zghlxwxcb.cn/news/detail-468546.html

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的區(qū)別
        while (in.hasNext()) { // 注意 while 處理多個 case
            List<Node> list = new ArrayList<>();
            //取用例個數(shù)
            int count = in.nextInt();
            for (int i = 0; i < count; i++) {
                //取行數(shù)（視頻幀數(shù)）
                int n = in.nextInt();
                for (int j = 0; j < n; j++) {
                    //取每行的特征數(shù)量
                    int m = in.nextInt();
                    //依次取出數(shù)組，每個數(shù)組兩個元素
                    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);
                            //判斷當前行是否和之前存在的連續(xù)
                            if (j == node.lastIndex + 1){
                                //如果連續(xù)，判斷maxTemp是否計數(shù)過，并更新max值
                                if (node.maxTemp > 0){
                                    node.maxTemp++;
                                    if (node.maxTemp > node.max){
                                        node.max = node.maxTemp;
                                    }
                                }
                                //否則，max+1
                                else
                                    node.max++;
                            }
                            //如果不連續(xù)
                            else {
                                //更新max值
                                if (node.maxTemp > node.max){
                                    node.max = node.maxTemp;
                                }
                                //maxTemp重置為1，開始下一輪計數(shù)
                                node.maxTemp = 1;
                            }
                            //更新最后出現(xiàn)行數(shù)索引
                            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{
        //數(shù)組第一個元素
        int value1;
        //數(shù)組第二個元素
        int value2;
        //連續(xù)出現(xiàn)的最大累加次數(shù)
        int max;
        //這是一個臨時計數(shù)變量，當數(shù)組出現(xiàn)的行數(shù)，不是緊挨著上一次出現(xiàn)的行數(shù)時
        //暫時用這個變量計數(shù)，當再次出現(xiàn)不連續(xù)時，比較maxTemp和max，更新max
        //maxTemp重置為1
        int maxTemp;
        //最后出現(xiàn)的索引，就是行數(shù)，從0開始
        int lastIndex;
        public Node(int v1,int v2,int index){
            value1 = v1;
            value2 = v2;
            max = 1;
            lastIndex = index;
        }
    }
}

到了這里，關(guān)于字節(jié)跳動春招——特征提取的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！