题目描述
小明是一名算法工程师，同时也是一名铲屎官。某天，他突发奇想，想从猫咪的视频里挖掘一些猫咪的运动信息。为了提取运动信息，他需要从视频的每一帧提取“猫咪特征”。一个猫咪特征是一个两维的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 def main(): 2 #test = [[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 N = int(input()) 4 #N = 1 5 for i in range(N): 6 M = int(input()) 7 #M = 8 8 dic = {} 9 for j in range(M): 10 line = list(map(int,input().split(' '))) 11 #line = test[j] 12 T = line[0] 13 ts = line[1:] 14 n = len(ts) 15 k = 0 16 step = 2 17 while k < n // 2: 18 key = (ts[step * k],ts[step * k+1]) 19 if key in dic: 20 dic[key].append(j) 21 else: 22 dic[key] = [j] 23 k += 1 24 maxlen = 0 25 for z in dic.values(): 26 l = len(z) 27 if l == 1: 28 maxlen = max(maxlen,1) 29 else: 30 left = 0 31 pre = z[0] 32 idx = 1 33 while idx < l: 34 if z[idx] - pre == 1: 35 pre = z[idx] 36 idx += 1 37 else: 38 maxlen = max(maxlen,idx-left) 39 left = idx 40 idx += 1 41 maxlen = max(maxlen,idx-left) 42 print(maxlen) 43 44 if __name__ == '__main__': 45 main()
算法思路：数组遍历，哈希。
建立字典dic，以tuple为键，以该tuple所在的帧数为值(列表)。
遍历字典dic，计算所有的tuple连续帧数的长度，并保留最长的长度，即为所求。