hihoCoder 1551-合并子目录

hihoCoder 1551-合并子目录

#1551 : 合并子目录

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi的电脑的文件系统中一共有N个文件,例如: /hihocoder/offer22/solutions/p1 /hihocoder/challenge30/p1/test /game/moba/dota2/uninstall 小Hi想统计其中一共有多少个不同的子目录。上例中一共有8个不同的子目录: /hihocoder /hihocoder/offer22 /hihocoder/offer22/solutions /hihocoder/challenge30 /hihocoder/challenge30/p1 /game /game/moba /game/moba/dota2/

输入

第一行包含一个整数N (1 ≤ N ≤ 10000) 以下N行每行包含一个字符串,代表一个文件的绝对路径。保证路径从根目录”/”开始,并且文件名和目录名只包含小写字母和数字。 对于80%的数据,N个文件的绝对路径长度之和不超过10000 对于100%的数据,N个文件的绝对路径长度之和不超过500000

输出

一个整数代表不同子目录的数目。
样例输入
3
/hihocoder/offer22/solutions/p1
/hihocoder/challenge30/p1/test
/game/moba/dota2/uninstall
样例输出
8

给定很多个文件的绝对路径,问从这些文件的绝对路径中,我们可以知道其一共有多少个不同文件夹出现过。 常规思路很简单,直接解析每个文件所在的每一级文件夹路径,存到一个set里面,最后返回unordered_set的大小。但是这种方法TLE,看了一下,内存基本也用完了。因为对于100%的数据,路径长度太长了,hash的时间和空间都随之增长。 后来马上想到,路径问题是一层一层的,有可能很多文件的路径前缀都是相同的,那么我们可以构建一个Trie树,每个节点仅是当前文件夹的名称。最后我们统计一下构建好的Trie树的节点个数,就是文件夹的个数。 完整代码如下: [cpp] #include<algorithm> #include<vector> #include<iostream> #include<unordered_map> #include<unordered_set> #include<string> #include<set> #include<map> #include<queue> using namespace std; typedef long long ll; struct Node { string key_; map<string, Node*> children_; Node(string key) :key_(key) {}; }; int main() { //freopen("input.txt", "r", stdin); int n; scanf("%d\n", &n); string line; Node* root = new Node(""); while (n–) { getline(cin, line); int pre = 0; int pos = line.find(‘//’); Node* cur = root; while (pos != string::npos) { if (pos != 0) { string tmp = line.substr(pre + 1, pos – pre – 1); if (cur->children_[tmp] == NULL) { cur->children_[tmp] = new Node(tmp); } cur = cur->children_[tmp]; } pre = pos; pos = line.find(‘//’, pos + 1); } } ll ans = 0; queue<Node*> q; q.push(root); while (!q.empty()) { Node* cur = q.front(); q.pop(); ++ans; for (auto it : cur->children_) { q.push(it.second); } } printf("%lld\n", ans – 1); return 0; } [/cpp] 本代码提交AC,用时126MS。]]>

Leave a Reply

Your email address will not be published. Required fields are marked *