手串颜色算法机试题理解

算法机试题理解"/>

手串颜色算法机试题理解

作为一个手串艺人，有金主向你订购了一条包含n个杂色串珠的手串——每个串珠要么无色，要么涂了若干种颜色。为了使手串的色彩看起来不那么单调，金主要求，手串上的任意一种颜色（不包含无色），在任意连续的m个串珠里至多出现一次（注意这里手串是一个环形）。手串上的颜色一共有c种。现在按顺时针序告诉你n个串珠的手串上，每个串珠用所包含的颜色分别有哪些。请你判断该手串上有多少种颜色不符合要求。即询问有多少种颜色在任意连续m个串珠中出现了至少两次。

输入

第一行输入n，m，c三个数，用空格隔开。(1 <= n <= 10000, 1 <= m <= 1000, 1 <= c <= 50) 接下来n行每行的第一个数num_i(0 <= num_i <= c)表示第i颗珠子有多少种颜色。接下来依次读入num_i个数字，每个数字x表示第i颗柱子上包含第x种颜色(1 <= x <= c)

样例输入

5 2 3

3 1 2 3

0

2 2 3

1 2

1 3

样例输出

2

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);//接受输入n、m、cint n = scanner.nextInt();int m = scanner.nextInt();int c = scanner.nextInt();//题目中最大是50种颜色int [][]colors = new int[n][51];//开始输入手串颜色信息for (int i = 0; i < n; i++) {colors[i][0] = scanner.nextInt();for (int j = 1; j <= colors[i][0]; j++) {colors[i][j]= scanner.nextInt();}}scanner.close();   //这个很特殊  非常重要//将输入数据做转换：以第i种颜色的索引i作为map的key值，//value是一个list表，用于存储第i种颜色出现在第几个串珠上Map<Integer, List<Integer>> posMap = new HashMap<>();for (int i = 0; i < n; i++) {for (int j = 1; j <= colors[i][0]; j++) {int colorType = colors[i][j];if (colorType != 0) {//一种颜色存储一个mapif (!posMap.containsKey(colorType)) {List<Integer> list = new ArrayList<>();list.add(i);posMap.put(colorType, list);} else {List<Integer> list = posMap.get(colorType);list.add(i);}}}}Set<Integer> set = posMap.keySet();Iterator<Integer> iterator = set.iterator();int count = 0;while (iterator.hasNext()) {Integer integer = iterator.next();List<Integer> list = posMap.get(integer);for (int i = 0; i < list.size(); i++) {//后一个与前一个差值小于m，则属于不满足要求的颜色if (i < list.size() - 1) {if (list.get(i + 1) - list.get(i) < m) {count++;break;}} else {//最后一个和第一个串珠的位置比较，间隔也不能小于mif (n - list.get(i) + list.get(0) < m) {count++;break;}}}}System.out.println(count);}
}