My code:
import java.util.Stack;
public class Solution {
public String simplifyPath(String path) {
if (path == null || path.length() == 0)
return path;
if (path.charAt(0) != '/')
return null;
Stack<String> stack = new Stack<String>();
int head = 1;
for (int i = 1; i < path.length(); i++) {
if (path.charAt(i - 1) != '/' && path.charAt(i) == '/') {
String temp = path.substring(head, i);
head = i + 1;
if (temp.equals("."))
continue;
else if (temp.equals("..")) {
if (!stack.isEmpty())
stack.pop();
}
else if (temp.equals("/"))
;
else
stack.push(temp);
}
else if (path.charAt(i - 1) == '/' && path.charAt(i) == '/')
head++;
}
if (head < path.length()) {
String temp = path.substring(head, path.length());
if (temp.equals("."))
;
else if (temp.equals("..")) {
if (!stack.isEmpty())
stack.pop();
}
else if (temp.equals("/"))
;
else
stack.push(temp);
}
String result = "";
if (stack.isEmpty())
result = "/";
else {
for (String temp : stack)
result += "/" + temp;
}
return result;
}
public static void main(String[] args) {
Solution test = new Solution();
System.out.println(test.simplifyPath("/////"));
}
}
My test result:
这道题目拖欠了一个多礼拜。。。
因为傻逼的一门课，做乐高机器人，废了我太多时间，许多功课落下了。这他妈傻逼。
而且什么都学不到。目测这几天会退了。
这题目就是用一个栈来解决。
注意点。
for (String temp : stack)
....
这个迭代器，还是从栈的底部还是遍历整个栈的。
还有，
if ()
...
else if()
...
else
...
如果else if下面只有一行代码，也要用大括号{}括起来。否则会直接继续执行else。。。
不知道为什么。
还有， 如果 if(..)
之后不打算进行任何操作。
那就，
if (....)
;
这样是可以的。。。
来美国快一个月了。
很多感受。
我觉得一开始我的自我感觉太好，觉得这边的人都太菜。。。然后被打的体无完肤。
还记得当时去和一个项目的教授谈。他是本科，硕士，博士都是MIT的。
但我依然感觉很好。。。很拽。。。意思是，这么多学生，你不选我，还能选谁。。。
结果。。。
后来又去见了一个老师，本科北大，博士伯克利的。。。
结果我还是自我感觉过好。
然后。。。
经历了两次被刷。。我心态正了。
昨天去见一个伯克利毕业的老师，终于拿到了一个项目。。。
还有，我太理想化了。选CS课，做了很多努力，写了很多封邮件。最后没有用。也有一点感受。
来这里的人，之前也许不是最优秀的，但一定是很努力的，很拼命的。我拼命争取的东西，他们也一定会拼命争取。我写了那么多封邮件，跑了那个多次办公室，他们也一定做过。
那么，
凭什么我想要的东西就只能给我。
现在每天都很累，很忙。基本都是自习到凌晨一点才回去。真的不是因为我计划不好。是真的作业太多了，project太多了，太难了，太花时间了。
说这些给女朋友听，她不能理解。其实我也不期望她理解。因为我的专业和她的专业完全不同，她是无法理解，工程类专业有多么累，作业有多么多的。至于她说什么，以后来了美国，要打工。。只能说是理想。
刚到美国，老师上课，基本听不懂，至少得要一两个月时间去适应。还有多门课，作业。需要花比别人更多的精力去复习。
更别说，硕士项目是要找工作的，一早就要开始准备。还要考证。
更别说，还要早睡。
请问，哪里来的时间，给你打工呢？
放假了，出去旅游倒是可以的。
**
总结： String, stack
**
Anyway, Good luck, Richardo!
My code:
public class Solution {
public String simplifyPath(String path) {
if (path == null || path.length() == 0)
return path;
Stack<String> s = new Stack<String>();
int begin = 1;
int end = 1; // get string from [begin, end)
while (end < path.length()) {
if (path.charAt(end) != '/') {
end++;
}
else {
String curr = path.substring(begin, end);
if (curr.equals("..")) {
if (!s.isEmpty())
s.pop();
}
else if (curr.length() == 0 || curr.equals(".")) {
begin = end + 1;
end = end + 1;
continue;
}
else
s.push(curr);
begin = end + 1;
end = end + 1;
}
}
if (begin < path.length()) {
String curr = path.substring(begin, path.length());
if (curr.equals("..")) {
if (!s.isEmpty())
s.pop();
}
else if (curr.length() == 0 || curr.equals(".")) {} // do nothing
else
s.push(curr);
}
String ret = "";
while (!s.isEmpty()) {
ret = "/" + s.pop() + ret;
}
if (ret.length() == 0)
ret = "/";
return ret;
}
}
这道题木就是用一个栈来做，思路很明确。就是corner case多。
- 如果最后stack为空，也需要返回一个"/"
- 可能出现 //// 的情况，怎么处理。
- end 到头时，begin指向的可能还是有效字母。退出循环后还需要再处理下。
所以代码写的冗长了，懒得优化了。
StringBuilder a.append(b),
a = a + b;
return a;
将自己现在的内存地址返回。
Anyway, Good luck, Richardo!
My code:
public class Solution {
public String simplifyPath(String path) {
if (path == null || path.length() == 0 || path.charAt(0) != '/') {
return null;
}
String[] parts = path.split("/");
Stack<String> s = new Stack<String>();
for (int i = parts.length - 1; i >= 0; i--) {
if (parts[i] == null || parts[i].length() == 0) {
continue;
}
else {
s.push(parts[i]);
}
}
// filter
Stack<String> s2 = new Stack<String>();
while (!s.isEmpty()) {
String part = s.pop();
if (part.equals(".")) {
continue;
}
else if (part.equals("..")) {
if (s2.isEmpty()) {
continue;
}
else {
s2.pop();
}
}
else {
s2.push(part);
}
}
String ret = "";
while (!s2.isEmpty()) {
String part = s2.pop();
ret = "/" + part + ret;
}
if (ret.length() == 0) {
return "/";
}
else {
return ret;
}
}
}
用了两个栈，思路更加清晰简洁了。
然后发现完全可以用一个栈做出来。
My code：
public class Solution {
public String simplifyPath(String path) {
if (path == null || path.length() == 0 || path.charAt(0) != '/') {
return null;
}
String[] parts = path.split("/");
Stack<String> s = new Stack<String>();
for (int i = 0; i < parts.length; i++) {
if (parts[i] == null || parts[i].length() == 0) {
continue;
}
else {
String part = parts[i];
if (part.equals(".")) {
continue;
}
else if (part.equals("..")) {
if (s.isEmpty()) {
continue;
}
else {
s.pop();
}
}
else {
s.push(part);
}
}
}
String ret = "";
while (!s.isEmpty()) {
String part = s.pop();
ret = "/" + part + ret;
}
if (ret.length() == 0) {
return "/";
}
else {
return ret;
}
}
}
注意一个corner case, 当 ret为empty时，返回 "/"
当栈为空且当前string是 “..” 时，continue， skip this case
Anyway, Good luck, Richardo! -- 08/16/2016
