作为一个手串艺人，有金主向你订购了一条包含n个杂色串珠的手串——每个串珠要么无色，要么涂了若干种颜色。为了使手串的色彩看起来不那么单调，金主要求，手串上的任意一种颜色（不包含无色），在任意连续的m个串珠里至多出现一次（注意这里手串是一个环形）。手串上的颜色一共有c种。现在按顺时针序告诉你n个串珠的手串上，每个串珠用所包含的颜色分别有哪些。请你判断该手串上有多少种颜色不符合要求。即询问有多少种颜色在任意连续m个串珠中出现了至少两次。
[编程题]手串
- 热度指数：6341 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
输入描述:
第一行输入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颗串珠是透明的。
用 last 数字记录每种颜色上次出现的位置，判断成功后加入哈希集合，最后的答案就是哈希集合中元素的数量。
由于是环形的，所以需要使用环形数组。
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(), m = in.nextInt(), c = in.nextInt();
List<List<Integer>> ls = new ArrayList<>();
for (int i = 0; i < n; ++i) {
List<Integer> lss = new ArrayList<>();
int x = in.nextInt();
for (int j = 0; j < x; ++j) lss.add(in.nextInt());
ls.add(lss);
}
int[] last = new int[c + 1];
Arrays.fill(last, Integer.MIN_VALUE / 2);
Set<Integer> s = new HashSet<>();
for (int i = 0; i < ls.size() * 2; ++i) {
List<Integer> colors = ls.get(i % ls.size());
for (int color: colors) {
if (i - last[color] + 1 <= m) s.add(color);
last[color] = i;
}
}
System.out.println(s.size());
}
}
编辑于 2023-12-21 21:33:53
回复(0)
import java.util.*;
public class Main
{
public Main(){}
public int getNum(){
Scanner sc = new Scanner(System.in);
//number
int n = sc.nextInt();
//limit
int m = sc.nextInt();
//color
int c = sc.nextInt();
//存储位置的hashmap
Map<Integer,ArrayList<Integer>> xpos = new HashMap<Integer,ArrayList<Integer>>();
for(int i=1;i<=c;i++){
//初始化一个空的表
ArrayList<Integer> list = new ArrayList<Integer>();
//i表示颜色，每个颜色有一个出现过位置记录的list
xpos.put(i,list);
}
int k=1;
while(k<=n&&sc.hasNextInt())
{
//颜色数量
int colorNum = sc.nextInt();
for(int i=0;i<colorNum;i++){
int x = sc.nextInt();
//此处加的k是有序的，k是第k个球，即出现的位置，x 是对应颜***r /> xpos.get(x).add(k);
}
k++;
}
//比较颜色出现的位置
int res=0;
for(int key:xpos.keySet())
{
//位置表长度
int len1 = xpos.get(key).size();
//长度为0直接返回
if(len1==0)continue;
//最小的距离初始化-1
int min_dis = -1;
//取最小的距离
for(int i=0;i<len1-1;i++)
{
int dis1 = xpos.get(key).get(i+1)-xpos.get(key).get(i);
//手链是环形，最大距离是n/2,此处所得是位置，位置差mod n/2是距离
if(min_dis==-1){
min_dis = dis1;
}else if(dis1<min_dis){
min_dis = dis1;
}
}
//如果最小距离小于m,则这个球不符合要求
if(min_dis!=-1&&min_dis%(n/2)<m){
res++;
}
}
return res;
}
public static void main(String[] a)
{
Main m = new Main();
int res = m.getNum();
System.out.println(res);
}
}
public class Main
{
public Main(){}
public int getNum(){
Scanner sc = new Scanner(System.in);
//number
int n = sc.nextInt();
//limit
int m = sc.nextInt();
//color
int c = sc.nextInt();
//存储位置的hashmap
Map<Integer,ArrayList<Integer>> xpos = new HashMap<Integer,ArrayList<Integer>>();
for(int i=1;i<=c;i++){
//初始化一个空的表
ArrayList<Integer> list = new ArrayList<Integer>();
//i表示颜色，每个颜色有一个出现过位置记录的list
xpos.put(i,list);
}
int k=1;
while(k<=n&&sc.hasNextInt())
{
//颜色数量
int colorNum = sc.nextInt();
for(int i=0;i<colorNum;i++){
int x = sc.nextInt();
//此处加的k是有序的，k是第k个球，即出现的位置，x 是对应颜***r /> xpos.get(x).add(k);
}
k++;
}
//比较颜色出现的位置
int res=0;
for(int key:xpos.keySet())
{
//位置表长度
int len1 = xpos.get(key).size();
//长度为0直接返回
if(len1==0)continue;
//最小的距离初始化-1
int min_dis = -1;
//取最小的距离
for(int i=0;i<len1-1;i++)
{
int dis1 = xpos.get(key).get(i+1)-xpos.get(key).get(i);
//手链是环形，最大距离是n/2,此处所得是位置，位置差mod n/2是距离
if(min_dis==-1){
min_dis = dis1;
}else if(dis1<min_dis){
min_dis = dis1;
}
}
//如果最小距离小于m,则这个球不符合要求
if(min_dis!=-1&&min_dis%(n/2)<m){
res++;
}
}
return res;
}
public static void main(String[] a)
{
Main m = new Main();
int res = m.getNum();
System.out.println(res);
}
}
发表于 2020-09-17 14:43:42
回复(0)
暴 力 爆 破
（多试几次，过不过看运气，连通过率都能浮动， 鉴定欧非
import java.util.Scanner;
import java.util.ArrayList;
public class 手环_暴力炸 {
public static void main (String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int c = sc.nextInt();
int[][] table= new int[n][c];
ArrayList<Integer> wrong = new ArrayList<Integer>();
int res = 0;
for (int j=0;j<n;j++){
int x = sc.nextInt();
for(int k=0;k<x;k++){
table[j][k] = sc.nextInt();
}
}
for (int i = 0;i<n;i++){
ArrayList<Integer> colors = new ArrayList<Integer>();
for (int t=0;t<m;t++){
int num = i+t;//一简化就必定爆
if (num>=n){
num -= n;
}
for (int k=0;k<table[num].length;k++){
if (table[num][k] != 0 && wrong.contains(table[num][k])== false ){
if (colors.contains(table[num][k])){
wrong.add(table[num][k]);
res++;
}else{
colors.add(table[num][k]);
}
}
}
}
}
System.out.println(res);
}
}
编辑于 2020-01-13 17:52:28
回复(0)
计算思路：将每种颜色的位置存入map中，然后按照规则计算错误的颜色数量。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 珠子数量
int n = scanner.nextInt();
// 测试范围
int m = scanner.nextInt();
// 颜色总数
int c = scanner.nextInt();
// 将每个颜色和颜色的范围存入map中
Map<Integer, List<Integer>> colorMap = new HashMap<Integer, List<Integer>>();
for (int i = 0; i < n; i++) {
int count = scanner.nextInt();
if (count == 0) {
continue;
}
for (int j = 0; j < count; j++) {
int color = scanner.nextInt();
if (colorMap.containsKey(color)) {
colorMap.get(color).add(i + 1);
} else {
List<Integer> indexList = new ArrayList<Integer>();
indexList.add(i + 1);
colorMap.put(color, indexList);
}
}
}
// 按照条件计算错误的颜色数量
int result = 0;
for (Entry<Integer, List<Integer>> colorEntry : colorMap.entrySet()) {
// 无色
if (colorEntry.getKey() == 0) {
continue;
}
List<Integer> colorIndexArray = colorEntry.getValue();
if (colorIndexArray.get(0) + n - colorIndexArray.get(colorIndexArray.size() - 1) < m) {
result++;
continue;
}
for (int i = 0; i < colorIndexArray.size() - 1; i++) {
if (colorIndexArray.get(i + 1) - colorIndexArray.get(i) < m) {
result++;
break;
}
}
}
System.out.println(result);
}
}
发表于 2019-09-16 19:42:24
回复(0)
import java.util.Scanner;
//统计出每种颜色出现的行数；如果相邻两个行数之差小于m
//或者最大的行数与最小的行数之差大于n-m，说明这种颜色不合要求
public class Main{
public static void main(String[] args){
Scanner input = new Scanner(System.in);
while(input.hasNext()) {
int n = input.nextInt();
int m = input.nextInt();
int c = input.nextInt();
int[][] color = new int[n][];
int[] num = new int[n];
for(int i = 0; i < n; i++) {
num[i] = input.nextInt();
color[i] = new int[num[i]];
for(int j = 0; j < num[i]; j++) {
color[i][j] = input.nextInt();
}
}
System.out.println(Solution(n, m, c, color));
}
input.close();
}
public static int Solution(int n, int m, int c, int[][] color){
int sum = 0;
int[][] row = new int[c][n];
int[] k = new int[c];
for(int i = 0; i < n; i++) {
for(int j = 0; j < color[i].length; j++) {
row[color[i][j]-1][k[color[i][j]-1]] = i;
k[color[i][j]-1]++;
}
}
for(int i = 0; i < c; i++) {
if(row[i][k[i]-1] - row[i][0] > n - m) {
sum++;
}else {
for(int j = 1; j < k[i]; j++) {
if(row[i][j] - row[i][j-1] < m) {
sum++;
break;
}
}
}
}
return sum;
}
}
编辑于 2019-09-15 10:57:03
回复(0)
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[]args) throws Exception{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String L1=br.readLine();
int n=Integer.parseInt(L1.split(" ")[0]);
int m=Integer.parseInt(L1.split(" ")[1]);
int c=Integer.parseInt(L1.split(" ")[2]);
List<ArrayList<Integer>>allballs=new ArrayList<>();
for(int i=0;i<n;++i){
String color=br.readLine();
String[] col=color.split(" ");
int num_i=Integer.parseInt(col[0]);
ArrayList<Integer>list=new ArrayList<>();
for(int j=1;j<=num_i;++j){
list.add(Integer.parseInt(col[j]));
}
Collections.sort(list,null);
allballs.add(list);
}
int countBall=0;
for(int myColor=1;myColor<=c;myColor++){
boolean[]hasColor=new boolean[n];
for(int ball=0;ball<n;++ball){
boolean has=false;
for(int i=0;i<allballs.get(ball).size();++i){
if(allballs.get(ball).get(i)==myColor){
has=true;
break;
}
}
/* int left=0;
int right=allballs.get(ball).size()-1;
while(left<=right){
if(left==right||left>right){
has= (allballs.get(ball).get(left).intValue()==myColor);
break;
}
int mid=(left+right)/2;
if(allballs.get(ball).get(mid).intValue()==myColor){
has=true;
break;
}else if(allballs.get(ball).get(mid).intValue()<=myColor){
left=mid+1;
}else{
right=mid-1;
}
} */
hasColor[ball]=has;
}
if(shouldBeCount(hasColor,m)){
countBall++;
}
}
System.out.println(countBall);
}
//若是发生冲突，那么应该记录
private static boolean shouldBeCount(boolean[] hasColor, int m){
int start=Integer.MIN_VALUE/2;
int first=Integer.MIN_VALUE;
int last=Integer.MIN_VALUE;
for(int i=0;i<hasColor.length;++i){
if(hasColor[i]){
if(start==Integer.MIN_VALUE/2){
first=i;
}
if(i-start<m){
return true;
}
start=i;
last=i;
}
}
if(first!=Integer.MIN_VALUE && hasColor.length-last+first+1<=m){
return true;
}
return false;
}
}
import java.util.*;
public class Main{
public static void main(String[]args) throws Exception{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String L1=br.readLine();
int n=Integer.parseInt(L1.split(" ")[0]);
int m=Integer.parseInt(L1.split(" ")[1]);
int c=Integer.parseInt(L1.split(" ")[2]);
List<ArrayList<Integer>>allballs=new ArrayList<>();
for(int i=0;i<n;++i){
String color=br.readLine();
String[] col=color.split(" ");
int num_i=Integer.parseInt(col[0]);
ArrayList<Integer>list=new ArrayList<>();
for(int j=1;j<=num_i;++j){
list.add(Integer.parseInt(col[j]));
}
Collections.sort(list,null);
allballs.add(list);
}
int countBall=0;
for(int myColor=1;myColor<=c;myColor++){
boolean[]hasColor=new boolean[n];
for(int ball=0;ball<n;++ball){
boolean has=false;
for(int i=0;i<allballs.get(ball).size();++i){
if(allballs.get(ball).get(i)==myColor){
has=true;
break;
}
}
/* int left=0;
int right=allballs.get(ball).size()-1;
while(left<=right){
if(left==right||left>right){
has= (allballs.get(ball).get(left).intValue()==myColor);
break;
}
int mid=(left+right)/2;
if(allballs.get(ball).get(mid).intValue()==myColor){
has=true;
break;
}else if(allballs.get(ball).get(mid).intValue()<=myColor){
left=mid+1;
}else{
right=mid-1;
}
} */
hasColor[ball]=has;
}
if(shouldBeCount(hasColor,m)){
countBall++;
}
}
System.out.println(countBall);
}
//若是发生冲突，那么应该记录
private static boolean shouldBeCount(boolean[] hasColor, int m){
int start=Integer.MIN_VALUE/2;
int first=Integer.MIN_VALUE;
int last=Integer.MIN_VALUE;
for(int i=0;i<hasColor.length;++i){
if(hasColor[i]){
if(start==Integer.MIN_VALUE/2){
first=i;
}
if(i-start<m){
return true;
}
start=i;
last=i;
}
}
if(first!=Integer.MIN_VALUE && hasColor.length-last+first+1<=m){
return true;
}
return false;
}
}
发表于 2018-02-11 15:08:58
回复(0)
问题信息
通过挑战的用户
-
2023-03-12 00:33:58 -
2023-02-23 21:16:54
-
2022-12-17 19:18:00 -
2022-11-13 23:30:40
-
2022-11-08 23:30:40
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
