71.|71. 简化路径-leetcode简化Unix路径算法的Java实现 71.简化路径-leetcode简化Unix路径

【71.|71. 简化路径-leetcode简化Unix路径算法的Java实现】我的LeetCode评论:
https://leetcode-cn.com/problems/simplify-path/comments/31264
我的GitHub代码地址:
https://github.com/geyingqi777/the-big-test/tree/master/src/main/java/gyq/java/algorithm/leetcode/_71
题目描述

以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点（..）表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。示例 1：输入："/home/" 输出："/home" 解释：注意，最后一个目录名后面没有斜杠。示例 2：输入："/../" 输出："/" 解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。示例 3：输入："/home//foo/" 输出："/home/foo" 解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。示例 4：输入："/a/./b/../../c/" 输出："/c" 示例 5：输入："/a/../../b/../c//.//" 输出："/c" 示例 6：输入："/a//b////c/d//././/.." 输出："/a/b/c"

实现代码,共2种方式

package gyq.java.algorithm.leetcode._71; import java.util.ArrayList; import java.util.List; /** * 简化路径 Created by ge_yi on 2019/2/19. */ public class Solution { /** * 以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。 * * 在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点（..）表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径 * * 请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。 * * * * 示例 1： * * 输入："/home/" * * 输出："/home" * * 解释：注意，最后一个目录名后面没有斜杠。 * * 示例 2： * * 输入："/../" * * 输出："/" * * 解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。 * * 示例 3： * * 输入："/home//foo/" * * 输出："/home/foo" * * 解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。 * * 示例 4： * * 输入："/a/./b/../../c/" * * 输出："/c" * * 示例 5： * * 输入："/a/../../b/../c//.//" * * 输出："/c" * * 示例 6： * * 输入："/a//b////c/d//././/.." * * 输出："/a/b/c" * * @param path * @return */ public String simplifyPath(String path) { // 思路: 用正则替换, 这里需要用到正则语法里面的零宽断言 // /. 当前路径,替换成"/", 这里用了负向零宽断言 // (?!exp):零宽度负预测先行断言，断言此位置的后面不能匹配表达式exp path = path.replaceAll("\\/\\.(?!([\\.]|[^\\/]))", "/"); // /..在路径行首,直接换成/ path = path.replaceAll("^\\/\\.\\.(?!([\\.]|[^\\/]))", "/"); // 多个/////,替换成一个/ path = path.replaceAll("\\/+", "\\/"); int lengthBefore = path.length(); while (true) { // 循环逐个替换 // /..上一级目录, 连到上一级的路径替换成"/" path = path.replaceFirst("\\/[^\\/]+\\/\\.\\.(?!([\\.]|[^\\/]))", "/"); // 多个/////,替换成一个/ path = path.replaceAll("\\/+", "\\/"); int length = path.length(); if (lengthBefore == length) { // 没有可换的了 break; } else { lengthBefore = length; } } // 执行完上面循环之后,还是可能出现 /..在路径行首,直接换成/ // 例如 /a/../../b/../c/ path = path.replaceAll("^\\/\\.\\.(?!([\\.]|[^\\/]))", "/"); // 多个/////,替换成一个/ path = path.replaceAll("\\/+", "\\/"); int length = path.length(); // 去掉最后的/ if (length > 1 && path.charAt(length - 1) == '/') { path = path.substring(0, length - 1); } return path; }/** * 利用栈的方式 * * @param path * @return */ public String simplifyPath2(String path) { // 思路: 利用栈的思想 String[] strings = path.split("\\/"); List list = new ArrayList<>(strings.length); for (String string : strings) { if (string.equals(".") || string.equals("")) { // 不变 } else if (string.equals("..")) { // 删掉最后一个 int size = list.size(); if (size > 0) { list.remove(size - 1); } } else { // 加到最后一个 list.add(string); } }StringBuilder stringBuilder = new StringBuilder(); // String result = ""; for (int i = 0; i < list.size(); i++) { String s = list.get(i); if (!s.equals("")) { stringBuilder.append(s).append("/"); // result = result + s + "/"; } } int length = stringBuilder.length(); // int length = result.length(); if (length == 0) { // 这种情况, 要么是/ 要么是. if (path.charAt(0) == '/') { return "/"; } else { return "."; } // return path.substring(0, 1); } else { // 删除最后的/, 首位插上/ String s = stringBuilder.deleteCharAt(length - 1).insert(0, "/").toString(); // String s = "/" + result.substring(0, length - 1); return s; } }public static void main(String[] args) { Solution solution = new Solution(); String s = "./a////.//b/c/../d////"; s = "/../"; s = "/a//b////c/d//././/.."; s = "/abc/..."; s = "/..hidden"; s = "/a/../../b/../c//.//"; s = "/home/../../.."; s = "/a/./b/../../c/"; s = "/.././em/jl///../.././../E/"; String simplifyPath = solution.simplifyPath(s); System.out.println(simplifyPath); } }