[LeetCode] 71. Simplify Path

这道题的要求是:简化(Unix/Linux风格的)文件系统路径。

会用到大概以下一些规则:

  • . 代表当前目录;
  • .. 代表上一级目录;

注意:它们单独使用才具有特殊意义,比如 /..abc/ 中的 “..”就没有特殊意义,不应该被简化掉。

比如:

  • 路径 /home/ 简化成 /home
  • 路径 /../ 简化成 /
  • 路径 /home//foo/ 简化成 /home/foo
  • 路径 /a/./b/../../c/ 简化成 /c
  • 路径 /... 简化成 /...
  • 路径 /.hidden 简化成 /.hidden
  • 路径 /. 简化成 /.
  • ...

这道题被打上了“栈”和“字符串”的标签,于是考虑会用到栈来处理:遇到 “/./”就简化成“/”,遇到“/foo/bar/../”之类的就需要简化成“/foo/”。

也就是一个栈的应用,也不复杂,利用C++的 std::vector 实现栈的版本如下:

class Solution {
public:
	string simplifyPath(string path) {
		vector<char> v;
		const char* p = path.c_str();

		char c;
		while((c = *p++)) {
			if(c == '.' && v.size() && v.back() == '/') {
				c = *p++;
				if(c == '/') {
					continue;
				} else if(c == '.') {
					c = *p++;
					if(c == '/' || !c) {
						while(v.size() && v.back() != '/') {
							v.pop_back();
						}

						if(v.size()) v.pop_back();

						while(v.size() && v.back() != '/')
							v.pop_back();

						if(!c) break;
						else {
							if(v.size() == 0) v.push_back('/');
							continue;
						}
					}

					v.push_back('.');
					v.push_back('.');
					v.push_back(c);
					continue;
				} else if(c == 0) {
					break;
				} else {
					v.push_back('.');
					v.push_back(c);
					continue;
				}
			} else if(c == '/') {
				while(v.size() && v.back() == '/') {
					v.pop_back();
				}

				v.push_back(c);
				continue;
			} else {
				v.push_back(c);
			}
		}

		if(v.size() == 0) v.push_back('/');
		if(v.size() > 1 && v.back() == '/') v.pop_back();

		v.push_back('\0');

		return string(&v[0]);
	}
};

看起来略显复杂,其实也就那样吧~ 只要是用 std::vector 模拟了栈。

但我马上就发现了这个栈其实可以完全用指针的移动来实现,于是马上换用了C语言重写:

char* simplify_path(const char* path) {
	char* new_path = (char*)malloc(strlen(path) + 1);
	char* i = new_path;
	const char* p = path;

	char c;
	while(c = *p++) {
		if(c == '/') {
			while(i > new_path && i[-1] == '/')
				i--;

			*i++ = '/';
			continue;
		} else if(c == '.' && i[-1] == '/') {
			c = *p++;
			if(c == '/') {
				continue;
			} else if(c == '.') {
				c = *p++;
				if(c == '/' || c == '\0') {
					if(i - new_path > 1) i--;
					while(i > new_path && i[-1] != '/')
						i--;

					if(c == '\0') break;
					else continue;
				} else {
					*i++ = '.';
					*i++ = '.';
					*i++ = c;
					continue;
				}
			} else if(c == '\0') {
				break;
			} else {
				*i++ = '.';
				*i++ = c;
				continue;
			}
		} else {
			*i++ = c;
		}
	}

	if(i == new_path) *i++ = '/';
	if(i - new_path > 1 && i[-1] == '/') i--;

	*i++ = '\0';

	return (char*)new_path;
}

用C语言写的好处非常多,可以看到:少了很多次的入栈/出栈/计算大小的函数调用(换成了指针的移动);而且至多进行一次内存分配,实际上,如果传入的参数允许修改的话,根本无需进行内存分配,因为:简化后的路径长度只可能少于或等于原路径的长度,所以可以直接在原路径上面修改就行。(C的效率就体现在这些方方面面)

这里是一张官方截至今天的统计图,看到“You are here”了吗? :-)

运行时间图.png

这张图说明了什么?

发表于:2015年07月28日 ,阅读量:908 ,标签:算法 · LeetCode · 文件系统

版权声明:若非特别注明,本站所有文章均为作者原创,转载请务必注明原文地址。