Javascript手串颜色题——2018字节前端算法题 较难

字节前端算法题 较难"/>

Javascript手串颜色题——2018字节前端算法题 较难

Javascript手串颜色题——2018字节前端算法题 较难

作为一个手串艺人，有金主向你订购了一条包含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颗串珠是透明的。

let ballNums,linkNums, colorNums, ballColor =[], sameColorBall = [], count = 0;
[ballNums,linkNums, colorNums]=readline().split(' ');// 数组的每个元素都是一个数组，元素数组的第一位代表颜色个数，后续代表所用颜色
for(let i = 0; i < ballNums; ++i) {ballColor[i] = readline().split(' ').map(item => Number(item))
}//将同一颜色出现的串珠序号进行收集
//要求的sameColorBall是[,[1],[1,3,4],[1,3,5]]
ballColor.forEach((item, index) => {// 若该串珠所用颜色种类大于0// console.log(item, 'item');if(item[0] > 0) {let colorArr = item.slice(1)// 下面的item代表不同的颜色种类colorArr.forEach(color => {    // 如果之前已经保存过使用某颜色的串珠序号，则直接将其添加到数组中去if(sameColorBall[color]) {sameColorBall[color].push(index + 1)} else {sameColorBall[color] = [index + 1]}})}
})/*
colorArr对应的就是
1,2,3
2,3
2
3
*/sameColorBall.forEach(item=>{for(let i=0;i<item.length-1;i++){//原答主用的是++iif(item[i+1]-item[i]<linkNums){++count;break;	//因为当前珠子已被检测出不符合要求，无需后续检测}//注意：这里的难点在于手串是一个圈，要考虑循环的情况，考虑头尾有没有出现不满足要求if(ballNums+item[0]-item[item.length-1]<linkNums){	//item.length-1也可以写成-1，即item[item.length-1]//此时的第1颗珠子相当于第6颗珠子，即ballNums+item[0]++count;break;}     }    
})console.log(count)/*
var fruits = ["Banana", "Orange", "Lemon", "Apple", "Mango"];var citrus = fruits.slice(1,3);//Orange,LemonJavaScript slice() 方法
slice() 方法可从已有的数组中返回选定的元素。
slice()方法可提取字符串的某个部分，并以新的字符串返回被提取的部分。
array.slice(start, end)start
可选。规定从何处开始选取。如果是负数，那么它规定从数组尾部开始算起的位置。也就是说，-1 指最后一个元素，-2 指倒数第二个元素，以此类推。
end
可选。规定从何处结束选取。该参数是数组片断结束处的数组下标。如果没有指定该参数，那么切分的数组包含从 start 到数组结束的所有元素。如果这个参数是负数，那么它规定的是从数组尾部开始算起的元素。*/

好难，啥时候能找到工作啊？？？

下面看下智障博主写得C++算法：

#include<iostream>
using namespace std;int main(){int n,m,c;    //m为差距cin>>n>>m>>c;//int * color;//color=new int[n];int res=0;int *temp;temp=new int[c];for(int i=0;i<n;i++){int cn=0;cin>>cn;for(int j=0;j<cn;j++){int number;cin>>number;if(i-temp[number-1]<m)res++;temp[number-1]=i;}}cout<<res;return 0;       
}

输出为4，答案为2.

请在座的小盆友思考一下为什么错了，5分钟时间。

叮叮叮，到时了，博主在写这段代码时并没有考虑环状的情况，而且可能会重复计算珠子。

链接：
整理自牛客网