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