牛客 字节跳动 ZJ9 手串问题

字节跳动 ZJ9 手串问题"/>

牛客 字节跳动 ZJ9 手串问题

1、问题描述

问题描述
描述
作为一个手串艺人，有金主向你订购了一条包含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)
输出描述：
一个非负整数，表示该手链上有多少种颜色不符需求。
示例1
输入：
5 2 3
3 1 2 3
0
2 2 3
1 2
1 3
复制
输出：
2
复制
说明：
第一种颜色出现在第1颗串珠，与规则无冲突。
第二种颜色分别出现在第 1，3，4颗串珠，第3颗与第4颗串珠相邻，所以不合要求。
第三种颜色分别出现在第1，3，5颗串珠，第5颗串珠的下一个是第1颗，所以不合要求。
总计有2种颜色的分布是有问题的。
这里第2颗串珠是透明的。

2、思路

我的思路就是用hashmap的key来存储颜色，value是list来存储该颜色出现的手串的下标，然后遍历list,判断list(i)-list(i-1)<c,要注意第一个和最后一个。

3、代码

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;public class Main {public static int n;public static int m;public static  void ShouChuan() {Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();int c = sc.nextInt();Map<Integer, List<Integer>> map = new HashMap<>();for (int i = 0; i < n; i++) {int nums_i = sc.nextInt();for (int j = 0; j < nums_i; j++) {int t = sc.nextInt();if (map.containsKey(t))map.get(t).add(i);else {List<Integer> list = new ArrayList<>();list.add(i);map.put(t, list);}}}int ans = 0;for (Map.Entry<Integer, List<Integer>> temp : map.entrySet()) {List<Integer> list = temp.getValue();ans += Judge(list, m);}System.out.println(ans);}public static int Judge(List<Integer> list, int c) {int len = list.size();int ans = 1;if (list.get(0) == (list.get(len - 1) + 1) % len) {return 1;}for (int i = 0; i < len; i++) {if (i > 0 && ((list.get(i) - list.get(i - 1) < c))) {// System.out.println("符合" );return 1;}}return 0;}public static void main(String[] args) throws IOException {ShouChuan();}
}

4、运行结果