题解 | #手串#
手串
https://www.nowcoder.com/practice/0bb1fad52f474bdaa4d7636ca3a98244
思路1：最直观的想法是，不用存储每个串珠对应的颜色数组，直接存储每种颜色出现的串珠位置，使用colors存储每种颜色出现的串珠位置！遍历每种颜色并判断连续m个是否出现重复：首先判断首尾出现的位置差，由于是按照顺序填充数组，故colors[i]有序，那么可以使用(start+n-end)<m进行判断；接着判断每个相邻位置差，一旦发现连续m个出现重复，就直接判断下一种颜色。
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, m, c;
int ans = 0;
cin >> n >> m >> c;
//存储颜色出现的串珠位置
vector<int> colors[c + 1];
int num, color;
for (int i = 0; i < n; i++) {
cin >> num;
for (int j = 0; j < num; j++) {
cin >> color;
colors[color].push_back(i);
}
}
// for(int i=1;i<=c;i++)
// {
// for(int j=0;j<colors[i].size();j++)
// {
// cout<<colors[i][j]<<" ";
// }
// cout<<endl;
// }
//判断连续m个是否出现重复
//只需对每个颜色判断同颜色相邻的位置差是否小于m
for (int i = 1; i <= c; i++) {
//先判断首尾出现的位置差
if (colors[i][0] + n - colors[i][colors[i].size() - 1] < m) {
ans++;
continue;
}
//判断每个相邻位置差
for (int j = 0; j < colors[i].size() - 1; j++) {
if (colors[i][j + 1] - colors[i][j] < m) {
ans++;
break;
}
}
}
cout << ans;
return 0;
}
总结：注意，如果直接vector<vector<int>> colors(n)，那么会生成n乘以n的二维数组喔！建议使用vector<int> colors[n]，那么即是n个vector<int>。
#手串#字节跳动前端 文章被收录于专栏
字节跳动公司真题！！我最爱字节跳动！！
文远知行公司福利 581人发布