题解 | #手串#_牛客博客

1. 解题思路
这道题主要的难点是，如何提高颜色对比时的速度，惯性思维会直接暴力求解，一个一个去对比，这样造成的结果使得时间复杂度非常高。
由于该题的颜色是用数字来表示，那么我们可以使用一个一维数组来表示，也就是用数组的下标“1，2，3，4，......，n”来表示颜色，由于没有颜色0，因此再最后计数时需要注意直接从下标1开始。
又因为该题是对颜色种数进行计数，所以我们可以使用boolean类型标记，将该数组初始化为false，当且仅当在m个连续串珠内某种颜色出现的次数大于或等于2时，则将该颜色对应的下标值置为true。在本题解中我定义该数组为flag。
例如：该题的示例1为：

那么在第三颗珠子和第四颗珠子的颜色出现次数分别为：

颜色：2，次数：2；
颜色：3，次数：1；

此时颜色2即为重复出现的颜色，因此在一维数组flag中将数组下标为2的值置为true，即：flag[2]=true。

2.采用List和ArrayList的数据结构来进行存储数据
为了更好地实现这个解题思路，我们首要问题是解决数据获取与存储问题，根据题目要求的输入格式，最佳方式是采用二维数组；但是有一个问题是每一行颜色的数目我们并不知道，也就是说这是动态的。
因此，我们需要采用动态的二维数组，避免浪费大量的空间。我们可以采用如下定义：

List list = new ArrayList();
List li = new ArrayList();
list.add(li);

这样就实现一个简单的动态二维数组。

3.获取数据
根据题目要求的数据格式，第一行可以使用nextInt()来获取一个整数，接下来的几行直接使用nextLine()读取字符串，再通过split函数对字符串进行分割，最后用Integer.parseInt将字符串转换为整形变量。
这里需要特别注意，使用nextInt()后，需要先使用一次nextLine()来清楚缓存，否则会读入一个换行符，导致Integer.parseInt运行异常。
代码片段如下：

    int n,m,c;
        List list = new ArrayList();//二维数组
        n = input.nextInt();
        m = input.nextInt();
        c = input.nextInt();
        boolean flag[] = new boolean[c+1];//保存重复颜色
        for(int i=0; i<=c; i++)flag[i] = false;//数组初始化
        input.nextLine();//清除缓存
        for(int i=0; i<n; i++){
            String str = input.nextLine();
            String s[] = str.split(" ");//分割字符串
            int len = s.length;
            List li = new ArrayList();//用于保存每一行的数据
            for(String sh:s){
                int num = 0;
                try {
                    num = Integer.parseInt(sh);
                } catch (NumberFormatException e) {
                    e.printStackTrace();
                }
                li.add(num);
            }
            list.add(li);
        }

4.颜色计数
对于颜色计数，我们需要在每m个珠子中，对每种颜色进行计数；根据解题思路，我们可以使用map来计数，通过将颜色种类保存在key值，value值保存该颜色在连续的m个珠子中出现的次数。通过这样的方式，我们可以利用起map的检索能力，保证时间复杂度不会过高，即在每一轮颜色出现次数计数完后，可以直接查找value值大于或等于2对应的key值，再将flag数组中对应的颜色下标值置为true。
代码如下：

        for(int i=0; i<n; i++){
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();//key代表颜色，value代表颜色出现次数
            int k=i;//k值用于遍历m个连续的珠子
            for(int j=0; j<m; j++){
                //由于获取颜色数据时，每一行的第一个数字代表颜色数量，因此该值若为0则直接跳过，注意数组的下标溢出处理
                if((int)list.get(k).get(0) == 0){
                    k++;
                    if(k>=n){
                    k=k-n;
                    }
                    continue;
                }
                int len = list.get(k).size();
                //第一个值为颜色数量，直接从第二个值开始遍历
                for(int l=1; l<len; l++){
                    //获取颜色
                    int color = (int)list.get(k).get(l);
                    //初始化颜色出现次数
                    int colorNumber = 0;
                    //若map中找得到该颜色，说明该颜色已经出现过，将该颜色出现次数拿出来
                    if(map.containsKey(color)){
                        colorNumber = map.get(color);
                    }
                    colorNumber+=1;
                    map.put(color,colorNumber);
                }
                k++;
                //k值溢出，从0开始
                if(k>=n){
                    k=k-n;
                }
            }

            for(Map.Entry<Integer,Integer > entry:map.entrySet()){  
                //判断map中value值是否有大于1的值，若有则说明该颜色已经重复出现
                if(entry.getValue()>=2){
                    int key = entry.getKey();
                    flag[key] = true;
                }
            }
            map.clear();//清空map
        }

5.最终计数
这个很简单，直接贴代码（注意计数时从下标1开始）：

    int number=0;
        for(int p=1; p<=c; p++){
            if(flag[p])number++;
        }

6.完整代码

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.HashMap;

public class Main{
    public static Scanner input = new Scanner(System.in);
    public static void main(String []args){
        int n,m,c;
        List<List> list = new ArrayList<List>();//二维数组
        n = input.nextInt();
        m = input.nextInt();
        c = input.nextInt();
        boolean flag[] = new boolean[c+1];//保存重复颜色
        for(int i=0; i<=c; i++)flag[i] = false;//数组初始化
        input.nextLine();//清除缓存
        for(int i=0; i<n; i++){
            String str = input.nextLine();
            String s[] = str.split(" ");//分割字符串
            int len = s.length;
            List<Integer> li = new ArrayList<Integer>();
            for(String sh:s){
                int num = 0;
                try {
                    num = Integer.parseInt(sh);
                } catch (NumberFormatException e) {
                    e.printStackTrace();
                }
                li.add(num);
            }
            list.add(li);
        }


        for(int i=0; i<n; i++){
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();//key代表颜色，value代表颜色出现次数
            int k=i;//k值用于遍历m个连续的珠子
            for(int j=0; j<m; j++){
                //由于获取颜色数据时，每一行的第一个数字代表颜色数量，因此该值若为0则直接跳过，注意数组的下标溢出处理
                if((int)list.get(k).get(0) == 0){
                    k++;
                    if(k>=n){
                    k=k-n;
                    }
                    continue;
                }
                int len = list.get(k).size();
                //第一个值为颜色数量，直接从第二个值开始遍历
                for(int l=1; l<len; l++){
                    //获取颜色
                    int color = (int)list.get(k).get(l);
                    //初始化颜色出现次数
                    int colorNumber = 0;
                    //若map中找得到该颜色，说明该颜色已经出现过，将该颜色出现次数拿出来
                    if(map.containsKey(color)){
                        colorNumber = map.get(color);
                    }
                    colorNumber+=1;
                    map.put(color,colorNumber);
                }
                k++;
                //k值溢出，从0开始
                if(k>=n){
                    k=k-n;
                }
            }

            for(Map.Entry<Integer,Integer > entry:map.entrySet()){  
                //判断map中value值是否有大于1的值，若有则说明该颜色已经重复出现
                if(entry.getValue()>=2){
                    int key = entry.getKey();
                    flag[key] = true;
                }
            }
            map.clear();//清空map
        }
        int number=0;
        for(int p=1; p<=c; p++){
            if(flag[p])number++;
        }
        System.out.println(number);
    }
}