HJ25 数据分类处理【牛客网】

零、原题链接

HJ25 数据分类处理

一、题目描述

二、测试用例

三、解题思路

1. 基本思路：
     首先理解题目，题目要求对规则集先进行排序，然后去重，这一步我们可以使用 sort + 双指针解决；然后题目要求使用新的规则集去匹配数据集，匹配规则为：如果数据集元素 e 存在连续子串等于规则 r ，则说明元素 e 符合规则 r 。题目要求输出每个规则的符合的元素有哪些。对于规则匹配，可以用正则表达式或者自己写。
2. 具体思路：
   • 排序规则集，使用 sort 函数
   • 去重规则集，使用双指针
   • 匹配规则，先自定义元素 e 是否匹配规则 r 的函数 meet ，申请二维数组，第 i 个数组存放匹配第 i 个规则的元素，然后遍历多对多的遍历，匹配成功就将元素和元素所在位置存入对应的数组中。
   • 按题目要求输出。

四、参考代码

时间复杂度：$\mathrm{O}(|R|\times |S|)$ 【|R| 是规则集大小，|S| 是数据集大小】
空间复杂度：$\mathrm{O}(|R|\times |S|)$

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;bool meet(const string& x, const string& y) {for (int i = 0; i < x.length(); i++) {if (x[i] == y[0] && i + y.length() - 1 < x.length()) {if (x.substr(i, y.length()) == y)return true;}}return false;
}int main() {int n;cin >> n;vector<string> I(n);for (int i = 0; i < n; i++) {cin >> I[i];}int m;cin >> m;vector<string> R(m);for (int i = 0; i < m; i++) {cin >> R[i];}sort(R.begin(), R.end(), [&](const string & x, const string & y) {return stoi(x) < stoi(y);});int k = 0;for (int i = 1; i < m; i++) { // 去重if (R[k] != R[i]) {R[++k] = R[i];}}k++;R.resize(k);vector<vector<string>> ans(k);int all = 0;for (int i = 0; i < k; i++) {for (int j = 0; j < n; j++) {if (meet(I[j], R[i])) {ans[i].emplace_back(to_string(j));ans[i].emplace_back(I[j]);}}if (ans[i].size())all += ans[i].size() + 2;}cout << all << ' ';for (int i = 0; i < k; i++) {if (ans[i].size()) {cout << R[i] << ' ' << (ans[i].size() >> 1) << ' ';for (int j = 0; j < ans[i].size(); j++) {cout << ans[i][j] << ' ';}}}
}
// 64 位输出请用 printf("%lld")