本文共 2717 字,大约阅读时间需要 9 分钟。
LeetCode刷题:71. Simplify Path
原题链接:
Given an absolute path for a file (Unix-style), simplify it. Or in other words, convert it to the canonical path.
In a UNIX-style file system, a period . refers to the current directory. Furthermore, a double period .. moves the directory up a level. For more information, see: Absolute path vs relative path in Linux/Unix
Note that the returned canonical path must always begin with a slash /, and there must be only a single slash / between two directory names. The last directory name (if it exists) must not end with a trailing /. Also, the canonical path must be the shortest string representing the absolute path.
Example 1:
Input: "/home/"
Output: "/home" Explanation: Note that there is no trailing slash after the last directory name. Example 2:Input: "/../"
Output: "/" Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go. Example 3:Input: "/home//foo/"
Output: "/home/foo" Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one. Example 4:Input: "/a/./b/../../c/"
Output: "/c" Example 5:Input: "/a/../../b/../c//.//"
Output: "/c" Example 6:Input: "/a//bc/d//././/.."
Output: "/a/b/c"以 Unix 风格给出一个文件的绝对路径,你需要简化它。或者换句话说,将其转换为规范路径。
在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (..) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。更多信息请参阅:Linux / Unix中的绝对路径 vs 相对路径
请注意,返回的规范路径必须始终以斜杠 / 开头,并且两个目录名之间必须只有一个斜杠 /。最后一个目录名(如果存在)不能以 / 结尾。此外,规范路径必须是表示绝对路径的最短字符串。
算法设计
package com.bean.algorithmbasic;import java.util.Stack;public class SimplifyPathDemo { /** * 使用栈实现 * 1.将字符串根据/分割成一个字符串数组 * 2.遍历字符串,如果是".."则弹出一个元素,如果是"."则不做任何操作, * 否则将当前的字符串入栈 * 3.如果栈内没有元素,则代表根路径"/"。如果有元素,则将栈中的元素逆序拼接。 */ public String simplifyPath(String path) { if (path == null) { return ""; } String[] pathList = path.split("/"); Stackstack = new Stack<>(); for (int i = 0; i < pathList.length; i++) { if (pathList[i] != null && !pathList[i].equals("")) { if (pathList[i].equals(".")) { continue; } else if (pathList[i].equals("..")) { if (!stack.isEmpty()) { stack.pop(); } } else { stack.add(pathList[i]); } } } StringBuilder sb = new StringBuilder(); if (stack.isEmpty()) { return "/"; } while (!stack.isEmpty()) { sb.insert(0, "/" + stack.pop()); } return sb.toString(); } public static void main(String[] args) { // TODO Auto-generated method stub /* * Input: "/home//foo/" * Output: "/home/foo" */ SimplifyPathDemo simplify=new SimplifyPathDemo(); String path="/home//foo/"; String result = simplify.simplifyPath(path); System.out.println("result is: "+result); }}
程序输出结果:
result is: /home/foo
转载地址:http://yntdi.baihongyu.com/