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树的节点个数,就是文件夹的个数。

完整代码如下:

#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;
}

本代码提交AC,用时126MS。

Leave a Reply

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