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。]]>