网站界面友好,超级工程网站建设上海中心大厦,营销型网站的定位,wordpress入口题目的意思是找到两行在两列处相等#xff0c;主要要做的是记录某个值是否重复出现过。
经过思考#xff0c;我的思路是#xff1a;每一列用一个unordered_mapstring,vectorint记录单词出现的行数#xff0c;对于某一行中的两列#xff0c;如果有两个元素…题目的意思是找到两行在两列处相等主要要做的是记录某个值是否重复出现过。
经过思考我的思路是每一列用一个unordered_mapstring,vectorint记录单词出现的行数对于某一行中的两列如果有两个元素在同一其他行出现了重复则可以输出结果
例如第4行的第1个元素在1 3 5 6行都出现了重复第4行的第2个元素在2 3行出现了重复则r1 3; r2 4; c1 1; c2 2;
每一行用一个数据结构保存每一列在哪些行出现了重复如果某一行被重复了两次则说明不满足PNF输出结果。
为了保存每一行中出现重复的列我们可以使用两种数据结构一种是数组一种是unordered_map保存的键值对key, val的含义是本行的val列在key行出现了重复。
数组每一行需要清空复杂度是O(n)键值对的插入的复杂度是O(n)每一次是常数最多插入n次总复杂度是O(n^2)
使用unordered_map的复杂度每一行也是O(n)但是常数会更大一些。
读入可以一个一个读如果嫌弃复杂可以将所有的,变成\n然后一行一行读我使用的是C的正则表达式库regex挺好用的。
两种数据结构的实现代码如下 数组
#include iostream
#include unordered_map
#include array
#include vector
#include regex
#include stringusing namespace std;namespace {constexpr int MAXN 1e4 5;constexpr int MAXM 1e1 5;arrayint, MAXN exists;arrayunordered_mapstring, vectorint, MAXM dict;int n, m;const string YES YES;const string NO NO;string line, word;regex r(([^,]*),);bool flag;int r1, r2, c1, c2;
}int main() {while (cin n m) {fill(dict.begin(), dict.end(), unordered_mapstring, vectorint());//读取空行getline(cin, line);flag false;for (int i 1; i n; i) {getline(cin, line);if (flag) continue;fill(exists.begin(), exists.begin() i, 0);line.push_back(,);int j 1;for (sregex_iterator it(line.begin(), line.end(), r), end_it; it ! end_it; it, j) {word it-str(1);
// cout word ;auto exist dict[j][word];for (auto k : exist) {if (exists[k] 0) {r1 k; r2 i;c1 exists[k]; c2 j;flag true;break;} else {exists[k] j;}}if (flag) break;dict[j][word].push_back(i);}
// cout \n;}if (flag) {cout NO \n r1 r2 \n c1 c2 \n;} else {cout YES \n;}}
}unordered_map
#include iostream
#include unordered_map
#include array
#include vector
#include regex
#include string
#include setusing namespace std;namespace {constexpr int MAXN 1e4 5;constexpr int MAXM 1e1 5;unordered_mapint, int exists;arrayunordered_mapstring, vectorint, MAXM dict;int n, m;const string YES YES;const string NO NO;string line, word;regex r(([^,]*),);bool flag;int r1, r2, c1, c2;
}int main() {while (cin n m) {fill(dict.begin(), dict.end(), unordered_mapstring, vectorint());//读取空行getline(cin, line);flag false;for (int i 1; i n; i) {getline(cin, line);if (flag) continue;exists.clear();line.push_back(,);int j 1;for (sregex_iterator it(line.begin(), line.end(), r), end_it; it ! end_it; it, j) {word it-str(1);
// cout word ;auto exist dict[j][word];for (auto k : exist) {if (exists.count(k) 0) {r1 k; r2 i;c1 exists[k]; c2 j;flag true;break;} else {exists[k] j;}}if (flag) break;dict[j][word].push_back(i);}
// cout \n;}if (flag) {cout NO \n r1 r2 \n c1 c2 \n;} else {cout YES \n;}}
}提交以后发现还是使用数组快一点毕竟常数比较小
看了书以后发现书中采用的是完全不同的思路不过把字符串首先哈希成数字这个思想我觉得挺重要对上面的代码也是一种优化。以后遇到对这种复杂数据结构的映射处理都应该想到这种哈希方法。
然后遍历每两列将每一行的两个的值加入unordered_map如果出现重复则输出。
复杂度是O(nm^2)按道理来讲比上面的代码会快很多但是实际提交却比上面的还慢不清楚为什么觉得OJ的测评也挺奇怪的。
经过思考我觉得上面O(n^2)的算法中每一行的复杂度在实际数据中应该比O(n)小很多导致算法大概就是O(n)的所以速度更快。
#include iostream
#include unordered_map
#include array
#include vector
#include regex
#include string
#include setusing namespace std;namespace {constexpr int MAXN 1e4 5;constexpr int MAXM 1e1 5;arrayarrayint, MAXM, MAXN dict;class StrHash {unordered_mapstring, int hash;int idx 0;public:int operator ()(const string s);};int StrHash::operator()(const string s) {if (hash.count(s)) return hash[s];return hash[s] idx;}class IntHash {int len 0;public:IntHash(int _len):len(_len) {}int operator() (int a, int b) {return a * len b;}};int n, m, len;regex r(([^,]*),);string line;bool flag;int r1, r2, c1, c2;unordered_mapint, int record;
}int main() {ios::sync_with_stdio(false);while (cin n m) {flag false;IntHash intHash(n * m);StrHash strHash;getline(cin, line);for (int i 0; i n; i) {getline(cin, line);line.push_back(,);int j 0;for (sregex_iterator it(line.begin(), line.end(), r), end_it; it ! end_it; it, j) {
// cout it-str(1) endl;dict[i][j] strHash(it-str(1));}}int word;for (int i 0; i m; i) {for (int j 0; j i; j) {record.clear();for (int k 0; k n; k) {word intHash(dict[k][i], dict[k][j]);if (record.count(word) 0) {flag true;r1 record[word] 1;r2 k 1;c1 j 1;c2 i 1;break;} else {record[word] k;}}if (flag) break;}if (flag) break;}if (flag) {cout NO\n r1 r2 \n c1 c2 \n;} else {cout YES\n;
//}}
}
